编译原理作业集-第四章-修订版

编译原理作业集第四章自上而下语法分析西安理工大学计算机科学与工程学院张发存编写3/14/20206:54:28PM-1-第四章语法分析—自上而下分析本章要点1.语法分析器的功能；2.自上而下分析方法，LL(1)文法3.递归下降分析程序构造；4.预测分析表的构造及预测分析过程；5.LL(1)分析中的错误处理。本章目标理解和掌握语法分析器的功能、自上而下分析所面临的问题、LL（1）分析法、递归下降分析的构造过程、预测分析程序等内容。本章重点1．语法分析器的功能，自上而下的基本概念2．LL（1）文法的条件及其判别，计算first集和follow集3．递归下降分析方法、预测分析表的构造及其预测过程。本章难点1.非终结符的First集合，产生式候选的First集合，非终结符的follow集合的求解；2.左递归消除；3.递归下降分析程序的编写；作业题一、单项选择题：1.高级语言编译程序常用的语法分析方法中，递归下降分析法属于分析法。编译原理作业集第四章自上而下语法分析西安理工大学计算机科学与工程学院张发存编写3/14/20206:54:28PM-2-a.自左至右b.自顶向下c.自底向上d.自右向左2.上下文无关文法可以用来描述。a.正则表达式b.正规文法c.扩展的BNFd.翻译模式3.自上而下分析面临的四个问题中，不包括a.需消除左递归；b.存在回朔；c.虚假匹配；d.寻找可归约串4.语法分析器接收以________为单位的输入，并产生有关信息供以后各阶段使用。a.表达式；b.产生式；c.单词；d.语句；5.自上而下分析的主旨是，对任何单词符号串，试图用一切可能的办法，从文法开始符号（根结点）出发，________。a.为输入串寻找最右推导；b.为输入串寻找最左直接子树；c.为输入串建立最右直接子树；d.为输入串寻找最左推导；6.把规则T→F|T*F表示成扩展的巴克斯范式以后，画出它的语法图应该是。TF*FTF*FTF*FTF*F图a图b图c图d7.下列文法中，_______是LL(1)文法。a.S→aSb|abb.S→ab|Sabc.S→aS|bd.S→aS|a8.设有文法G：S→Ap|BqA→a|cAB→b|dB则，First(Ap)={_______________}a.a,cb.b,dc.p,qd.A,p一．答案：1.b；2.c；3.d；4.c；5.d；6.图a；二、填空题：1.语法分析器的工作本质上就是按____________________，识别输入符号串是否为一个句编译原理作业集第四章自上而下语法分析西安理工大学计算机科学与工程学院张发存编写3/14/20206:54:28PM-3-子。这里所说的输入串是指由____________________组成的有限序列。2.自顶向下分析会遇到的主要问题是____________________和__________________。3.自上而下地为输入串建立一棵语法树，就是为输入串寻找一个______________。4.在扩充的巴科斯范式中，用______________表示符号或串α的出现可有可无。5.对于一个文法，当给出一串符号时，怎么能知道它是不是该文法的一个句子呢？这就要判断，看是否能。6.文法exp→expaddopterm|term消除左递归的结果为。7.写出E→T|E+T的EBNF范式为。8.扩展的巴克斯范式描述语法的好处是，直观易懂，便于表示。二．答案：1.文法的产生式，单词符号（文法的终结符）2.左递归，回溯；3.最左推导；4.方括号（或[]）；5.从文法的开始符号出发推导出这个输入串。（或：能否建立一棵与输入串相匹配的语法分析树。）6.exp→termexp′；exp′→addoptermexp′|；7.E→T{+T}；8.左递归消去和左因子提取。三、判断题：1.LL(k)文法都不是二义性的。（）2.存在一种算法，能判定任何上下文无关文法是否是LL(1)的。()3.一个文法是含有左递归的，如果存在非终结符P，使得P*P。（）4.提取公共左因子的副产品是引进了大量的非终结符和ε产生式。()5.把一个文法改造成任何非终结符的所有后选终结首符集两两不相交的办法是消除左递归。()6.若X∈VT，则FIRST(X)={X}。()7.一个文法的预测分析表含有多重定义入口，说明该文法是LL(1)的。（）8.自上而下分析及自下而上分析中的“下”是指被分析的源程序串。（）三．答案：1.；2.；3.×；4.；5.×；6.；7.×；8.；四、名词解释：1.左递归；2.递归下降分析器；3.LL(1)文法；4.预测分析表5.自上而下分析四．答案：1.一个文法如果存在非终结符P，P=+P，则称该文法是左递归的。2.当一个文法满足LL(1)条件时，可以为它构造一个不带回溯的的自上而下分析程序，该程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的分析程序称为递归编译原理作业集第四章自上而下语法分析西安理工大学计算机科学与工程学院张发存编写3/14/20206:54:28PM-4-下降分析器。3.一个文法G，如果满足以下条件，则称为LL(1)文法：（1）文法不含左递归；（2）对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交；（3）对文法中的每个非终结符A，若它存在某个候选首符集包含，则A的First集合和Follow集合的交集为空。4.预测分析表是一个M[A,a]形式的矩阵。其中A为非终结符，a是终结符或“#”。矩阵元素M[A,a]中存放着一条关于A的产生式，指出当A面临输入符号a时所应采取的候选。M[A,a]中也可能存放一个“出错标志”，指出A根本不该面临输入符号a。5.自上而下分析是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。五、简答题：1.词法分析和语法分析都是对字符串进行识别的，二者有何区别？2.试说明没有一个左递归文法是LL(1)的。3.试说明没有一个LL(1)文法是二义性的。4.为什么要消除回溯？5.为什么要提取左因子？6.下面文法是有左递归吗？若有，提取左递归。Declist→Declist;Decl|DeclDecl→idList:TypeIdList→Idlist,id|idType→ScalarType|array(ScalarTypeList)ofTypeScalarType→id|Bound..BoundBound→SignIntLiteral|idSign→+|-|eScalarTypeList→ScalarTypeList,ScalarType|ScalarType五．答案：1.答：词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子。词法分析的一个输入符号串是由单个符号组成的单词；语法分析的输入符号串是由词法分析得来的单词组成的句子。2.对于任一个左递归文法来说，存在一个AVN，有AA...，因此，在文法中必有如下的规则序列：A→A1...A1→A2........................An→Aα|βAαβ。显然，FIRST(Aα)∩FIRST(β)≠Φ。因此，没有一个左递归文法是LL(1)的。3.解：编译原理作业集第四章自上而下语法分析西安理工大学计算机科学与工程学院张发存编写3/14/20206:54:28PM-5-设有一个LL(1)文法G是二义性的，那么，一定存在一个W∈L(G)，W=a1,a2......,an，有两棵不同的分析树。如果按最左推导构造这两棵分析树，按么，一定有两个最左推导序列，这来年改革最左推导序列的不同在于，于对某一个A∈VN和当前要匹配的ai(1≤i≤n)，分别使用A的两个不同的候选式A→α和A→β进行推导以匹配ai(i)若αε且βε，则必有ai∈FIRST(α)且ai∈FIRST(β)，FIRST(α)∩FIRST(β)≠Φ(ii)若α和β有一个能推导出ε，比如βε，则ai∈FIRST(α)且ai∈FOLLOW(A)显然，FIRST(α)∩FOLLOW(A)≠Φ无论(i)还是(ii)，都和G是LL(1)文法矛盾。4.假定当前轮到非终结符A去执行匹配任务，A共有n个候选1、2、……n，这时候该用哪一个候选去替换A，原始的办法是采用对所有候选采取“试探”的方法。如果某个候选不成功就需要“回退”。这个回退的过程会导致前次匹配的许多工作推到重来，效率低。而且，最终匹配不成功的时候，难以直到输入串中出错的确切位置。5.假定当前轮到非终结符A去执行匹配任务，A共有n个候选1、2、……n，即A→1|2|……|n。A面临的第一个输入符号为a，如果a属于某个First(i)，则用该i来匹配A。但是，若a既属于某个First(i)，又属于某个First(j)，则说明i和i存在共同的左部，也就是说，有共同的左因子。此时无法确定到底是用i还是用j来匹配A。所以要消除左因子。六、应用题1.已知文法G[S]：S→(L)|aL→L,S|Sⅰ.消除左递归，若有左因子则提取之；ⅱ.对（1）中得到的文法求First集合和Follow集合ⅲ.对（1）中得到的文法构造一个预测分析表；ⅳ.给出对句子(a,(a,a))上的分析动作1.答案：将所给文法消除左递归得G′：S→(L)|aL→SL′L′→,SL′|实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G′有FIRST(S)={(,a}FOLLOW(S)={#,),′,′}FIRST(L)={(,a}FOLLOW(S)={)}编译原理作业集第四章自上而下语法分析西安理工大学计算机科学与工程学院张发存编写3/14/20206:54:28PM-6-FIRST(L′)={′,′,}FOLLOW(L′)={)}按以上结果，构造预测分析表M如下：非终结符号输入符号(),a#SS→(L)S→aLL→SL′L→SL′L′L′→L′→,SL′文法G′是LL(1)的，因为它的分析表不含多重定义入口。预测分析器对输入符号串(a,(a,a))做出的分析动作如下：栈输入输出$S(a,(a,a))$$)L((a,(a,a))$S→(L)$)La,(a,a))$$)L′Sa,(a,a))$L→SL′$)L′aa,(a,a))$S→a$)L′,(a,a))$$)L′S,,(a,a))$L′→,SL′$)L′S(a,a))$$)L′)L((a,a))$S→(L)$)L′)La,a))$$)L′)L′Sa,a))$L→SL′$)L′)L′aa,a))$S→a$)L′)L′,a))$$)L′)L′S,,a))$L′→,SL′$)L′)L′Sa))$$)L′)L′aa))$S→a$)L′)L′))$$)L′)))$L′→$)L′)$$))$L′→$$2.考查文法G(s):S→(T)|a+S|aT→T,S|Sⅰ.消除文法的左递归，提取公共左因子ⅱ.改造后的文法是LL(1)的吗？为什么？ⅲ.如果是LL(1)文法，对每个非终结符，写出不带回朔的递归子程序。2.答案：ⅰ.消除文法的左递归G(s)：S→(T)|a+S|aT→ST′编译原理作业集第四章自上而下语法分析西安理工大学计算机科学与工程学院张发存编写3/14/20206:54:28PM-7-T`→,ST′|再提取公共左因子，最后得到改造后的文法G[S]:①S→(T)|aS′②S′→+S|③T→ST′④T′→,ST′|ⅱ.First(S)={(，a}；Follow(S)={#，‘,’}；First(S’)={＋，ε}；Follow(S’)={#，‘,’}；First(T)={(，a}；Follow(T)={)}；First(T’)={‘,’，ε};Follow(T’)={)}；产生式①的两个候选的First集合：Fist(（T）)=｛（｝，First(aS’)={a}不相交，满足条件。产生式②，First(S’)∩Follow