编译原理学习笔记计算机linuxUnix相关_计算机-计算机原理.pdf

《编译原理学习笔记计算机linuxUnix相关_计算机-计算机原理.pdf》由会员分享，可在线阅读，更多相关《编译原理学习笔记计算机linuxUnix相关_计算机-计算机原理.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 若其他推导式中S 不出现在其他产生式的右边,不影响正规文法要求,若出现在右边,则是短语文法.eg:B cB 则一定是短语文法.4.A aB 或者 A a 则属于右线性文法,A Ba 或 A a 属于左线性文法.若一个文法有型如A aB 又有 A Ba 的推导式,则排除该文法最多是正规文法.短语文法 上下文相关文法 上下文无关文法

3、正规 左线性 右线性 给出文法 用最左或最右推导句子建立推导树 例:已知文法 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)

4、=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 的一份复习笔记一些是自己总结出来的方

5、法有一些考点这份笔记没有覆盖到请大家补充严重声明仅是个人的理解如果有错请高手们指出以免误人谢谢如果大家有什么不明可以共同探讨几种文法的区分文法分为四类短语文法型文法上子集型文法是型文法的一个子集型文法是型文法的一个子集短语文法上下文相关文法上下文无关文法正规左线性右线性一些判断和排除的技巧正规文法右边只有一个非终止符可排除此文法是正规文法区分上下文相关文法和上下文无下文无关文法对于若其他推导式中不出现在其他产生式的右边不影响正规文法要求若出现在右边则是短语文法则一定是短语文法或者则属于右线性文法或属于左线性文法若一个文法有型如又有的推导式则排除该文法最多是正规文法B-Bc|c 证明文法的二义性

6、(题型可参照书本 p40 2-10,方法用老师给的方法)基本思路:找出一个句子,证明它可从两种推导方式得到相同的推导结果即可.例:证明下面文法具有二义性.S-aB|bA B-bS|aBB|b A-aS|bAA|a 找出一句子 aabbab 有两种不同的推导。S=aB=aaBB=aabB=aabbS=aabbaB=aabbab S=aB=aaBB=aabSB=aabbAB=aabbaB=aabbab 即它可以产生两棵不同的语法树，故它是二义的。关于 NFA 确定化和 DFA 的最小化详见老师给出的习题答案.消除左递规 直接左递规:左递归产生式 AA，可以用非左递归的 A A A A|来代替，它们

7、没有改变从 A 推导出的串集。eg:T T*F|F 消除左递规得:T FT ;T *F T|例题可参照书本 p109 总结:不管有多少 A 产生式，可以用下面的技术消除直接左递归。首先把 A 产生式组在一起：A A1|A2|Am|1|2|n 其中i都不以 A开始，i都非空，然后用 A 1A|2 A|n A A 1A|2 A|m A|代替 A产生式。这些产生式和前面的产生式产生一样的串集，但是不再有左递归。间接左递规:书本用的是用矩阵的解法,可一次性消除文法左递规.具有一般性,也可以用代入的方法,可避免求解矩阵,在有些时候这种方法较简便(仅代表个人意见).下面用代入的方法解书本 p110 例 4

8、.1 SSa|Ab|a;A Sc 将第二式代入第一式可得:SSa|Scb|a 这样就变成直接左递规了，便可用消除直接左递规的方法解答.可得:SaS S aS|cbS|的一份复习笔记一些是自己总结出来的方法有一些考点这份笔记没有覆盖到请大家补充严重声明仅是个人的理解如果有错请高手们指出以免误人谢谢如果大家有什么不明可以共同探讨几种文法的区分文法分为四类短语文法型文法上子集型文法是型文法的一个子集型文法是型文法的一个子集短语文法上下文相关文法上下文无关文法正规左线性右线性一些判断和排除的技巧正规文法右边只有一个非终止符可排除此文法是正规文法区分上下文相关文法和上下文无下文无关文法对于若其他推导式中

9、不出现在其他产生式的右边不影响正规文法要求若出现在右边则是短语文法则一定是短语文法或者则属于右线性文法或属于左线性文法若一个文法有型如又有的推导式则排除该文法最多是正规文法再举一例:Gs:(1)S Qc|c (2)QRb|b (3)R Sa|a 消除左递规 把(2)右部代入(1)(4)SRbc|bc|c 把(3)右部代入(4)(5)SSabc|abc|bc|c 消除直接左递归 S(abc|bc|c)S S abcS|文法最终为：S(abc|bc|c)S S abcS|LR(0),LR(1),SLR(1),LALR(1)四种文法:LR(0)文法项目集里不含移进归约,归约归约冲突.如:对于某项目为

