莫力 望城县 黎平县 石嘴山市 富源县 信宜市 胶州市 岱山县 镇安县 旺苍县 黄石市 沧源 乐平市 夏河县 富阳市 晴隆县
淘豆网
下载此文档放大查看缩小查看   1/6
0/100
标签:年终奖 英超 您的浏览器不支持进度条
更多>>该用户其他文档
下载所得到的文件列表
编译原理学习笔记.doc
文档介绍:
本份资料是03软件学习委员按照老师上课复习的时候给我们讲的一些考试重点考点,和我看书上网查资料等总结出来的一份复习笔记,一些是自己总结出来的方法, 有一些考点这份笔记没有覆盖到,请大家补充.严重声明:仅是个人的理解,如果有错请高手们指出,以免误人,谢谢……如果大家有什么不明,可以共同探讨…
几种文法的区分:
文法分为四类:
(1)短语文法(0型文法)
(2)上下文相关文法(1型文法)
(3)上下文无关文法(2型文法)
(4)正规(则)文法(3型文法)

上面四种文法有包含的关系,1型文法是0型文法的一个子集,2型文法是1型文法的一个子集,,3型文法是2型文法的一个子集。
短语文法
上下文相关文法
上下文无关文法
正规
左线性
右线性
一些判断和排除的技巧:
正规文法右边只有一个非终止符, eg: S à AB可排除此文法是正规文法.
区分上下文相关文法和上下文无关文法的情况: 看左端有几个非终止符,如果不只一个,则该文法不是上下文无关文法. AB à a 可排除上下文相关文法, Aà a则可能是上下文无关文法.
对于S à e 若其他推导式中S不出现在其他产生式的右边,不影响正规文法要求,若出现在右边,则是短语文法. eg: B à cB则一定是短语文法.
A à aB或者 A à a则属于右线性文法, A à Ba或A à a属于左线性文法.若一个文法有型如A à aB又有A à Ba的推导式,则排除该文法最多是正规文法.
给出文法用最左或最右推导句子建立推导树
例: 已知文法G:
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|i
试给出下述表达式的推导及语法树
(1)i; (2)i*i+i (3)i+i*i (4)i+(i+i)
[答案]
(1)E=>T=>F=>i
(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i
(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i)
               
给出语言写出文法(题型可参照书本p39 2 -2)
例: 给出语言{ anbncm | n>=1,m>=0}的上下文无关文法。
解: 基本思路是这样的:
要求符合anbncm,因为a与b要求个数相等,所以把它们应看作一个整体单元进行,而cm做为另一个单位,初步产生式就应写为S->AB,其中A推出anbn,B推出cm。因为m可为0,故上式进一步改写为S->AB|A。接下来考虑A,凡是要求两个终结符个数相等的问题,都写为A->aAb|ab形式,对于B就很容易写成B->Bc|c了。
构造上下文无关文法如下:
S->AB|A
A->aAb|ab
B->Bc|c
证明文法的二义性(题型可参照书本p40 2-10,方法用老师给的方法)
基本思路:找出一个句子,证明它可从两种推导方式得到相同的推导结果即可.
例:证明下面文法具有二义性 内容来自淘豆网www.taodocs.com转载请标明出处.
更多>>相关文档
文档信息
最近更新
文档标签