还剩13页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《编译原理》期末复习资料【题1】
1.(a|b)*(aa|bb)(a|b)*画出状态转换图IaIb
①123234235
②234234678235
③235234235678
④23467823467823578
⑤23567823478235678
⑥2357823478235678
⑦2347823467823578IaIb123243325446575675746新的状态转换图如下
(1)A={123},B={4567}Aa={24}×
(2)A={13},B={2},C={4567}Aa={2}B,Ab={35}×
(3)A={1},B={2},C={3}D={4567}(单元素可以不用看,必有,古先看D)Da={47}D,Db={56}D,Aa={2}B,Ab={3}C,Ba={4}D,Bb={3}C,Ca={2}B,Cb={5}C,则有abABCBDCCBDDDD
2.(a*|b*)b(ba)*的状态转换图IaIb
①12342434568
②2424568
③34568---345678
④568---7
⑤34567868345678
⑥768---
⑦68---7IaIb1232243---54---657567---7---6新的状态转换图如下化简(用终结状态与非终结状态,然后输出状态一致分一类)
(1)A={126},B={3457}Aa={2}×
(2)A={12},B={6},C={347},D={5}Cb={56}×(只要有一个不属于任何一个集合,就不行)
(3)A={12},B={6},C={3},D={47},E={5}Ab={34}×
(4)A={1},B={2},C={6},D={3},E={47},F={5}Aa={2}B,Ab={3}D,Ba={2}B,Bb={4}E,Ca={7}E,Db={5}F,Eb={6}C,Fa={7}E,Fb={5}FabABDBBECE---D---FE---CFEF[注意事项][知识要点]正则表达式;;;;是最左边一个字母一定是,其余字母为的任意组合,不包括{a和若干个a(包括0的情形)后跟一个b构成的符号串集合}{a和a后跟若干个(包括0的情形)b构成的符号串集合}状态转换图(有穷状态自动机)【题2】
1.求如下简单算术表达式文法中语法变量的FOLLOW集[解答]
(1)求表达式文法的语法符号的FIRST集FIRSTF={(id}FIRSTT=FIRSTF={(id}FIRSTE=FIRSTT={(id}FIRSTE={+,ε}FIRSTT={*ε}FIRST+={+}FIRST*={*}FIRST(={(}FIRST)={)}FIRSTid={id}
(2)求表达式文法的语法变量的FOLLOW集FOLLOWE={#}FOLLOWE=FOLLOWE={#}FOLLOWT={FIRSTE-{ε}}∪FOLLOWE∪FOLLOWE={+#}FOLLOWT=FOLLOWT={+#}FOLLOWF=FIRSTT’∪FOLLOWT∪FOLLOWT={*+#}6[知识点]First集合的求法First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可很直观地得到每个字符串的First集合
1.直接收取对形如U-a…的产生式(其中a是终结符),把a收入到FirstU中
2.反复传送对形入U-P1P2P3…Pn的产生式(其中P是非终结符),应先把FirstP1中的全部内容传送到FirstU中如果P1中有ε,把FirstP2中的内容传送到FirstU中类推直到Pi中无εFollow集合的求法Follow集合是针对非终结符而言的,FollowU所表达的是句型中非终结符U所有可能的后随终结符号的集合,特别地,“$”是识别符号的后随符先直接加入到S中
1.直接收取注意产生式右部的每一个形如“…Ua…”的组合,把a直接收入到FollowU中
2.直接收取对形如“…UP…”P是非终结符的组合,把FirstP中非ε收入到FollowU中
3.反复传送对形如U-aP的产生式(其中P是非终结符)或U-aPQPQ为非终结符且Q中含ε,应把FollowU中的全部内容传送到FollowP中[例]文法S→ABcA→a|εB→b|εFirst集合求法:能由非终结符号推出的所有的开头符号或可能的ε,但要求这个开头符号是终结符号如此题A可以推导出a和ε,所以FIRST(A)={a,ε};同理FIRST(B)={bε};S可以推导出aBc,还可以推导出bc,还可以推导出c,所以FIRSTS)={a,b,c}Follow集合的求法:紧跟随其后面的终结符号或#但文法的识别符号包含#,在求的时候还要考虑到ε具体做法是把所有包含你要求的符号的产生式都找出来,再看哪个有用Follow(S)={#}如求A的,产生式S→ABcA→a|ε,但只有S→ABc有用跟随在A后面的终结符号是FIRST(B)={b,ε},当FIRST(B)的元素为ε时,跟随在A后的符号就是c,所以Follow(A)={b,c}同理Follow(B)={c}
2.对下面的文法G解
(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集FIRST集合有FIRSTE=FIRSTT=FIRSTF=FIRSTP={ab^};FIRSTE={+ε}FIRSTT=FIRSTF=FIRSTP={ab^};FIRSTT=FIRSTT∪{ε}={ab^ε};FIRSTF=FIRSTP={ab^};FIRSTF=FIRSTP={*ε};FIRSTP={ab^};FOLLOW集合有FOLLOWE={#};FOLLOWE=FOLLOWE={#};FOLLOWT=FIRSTE∪FOLLOWE={+#};//不包含εFOLLOWT=FOLLOWT=FIRSTE∪FOLLOWE={+#};FOLLOWF=FIRSTT∪FOLLOWT={ab^+#};//不包含εFOLLOWF=FOLLOWF=FIRSTT∪FOLLOWT={ab^+#};FOLLOWP=FIRSTF∪FOLLOWF={*ab^+#};//不包含ε2证明这个方法是LL1的各产生式的SELECT集合有SELECTE-TE=FIRSTT={ab^};SELECTE-+E={+};SELECTE-ε=FOLLOWE/={#}SELECTT-FT=FIRSTF={ab^};SELECTT-T=FIRSTT={ab^};SELECTT-ε=FOLLOWT/={+#};SELECTF-PF=FIRSTP={ab^};SELECTF-*F={*};SELECTF-ε=FOLLOWF={ab^+#};SELECTP-E={}SELECTP-a={a}SELECTP-b={b}SELECTP-^={^}可见,相同左部产生式的SELECT集的交集均为空,所以文法G[E]是LL1文法3构造它的预测分析表文法G[E]的预测分析表如下【题3】考虑下面的文法[解答]
(1)所有语法变量的FIRSTOP集合和LASTOP集合如下
(2)文法的算符优先关系表算符关系算符+-*/id+-*/()id因为文法中任意两个终结符之间只存在一种关系,因此该文法为算符优先文法
(3)文法的算符优先函数优先函数算符+-*/()id#(栈内优先函数)22440440(栈外优先函数)11335050
(4)表达式的算符优先分析过程步骤栈输入串优先关系动作1#+#2#+##移进3#F+###用归约4#F+#移进+5#F+#移进6#F+F#+#用归约7#E##+#用归约表达式id*id+id的算符优先分析过程步骤栈S优先关系当前输入字符R输入字符串0#id*id+id#1#id*id+id#2#N*id+id#3#N*(id+id#4#N*id+id#5#N*id+id#6#N*N+id#7#N*N+id#8#N*N+id#9#N*N+N#10#N*N#11#N*N#12#N*N#13#N停止#
2.已知文法G[S]为S-a|^|TT-TS|S1计算G[S]的FIRSTVT和LASTVT2构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法3计算G[S]的优先函数4给出输入串aa#的算符优先分析过程解
(1)各符号的FIRSTVT和LASTVT
(2)算符优先关系表因为文法中任意两个终结符之间只存在一种关系,因此该文法为算符优先文法
(3)对应的算符优先函数为
(4)句子aa#分析过程如下[知识点]FIRSTVT及LASTVT求法构造集合FIRSTVT(P)的两条规则(i)若有产生式P→a…,或P→Qa…,则a∈FIRSTVT(P)(ii)若a∈FIRSTVT(P),且有产生式P→Q…,则a∈FIRSTVT(P)构造集合FIRSTVT(P)的两条规则(i)有产生式P→…a,或P→…aQ,则a∈LASTVT(P)(ii)若a∈LASTVT(Q),且有产生式P→Q…,则a∈FIRSTVT(P)【题4】
1.令文法G S→BBB→aBB→b判断该文法是否LR
(1)文法,若是构造LR
(1)分析表解1)将文法G拓广为G`
(0)S`→S
(1)S→BB
(2)B→Ab
(3)B→b2求出G`的非终结符的FOLLOW和FIRST集AFOLLOWAFIRSTAS`#abS#abBab#ab3)构造个G`的LR1的项目集族及GO函数BSBabBaaaBbb3判断文法是否为LR
(1)文法该文法构出的C={I0I1I2I3I4I5I6I7I8I9}中,每个状态集均无冲突,所以该文法是LR
(1)文法4)构造LR1分析表状态ACTIONGOTOab#SB0S3S4121acc2S6S753S3S484r3r35r16S6S77r38r2r29r2填空题
1.消除左递归(P124)文法左递归问题:一个文法是含有左递归的,如果存在非终结符P直接消除见诸于产生式中的左递归假定关于非终结符P的规则为P→Pa|b其中b不以P开头那么,我们可以把P的规则等价地改写为如下的非直接左递归形式P→bP¢P¢→aP¢|e一般而言,假定关于P的全部产生式是P→Pa1|Pa2|…|Pam|b1|b2|…|bn其中,每个a都不等于e,而每个b都不以P开头那么,消除P的直接左递归性就是把这些规则改写成P→b1P¢|b2P¢|…|bnP¢P¢→a1P¢|a2P¢|…|amP¢|e[例]文法E→E+T|TT→T*F|FF→E|i经消去直接左递归后变成E→TE¢E¢→+TE¢|eT→FT¢T¢→*FT¢|eF→E|i例如文法S→Qc|cQ→Rb|bR→Sa|a虽没有直接左递归,但S、Q、R都是左递归的SÞQcÞRbcÞSabc一个文法消除左递归的条件1不含以e为右部的产生式(无空产生式);2不含回路消除左递归的算法
1.把文法G的所有非终结符按任一种顺序排列成P1,P2,…,Pn;按此顺序执行;
2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如Pi→Pjg的规则改写成Pi→d1g|d2g|…|dkg;其中Pj→d1|d2|…|dk是关于Pj的所有规则消除关于Pi规则的直接左递归性END
3.化简由2所得的文法即去除那些从开始符号出发永远无法到达的非终结符的产生规则[例]考虑文法GSS→Qc|cQ→Rb|bR→Sa|a令它的非终结符的排序为R、Q、S对于R,不存在直接左递归把R代入到Q的有关候选后,把Q的规则变为Q→Sab|ab|b,现在的Q不含直接左递归把Q代入到S的有关候选后,S变成S→Sabc|abc|bc|c,由于S→Sabc|abc|bc|c存在直接左递归,消除S的直接左递归后S→abcS¢|bcS¢|cS¢S¢→abcS¢|eQ→Sab|ab|bR→Sa|a关于Q和R的规则已是多余的,化简为S→abcS¢|bcS¢|cS¢S¢→abcS¢|e注意由于对非终结符排序的不同,最后所得的文法在形式上可能不一样但不难证明,它们都是等价的同样[例]考虑文法GSS→Qc|cQ→Rb|bR→Sa|a非终结符排序选为S、Q、R,那么,R→Qca|ca|aR→Rbca|bca|ca|a最后所得的无左递归文法是S→Qc|cQ→Rb|bR→bcaR¢|caR¢|aR¢R¢→bcaR¢|e不同排序所得的文法的等价性是显然的
2.文法的分类Chomsky体系(P41)
(1)短语结构文法(PSG)如果G满足文法定义的要求,则G是0型文法(短语结构文法PSG:PhraseStructureGrammar)LG为PSL
(1)上下文有关文法CSG如果对于,均有|β|≥|α|成立S→ε除外,则称G为1型文法即上下文有关文法(CSG)LG为1型/上下文有关/敏感语言CSL其他定义方法设文法G[S],若P中任一产生式α→β的形式为→其中β∈V∪T)*β≠εA∈V
(2)上下文无关文法CFG如果对于,均有|β|≥|α|,并且α∈V成立,则称G为2型文法即上下文无关文法CFG:LG为2型/上下文无关语言(CFL),CFG能描述程序设计语言的多数语法成分
(3)正规(则)文法RG设AB∈V,w∈T+或为,如果对于均具有如下形式右线性RightLinear文法或左线性LeftLinear文法或都是3型文法正规文法RG,LG为3型/正规集/正则集/正则语言(RL),能描述程序设计语言的多数单词左、右线性文法不可混用[例]正规文法(RG)G1S0|1|00|11G3S0|1|0A|1B,A0,B1G5S0|0SG8AaS|bS|cS|a|b|c上下文无关文法(CFG)G2SA|B|AA|BBA0,B1G4SA|B|BBA0,B1G14S0|1|2|3|0S0|1S1|2S2|3S3上下文有关文法(CSG)G S→CDC→aCACA→CaCaD→daDdAc→decG=V,T,P,S是一个文法α→β∈P*G是0型文法,LG是0型语言;---其能力相当于图灵机*|α|≤|β|:G是1型文法,LG是1型语言除S→ε;---其识别系统是线性界限自动机*α∈VN:G是2型文法,LG是2型语言;---其识别系统是不确定的下推自动机*A→aB或A→a:G是右线性文法,LG是3型语言A→Ba或A→a:G是左线性文法,LG是3型语言---其识别系统是有穷自动机
3.逆波兰表示法,请注意IF---ELSE及FOR循环的特例逆波兰表达式又叫做后缀表达式在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法按此方法,每一运算符都置于其运算对象之后,故称为后缀表示将一个普通的中序表达式转换为逆波兰表达式的一般算法是 1首先构造一个运算符栈,此运算符在栈内遵循越往栈顶优先级越高的原则 2读入一个用中缀表示的简单算术表达式,为方便起见设该简单算术表达式的右端多加上了优先级最低的特殊符号“#” 3从左至右扫描该算术表达式,从第一个字符开始判断,如果该字符是数字,则分析到该数字串的结束并将该数字串直接输出 4如果不是数字,该字符则是运算符,此时需比较优先关系做法如下将该字符与运算符栈顶的运算符的优先关系相比较如果,该字符优先关系高于此运算符栈顶的运算符,则将该运算符入栈倘若不是的话,则将栈顶的运算符从栈中弹出,直到栈顶运算符的优先级低于当前运算符,将该字符入栈 5重复上述操作3-4直至扫描完整个简单算术表达式,确定所有字符都得到正确处理,我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式逆波兰表达式,它的语法规定,表达式必须以逆波兰表达式的方式给出逆波兰表达式又叫做后缀表达式这个知识点在数据结构和编译原理这两门课程中都有介绍,下面是一些例子 正常的表达式逆波兰表达式 a+b---ab+ a+b-c---abc-+ a+b-c*d---abc-d*+ a+d*b-c---adbc-*+ a=1+3---a=13+ http=smtp+http+telnet/1024---http=smtphttptelnet++1024/例9将下列语句翻译为逆波兰表示后缀式、三元式和四元表示a:=b+c*e+b+c/f【解】解题思路把中缀式转换为后缀式的简单方法按中缀式中各运算符的优先规则,从最先执行的部分开始写,一层层套如a≤b+c∧a>d∨a+b≠e,先把b+c写为bc+;然后把a≤套上去,成为abc+≤;再把a>d表示为ad>;然后把∧套上去,成为abc+≤ad>∧,依此类推[练习]给出下列表达式的逆波兰表示
(1)
(2)5.句柄设有CFGG=VTPSG的句型的最左直接短语称为句柄附定义
2.27设有CFGG=V,T,P,S,,γ,β∈V∪T*,S,Aα,则称α是句型的相对于变量A的短语phrase;如果此时有Aα,则称α是句型的相对于变量A的直接短语在无意义冲突时,简称为句型的直接短语直接短语也叫做简单短语[例]对于文法的句型来说,它的短语有,,,其中直接短语有,而就是句型的句柄
6.综合属性和继承属性2012---2013年已经取消这题如果节点的属性值是通过分析树中该节点或其子节点的属性值计算出来的,则称其为综合属性;如果节点的属性值是由该节点、该节点的兄弟节点或父节点的属性值计算出来的,则称其为继承属性[例1]文法符号的属性有综合属性和继承属性两种[例2]S—属性文法中的每个文法符号,只含有综合属性[例3]终结符只有综合属性,它们有词法分析器提供
7.语法制导定义,出现在第四大题的最后一步
(0)s-s{printf(“0”);}
(1)s-BB{printf(“1”);}
(2)B-aB{printf(“2”);}3B-b{printf(“3”);}输入#bab#输出结果是332101计算这个文法的每个非终结符的FIRST集和FOLLOW集2证明这个方法是LL1的3构造它的预测分析表
(1)求出所有语法变量的FIRSTOP集合和LASTOP集合
(2)构造文法的算符优先关系表,并判断是否为算符优先文法
(3)计算文法的算符优先函数
(4)给出表达式和id*id+id的算符优先分析过程I5:S→BB.#I2:S→B.B#B→.Ab#B→.b#I1:S`→S.#I7:B→b.#I6:B→a.B#B→.Ab#B→.b#I0:S`→.S#S→.BB#B→.aBa|bB→.ba|bI9:B→aB.#I3:B→a.Ba|bB→.aBa|bB→.ba|bI8:B→aB.a|bI4:B→b.a|b。