3.4形式语言鸟瞰

• 乔姆斯基于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}不能由上下文无关文法产生，但可以由上下文有关文法产生

四种类型描述能力比较

程序设计语言不是上下文无关语言，甚至不是上下文有关语言

 对于现今的程序设计语言，在编译程序中，仍然采用上下文无关文法来描述其语言机构