上下文无关文法

上下文无关文法$G$是一个四元组$G=(T,N,P,S)$:

• $T$是终结符号，对应词法单元
• $N$是非终结符号集合
• $P$是产生式集合

• $A$：单个非终结符
• $\alpha$：终结符与非终结符构成的串，也可以是空串
• $S$为开始符号，要求$S\in N$且唯一

推导

推导即将产生式的左侧替换成右侧

• $E\rightarrow D$ 经过一步推导得出
• $E\xrightarrow{+}D$经过一步或多步推导得出
• $E\xrightarrow{*}D$经过零步或多步推导得出

句

如果$S\xrightarrow{}\alpha, \alpha\in (T\cup N)^ $，则称$\alpha$是文法$G$的一个句型

如果$S\xrightarrow{}\omega, \omega\in T^ $，则称$\omega$是文法$G$的一个句子

文法$G$的语言$L(G)$是它能推导出的所有句子构成的集合

正则表达式

正则表达式的表达能力严格低于上下文无关文法