文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 形式语言及自动机 哈尔滨工业大学(中文版)
侵权投诉

形式语言及自动机 哈尔滨工业大学(中文版)

PartV

Context-FreeGrammarsandLanguages

1

上下文无关文法

上下文无关文法在程序设计语言的设计、编译器的实现等方面有重要应用,也应用在可扩展标记语言(XML)的格式类型定义(DTD)中等.上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法;实际上,几乎所有程序设计语言都是通过上下文无关文法来定义的.另一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的.(如LR分析器和LL分析器)

1.1文法的示例

自然语言

上下文无关文法最初是用来描述自然语言的,比如如下文法规则:

sentence → nounphrase verbphrase nounphrase → adjective nounphrase nounphrase → noun noun →boy

adjective →little···

算数表达式

用于产生具有+, 的表达式的规则,用id表示操作数

expression → expression + expression expression → expression expression expression →( expression ) expression →id

这种表示方法也称为BNF(Backus-NaurForm).示例

串w称为“回文(palindrome)”,当且仅当w=wR,比如drawkward(Dr.Awkward),“僧游云隐寺,寺隐云游僧”.那么{0,1}上的回文语言Lpal可定义为:

Lpal={w∈{0,1} |w=wR}

并且,很容易证明是Lpal是非正则的.显然ε,0,1都是回文,而且如果w是回文,0w0和1w1也是回文.如果我们把这种递归的定义表示为文法,可以如下定义:

P→εP→0P→1

P→0P0P→1P1

使用上面的文法,可以通过P产生{0,1}上全部的回文串,比如串0010100可以通过先使用P→0P0两次,再使用P→1P1一次,再使用P→0一次得到.

第1页

你可能喜欢

  • 哈尔滨工业大学考研真题
  • 哈尔滨工业大学专业
  • 哈尔滨工业大学培养方案
  • 哈尔滨工业大学试卷

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email