编译原理习题答案文库

第一章引论本章要点：本章目标：掌握本章的编译程序交叉编译程序编译前端与编译后端”T本章重点：概念比较本章难点作业题及参考答案（按照组卷方案，至少8道小题 a.诊断编译程序b.优化编译程序c.d.可变目 机器语言程序或高级语言程序 c.汇编语言程序或高级语言程序d. a.词法分析程序b.代码生成程序c.d.语法分现代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码，在运行前必须借助于一个序。a.重定位程序b.解释程序；c.连接装配程序；d.诊断程 词法错误和语法错误；b.c.d.词法错误和语义错误 c.Lex是语法分析自动d.解释程序属于编译程 b.可充定位的指令代码c.汇编指令代 d.三地址代a.字符错 b.类型不一致错误c.作用域错 d.说明错一．答案：1.c；2.b；3.c；4.c；5.b；6.d；7. （按照组卷方案，至少8道小题 如果不需改写编译程序中与机器无关的部分就可以把编译程序移植到另外一个目标机上，则称该编译程序是 。 为了使编译后的Java程序从一个平台移到另外一个平台上执行，Java定义了一种称为ByteCode的虚拟机代码。只要实际使用的操作平台上实现了执行ByteCode的Java解释器， 在一个程序设计环境中，起着中心作用。连接程序、调试程序、程序分析等工具二．答案：二．答案：1.源程序，目标机；2.源程序，目标程序；3.中间语言；4.可变目标编译程序 （按照组卷方案，至少8道小题遍 （ （ （的任务于前端编所生的中代进行加和换，以能生运行果更为准确目代码。 （ （ （ （ 三．答案1.√；2.×；3.×；4.×；5.√；6.×；7.√；8. 四、（按照组卷方案，至少3道小题诊断编译程序：专门用于帮助程序开发和调试的编译程序。优化编译程序：着重于提高目标代码效率的编译程序。程序设计环境：支持程序设计人员进行程序设计开发所需要的如编辑程序、编译程序、连接程序和调试程序等软件工具，一起构成程序设计环境。（按照组卷方案，至少3道小题AAL1L1编写另一种高级语言L2的编译程序，画出这个实现过程的T形图表示。如何采用“移植”ALB机器上运行的高级语言L的编译程序？画出T形图表示。标识符是由字母或数字以及某些特殊符号（因不同的高级语言而不同）组成的，但是必须以字母开头的一个字符串。L2AL2AL1L1B代码L语 L语BBAA第二章高级语言及其语法描述本章要点Chomsky本章目标本章重点语法，词则与语则本章难点Chomsky作业一、单项选择题：（按照组卷方案，至少15道小题Chomsky把文法分成四种类型，0型、1型、2型和3型。3型文法也称为 a.上下文无关文法b.上下文相关文法c.正则文法d.许多广为使用的语言，如Fortran、C、Pascal等，属 a.强制式语 b.应用式语 c.基于规则的语 d.面向对象的语设G是一个文法，S是开始符号。若S*，(VT∪VN)*，则称是一 a.句 b.句 c.推 d.语 Chomsky把文法分成四种类型，其中 a.0 b.1 c.2 d.3语言的词则一般用Chomsky a. b. c. d.S→(L)|aL→L， a. b. c. d.文法G所描述的语言 文法G的字母表文法G的字母表的闭包*文法G文法G语言L={c|(a|b)*}，该语言 语言a3型语言，b.2型语言，c1型语言，d.0I→I1|I0|Ia|Ic|a|b|ca. b. c.aaa，d.给定文 a.bcbc，b. c. d.Chomsky定义的四种形式语言文法中，2型文法可由（ 图灵机；b.确定性有限自动机；c.下推自动机；d.若文法G定义的语言是无限集，则文法必然 a.上下文无关的b.递归的c.二义性 d.无二义性文法S→aaS|abc定义的语言 b.c.{a2k- d.文法：G：S→xSx|y所识别的语言是 a. b. c. d.一．答案：1.c.；2.a.；3.b；4.c；5.d；6.d；7.b；8.d；9.d；10.a；11.b；12.c；13.14.c；15.二、填空题：（按照组卷方案，至少15道小题假设G是一个文法，是由终结符和非终结符组成的串S是文法的开始符号如果S=>*， 在赋值语句中，赋值号‘：=’左右两边的变量名扮演着两种不同的角色，为了区分一个名字的这两种特征，我们把一个名字所代表的称为该名的左值，把一个名字的称为该名字的右值。对于文法G，仅含终结符号的句型称 设有文法G[S]，其部分产生式E→E+T|T→T*F|FF→(E)|a则VN Chomsky语法定义的3型文法又可以分 一个上下文文法G的四个组成部分分别是 已知语言：{anbnambm|n，m≥0}，其语法定义为：G=({a，b}，{S，A，B}，S，P)，其P为 已知某语言的语法定义为：G=({a},{S}S,P)P:SaS|，则该语言为。已知某语言为{cwR|∈{a，b}*}，其语法定义 为 13.G[S]：S→aA|aA→aS。。就一个句型15.我们说G=(VT，VN，S，P)是一个0型文法，如果它的每一个产生式→是这样一种结 二．答案：1.句型；2.单元的地址（或者：单元、单元的地址值（或者：单元的内容）3.句子；4.VN={E，T，F}，VT={+，*，(，)，a}；5.句子；6.右线性文法和左线性文法；7.8.S→AB；A→aAb|；B→aBb|；9.{an|n≥0}；10.S→aSa|bSb|；11.任何一步都是对中的最右非终结符进行替换。12.iii↑*+；13. {a2n+1|n≥0}；14. 所有那些没有后代的末端结点从左到右排列起来；15.∈(VN∪VT)*且至少含有一个非终结符，而∈(VN∪VT)*三、判断题：（按照组卷方案，至少15道小题一棵语法树表示了一个句型所有的不同推导过程，包括最右推导和最左推导。 可能有两个不同的文法G和G′＝L(G′)（ 定义的语言是所有以b开头的后跟至少一个a的字符串的集合 设有文法G：S→S*S|S+S|S|a该文法是二（（Lanbnci|i>=1,n>=1（L={anbn|n>=1}（对于每一个左线性文法G1，都存在一个右线性文法G2，使得L(G1)=L(G2) （）给出该文法是否二义的答案。（）的（）C语言（三．答案：1.；2.；3.；4.；5.；6.×；7；8.；9.；10.；11.；12.×；14.√；15.四、（按照组卷方案，至少3道小题1.二义性文法；2.推导和直接推导；3.句型，句子和语言；4.5.语法；6.正规文法（左线性文法和右线性文法设A→是一个产生式，且、(VTVN)*，若A=>，则称A直接推出；或者说，是A的一个直接推导。如果1=>2=>……=>n，则称这个序列是从1到nG是一个文法，SS=>*，则称是一个句型。GGL(G)，L(G)={|S=>*，∈VT*｝上下文无关文法G是一个四元式(VT，VN，S，P) VNPP→PVN，∈(VTVN)*。开始符号S至少必须在某个产生式的左部出现一次。5G=VT，VN，S，P)A→BA→，其中，VT*，A，B∈VN，则称G是右线性文法；若文法G=(VT，VN，S，P)的任何产生式为A→B或A→，其中，VT*，A，B∈VN，则称G是左线性文法；五、简答题：（按照组卷方案，至少3道小题作为描述程序语言的上下文无关文法，对它有哪些限制？答： 第二点：每个非终结符P都必须有用处。也就是说，必须存在含P的句型；或者说，对什么是二义性文法？从输入串abab 例如输入串abab，它有两棵语法树如下： S S ab 此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。对于串对于串(1)S=>Ac=>abc即存在两不同的最右推导。所以，该文法是二义的。或者： G=({A,B,C}，{a,b,c}，P，A),P由以下产生式组成:每使用一次Bc→Cbcc，b、caC→aaBaC→aa,a的个数就增加一个；产生式Bb→bB、bC→Cb起连接转换作用。由于A是开始符号，由产生式A→abc推导得到终结符号串abc；由产生式A→aBbc推导得到B后，每当使用产生式Bb→bB、Bc→Cbcc、bC→Cb、aC→aaB就会递归调用B一次，所产生的a、b、c的个数分别增加一个，因此推导所得的终结符号串为abc、aabbcc、 G[Z]:（1）0101，0110，1010，（1）0101，0110，1010，（2）分析G[Z]所推导出的句子的特点：由Z开始的推导不外乎图1ZZZZ0U0U1V1V1Z10Z0Z1001Z的每次递归将推导出相同的符号串：1001。所以G[Z]产生的语言L(G[Z])={x|x∈(10|01)+}(3)3七、应用题：试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-stmt→ifexprthenstmt|matched-matched-stmt→ifexprthenmatched-stmtelsestmt|考虑句子ifethenifethenotherelseifethenotherelseother，试说明此文法仍然是二义性的。考虑句子ifethenifethenotherelseifethenotherelse expr matched- exprthenmatched- esle matched- exprthenmatched- esle exprthenmatched- esle

exprthenmatched- eslestmtexprthenmatched- eslestmtmatched-则上面给出的if-then-else考虑文法G[bexpr]：bexpr→bexprorbterm|btermbterm→btermandbfactor|bfactorbfactor→notbfactor|(bexpr)|true|试对于句子not(trueorfalse)终结符号为：{orandnottrue非终结符号为：{bexpr,bterm,not(trueorfalse)truefalse由此文法产bexpr=>bterm=>bfactor=>truebexpr=>bterm=>bfactor=>设结论对于少于n(n≥1)个运算的布尔表达式成立，即若be1和be2是含有少于n个运算的布尔表达式，则有：对于含有n个运算的布尔表达式，可表示成下面三种(be1)or(be1)andnot对于(a)：bexprbexpror=>btermorbterm=>bfactoror=>(bexpr)orbterm=>+(be1)or=>(be1)orbfactor=>(be1)or=>+(be1)orBexpr=>+(be1)and(be2)Bexpr=>+not(be1)已知文法G[S],其产生式为：S→(S)|L(Gnn|nL(Gnn|n:当推导次数为1时，使用产生式S→，此时左括号与右括号个数为:假设推导次数为n时(a)成立,即S(((...S...))) 则推导次数为n+1次时，多使用一次产生式S→(S)即S(((...S...)))(((...S...))) 推导次数为n+1次时(a)根据(1)(2)L(Gnn|n其次证明{(nn|n0}n:n=0时,S→:n=k时,结论成立，即(kkL(G)n=k+1时结论成立。由(k)kL(G)，其推导过程如下：S(((...S...))) 当n=k+1S(((...S...)))(((...S...))) k1故(k1k1根据(1)(2)可得：{(nn|n0}1，2L(Gnn|{anbnci|n≥1,i≥0把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产S→A→B→SwabE为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S→aE|Ea|bSS|SbS|SSbE→aEbE|bEaE|ε(3)Sw中满足|a|≤|b|≤2|a|S（其中B产生1到2个bS→aSBS|BSaS|εB→b|bbG[S]:2可推出:a,aa,aaa,……从规则3可推出:b,bb,bbb,……再从规则1可推出句子：ab,aab,aabb,aaab,Sabab的个数不尽相同。故：L(G)={ambn|m,n≥1}G[S]：(1)aa+a*分别给出最左推导和最右推导过程，并为该串构造语法树。(1)此文法生成串aa+a*的最右推导：此文法生成串aa+a*的最左推导：7GN→D|D→0|1|2|3|4|5|6|7|8|GL（G）0127、34568的最左推导和最右推导。∵N∴L(G)=｛d(n+1)|n≥0,d∈{0,1,…,允许以0开头的自然数（十进制无符号整数 写一个文法，使其语言是奇数集，且每个奇数不以0（首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别个非终结符来产生句子的第1引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0；一个用来产生句子的结尾，为奇数；另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了）S0S 〈奇数尾〉→〈奇数头〉→2|4|6|8| 〈数字〉→0|9写一个上下文无关文法CFG，使其语言是能被5整除且不以0｛5,10,15，….5050注意010证明下面的文法是二义的：（根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该f….ese…结构的（用“”代表“fe”代表“ese。因此我们就要到f….se…结构中去找二义性。我们知道，程序语言一般都规定ese部分是和它前面离它最近的没有被匹配的的f语句进行匹配。而上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在ese前面有两个（iiiei，elseif）iiiei，存在如下两个最右推导：S=>iSeS=>iSei=>iiSei=>iiieiS=>iS=>iiSeS=>iiSei=>11θ1、θ2、θ3、标识符、（）θ1θ2的优先级相同，θ3的优先级低于θ1、θ2的优先级，优先级相同的运算符从右往左计算，可以用设E为识别符号，终结符号集={θ1、θ2、θ3（、I}，非终结符号集={E、T、F}E→T|Tθ3E3题意要求：θ1和θ2的优先级相U，θ3θ1、θ2θUθ1、θ23导出来，即应为图3 U

U

1

V 2

3ab不成立又因为优先级相同的运算符从右往左计算，应采用右递归，即应为图 U

4c不成立,d第三章词法分析本章要点本章目标：３．掌握词法分析器的自动产生本章重点：词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。正规式NFA（非确定的有限自动机NFADFA（确定的有限自动机DFA正规式NFA（非确定的有限自动机NFADFA（确定的有限自动机DFA作业一、单项选择题（按照组卷方案，至少15道 a.关键 b.标识 c.常 d.算符和界 a.不含回路的分叉结 b.含回路的状态结 c.终态结 d.都不 (c)l(l| (d)ll*|正规表达式(ε|a|b)2 (b){ab，ba，aa，bb}(c){a，b，ab，aa，ba，bb}(d){ε，a，b，aa，bb，ab，ba}有限状态自动机可用五元组（VT，Q，δ，q0，Qf）来描述，设有一有限状态自动机M的VT={01}，Q={q0q1q2}，Qf={q2}，δ的定 M所对应的状态转换图 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）来描述，设有一有限状态自动机M的VT={01}，Q={q0q1q2}，Qf={q2}，δ的定 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）M的VT={01}，Q={q0q1q2}，Qf={q2}，δ的定 M所能接受的语言 01001001001 ①组织源程序的输入；按词则分割出单词，识别其属性，并转换成属性字的形式输10.NFA11.。A.有穷自动机理论B.图灵机理论Ｃ.图论Ｄ.设有两个状态S和T，如果从S出发能读出某个字w而停于终态，那么从T出发也能读出同样的字而停于终态；反之，果从T出发能读出某个字w而停于终态，那么从S出发也能读出同样的字而停于终态。则我们称状态S和状态T是 A.可区分的；B.等价的；C.多余的；D. a.②③④⑦b．②③④⑥⑦c．①②③④⑥⑦ 与(a*+b)*(c+d)等价(即有相同符号串集)。(x+y亦可写作 b.③④⑤ 。 L或 与(a|b)*(a|b)等价的正规式 A.a*| B. C. D. 一．答案：1.b；2.b；3.c；4.d；5.②；6.②，7.④；8.b；9.①；10.B；11.12.B；13.d；14.d；15.d；16.d；17.c；18.C；19.二、填空题：（按照组卷方案，至少15道 DFAM的化简是指：寻找一个状态数比MDFAM’，使词法分析器所的输出常表示成如下形式的二元式 把状态转换图用程序实现时，对于含有回路的状态结点来说，可以让它对应一个 单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比如，对于某个标识符，常将 作其属性值单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比如，对于常数，常将 作为其属值如果一个种别含有多个单词符号那么对于它的每个单词符号除了给出种别编码以外，还应给出有关 。如 对于*中的任何符号串，如果存在一条从初态结点到某一终态结点的通路，且则称（识别。一个Lex源程序主要包括两部分，一部分 一个DFA可用一个矩阵表示，该矩阵的行表，列示。这个矩阵叫状态转换矩阵15.对于词法分析程序来说，当程序到达“错误处理”时，意味着现行状态i和当前所。 终点；2.L(M)=L(M')；3.单词种别，单词符号的属性值；4.初态，终态；5.whileif语句构成的；6.源程序，单词；7.种别编码；8.存放它的有关信息的符号表项的指针；9.存放它的常数表项的指针；10.单词符号的属性信息（属性值11.两个正规式所表示的正规集相同；12.这条通所有弧的标记符号连接起来形成的符号串等于；13.正规定义式，识别规则；14.状态，输入字符，转换函数（或(s,a)）的值；15.将搜索器回退一个位置，并三、判断题：（按照组卷方案，至少15道1．NFAM（） （）3.r1r2Σr1|r2（）（）5.Σ＝{a，b}Σbb*(a|b)*（）6.NFAMDFAM'L(M')=L(M)（）对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')）GNFAML(G)=L(M)()GDFAML(G)=L(M)()rNFAML(M)=L(r)()rDFAML(M)=L(r) （ 适当设置扫描缓冲区的大小（比如容纳256个字符）可以保证单词符号不会被它的边界所 （）四．答案：1.×；2.；3.；4.×；5.×；6.；7.；8.；9.；10.；11.13.×；14.；15.四、（按照组卷方案，至少5道DFA一张状态转换图只包含有限个状态（即有限个结点，其中一个被认为是初态，而且实际上至少要有一个终态（圈表示。任何a∈，a是rs都是r|s、rsr* 是一个五元式：M=(S，，，s0，F)，其中 S×S的单值部分映射。(s，a)=s's，输入字符为a时，自动机将转入下一个状态s'。s'称为s的后继状态；s0∈S，是自动机的惟一初态 是一个五元式：M=(S，，，s0，F)，其中 是一个从S×到S的子集的映射。(s，a)={s1，s2，……，sm}，意思是：当前sas1s2，……sm；s0∈S，是自动机的惟一初态五、简答题：（按照组卷方案，至少5道1写出标识符（以字母打头，由字母和数字组成的符号串）的正则表达式。答：letterAB...Zab...zdigit01...9id2.词法分析器对程序语言的单词符号一般如何分类？3.人运狼、羊、菜过河，一次运一件，不让羊菜，也不让狼羊，画出渡河的状态转换图。可否将其抽象为一个有限自动机？ NFA: digit01...9digitsdigit(digit)*fraction.digitsexponentE(+-)digitsnumdigits(fraction|)(exponent|答：(1){α|α∈{0，1}*，α01}01词法分析器工作的第一步是输入源程序文本。输入串中一般都包含一些没有意义的字ML(M)是∑上的一个正规集；同时，对于∑上的每个正规集V，存在一个∑上的确定有限自动机M，使得V=L(M)。六、应用题：有一个语言，它接收Σ={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右（２）画出接收该语言的（３）NFA（４）DFA进行状态最小化解法1：（１）0*(0|10)*0*0*(100*)*0*（２）NFA0*NFA000|10NFA01 (0|10)*NFA为0100*(0|10)*0*NFA为（给各个结点标上序号001230 0I———————————————{2，7，16}—————{10———————————————{2716，同—————{10上同—————{12}———————————{7，16}—————{10态旧———————————{716}旧—————{10态旧{5，6，7，8，9，13，14，15，16，17＝E；画出DFA如图所示：000AB1101C0D0E1（４）对该DFA{A，B，D，E}0＝{B，E}，落入了{A，B，D，E}1＝{C}，落入了因此，从{A，B，D，E}中抽取一个状态作为代表，C不变，得到简化了的DFA如图011AC0（２）NFA εεεεεX013Y102IS01123223/34443DFA为A0A0B11C0D10{A，B，D}0{A，B，D}1所以A，B，D011AC0已知字母表ab}上语言Lw|wa的个数是偶数}（２）画出接收该语言的（３）NFA（４）对该DFA（１）语言L的正规式是(ab*a|b)*b*(ab*a（２）画出接收该语言的 ba123456789b（3）NFAISaB——————ABC——————BDE——————CBC——————DBC——————EDEbBbaabBbaaAaAabaabCDEb（４）对该DFA＝{I(1)，I(2)}＝{{B，E}，{A，C，D∵{B，Ea＝{D}I(2)中；{B，Eb＝{E}I(1)∴I(1)＝{B，E∵I(2)}＝{A，C，D}a＝{B}，落入I(1)中；I(2)}＝{A，C，D}b＝{C}，落入I(2)中∴I(2)}＝{A，C，D}不必再分故，得到的接受该语言的最简DFAbbaAaB（２）画出接收该语言的bbaa12b3（3）NFAISaB——————ABA——————BABDFAbbaAaB（４）对该DFA有一个语言，它接收Σ={0，1}上的含奇数个1（２）画出接收该语言的（３）NFA（４）对该DFA进行状态最小化0*10|10*1)*已知Σ={0，1}上正则表达式为（２）画出接收该语言的（３）NFA（４）对该DFA提示：(1)0001已知Σ={0，1}上正则表达式为（２）画出接收该语言的（３）NFA（４）对该DFA提示：(1)0130已知Σ={0，1}上正则表达式为（２）画出接收该语言的（３）NFA（４）对该DFA提示：(13101组成的符号串。{α|α∈{0，1}+α31有一个语言，它接收Σ={a，b}上所有满足如下条件的字符串：不含子串abb的由a和（２）画出接收该语言的（３）NFA（４）对该DFA进行状态最小化提示：正则表达式为：b*(a*|(ba)*)*已知Σ={0，1}上正则表达式为（２）画出接收该语言的（３）NFA（４）对该DFA进行状态最小化提示：(1)01已知Σ={0，1}上正则表达式为（２）画出接收该语言的（３）NFA（４）对该DFA提示：(1)abΣ={a，b}abbb（２）画出接收该语言的（３）NFA（４）对该DFA提示：(1)(a|b)*a(a|b|ε)。Allthestringsofa’sandb’sthatendwitha,aboraa. Allthestringsofa’sandb’sthatdonotendwithbb.。11已知Σ={a，b}上正则表达式为（２）画出接收该语言的（３）NFA（４）对该DFA（1）Allthestringsofa’sandb’sthatcanbedividedintotwosubstingswhereinthesubstring,theevennumberofconsecutivea’sareseparatedbyb’swhileintherightsubstring,theevennumberofconsecutiveb’areseparatedbya’s.12.已知语言为Σ={0，1}上所有由0和14（２）画出接收该语言的（３）NFA（４）DFA进行状态最小化13Σ={0，1}010（２）画出接收该语言的（３）NFA（４）DFA进行状态最小化14.Σ={0，1}（２）画出接收该语言的（３）NFA（４）对该DFA15已知Σ={a，b}上正则表达式为（２）画出接收该语言的（３）NFA（４）对该DFA第四章语法分析—自上而下分析本章要点本章目标理解和掌握语法分析器的功能、自上而下分析所的问题、L（1分析、下降分析的构造过程、预测分析程序等内容。本章重点 文法的条件及其判别，计算first集和follow集3．递归下降本章难点First集合，产生式候选的First集合，非终结符的follow作业一、单项选择题： a.自左b.自顶向下c.自底d.自右向 a.正则表达 b.正规文 c.扩展的 d.翻译模自上而下分析的四个问题中，不包a.需消除左递归；b.存在回朔；c.虚假匹配；d. a.表达式；b.c.单词；d. 把规则T→F|T*F表示成扩展克斯范式以后，画出它的语法图应该是。TFTFF*TF*FTFTF*FTF*F图 图 是LL(1)文法a. b. c.S→aS|bd.G：则 a. b. c.p, d.A,一．答案：1b；2.c；3.d；4.c；5.d；6.二、填空题： 在扩充科斯范式中， 表示符号或串α的出现可有可无对于一个文法，当给出一串符号时，怎么能知道它是不是该文法的一个句子呢？这就要判断，看是否能 。文法exp→expaddopterm|term消除左递归的结果 写出E→T|E+T的EBNF范式 扩展克斯范式描述语法的好处是直观易懂便于表 二．答案：1.文法的产生式，单词符号（文法的终结符）2.左递归，回溯；3.方括号（或[]）；5.从文法的开始符号出发推导出这个输入串（或：能否建立一棵与输入串相匹配的语法分析树。）6exptermexp′；expaddoptermexp′|；7E→T{+T}；8.左三、判断题：LL(k)（存在一种算法，能判定任何上下文无关文法是否是LL(1)的。()一个文法是含有左递归的，如果存在非终结符P，使得P*P 提取公共左因子的副产品是引进了大量的非终结符和ε产生式 把一个文法改造成任何非终结符的所有后选终结首符集两两不相交的办法是消除左递归。( )若XVT，则FIRST(X)={X}。 一个文法的预测分析表含有多重定义，说明该文法是LL(1) 三．答案：1.；2.；3.×；4.；5.×；6.；7.×；8.；四、一个文法如果存在非终结符P，P=>+P当一个文法满足LL(1)条件时，可以为它构造一个不带回溯的的自上而下分析程序，该程序一个文法G，如果满足以下条件，则称为LL(1)对于文法中每一个非终结符AM[A,a]A为非终结符，a是终结符或“”。矩阵元素M[A,a]中存放着一条关于A的产生式，当A输入符号a时所应采取的候选。M[A,a]中也可能存放一个“出错标志”，A根本不该输入符号a。自上而下分析是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。五、简答题：试说明没有一个左递归文法是LL(1)试说明没有一个LL(1)Declist→Declist;Decl|DeclIdList→Idlist,id|Type→ScalarType|array(ScalarTypeList)ofTypeScalarType→id|Bound..BoundBound→SignIntLiteral|idSign→+|-|eScalarTypeList→ScalarTypeList,ScalarType|答：词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子。词法分对于任一个左递归文法来说，存在AVNAA...，因此，在文法中必有如下的A→A1→An→ LL(1)文法G是二义性的，那么，一定存WL(G)，W=a1,a2......,an，有最左推导序列的不同在于，于对某一AVN和当前要匹配ai(1≤i≤n)，分别A的两个不同的候选A→αA→β进行推导ai若 ε且 aiFIRST(α)aiαβεβεaiFIRST(α)aiFOLLOW(A)显然无论(i)还是(ii)，都和G是LL(1)文法假定当前轮到非终结符A去执行匹配任务，A共有n个候选1、2、……n，这时候该用哪一个候选去替换A，原始的办法是采用对所有候选采取“试探”的方法。如果某个候选不A去执行匹配任务，An个候选1、2、……n1|2|……|n。A的第一个输入符号为a，如果a属于某个First(i)，则用该i来匹配A。但是，若a既属于某个First(i)，又属于某个First(j)，则说明i和i存在共同的左部，也就是说，有共同的左因子。此时无法确定到底是用i还是用j来匹配A。所以要消除左因子。六、应用题G[S]：S→(L)|aL→L,S|.对（1）中得到的文法FirstFollow.给出对句子(a,(a,a))G′：S→(L)|aL→L′→,SL′实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：G′FIRST(S)={(,a FOLLOW(S)={#,),FIRST(L)={(,a FOLLOW(S)={)FIRST(L′)={′,′, FOLLOW(L′)={)按以上结果，构造预测分析表M(),a#SSS→→(LLL→LL′L′→文法G′是LL(1)的，因为它的分析表不含多重定义。预测分析器对输入符号串(a,(a,a))做出的分析动作如下：栈(a,(a,$(a,(a,S→a,(a,a,(a,L→a,(a,S→,(a,,(a,L′→,(a,(a,S→a,a,L→a,S→,,L′→S→L′L′$$考查文法G(s):ST|aS|aT→T,S|S 如果是LL(1).消除文法的Gs：S→(T)|a+S|aT→ST′T`→,ST′|再提取公共左因子，最后得到改造后的文法①S→(T)|a②S′→+S|③T→S④T′→,ST′|.First(S)={(，a Follow(S’)=First(T)={(，a}； Follow(T)={)}；First(T’)={‘,’，ε}; Follow(T’)={)}；产生式①的两个候选的First集合：Fist(（T）)=（，First(aS’)={a}产生式②，First(S’)∩Follow(S’)=；产生式④，First(T’)∩Follow(T’)=；LL(1)的，①S→(T)|aPROCEDUREIFSYM=′(′THENIFSYM=′)′THENELSEELSEIFSYM=′a′THENELSE②S′→+S|PROCEDURES′;IFSYM=′+′THENBEGINADVANCE;SEND③T→ST′PROCEDURET; T④T′→,ST′|PROCEDURET′;IFSYM=′,′THENS;T′G[S]：S→uBDzB→Br|D→E→y|F→x|FIRSTFollow构造这个文法的LL(1)说明这个文法不是LL(1)的 FIRST(S)={u FOLLOW(S)=FIRST(B)={w FOLLOW(B)={r,zFIRST(D)={x,y, FOLLOW(D)={zFIRST(E)={y, FOLLOW(E)={x,zFIRST(F)={x, FOLLOW(F)={z该文法的LL(1)uzrwxy#SBDEFM[B,w]有两个产生式B→Bv,FIRST(Bv)=FIRST(ww所以不是LL(1)B′→rB′|D→E=y|F=x|E→T| T→F| F→i|构造预测分析表，并给出对输入串i*i+iFirstFollowFIRST(E)=FIRST(T)=FIRST(F)={(,i}；FIRST(E′)={+,ε}；FIRST(T′)={*,ε}FOLLOW(E)=FOLLOW(E′)={),#}；FOLLOW(T)=FOLLOW(T′)={+，)，# FOLLOW(F)={*,+,),#}再通过对文法的每个非终结符的任意候选都构造出First {(,i} ；FIRST(FT′)={(,i}；FIRST(*FT′)={*}iEiEE→TE′+*()#E′→E′→TT′→ T′→T′→FGLL(1)构造LL(1)先消除左递归，得到文法S→(TT→SN2→,SFirstFollowS{a，^，({#，,，)T{a，^，({){,，ε{)N2FIRST（,SFIRSTFIRST(,SN2)∩且：FIRST(N2)∩FOLLOW(N2)=所以文法是LL(1)得到预测分析表： S→(T 也可由预测分析表中无多重判定文法是LL(1)的。#### FIRSTbexpr→bexprorbterm|btermbterm→btermandbfactor|bfactorbfactor→notbfactor|(bexpr)|true|bexpr→ btermbexpr′bexpr′→orbtermbexpr′|bterm→bfactorbterm′bterm′→andbfactorbterm′|bfactor→notbfactor|(bexpr)|true|falseFirst(bexpr)=First(bterm)=First(bfactor)={not,(,true,false}First(bexpr′)={or,}First(bterm′)={and,Follow(bexpr)=Follow(bexpr′)={),$}Follow(bterm)=Follow(bterm′)={or,),$}Follow(bfactor)={and,or,),$}已知G[R]的产生式如下R→R′|′T|TT→TF|FF→F*|C→(R)|a|构造它的LL(1)分析表，并写出对输入串a|ba*消除上面文法中的左递R→R′→′|′TR′|εT→FT′T′→FT′|εF→CF′F→*F′|C→(R)|a|S→S*T|S/T|TT→T+F|T-F|F→(S)|i|ie构造预测分析表，并给出对输入串i/i*i+i构造预测分析表，给出对输入串cabc已知文法G：S→ (L|aL→ S,L|)构造文法G“（ａ）”解FISRTFOLLOWFIRST(S)={(,aFIRST(L)={a}FIRST(S)={(,),a}FOLLOW(S)={′,′,#}FOLLOW(L) FOLLOW(S)={′,′,#(a,}#SS→(S→LL→S,L→S,L→０（ａ）＃（２）“（ａ）”1所示。表1对输入０（ａ）＃１（ａ）＃S→(２ａ）＃３＃L,ａ）＃L→S,４＃L,ａ）＃５６７L→８＃＃Ｇ＝({i，d，′(′，′)′其中Ｐ：E→iAEA→iAA→FIRSTFOLLOW集；(3)构造改写后文法的预测分析表；该文法是LL(1)文法吗?。E→iAE′Ｅ′→|AE′A→iAA→(E各非终结符的FISRTFOLLOWFIRST(E)={i}FIRST(E′)={i,d,(,)FIRST(A)={i,d,FOLLOW(E)={,#FOLLOW(E′)={},#}FOLLOW(A)={i,d,(,),#}id()#EEE→AA→预测分析表中无多重,因此该文法是LL(1)文法.对（1）中得到的文法FirstFollow.给出对句子aadb上的分A→aN3→ABB→dN2→bAB ysisaebd#AA→aBB→dN2→bN3→Ae由预测分析表中无多重判定文法是LL(1)的FIRSTFOLLOW集构造改写后文法的预测分析表；该文法是 1种改写：S→bN2→BaB→aSB ysisab#S→bB→a→Ba由预测分析表中无多重判定文法是LL(1)的。第2种改写：S→AA→bBN3→aBB→aSAB{a, ysisab#S→AA→bBB→a→aB由预测分析表中含有多重判定文法不 FIRSTFOLLOW集构造改写后文法的预测分析表；该文法是 S→MH→LSK→dML→eHM→bLS{a,d,b,M{d,HLK{d, ysisaodefb#S→M→M→M→M→MM MH oL→eHK→dM由预测分析表中无多重判定文法是LL(1)的Expr→(Expr)|VarExprTailExprTail→-Expr|Var→idVarTailVarTail→(Expr)|构造LL（1）给出对句子id--id((id))考查文法G(s):ST|aS|aT→T,S|S.LL(1)a+(a,a)写出分析过程第五章语法分析—自下而上分析本章要点LR语法分析器自动产生工具LR本章目标掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。本章重点算符优先分析方法：FirstVT, LRLR(0)、SLR、LR(1)和LALR(1)LRLR本章难点LR作业一、单项选择题：LR语法分析栈中存放的状态是识 的DFA状态a.前缀；b.可归前缀；c.项目；d.句柄 句 G＝｛S｛a｛S→SaS，S→ε，S， a.深度分析b.宽度优c.算符优先分析法d.递归下降子程序自底向上语法分析采用 分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。a.b.c.d.移进－归一个LR(k)文法，无论k取多大 a.都是无二义性的；b.都是二义性的；c.一部分是二义性的；d.无法判定二义性 和LR分析法a.深度分析b.宽度优c.算符优先分析法d.递归下降子程序在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自顶向下分析试图为输入符号串构造一个 ；a.语法树b.c.最左推导d.在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自底向上分析试图为输入符号串构造一个 。a.语法树b.c.最左推导d. a.右递归b.c.直接右递归d.直接LR分析是寻找右句型 a.短语b.素短语c.最左素短语d.LR分析法中分析能力最强的 a.SLR(1)；b.LR(0)；c.LR(1)；d.T->T*F|FF->FP|PP->(T)|a该文法句型T*P(T*F)的最左直接短语是下列符号 a. b. c. d. a．算符优先分析法b．LR分析法c．递归下降分析法d．LL(1) a.3 b.2 c.4 d.1算符优先法属于（a.自上而下分析法b.LR分析法c.ＳLR分析法d.在LR分析法中，分析栈中存放的状态是识别规范句 的DFA状态 b.前 c.活前 d.LR(0)项1.b；2.b；3.b；4.d；5.d；6.a；7.c；8.c；9.d；10.b；11.d，c；12.c，b；13.a；14.15.a；16.d；17.二、填空题： LR(k)分析法中， 的含义，k的含义

， 设文法G（E为其开始符号）T→T*F|F则句型E+T*F+i的句柄 自下而上分析方法的基本思想是：从输入符号串开始，利用文则逐步进行归约，直至归约到文法的 。 在LR(0)分析中，相容的项目集，必须满足的条件 LR语法分析栈中存放的状态是识 的DFA状态在LR分析过程中的任何时候，栈里的文法符号从下往上应该构成 对于LR(0)A→12对活前缀1是有效的，其条件是存在规范推导。形式上我们说一个LR(1)项目[A→a]对于活前缀是有效的，如果存在规范推导。 所谓算符优先分析法就是仿照算术四则运算的运算过程设计的一种语法分析方法它首先要规定 ，然后利用这种关系确定 ，并进行 如图所示的语法树中，a，b不在同一句柄中，先归约，所以的优先级高于。PPRb…aQ对于句型η的语法树，若它的一棵子树的根标记为A，且将此子树的末端结点标记从左至右排列起来所形成的符号串为β，则β是 ；此时文法中 LR(0)每个项目中圆点的左部表示在分析过程中，要用该产生式归约 NFA1.寻找或确定一个句型的句柄；2.从左到右扫描输入串最右推导的逆过程；3.归约，接受；4.T*F；5.开始符号；6.最左素短语，句柄；7.移进项目和归约项目并存，多个归约项目并存；8.9.10.*S'A12

S'A，其中=，a是的第一个符号，或者 是#而为。12.归约项目，接受项目，移进项目，待约项目；13.运算符之间的优先关系；句型的“句柄”，归约；14.a，a，b；15.句型η相对于A的一个短语；A==>+β；16.句柄已识别的部分(进入符号栈)，等待识别的部分；17.活前缀三、判断题SLR文法或LALR文法（LL(1)文法不能用LR（1）分析器来分析 存在有左递归规则的文法是LL(1)的。 (算符优先文法中任何两个相邻的终结符号之间至少满足三种关系(＜·，·＞，＝·之一。()任何LL(1)文法都是无二义性的。 每一个SLR(1)文法也都是LR(1)文法。 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。()LL(1)LR(1)文法，反之亦然。()LR(1)分析中括号中的1是指，在选用产生式A→αFIRST(α) （ （ （ （ （14.×；15.√；16.×；17.√；⒙×；19.五、五.答案G是一个文法，SGS=>*A且A=>*，则称是句型相对于非终结符A的短语。特别地，如A=>，则称是句型相对A->的直接短语。一个文法，如果它的任何一个产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：……QR……，则我们称该文法为算符文法。a>b，则称G所谓素短语是指这样的一个短语，它至少含有一个终结符，并且，除自身之外不再含任何更小的素短语。一个字的前缀是指该字的任意首部。活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。文法G的每一个产生式的右部添加一个小圆点，称为G的一个LR(0)构成识别一个文法活前缀的 六、简答题：说明任何SLR(1)文法都是LR(1)LRSLR(1)GLR(1)GLR(1)项目集规范族中，或有下 的LR(0)项目集规范族或有下面的(i)，或有下面的(ii)，或两者皆有GSLR(1)a不属于FOLLOW(A)GLR(1)a∈FOLLOW(A)，这和假设。因此，任何SLR(1)文法都是LR(1)文法自底向上分析技术采用移进－归约法实现句型分析，但移进－归约法决不是一种分析技于各种自底向上技术的一种实现方法。自底向上分析的关键是寻找句柄。简单优先分析法、算符优先分析法都是自左向右地向前查看若干个输入符号，找出句柄（或其变型－最左素短语）的尾，然后回头（从右到左）找出句柄（或其变型－最左素短语）的头，这已不是严格地从左到右查看源程序来进行归约了LR(k)分析法则严格地从左到右地读入输入符号串中的符号，且最多向貌似句柄的符号历史”，另一方面根据所用的产生式（规则）推测未来可能碰到的输入符号，即对未来进行展望”串貌似句柄的符号串呈现于分析栈的顶部时，能够根据所记载的历史“展望的信息以及“现实”号规为了记住分析的历史和汇集全新的展望信息，LR分析技术这样来处理：将归约过程的历史和“展望”历史和“展望”历史和已推测出的展望”底向上翻阅整个栈。LR分析程序的每一步工作都是由栈顶状态和现行输入符号惟一确定的。根据文法，可以将各种状态下不同输入符号所要做的工作用一张表表示出来，然后用这张表直到整个分析过程的进行。这是因为，许多句型在归约过程中虽然分析的步数和过程不一样，但它们所处的状态有一些是一样的，而这些同样的状态在有穷自动机中只需要出现一个即可。LR项目是在规则右部适当位置加一个圆点得到的，用圆点的位置来标记分析过程中的某希望能进一步看到可由圆点右部推出的符号串；如果圆点右部为，则自然联想到可将规则七、应用题：Sa||TT,S|Firstvt构造算符优先关系表,并说明该文法是否是OPG （1）Firstvt(S)={a,,(}，Firstvt(T)={a,,,,(}，Lastvt(S)={a,,)}，Lastvt(T)={a,,,,)a(),a(),OPG文法a(),111111111122133222123313344412S a栈0(a,a)1<(a,a)2<a,a)3>,4<,5<a)6>)7>)8=)9=SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。S→Sab|bRR→S|该文法的文法G'(0)S'→(1)S→(2)S→(3)R→(4)R→LR(0)goto函数(DFA)如下：I0={S'→·S,S→·Sab,S→·bR}I1={S'→S·,I2={S→b·R,R→·S,R→·a,S→·Sab,S→·bR}I3={S→Sa·b}I4=I5={R→S·,S→S·ab}I6={R→a·}I7=求FOLLOW集：在I5中，出现移进－归约，且因此，此文法不是SLR(1)证明下面文法是SLR(1)文法，并构造其SLR 答案：3.该文法的文法G'为(0)E'→(1)E→(2)E→(3)T→(4)T→(5)F→(6)F→(7)F→LR(0)goto函数(DFA)如下:I0={E'→·E,E→·E+T,E→·T,T→·TF,T→·F,F→·F*,F→·a,I1={E'→E·,I2={E→T·,T→T·F,F→·F*,F→·a,I3={T→F·,F→F·*}I4={F→a·}I5=I6={E→E+·T,T→·TF,T→·F,F→·F*,F→·a,F→·b}I7={T→TF·,F→F·*}I8=I9={E→E+T·,T→T·F,F→·F*,F→·a,FOLLOWFOLLOW(E)={＋,FOLLOW(T)={＋,＄,a,FOLLOW(F)={＋,＄,a,b,SLR显然，此分析表无多重定义，所以此文法是SLR文法下面文法属于哪类LR(1)S→(0)(1)S→(0)S'→(2)S→(3)R→(4)R→LR(0)goto函数(DFA)如下:I0={S'→·S,S→·(SR,S→·a}I1=I2={S→(·SR,S→·(SR,S→·a}I3={S→a·}I4={S→(S·R,R→·,SR,R→·)}I5={S→(SR·}I6=I7={R→,·SR,S→·(SR,S→·a}I8={R→,S·R,R→·,SR,R→·)}I9={R→,SR·}每个LR(0)项目集中没有。因此，此文法是LR(0)文法。其分析表如下设文法GS→A→BA|B→aB|证明它是LR(1)构造它的LR(1)给出输入符号串abab5.答案：(1)构造其文法G'的产生式(0)S'→(1)SA (3)A→(4)B→(5)B→构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)I0={[S'→·S,$],[S→·A,$],[A→·BA,$],[A→·,$],[B→·aB,a/b/$],[B→·b,a/b/$]}I1={[S'→S·,$]}I2={[S→A·,I3={[A→B·A,$],[A→·BA,$],[A→·,$],[B→·aB,a/b/$],[B→·b,a/b/$]}I4={[B→b·,a/b/$]}I5={[B→a·B,a/b/$],[B→·aB,a/b/$],[B→·b,a/b/$]}I6={[A→BA·,$]}I7={[B→aB·,该文法的LR(1)项目集规范族中没有，所以该文法是LR(1)文法构造LR(1)以上分析表无多的定义，所以该文法 对于输入串abab6.LALR(1)分析表E→E+T|T→(E)|其文法(0)S'→(1)S→(2)E→(3)ET(4)T→(5)T→构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)I0={[S’→·S,$],[S→·E,$],[E→·E+T,$/+],[E→·T,$/+],[T→·(E),$/+],[T→·a,$/+]}I1={[S’→S·,$]}I2={[S→E·,$],[E→E·+T,$/+]}I3={[E→T·,$/+]}I4={[T→(·E),$/+],[E→·E+T,)/+],[E→·T,)/+],[T→·(E),)/+],[T→·a,I5={[T→a·,I6={[E→E+·T,$/+],[T→·(E),$/+],[T→·a,I7={[T→(E·),$/+],[E→E·+T,)/+]}I8={[E→T·,)/+]}I9={[T→(·E),)/+},[E→·E+T,)/+],[E→·T,)/+],[T→·(E),)/+],[T→·a,)/+]}I10={[T→a·,)/+]}I11={[E→E+T·,$/+]}I12={[T→(E)·,$/+]}I13={[E→E+·T,)/+],[T→·(E),)/+],[T→·a,I14={[T→(E·),)/+],[E→E·+T,)/+]}I15={[E→E+T·,)/+]}I16={[T→(E)·,合并同心的LR(1)项目集，得到LALRI0={[S’→·S,$],[S→·E,$],[E→·E+T,$/+],[E→·T,$/+],[T→··(E),$/+],[T→·a,$/+]}I1={[S’→S·,$]}I2={[S→E·,$],[E→E·+T,I3,8={[E→T·,I4,9={[T→(·E),$/+/)],[E→·E+T,)/+],[E→·T,)/+],[T→·(E),)/+],[T→·a,)/+]}I5,10={[T→a·,$/+/)]}I6,13={[E→E+·T,$/+/)],[T→·(E),$/+/)],[T→·a,I7,14={[T→(E·),$/+/)],[E→E·+T,)/+]}I11,15={[E→E+T·,$/+/)]}I12,16={[T→(E)·,LALRSS→LLL→BB→0B→1LR101.110（1）文法为G′，增加产生式S'SSLLBBFIRST(S')=FIRST(S)=FIRST(L)=FIRST(B)=FOLLOW(S')=FOLLOW(S)={#}FOLLOW(L)=FOLLOW(B)=GLR(0)DFA如下图所示：在I2中：B→.0和B→.1为移进项目，S→L.为归约项目，存在移进-归约，因此所给文法不是LR(0)文法。I2、I8FOLLOW(S)∩{0，1}={#}所以在I2、I8中的移进-归约可以由FOLLOW集解决，所以G是SLR(1)文法构造的SLR(1)·01#SLB0123127345683787对输入串101.110#10#20304050260270802902002026026026026802680260268#0268#0#归约L#分析成功，说明输入串101.110构造LR(1)给出用LR(1)分析表对输入符号串abab①Z→C②C→ifE④E→E其中：Z、C、S、A、EVN；if、then、＝、、i构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA构造其SLR（1）1.首先文法：在G中加入产生式0．Z'→Z，然后得到新的文法G'，再求G'的识别全部活前缀的DFA：Z→.CC→.ifEthenI1：I2：Z→CI3：C→if.EthenE→.EAI4：Z→CS.C→ifE.thenE→E.AE→.EAA→.iI10：C→ifEthen.I11：E→E.AE→E.AI13：E→EA.＝{#,,then}{＝,#,,then则可构造SLR（1）0＝i#ZCSEA0121245378456718981G[S]：DFALRabb首先文法G0.S′→S再求G′的识别全部活前缀的给定文法G[S]S→SaA|aA→⑴请构造该LR(0)项目集为状态的识别规范句型活DFA⑵请构造该LR(0)分析表⑶什么是LR(0)文法？该LR(0)⑷什么是SLR(1)文法SLR(1)文法吗下面文法属于哪类LRS→aSAB|BAA→aA|BB→b输入串abababb该文法的文法G'(0)S'→(1)S→(2)S→(3)A→(4)A→(5)B→LR(0)goto函数(DFA)如下：I0={S'→·S,S→·aSAB,S→·BA,B→·b}I1=I2=I3={S→a·SAB,S→·aSAB,S→·BA,B→·b}I4={S→B·A,A→·aA,A→·B,B→·b}I5={S→aS·AB,A→·aA,A→·B,B→·b}I6={S→aSA·B,B→·b}I7={A→a·A,A→·aA,A→·B,B→·b}I8={A→B·}I9={S→BA·}I10={S→aSAB·}I11={A→aA·}FOLLOW文S→(L)| L→L,S|Firstvt构造算符优先关系表,并说明该文法是否是OPG给出串(a,(a,a)),(,栈输动$$$构造其LALR(1)文法，并分析输入串bdc下面是一个描述={ab}LALR文法（SLR文法）‘＋’代|’，用∧代替（空字。E→E+T|T→TF|F→F*|(E)|a|b|构造这个文法的LALR第六章属性文法和语法制导翻译本章要点本章目标S-属性文法和自下而上计算、L-属性文法和自顶向下翻译、自下而上计算继承属性等内容。本章重点语义规则的两种描述方法：语法制导的定义和翻译方案。语法制导的定义没有指明语义规则的计算次序，而翻译方案显式给出语义规则（或叫语义动作）的计算次序和位置。3．基于属性文法的处理方法，综合属性定义（S属性定义）和L属性定义。4．设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点。这种设计可看成是件。 5．语义规则的三种计算方法：分析树方法、基于规则的方法和忽略规则的方法 本章难点作业一、单项选择题： a.综合属 b.继承属 c.继承属性和综合属 d.都不对应于产生式A→XY继承属性Y.y的属性计算，可能正确的语义规则 a.A.a:=f(X.x，Y.y)；b.)Y.y:=f(A.a，Y.y)；c.Y.y:=f(X.x)；d. a.L-b.R-c.综合属性d.出现在产生式和出现在产生式不由所给的产生式的属性计算规则进行a.左边的继承属性；b.左边的综合属性；c.右边的综合属性；d. a.父结点b.子结点c.兄弟结点d.父结点与子结点e.父结点与兄弟结 a.父结点b.子结点c.兄弟结点d.父结点与子结点e.父结点与兄弟结一般来说，对出现在产生式右边的和出现在产生式左边的都必须提供a.综合属性 b.继承属性 c.L-属性，d.R-属A、BCAab，Bc，C有继承dA→BC可能的属性计算规则中，属性要在其它地方计算，aC.dA.b；b.A.aA.b；c.A.aB.c；d.C.d a.自顶向下，b.自底向上，c.从左到右，d.S-属性文法的计算中，设当前的栈顶由指针op指示，假设综合属性刚好在每次归约前计算的。假定产生式为AXYZ，相应的语义规则为A.a:=f(X.x,Y.y，Z.)。在把XYZ归约成AZ.z的值放在va[op]Y.y的值放在va[op-1]中，X.x的值放在va[op-2]A（X的位置A.aa.b.state[top-1]，val[top-c.state[top-2]，val[top-d.state[top-3]，val[top-T→num{print(num.val)} 有一语法制导翻译如下所示:（第8章 {print“1” {print“2” {print“3” {print“4” 属性a.传 b.继 c.抽 d.综A→A1YA→X它的每一个文法符号都有一个综合属性，用相应的小写字母表示，gf是任意函数。消除 {R.i:=f(X.x) {A.a:=R.s {R1.i:=g(R.i,Y.y)}{R.s:=R1.s}，{R.s:=R.i}；b.{R.s:=R.i}，{R.s:=R1.sc.{R.s:=R1.i}，{R.s:=R.s}；d.{R.s:=R.s}，{R.s:=R1.i S-属性文法，L-属性文法； c.L-属性文法，S-属性文法；d.一．答案：1b；2.c；3.c，d4.ac；5.b；6.e；7b，a；8.c；9.b；10.a；11.d；12.13.d；14.a；15.二、填空题：属性用于“自下而上”传递信息；而属性用于“自上而下”如果一属性文法不存在属性之间的按照 的编译程序模型来理解语法制导翻译方法所谓的语法制导翻译，直观上说，就是为文法中每个 配上一组语义规则，并在 的同时执行这些语义规则。 Tval:=T1 S－属性文法中的每个文法符号，只含有属性。与树遍历的属性计算方法不同，一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性计算。 可用于一遍扫描的自而下分析，而 则适合于一遍扫描的自下而上分析。已知表达式文法的一条语则EE1+T，对每个文法符号引入nptr属性，可以写出为该文法建立抽象语法树的对应于这条规则的语义规则为 在S-属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的 通过在基础文法中新引入非终结符M，加入形式为 的新的产生式，可以使属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内 语义规则可能产生副作用（如产生代码，也可能不是变元的严格函数（入某个规则给出可用的下一个数据单元的地址。这样的语义规则通常写成 我们可以用一个 来一个标识符，看它是出现在赋值号的左边还是右边，以确定是需要这个标识符的地址还是值。在自下而上语法分析中若一个产生式匹配输入串成功或者在自下而上分析中当一个产生式被用于进行归约时， 完成相关的义分析和代码产生工作。S-属性文法自下而上计算属性时在分析栈中使用一个附加的域val来存放综合属性值。文法符号是隐含在state中而不是在栈中当把文法符号放入栈中时那么当第i个state对应符号为A时，va[]中就存放 。对于一个属性文法，A→XX2…XP,其每个语义规则中的每个属性都是一个综合属性;或者，X(1jn)是一个继承属性，这个继承属性仅依赖于:①②则，该属性文法是L-1.综合，继承；2.循环依赖关系；3.一遍扫描，产生式，语法分析；4. val*Fval}；6.L－属性文法，S－属性文法；7.Enptr:=mknode(´+´,E1nptr,Tnptr)；8.