10、:(1).Ss;S (2).S s 当接受下一个符号时,分析器就不知道要进行归约还是继续移进了,这样产生了移进归约冲突,如果存在冲突就不是 LR(0)文法了,SLR(1)比 LR(0)高级,可以处理一些冲突.如上面的这个问题,按照 SLR(0)分析,FOLLOW(S)=a,若 FOLLOW(S)!=;就可解决冲突.又如对于某项目发生归约冲突 Ca Da如果 FOLLOW(C)与 FOLLOW(D)的交集不是空的,SLR(1)不可以分析这样的文法,这时用 LR(1)就可以解决这样的问题了.LR(1)的效率较低,LALR是一种规模与SLR(1)差不多,分析能力和LR(1)差不了多少的分析法.证明给

11、出的文法是某种文法而并不是另一种文法可以利用上述文法的区别证明.LL(1)文法分析:算出非终结符的 follow 集合.对于某表达式如 S A 求出 FOLLOW(S)为#,则写成 S A,#,表示当下一个字符是#时便可照 S A 进行规约.其它的式子照此求出,这些式子的求出是得出分析表的依据.然后是写出拓展文法,确定项目集规范族及相应的DFA.对于某表达式:如 SAab,有 SAab SAab S Aab S Aab,以此类推对其他产生式有类似的推导.确定 DFA时,形式与 LL(0)相似,只是在式子的后面加上式子左边的非终结符的 FOLLOW 集即可.例:设文法 G为 S A A BA|B

12、 aB|b (1)证明它是 LR(1)文法；(2)构造它的 LR(1)分析表；(3)给出输入符号串 abab 的分析过程。答案(1)拓广文法 G:的一份复习笔记一些是自己总结出来的方法有一些考点这份笔记没有覆盖到请大家补充严重声明仅是个人的理解如果有错请高手们指出以免误人谢谢如果大家有什么不明可以共同探讨几种文法的区分文法分为四类短语文法型文法上子集型文法是型文法的一个子集型文法是型文法的一个子集短语文法上下文相关文法上下文无关文法正规左线性右线性一些判断和排除的技巧正规文法右边只有一个非终止符可排除此文法是正规文法区分上下文相关文法和上下文无下文无关文法对于若其他推导式中不出现在其他产生式的

13、右边不影响正规文法要求若出现在右边则是短语文法则一定是短语文法或者则属于右线性文法或属于左线性文法若一个文法有型如又有的推导式则排除该文法最多是正规文法(0)S S (1)S A (2)A BA (3)A (4)B aB (5)B b FIRST(A)=,a,b FIRST(B)=a,b FOLLOW(S)=#FOLLOW(A)=#FOLLOW(B)=a,b,#构造的 DFA如下:由项目集规范族看出，不存在冲突动作。该文法是 LR(1)文法。(2)LR(1)分析表 状态 Action Goto a B#S A B 0 S4 S5 r3 1 2 3 1 acc 2 r1 3 S4 S5 r3 6

14、 3 4 S4 S5 7 的一份复习笔记一些是自己总结出来的方法有一些考点这份笔记没有覆盖到请大家补充严重声明仅是个人的理解如果有错请高手们指出以免误人谢谢如果大家有什么不明可以共同探讨几种文法的区分文法分为四类短语文法型文法上子集型文法是型文法的一个子集型文法是型文法的一个子集短语文法上下文相关文法上下文无关文法正规左线性右线性一些判断和排除的技巧正规文法右边只有一个非终止符可排除此文法是正规文法区分上下文相关文法和上下文无下文无关文法对于若其他推导式中不出现在其他产生式的右边不影响正规文法要求若出现在右边则是短语文法则一定是短语文法或者则属于右线性文法或属于左线性文法若一个文法有型如又有的

15、推导式则排除该文法最多是正规文法5 r5 r5 r5 6 r2 7 r4 r4 r4 (3)输入串 abab 的分析过程为：步骤 状态栈 符号栈 当前字符 剩余字符串 动作 (1)0#a bab#移进 (2)04#a b ab#移进 (3)045#ab a b#归约 Bb (4)047#aB a b#归约 BaB (5)03#B a b#移进 (6)034#Ba b#移进 (7)0345#Bab#归约 Bb (8)0347#BaB#归约 BaB (9)033#BB#归约 A (10)0336#BBA#归约 ABA (11)036#BA#归约 ABA (12)02#A#归约 S A (13)01

16、#S#acc 的一份复习笔记一些是自己总结出来的方法有一些考点这份笔记没有覆盖到请大家补充严重声明仅是个人的理解如果有错请高手们指出以免误人谢谢如果大家有什么不明可以共同探讨几种文法的区分文法分为四类短语文法型文法上子集型文法是型文法的一个子集型文法是型文法的一个子集短语文法上下文相关文法上下文无关文法正规左线性右线性一些判断和排除的技巧正规文法右边只有一个非终止符可排除此文法是正规文法区分上下文相关文法和上下文无下文无关文法对于若其他推导式中不出现在其他产生式的右边不影响正规文法要求若出现在右边则是短语文法则一定是短语文法或者则属于右线性文法或属于左线性文法若一个文法有型如又有的推导式则排除该文法最多是正规文法