1 上下文无关文法的定义
手工实现的语法分析器通常使用 LL 文法
处理较大的 LR 文法类的语法分析器通常是使用自动化工具构造得到的
文法，可以理解成某一类东西的产生规则。
定义
一个上下文无关文法 G 是一个四元组，其包含：
（Ⅰ）一个非空有限集合 V_T，称之为终结符（记号名）的集合。
（Ⅱ）一个非空有限集合 V_N，称之为非终结符的集合。
可以理解成，非终结符是可以再分的。可以 N→AB，N→aB，N→ab。
（Ⅲ）一个非终结符 S，称之为开始符号。开始符号 定义的 终结符串集 就是文法定义的语言。
（Ⅳ）一个非空有限集合 P，其中每个元素是一个产生式。
一个产生式的形式是 A→\alpha，其中 A\in V_N，即非终结符；\alpha\in (V_T\cup V_N)^*。
示例
看一个 G 的例子：(\{\textbf{id},+,*,-,(,)\},\{expr,op\},expr,P)，P 由如下产生式组成：
- expr→expr\quad op\quad expr
- expr→(expr)
- expr→-expr
- expr→\textbf{id}
- op→+
- op→*
上面这些产生式可以用 “|” 符号来合并：
- expr→expr\quad or\quad expr|(expr)|-expr|\textbf{id}
- op→+|*
注意：
-
文法是比正则表达式表达能力更强的表示方法，可以用正则表达式描述的构造都可以用文法来描述，但是反之不成立。每个正则语言都是一个上下文无关语言，但是反之不成立。
-
有穷自动机不能计数（类似 $a^nb^n $ 这样的语言）；一个文法可以对两个个体进行计数，但是无法对三个个体计数。
推导
推导的意思是一个非终结符可以根据某个产生式（看成重写规则）来替代，如 $$ expr\Rightarrow expr\quad op\quad expr\Rightarrow expr+expr\Rightarrow\textbf{id}+expr\Rightarrow\textbf{id}+\textbf{id} $$ 也可以看成逐渐替换成实例。
其他定义
| TERM | EXPLANATION |
|---|---|
| \Rightarrow^* | 零步或多步推导 |
| \Rightarrow^+ | 一步或多步推导 |
| 上下文无关语言 | 上下文无关文法产生的语言 |
| 句型 | S\Rightarrow^* \alpha，则称 \alpha 是 G 的句型 |
| 句子 | 若上面的 \alpha 不含非终结符，则称之为句子 |
| \Rightarrow_{lm} | 最左推导，即每次都代换句型最左边的非终结符的推导（上面推到的示例就不是最左推导） |