资源描述：
《编译原理学习笔记》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、本份资料是03软件学习委员按照老师上课复习的时候给我们讲的一些考试重点考点,和我看书上网查资料等总结出来的一份复习笔记,一些是自己总结出来的方法,有一些考点这份笔记没有覆盖到,请大家补充.严重声明:仅是个人的理解,如果有错请高手们指出,以免误人,谢谢……如果大家有什么不明,可以共同探讨…几种文法的区分:文法分为四类：(1)短语文法(0型文法)(2)上下文相关文法(1型文法)(3)上下文无关文法(2型文法)(4)正规(则)文法(3型文法)上面四种文法有包含的关系，1型文法是0型文法的一个子集，2型文法是1型文法的一个子集，,3型文法
2、是2型文法的一个子集。短语文法上下文相关文法上下文无关文法正规左线性右线性一些判断和排除的技巧:1.正规文法右边只有一个非终止符,eg:SàAB可排除此文法是正规文法.2.区分上下文相关文法和上下文无关文法的情况:看左端有几个非终止符,如果不只一个,则该文法不是上下文无关文法.ABàa可排除上下文相关文法,Aàa则可能是上下文无关文法.3.对于Sàe若其他推导式中S不出现在其他产生式的右边,不影响正规文法要求,若出现在右边,则是短语文法.eg:BàcB则一定是短语文法.4.AàaB或者Aàa则属于右线性文法,AàBa或Aàa属于左
3、线性文法.若一个文法有型如AàaB又有AàBa的推导式,则排除该文法最多是正规文法.给出文法用最左或最右推导句子建立推导树例:已知文法G:E->E+T
4、E-T
5、TT->T*F
6、T/F
7、FF->(E)
8、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
9、+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) 给出语言写出文法(题型可参照书本p392-2)例:给出语言{anbncm
10、n>=1,m>=0}的上下文无关文法。解:基本思路是这样的：要求符合anbncm，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而cm做为另一个单位，初步产生式就应写为S->AB，其中A推出anbn，B推出cm。因为m可为0，故上式进
11、一步改写为S->AB
12、A。接下来考虑A,凡是要求两个终结符个数相等的问题，都写为A->aAb
13、ab形式，对于B就很容易写成B->Bc
14、c了。构造上下文无关文法如下：S->AB
15、AA->aAb
16、abB->Bc
17、c证明文法的二义性(题型可参照书本p402-10,方法用老师给的方法)基本思路:找出一个句子,证明它可从两种推导方式得到相同的推导结果即可.例:证明下面文法具有二义性.S->aB
18、bAB->bS
19、aBB
20、bA->aS
21、bAA
22、a找出一句子aabbab有两种不同的推导。S=>aB=>aaBB=>aabB=>aabbS=>aabb
23、aB=>aabbabS=>aB=>aaBB=>aabSB=>aabbAB=>aabbaB=>aabbab即它可以产生两棵不同的语法树，故它是二义的。关于NFA确定化和DFA的最小化详见老师给出的习题答案.消除左递规直接左递规:左递归产生式A®Aa
24、b，可以用非左递归的A®bA¢A¢®aA¢
25、e来代替，它们没有改变从A推导出的串集。eg:T®T*F
26、F消除左递规得:T®FT¢;T¢®*FT¢
27、e例题可参照书本p109总结:不管有多少A产生式，可以用下面的技术消除直接左递归。首先把A产生式组在一起：A®Aa1
28、Aa2
29、…
30、Aam
31、b1
32、
33、b2
34、…
35、bn其中bi都不以A开始，ai都非空，然后用A®b1A¢
36、b2A¢
37、…
38、bnA¢A¢®a1A¢
39、a2A¢
40、…
41、amA¢
42、e代替A产生式。这些产生式和前面的产生式产生一样的串集，但是不再有左递归。间接左递规:书本用的是用矩阵的解法,可一次性消除文法左递规.具有一般性,也可以用代入的方法,可避免求解矩阵,在有些时候这种方法较简便(仅代表个人意见).下面用代入的方法解书本p110例4.1S®Sa
43、Ab
44、a;A®Sc将第二式代入第一式可得:S®Sa
45、Scb
46、a这样就变成直接左递规了，便可用消除直接左递规的方法解答.可得:S®a
47、S¢S’®aS’
48、cbS’
49、e再举一例:G[s]:(1)S®Qc
50、c(2)Q®Rb
51、b(3)R®Sa
52、a消除左递规把(2)右部代入(1)(4)S®Rbc
53、bc
54、c把(3)右部代入(4)(5)S®Sabc
55、abc
56、bc
57、c消除直接左递归S®(abc
58、
