3.4形式语言鸟瞰

时间:2022-11-19 20:11:51
  • 乔姆斯基于1956年建立形式语言体系,他把文法分成四种类型: 0, 1 ,2, 3型
  • 与上下文无关文法一样,它们都由四部分组成但对产生式的限制有所不同
    • G=(VT, VN,S,P)
      • VT :终结符(Terminal)集合(非空)
      • VN :非终结符(Noterminal)集合(非空) ,且VT∩VN
      • S :文法的开始符号,S∈VN
      • P :产生式集合(有限)
  • 0型(短语文法,图灵机)
    • 产生式形如:α→β
    • 其中α∈(VT∪VN)*且至少含有一个非终结符,β∈(VT∪VN)*
  • 1型(上下文有关文法,线性界限自动机)
    • 产生式形如:α→β
    • 其中|α|<=|β|,仅S→ε
  • 2型(上下文无关文法,非确定下推自动机)
    • 产生形式如A→β
    • 其中:A∈VN,β∈(VT∪VN)*
  • 3型(正规文法,有限自动机)
    • 产生式形式如A→αB或A→α(右线性文法)
    • 其中:α∈VT*;A,B∈VN(右线性文法)
    • 产生式形式如A→Bα或A→α(左线性文法)
    • 其中:α∈VT*;A,B∈VN(左线性文法)
  • 四种类型文法描述能力比较
  • 3.4形式语言鸟瞰 

上下文无关文法与上下文有关文法

  • L5={anbn|n>=1}不能由正规文法产生,但可以由上下文无关文法产生

   G5(S):S→aSb|ab

  • L6={anbncn|n>=1}不能由上下文无关文法产生,但可以由上下文有关文法产生

四种类型描述能力比较

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

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