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一次得到.
形式语言及自动机 哈尔滨工业大学(中文版)_理学_高等教育_教育专区。Part IX Undecidability 1 问题 非形式的, 我们使用问题来表示诸如“一个给定的 CFG 是否是...
形式语言及自动机 哈尔滨工业大学(中文版) 隐藏>> 1 正则表达式 (Regular Expression) 自动机通过识别来定义语言,正则表达式通过规则产生语言 (或表示语言);正则...
形式语言及自动机 哈尔滨工业大学(中文版) 本资料是哈工大自动机课程的中文版,但授课教材是英文版本,望采纳~本资料是哈工大自动机课程的中文版,但授课教材是英文...
形式语言及自动机 哈尔滨工业大学(中文版) 隐藏>> Part VI Pushdown Automata 1 介绍 0 1 1 0 0 1 0 0 1 0 ··· 下推自动机是可以看做带有堆栈的 ...
形式语言及自动机 哈尔滨工业大学(中文版)_理学_高等教育_教育专区 暂无评价
形式语言与自动机 绪论 45页 免费 我的JAVA五子棋小游戏代... 9页 免费形式语言及自动机 哈尔滨工业...
形式语言与自动机 哈工大正心楼DFA_工学_高等教育_教育专区。Formal Language ... 形式语言与自动机 5 DFA... 33页 免费 哈尔滨工业大学园丁小区... 30页 ...
哈工大形式语言与自动机课件第三讲 授课老师:孙大烈授课老师:孙大烈隐藏>> Nondeterministic Finite Automata(NFA) 1. Definition 2. Notation 3. Construction 4...
哈工大形式语言与自动机课件第2讲 授课老师:孙大烈授课老师:孙大烈隐藏>> Finite Automata(FA) Introduction to following contents about three kinds of FA---...
热门文档