上下文无关文法

形式定义

• CFG 的定义

**例子：**回文语言语法 $G = (\{A\},\{0,1\},\{A\rightarrow \varepsilon |0|1|0A0|1A1\},A)$

常用定义：

1. 变元：$A,B,C$
2. 终结符：$0,1,a,b,c$
3. 终结符构成的串：$w,x,y,z$
4. 终结符或者非终结符构成的串：$\alpha,\beta,\gamma$

**例子：**简化的算术表达式

$G_{exp}=(\{E,I\},\{a,b,0,1,+,*,(,)\},P,E)$，其中$P$有 10 条产生式：

归约和派生

**归约：**从字符串到文法变元的分析过程

**派生：**从文法变元到字符串的分析过程

**归约例子：*用$G_{exp}$将$a(a+b00)$归约

归约到开始符号$E$。

*派生例子：$a(a+b00)$**在文法$G_{exp}$中的派生过程