编译器设计：文法与LL(1)

• 0型文法
• 1型文法（上下文相关文法）
• 2型文法（上下文无关文法）
• 3型文法
• LL（1）文法

根据形式语言理论的创立者乔姆斯基(Chomsky)的定义，形式语言的文法分为四种：

0型文法

$G=(V_n, V_T, P, S)$，如果产生式$\alpha\to\beta$中，$\alpha\in(V_N\bigcup V_T)^*$且至少有一个非终结符，$\beta\in(V_N\bigcup V_T)^*$，那么G就是一个0型文法。

1型文法（上下文相关文法）

在0型文法的基础上，规定对每一个$\alpha\to\beta$，都有$\beta\ge\alpha$

2型文法（上下文无关文法）

在1型文法的基础上满足每一个$\alpha\to\beta$中$\alpha$为非终结符。

3型文法

在2型的基础上满足右线性或者左线性。

LL（1）文法

第一个L指Left to right，第二个L指Leftmost derivation），数字1表示需要向前看1个字符才能确定用哪一个产生式。