A. 四種文法的類型(編譯原理)
喬姆斯基（Chomsky）按產生式的類型把文法分為四種類型：0、1、2、3型文法。
*在下文中的產生式中，箭頭左邊的大寫字母為嚴格的非終結符，而其左邊的小寫字母不嚴格要求為非終結符，如[0型文法]中的第2條產生式。
【0型文法】
產生式形式：α→β
要求：箭頭左邊的α 至少 含有 一個非終結符 ， 其餘 不加任何限制
例如，G：C→AaB
aA→a
B→b|Bb
【1型文法】
產生式形式：α→β
要求： |α|≤|β| (產生式左端的長度<=右端的長度)，S→ε除外。
例如G： C→aAB
aA→aBa
B→b|Bb
【2型文法】(上下文無關文法)
產生式形式：A→β，A∈VN(終結符) ，β∈V *(VN∪VT，即可為終結符也可為非終結符)
說明：當以β替換A時，與A的上下文環境無關；
大部分程序設計語言近似於2型文法。
【3型文法】(正規文法 / 右線性文法)
產生式形式：A→a，A→aB，
說明：a∈VT(終結符) ， A，B∈VN(非終結符)，即產生式右端的第一個符號必須為 終結符
例如 G：A→aB
B→b|bB
【其他說明】對於這四種類型的文法：
*包含關系：0 > 1 > 2 > 3 (以'>'代替包含符，'A>B'譯為A包含B)
*嚴格程度：3 > 2 > 1 > 0
*判斷文法所屬類型的順序：3 → 2 → 1 → 0