• 乔姆斯基于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(左线性文法)
  • 四种类型文法描述能力比较
  •  

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

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

   G5(S):S→aSb|ab

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

四种类型描述能力比较

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

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

原文地址:http://www.cnblogs.com/xzit201802/p/16906873.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性