文法基础

文法四元组

文法 $G$ 定义为一个四元组：

$G(V_N,V_T,P,S)$

• $V_N$：非终结符集合（语法变量）
• $V_T$：终结符集合（单词符号）
• $P$：产生式集合，形如 $\alpha \to \beta$，$\alpha \in (V_N\cup V_T{)}^{\ast }$ 且至少含一个非终结符，$\beta \in (V_N\cup V_T{)}^{\ast }$
• $S$：开始符号，$S\in V_N$

$V_N\cap V_T=\varnothing$，记 $V=V_N\cup V_T$。

BNF 表示法

Backus-Naur Form，描述文法产生式的标准形式：

<非终结符> ::= <候选式1> | <候选式2> | ... | <候选式n>

• ::= 表示 ” 定义为 ”
• | 表示 ” 或 ”
• < > 括起非终结符

示例：

<表达式> ::= <项> | <表达式> + <项>

直接推导与推导序列

• 直接推导：$\alpha A\beta \Rightarrow \alpha \gamma \beta$，其中 $A\to \gamma \in P$，$\alpha ,\beta ,\gamma \in V^{\ast }$
• $k$ 步推导：${\alpha }_0\Rightarrow {\alpha }_1\Rightarrow \cdots \Rightarrow {\alpha }_k$，记作 ${\alpha }_0\stackrel{k}{\Rightarrow }{\alpha }_k$
• 多步推导：${\alpha }_0\stackrel{+}{\Rightarrow }{\alpha }_k$（至少一步），${\alpha }_0\stackrel{\ast }{\Rightarrow }{\alpha }_k$（零步或多步）

句型 vs 句子

• 句型：从开始符号 $S$ 出发，经过零步或多步推导得到的符号串
• 句子：只含终结符的句型

$G$ 定义的语言：$L(G)=\{\alpha \in V_T^{\ast }\mid S\stackrel{\ast }{\Rightarrow }\alpha \}$

最左/最右推导

• 最左推导：每步替换最左边的非终结符
• 最右推导（规范推导）：每步替换最右边的非终结符

递归文法

若存在 $A\stackrel{+}{\Rightarrow }\alpha A\beta$，则 $G$ 是递归文法。

• 直接递归：$A\to \alpha A\beta$
• 间接递归：$A\Rightarrow B\Rightarrow A$（经过多步）
• 左递归：$A\stackrel{+}{\Rightarrow }A\alpha$（产生式左部在最左端出现）
• 右递归：$A\stackrel{+}{\Rightarrow }\alpha A$

文法定义的语言

$L(G)=\{\alpha \in V_T^{\ast }\mid S\stackrel{\ast }{\Rightarrow }\alpha \}$

给定文法 $G$，语言 $L(G)$ 是所有从 $S$ 推导出的句子集合。

文法等价

若 $L(G_1)=L(G_2)$，则称 $G_1$ 与 $G_2$ 等价。

同一语言可由多个不同文法描述。

EBNF 与语法图

EBNF（扩展 BNF）增加：

• []：可选部分
• {}：重复零次或多次
• ()：分组
• `{}^n_m$：重复$m$到$n$ 次

语法图：用图形表示产生式规则，方框表示非终结符，圆框表示终结符。

重点 文法四元组定义、最左/最右推导区分、递归文法判定。