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