3.4形式語言鳥瞰

• 2022 年 11 月 19 日
• 筆記
• 編譯原理

• 喬姆斯基於1956年建立形式語言體系,他把文法分成四種類型: 0, 1 ,2, 3型
• 與上下文無關文法一樣,它們都由四部分組成但對產生式的限制有所不同
  • G=(V_T, V_N,S,P)
    • V_T :終結符(Terminal)集合(非空)
    • V_N :非終結符(Noterminal)集合(非空) ,且V_T∩V_N=Ø
    • S :文法的開始符號，S∈V_N
    • P :產生式集合(有限)
• 0型(短語文法,圖靈機)
  • 產生式形如:α→β
  • 其中α∈(V_T∪V_N)*且至少含有一個非終結符，β∈(V_T∪V_N)*
• 1型(上下文有關文法，線性界限自動機)
  • 產生式形如:α→β
  • 其中|α|<=|β|，僅S→ε
• 2型(上下文無關文法，非確定下推自動機)
  • 產生形式如A→β
  • 其中:A∈V_N,β∈(V_T∪V_N)*
• 3型(正規文法，有限自動機)
  • 產生式形式如A→αB或A→α（右線性文法）
  • 其中:α∈V_T*;A,B∈V_N（右線性文法）
  • 產生式形式如A→Bα或A→α（左線性文法）
  • 其中:α∈V_T*;A,B∈V_N（左線性文法）
• 四種類型文法描述能力比較
•  

上下文無關文法與上下文有關文法

• L₅={aⁿbⁿ|n>=1}不能由正規文法產生，但可以由上下文無關文法產生

　　　G₅(S):S→aSb|ab

• L₆={aⁿbⁿcⁿ|n>=1}不能由上下文無關文法產生，但可以由上下文有關文法產生

四種類型描述能力比較

程式設計語言不是上下文無關語言，甚至不是上下文有關語言

 對於現今的程式設計語言，在編譯程式中，仍然採用上下文無關文法來描述其語言機構