编译原理复习-中国矿业大学北京.docx

第1章 引论（小结）1. 编译程序的功能：将翻译成2. 编译过程：词法分析、语法分析、语义分析、（中间代码生成、代码优化）、目标代码生成。3. 解释程序的工作模式：一个个获取、分析并执行源程序语句。4. 编译程序与解释程序的根本区别：是否生成目标代码。5. PL/0编译系统的构成：以语法语义分析程序为核心,词法分析程序和代码生成程序都作为一个独立的过程被语法语义分析程序调用。6. PL/0的语法描述：EBNF7. PL/0的目标代码：p-code8. PL/0的出错处理：语法错误、语义错误、运行错误第1章 练习1、程序语言一般分为 （1） 和 （2） 两大类。其中 （3） 与人类自然语言比较接近，（4）又称为面向机器的语言。A 高级语言B 专用程序语言C 低级语言D 通用程序语言A C A C2、面向机器的语言是指（1） ，其特点是（2） 。（1）A. 用于解决机器硬件设计问题的语言B. 特定计算机系统所固有的语言C. 各种计算机系统都通用的语言D. 只能在一台计算机上使用的语言（2）A. 程序执行效率低，编写效率低，可读性差B. 程序执行效率低，编写效率高，可读性强C. 程序执行效率高，编写效率高，可读性强D. 程序执行效率高，编写效率低，可读性差B D 3、编译程序是将 （1） 翻译成 （2） ；汇编程序是将 （3） 翻译成 （4） 。 A.汇编语言程序B.高级语言程序C.机器语言程序D.汇编语言程序 或 机器语言程序E.汇编语言程序 或 高级语言程序B D A C 4、编译程序的工作过程可以划分为 （1） 等六个阶段，同时还伴有 （2） 和（3） 。 （1）词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。（2）表格管理（3）出错处理5、编译程序可以发现源程序的全部 （1） 错误和部分 （2） 错误。A.语用B. 语义C.语法D. 运行C B6、要在某台机器上为某种语言构造一个编译程序（编译器），必须掌握的内容有（1）。 A.汇编语言B.源语言C.目标语言D.程序设计方法学 E.编译方法 F.测试方法 G.机器语言B C E7、一个编译程序，不仅包含词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成，还应包括（1） 。其中（2）和（3）不是每个编译程序都必需的。词法分析器用于识别（4） 。语法分析器可以发现源程序中的 （5）。 （1）表格处理和出错处理（2）中间代码生成（3） 代码优化 （4）单词 （5）语法错误8、程序语言的语言处理程序是一种（1）。（2）都是程序语言的处理程序，两者的主要区别在于（3） 。（1）A.系统软件B. 应用软件C.实时软件D. 分布式系统软件（2）A. 高级语言程序 和 低级语言程序B. 解释程序 和 编译程序C. 编译程序 和 操作系统D. 系统程序 和 应用程序（3）A. 单用户与多用户的差别B. 对用户程序的查错能力不同C. 机器执行的效率不同D. 是否生成目标代码A B D9、编译器必须完成的工作有（1） 。A.词法分析B.语法分析C.语义分析D.中间代码生成E.代码优化F.目标代码生成A B C F因为代码优化是为了提高目标程序的质量，不是必须的，没有优化源程序一样能够转化为目标代码。而中间代码生成是为代码优化服务的，没有代码优化的编译器可以直接生成目标代码。10、编译时，语法分析器的任务包括（1） 。A.分析单词是怎样构成的B.分析单词串是如何构成语句和说明的C.分析语句和说明是如何构成程序的D.分析程序的结构B C D11、与编译程序相比，解释程序通常缺少（1），同时，解释程序（2），它处理语言时采用的方法是（3）。（1）A.中间代码生成 B.目标代码生成C.词法分析D.语法分析 E.代码优化（2）A.比较简单，可以移植性好，执行速度快B.比较复杂，可以移植性好，执行速度快C.比较简单，可以移植性差，执行速度慢D.比较简单，可以移植性好，执行速度慢（3）A. 源程序语句被直接解释执行B. 将源程序逐句转化成中间代码，解释执行C. 先将源程序解释转化为目标代码，再执行D. 以上方法都行（1）B E (2) D (3) B编译与解释的根本区别：是否生成目标代码工作模式是一个个获取、分析并执行源程序12、判断：“含有代码优化的编译器的执行效率高”。错。含有代码优化的编译器，其优化是指对生成的目标代码进行了优化，而不是编译器本身得到了优化，所以，它提高的是目标代码的执行效率，而不是编译器本身的执行效率。13. 判断：“解释方式与编译方式的区别在于解释程序对源程序没有真正进行翻译”。错。编译方式和解释方式实际上都进行的翻译，只是编译相当于笔译，而解释相当于口译。解释方式下，不将于源程序彻底翻译成目标代码，而是每读入一条语句，将其翻译成中间代码，解释其含义并执行，然后再读入下一条语句，再翻译执行。编译方式和解释方式的根本区别在于“是否生成了目标代码”。1. 编译程序有哪些主要构成成分？各自的主要功能是什么？a) 词法分析：从左到右读入源程序的每个字符，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词b) 语法分析：在词法分析的基础上，将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等。c) 语义分析：在词法分析的基础上，将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等。d) 中间代码生成：在词法分析的基础上，将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等。e) 代码优化：对中间代码进行变换或改造，使之更为高效（时间、空间）。f) 目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的机器指令代码或汇编指令代码。g) 表格管理：用于保存源程序的各种信息。因为上述各阶段工作均需要查找、更新、构造表格。h) 出错处理: 报告源程序中错误的性质、地点，将错误所造成的影响限制在尽可能小的范围。有些编译程序还可以自动纠错。2. 什么是解释程序？它与编译程序的主要不同是什么？解释方式下，不将于源程序彻底翻译成目标代码，而是每读入一条语句，将其翻译成中间代码，解释其含义并执行，然后再读入下一条语句，再翻译执行。编译方式和解释方式的根本区别在于“是否生成了目标代码”。3. 对下列错误信息，请指出可能是编译的哪个阶段报告的？ （1）else没有匹配的if; 语法分析 （2）数组下标越界； 语义分析 （3）使用的函数没有定义； 语法分析（4）在数中出现非数字字符。 词法分析第2章 文法和语言（小结）重点掌握：通过文法，得到语言 通过语言，得到文法1. 符号和符号串相关概念(1) 字母表(2) 符号串长度、头、尾、固有头、固有尾、连接、幂集合、集合的乘积、集合的闭包、正闭包2. 文法和语言(1) 规则、文法(2) 推导、句子、句型(3) 语言：一切句子的集合(4) 文法语言 语言文法(5) 文法的等价性3. Chomsky文法的类型0型短语文法, 对产生式没有任何限制1型上下文有关文法2型上下文无关文法3型正规文法、正则文法 （左线性、右线性）最右推导被称为规范推导,由规范推导所得的句型称为规范句型4. 上下文无关文法及其语法树(1) 语法树的构造(2) 推导过程：最左推导、最右推导(3) 文法二义性：一个句子对应两个或以上语法树5. 句型的分析(1) 自上而下(2) 自下而上(3) 短语、直接短语、句柄6. 有关文法实际应用的一些说明a) 文法中不得含有“有害规则”， 引起文法二义性的规则。如AAb) 文法中不得含有“多余规则”文法中任何句子的推导都用不到的规则。i. 规则中有不可到达的VNii. 规则中有不可终止的VNc) 不含“左递归”规则（如：AA）d) 不含“空规则”（A）第2章 练习1. “符号就是字符”，这种说法正确吗？ A.正确 B.不正确B2. 文法GS：SA0 SB1 AS1 A1 BS0 B0 该文法是Chomsky 型文法，该文法所描述的所有只含四个符号的句子是 。(1) 3 (2)1010，0110，1001，01013. 文法GS：Sb|bBBbS 该文法所描述的语言是 A. L(G)=bi|i0 B. L(G)=b2i|i0C. L(G)=b2i+1|i0 D. L(G)=b2i+1|i1C4. 一个语言的文法是 ？A.唯一的 B.不唯一 C.个数有限的B5. 已知语言L=a2nbbn|n=1，写出对应文法。答案：SaaAb AaaAb|b6. 文法GE: EE+T|TTT*F|FF(E)|a写出该文法句型 E+F*(E+T)的短语、直接短语和句柄。a) 一个句型的语法树中 任一 子树 （所有）叶结点所组成的符号串都是该句型的短语b) 如果子树中不再包含其他更小的子树，即A只能推导出b，而b不能再推出其他的式子，则b为此句型的直接短语c) 直接短语中的最左直接短语为该句型的句柄。d) 短语没有要求是终结符短语 E+T、F*(E+T)、E+F*(E+T)、F直接短语 F、E+T句柄 F7. 文法GS：SAAB|if A then A else ABC|B+C|+CCD|C*D|*DDx|(A)|-D 哪些是终结符，哪些是非终结符？a) 终结符，通俗的说就是不能单独出现在推导式左边的符号，也就是说终结符不能再进行推导。不是终结符的都是非终结符。b) 非终结符可理解为一个可拆分元素，而终结符是不可拆分的最小元素。开始符：S非终结符：VN=S、A、B、C、D终结符：VT= if 、then 、else 、+、*、x 、( 、) 、-8. 正则文法能产生下面的语言: L=anbn|n=1A.存在一个B.不存在 C.无法判别B正则文法：左线性或右线性9. 文法GS：Sa|(T)|TT,S|S请给出句子(a,(a,a)的最左、最右推导。最左推导S = (T) = (T,S) = (S,S) = (a,S) = (a,(T) = (a,(T,S) = (a,(S,S) = (a,(a,S) = (a,(a,a)第2章 PPT习题独自增长型：卷心菜型例9 LG= an bn | n 0 求对应文法答案：SaSb 或AaB | ab SabBAb例10 LG= an bn | n 0 求对应文法答案：SaSb 或AaB | S BAb练习： LG= an b2n | n 0 求对应文法。答案：S-aSbb S-abb例11 LG= an b bn | n 0 求对应文法（独心卷心菜）答案：SaAbAaAbAb例12 LG= am bn | n=m=1 求对应文法(混合卷心菜)答案：SaAbAaAb AAbA例13 文法GS:SAB 求对应的语言。AaAb| abBBc |答案：LG= ambmcn | m0, n =0 句型 i*i+i 的两个不同的最左推导：推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导2：E E*E i*E i*E+E i*i+E i*i+i 例14：将 二义文法 改造为 无二义文法 GE: E i GE：E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 或规定优先顺序和结合律例15GE：EE+T|T TT*F|F F(E)|i求句型i*i+i的 短语、直接短语、句柄短语 i1*i2+i3、i1*i2、i1、i2、i3直接短语 i1、i2、i3 句柄i1第2章 课后习题解析习题 1、5、8、9、10、11、 12、13、1812. 构造产生如下语言的上下文无关文法(1) anbn | n0G: SaSb S(2) ambn | mn0G: SaSb SaS S(3) ab | ,a,b* |=|G: STb TaTa TbTb TaTb TbTa Ta(4) anbm | n2m0G: SaaSb SaS S(6) R | a,b* R表示反向串G: SaSa SbSb S习题解析13. 构造产生如下语言的上下文无关文法(1) anbmc2m | n,m0G: SAB AaA A BbBcc B (2) cR | a,b*G: SaSa SbSb Sc(3) ambnck | m=n 或 n=k, m,n,k0G: SAC | BD AaAb A CcC C BaB B DbDc D(4) ambnck | m=k 或 n=k, m,n,k0G: SA|B AaAc AK KbK K BaB BC CbCc C18. 写出下列语言的三型文法(1)an | n0 AaAA(2)an bm | n,m1AaAAaBBbBBb(3) anbmcm | n 0 AaAABBbBBCCcCC第3章 词法分析1. 基本概念 单词符号的类型（5种）一般可分为下列五种：标识符：各种名称，如常量名、变量名、过程名常数：25, 3.1415, TRUE, “ABC”等关键字(保留字)：begin, end, if, while运算符：如 + - * / =等界符：逗号，分号，括号等 词法分析：逐个读入源程序字符，输出“单词符号” ，供语法分析使用。主要任务：读取源程序，输出单词符号 词法分析的输出形式：二元式（单词种类，单词自身的值） 词法分析与语法分析的接口形式（2种）方式一（常用）优点：（1）整个编译结构简洁、清晰、条理化（2）可移植性好方式二（PL/0采用）：2. 单词的描述工具和识别工具 正规文法、正规式、有穷自动机（NFA、DFA） 正规式的代数规律（5条）3. 转换规则例：正规式 r = 0(0|1)* ，将正规式正规文法。 练习：r = (01|10)*(0|1)例：正规文法GS:SaA ，将正规文法正规式。SaAaAAdAAaAd参见P50 图3.6 构造NFA对应的子集步骤二：0，1，2，3，4Ia：1，1，1，1，1Ib：2，3，2，4，1（1）将M的状态分成两个子集：终态集、非终态集40,1,2,3（2）对于子集0,1,2,3读入a1,1,1,1到达了等价状态，不用分割读入b2,3,2,4到达了不等价状态，需要分割则新的划分:40,1,23（3）对于子集0,1,2读入a1,1,1到达了等价状态，不用分割读入b2,3,2到达了不等价状态，需要分割则新的划分:40,213（4）对于子集0,2读入a1,1到达了等价状态，不用分割读入b2,2到达了等价状态，不用分割最终得到：T1=0,2T2=1T3=3T4=4abT1T2T1T2T2T3T3T2T4T4T2T2举例：求FA所对应的正规式RR=(a|b)* (aa |bb)(a|b)*举例：为 R=(a|b)*abb 构造NFA N，使得L(N)=L(R)。举例：求与文法GS等价的 NFA MGS：SaASbBSAaBAbABaSBbAB举例：求与文法GS等价的 DFA，并给出该文法的语言的正规式。GS：SAaSAAaASbAa第3章 习题解析课后习题：81. 为正规式构造DFA： (3)a(a|b)*|ab*a)*b子集法：T0= _closure(1)=1T1= _closure(move(T0, a)=2 _closure(move(T0, b)=FT2= _closure(move(T1, a)=2, 3T3= _closure(move(T1, b)=2, 4 _closure(move(T2, a)=2, 3=T2T4= _closure(move(T2, b)=2, 3, 4 _closure(move(T3, a)=2, 3=T2 _closure(move(T3, b)=2, 4=T3 _closure(move(T4, a)=2, 3=T2 _closure(move(T4, b)=2, 3, 4=T4 2. 已知NFA=(x,y,z, 0,1, M, x, z)，其中：M(x, 0)=zM(y,0)=x, yM(z, 0)=x, zM(x, 1)=xM(y,1)=M(z,1)=y构造相应的DFA。最小化DFA：4. 图a 确定化和最小化5. 构造DFA和正规文法，接收=0,1上所有满足该条件的字符串：每个1都有0直接跟在右边。正规文法G： A0AA1BB0AA7. 构造文法GS的最小化DFAGS: SaASbQAaAAbBAbBbDBaQQaQQbDQbDbBDaAEaBEbFFbDFaEFb8. GS: S0AS1BA1SA1B0SB0 给出对应的正规式。 参考答案：(01 | 10)*(01 | 10) (01 | 10)(01 | 10)*9. 将DFA最小化，并用正规式描述它所识别的语言。正规式： b*a(da|c)*bb*10. 构造文法的有穷自动机，确定化。该自动机对应的语言是什么？ SA0 AA0 | S1 | 0左线性正规文法的转换规则： 增加一个初态结点，开始符号对应的结点作为终态 对形如 At 的规则，引一条从初始状态到A的弧，标记为t 对形如 ABt 的规则，引一条从B到A的弧，标记为t正规式： 00(10|0)*语言： 以00开头的0、1串，且每个1后紧随一个0。11. 证明下列正规式等价。（若它们的最小化DFA都相同，则等价。）(1) (a|b)*(2) (a*|b*)*(3) (|a)b*)*第4章 LL(1) 小结主要思想： 从文法开始符号出发，如何根据当前的单词符号，唯一地确定选用哪个产生式来替换相应的非终结符向下推导。 1.“能够使用自顶向下分析技术的文法必须是LL(1)文法。”LL(1)文法充要条件：对每个非终结符A的两个不同产生式 A 和 A，则Select(A) Select(A) = 2. LL(1)文法的判别(1) 求出能推导出的非终结符(2) 求First集(3) 求Follow集(4) 计算SELECT集 (5) 判别：左部相同的产生式，Select集两两相交为空。3. 非LL(1)文法到LL(1)文法的等价变换l 提取左公共因子的方法（显式、隐式）l 消除左递归的方法（消除直接左递归、消除间接左递归）4. 确定的自顶向下分析方法l 递归子程序法l 预测分析法 判定LL(1)文法 构造预测分析表 用预测分析程序分析5. 不确定的自顶向下分析方法l 带回溯的自顶向下分析第4章 ppt习题例5：设文法GS 为:SABSbCAAbBBaDCADCbDaSDc判断它是否是LL(1)文法。Select(SAB)Select(SbC)=b, Select(CAD)Select(Cb)=b,存在交集非空的SELECT集合，所以该文法不是LL(1)文法。提取左公共因子结论1：文法中不含左公共因子只是LL(1)文法的必要条件。即： LL(1)文法一定不含左公共因子 不含左公共因子的文法不一定是LL(1)文法提取隐含的左公共因子消除直接左递归消除间接左递归例11：消除文法GA 的一切左递归。SQc|cQRb|bRSa|a另解：终结符排序为：R,Q,S(1)对于R：无直接左递归（不用消除）(2)对于Q：右部含R开头的产生式:SQcQSabRSaScQabRaQb无直接左递归（不用消除）(3)对于S：右部不含R开头的产生式右部含Q开头的产生式SSabcQSabRSaSabcQabRaSbcQbSc消除直接左递归：S(abc | bc | c)SQSabRSaSabcS | QabRaQb(4) 考察是否有“无用产生式”：Q、R的产生式是无用产生式，删除！最终的产生式为：SabcSSbcSScSaSabcS S结论：由上述两种解法可以产生不同的产生式形式，但它们一定是等价文法。 例12：文法GE:EE+T|T构造预测分析表。TT*F|FFi|(E) 解：（1）消除左递归：VN排列为 E,T,F消除E一切直接左递归：ETETT*FFiE+TE| TFF(E)消除T的一切直接左递归：ETETFTFiE+TE| T*FT| F(E)F没有左递归。文法无左公共因子。所以，提取左公共因子和消除左递归后的文法为：ETETFTFiE+TE T*FT F(E)E T（2）判断改写后的文法是否为LL(1)文法：a) 可推导出的VN表： EETTF否是否是否a) 求First集：First(E)= i , ( First(E)= + , First(T)= i , ( First(T)= * , First(F)= i , ( First( TE )=First(T)= i , ( First( FT )=First(F)= i , ( b) 求Follow集：Follow(E)= # , ) Follow(E)=Follow(E)Follow(E) = # , )Follow(T)=(First(E)-) Follow(E)=+, #, )Follow(T)= Follow(T)Follow(T) = +, #, )Follow(F)=(First(T)-)Follow(T)Follow(T)= *, +, #, ) c) 求各产生式的SELECT集： SELECT(ETE) = First(TE) = i , ( SELECT(E+TE) = First(+TE) = + SELECT(E ) = Follow(E) = #,)SELECT(TFT) = First(FT) = i , ( SELECT(T*FT) = First(*FT) = * SELECT(T )= Follow(T)= +,#,)SELECT(F(E) ) = First(E) = ( SELECT(Fi) = First(i) = i d) 判定： SELECT(E+TE) SELECT(E ) = SELECT(T*FT) SELECT(T ) = SELECT(F(E) ) SELECT(Fi) = 所以该文法是LL(1)文法，可以使用预测分析法。e) 构造预测分析表的方法：对每个VT或“#”用符号a表示。若aSELECT（A），则把A放入MA,a中。（所有空白的MA,a表示出错。）f) 预测分析输入串#i+i*i#第4章 习题习题 P9913 并分析句子#befo#7 (3)-(5)消除左递归，提取左公共因子第5章 自底向上优先分析（小结）关键问题：l 在规范归约的过程中，如何确定“句柄”。l 在算符优先分析归约中，如何确定“最左素短语”。1. 简单优先分析 （规范归约） 优点：准确、规范 缺点：分析效率低，实际使用价值低 基本思想：按照一定原则，求出文法所有符号之间的优先关系，按照这种关系，确定归约过程中的句柄，之后进行归约。 优先关系的表示：ab 优先关系矩阵的构造： 对输入串的分析过程：归约2. 算符优先分析 优点：分析速度快，特别适用于表达式的分析 缺点：不规范，可能“错误的句子得到正确的归约” 基本思想：按照一定原则，求出文法所有终结符之间的优先关系，按照这种关系，确定归约过程中的最左素短语，之后进行归约。 优先关系的表示：ab 优先关系矩阵的构造：拓广文法S#S#;求FirstVT LastVT,寻找优先关系，构造优先关系表；判别。 对输入串的分析过程： 归约3. 优先函数 为什么要引入优先函数？ 为节约存储。l 优先矩阵占用内存空间：(n+1)2 / n:终结符个数； 1:“#”l 优先函数占用内存空间：2(n+1) 优先函数的定义：函数的值用整数表示，数值大小表示了优先关系的大小。 构造方法 缺点：出错时，不能准确指出出错的位置。 5.2 简单优先分析法n 主要思想：先按照一定原则，求出文法所有符号（VT和VN）之间的优先关系；再按照优先关系确定归约过程中的句柄。n 实现步骤：1. 拓广文法 S#S#2. 构造优先关系表3. 判断是否为简单优先文法4. 根据优先关系表分析句子5.3 算符优先分析法n 算符文法：上下文无关文法G中没有形如 ABC的产生式，其中B,CVN ，则称 G为算符文法（OG，Operator Grammer）。n 性质1：在算符文法中任何句型都不包含两个相邻的非终结符。n 性质2：如 Ab 或 bA 出现在算符文法的句型 g 中，其中 AVN, bVT, 则 g 中任何含 b 的短语必含有 A 。（但含A的短语未必含b。） 算符优先文法的定义n 设有一不含产生式的算符文法G，如果对任意两个终结符a和b之间至多只有 、 、 三种关系的一种成立，则称 G是一个算符优先文法（OPG , Operator Precedence Grammar）。n 不含空产生式n 任何产生式右部不包含两个相邻的非终结符n 任何两个终结符之间优先关系唯一n 算符优先文法是无二义的。n 归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单个非终结符的归约，所以用算符优先分析法的规约过程不是规范归约。n 为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念n 主要思想：对文法按照一定规则，求出VT之间的优先关系；再按照这种优先关系来确定句柄。n 实现步骤：1. 拓广文法 S#S#2. 构造算符优先关系表3. 判断是否为算符优先文法（OPG文法）4. 根据优先关系表分析句子n 优先函数为节约存储空间，用“优先函数”代替“优先关系表”算符优先关系的定义 a=b：存在产生式 ab或 aVN b ab：存在产生式 VN b，且VN能推导出a或VN能推导出aVNn 素短语设有文法GS，其句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。n 最左素短语：句型最左边的素短语。n 求素短语的方法：（1）画出句型对应的语法树（2）找出所有的短语（3）去掉所有不含VT的短语（4）去掉所有包含其他素短语的短语第5章 ppt习题例4 文法GE(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF(6) FP(7) P(E)(8) Pi构造算符优先关系表。构造优先分析法的步骤：1）计算每个VN的FirstVT集合和LastVT集合2）求优先关系 求 = 关系 求 关系：找aB，a 关系：找Bc，LastVT(B)c3）构造优先关系表例4 解：1）计算每个VN的FirstVT集合和LastVT集合FirstVT (E)= #FirstVT (E)= + ，* ，（ ，iFirstVT (T)= * ，（ ，i FirstVT (F)= ，（ ，iFirstVT (P)= （ ，iLastVT (E)= #LastVT (E)=+ ，* ，i，）LastVT (T)=*，i，）LastVT (F)= ，i，）LastVT (P)=，）2）求优先关系 求=关系：# = # ( = ) 求关系 逐条扫描产生式，寻找形如：AaB的产生式。由于 #E 故 # FirstVT (E)由于 +T 故+ FirstVT (T)由于 *F 故* FirstVT (F)由于 F 故 FirstVT (F)由于 (E 故( 关系 逐条扫描产生式，寻找形如：Ab的产生式。由于 E# 故LastVT (E) #由于 E+ 故LastVT (E) +由于 T* 故 LastVT (T) *由于 P故LastVT (P) 由于 E) 故 LastVT (E) )3）构造优先关系表利用上面的 = 关系可以构造相应的算符优先关系表 分析表分析句子 #i+i#例：文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF(6) FP(6) P(E)(7) Pi求句型 #T+T*F+i# 的素短语。短语：T+T*F+i、T+T*F、T、T*F、i素短语：T*F、i最左素短语：T*F第5章 习题P1211 (1)、(2)、(4) (a,a)#4 (1)、(2)、(3)a;(a+a)# 、(4)、(5)1.文法 Sa | | (T)TT,S | S(1) 计算FirstVT和LastVT。(2) 构造算符优先关系表，并说明该文法是否为算符优先文法。(4) 给出输入串(a,a)#的算符优先分析过程。判别：该文法(1)不含空产生式; (2)任何产生式右部不包含两个相邻的非终结符; (3)任何两个终结符之间优先关系唯一。 故该文法是算符优先文法。(4) 给出输入串(a,a)#的算符优先分析过程。4.文法 SS;GSGGG(T)GHHaH(S)TT+STS(1) 构造算符优先关系表，并判别该文法是否为算符优先文法。(2) 给出a(T+S);H;(S)的短语、句柄、素短语和最左素短语。(3) 给出a;(a+a)的算符优先分析过程。(4) 给出a;(a+a)的最右推导。(5) 说明算符优先分析的哪些缺点。(1) 拓广文法S#S# SS;GSGGG(T)GHHaH(S)TT+STS(2) 给出a(T+S);H;(S)的短语、句柄、素短语和 最左素短语。短语： a(T+S);H;(S)a(T+S);H(S)a(T+S)HaT+S直接短语： a T+S H (S)句柄： a素短语： (S) a T+S最左素短语： a(4) 最右推导 S= S;G= S;G(T)= S;G(T+S)= S;G(T+G)= S;G(T+H)= S;G(T+a)= S;G(S+a)= S;G(G+a)= S;G(H+a)= S;G(a+a)= S;H(a+a)= 无法继续(5) 说明：算符优先分析可能将错误的句子 得到正确的归约。第6章 LR分析 小结 LR(0)1. 拓广文法： SS2. 构造LR(0)项目集规范族3. 判断： 不存在“移进-归约冲突”和“归约-归约冲突”4. 构造识别活前缀的DFA(1) 构造状态结点和弧(2) 确定“句子识别态”和“句柄识别态”1. 构造LR(0)分析表(1) 根据DFA标记为非终结符的弧，构造GOTO表(2) 根据DFA标记为终结符的弧，构造ACTION表的Si(3) 根据DFA的句柄识别态，构造ACTION表的ri(4) 根据DFA的句子识别态，构造ACTION表的acc1. 分析句子 LR分析器的组成 LR分析器的工作过程：状态栈顶 与 当前输入符号 查Action表1）遇到 Si：表示“移进”，并转向下一个状态。 状态栈：i入栈 符号栈：当前输入符号入栈2）遇到 ri：表示使用第i个产生式“归约”。 k：所用产生式的右部长度 状态栈：弹出k个状态，栈顶状态 与 所用产生式的左部 查GOTO表并将相应的状态入栈。 符号栈：弹出k个符号，并将所用产生式的左部入栈。3）遇到 acc：表示接受该输入串。4）遇到 空白：表示出错 SLR(1)1. 拓广文法： SS2. 构造LR(0)项目集规范族3. 判断： Follow(归约项目的左部)移进项目的待移进符号= Follow(归约项目i的左部)Follow(归约项目j的左部) = 4. 构造识别活前缀的DFA(1) 构造状态结点和弧(2) 确定“句子识别态”和“句柄识别态”1. 构造LR(0)分析表(1) 根据DFA标记为非终结符的弧，构造GOTO表(2) 根据DFA标记为终结符的弧，构造ACTION表的Si(3) 根据DFA的句柄识别态，只对Follow(归约项目左部)的符号，构造ACTION表的ri(4) 根据DFA的句子识别态，构造ACTION表的acc1. 分析句子 同LR(0) LR(1)1. 拓广文法： SS2. 构造LR(1)项目集规范族 (有向前搜索符)3. 判断： 归约项目的向前搜索符 移进项目的待移进符号= 归约项目i的向前搜索符 归约项目j的向前搜索符 = 4. 构造识别活前缀的DFA(1) 构造状态结点和弧(2) 确定“句子识别态”和“句柄识别态”1. 构造LR(0)分析表(1) 根据DFA标记为非终结符的弧，构造GOTO表(2) 根据DFA标记为终结符的弧，构造ACTION表的Si(3) 根据DFA的句柄识别态，只对归约项目的向前搜索符，构造ACTION表的ri(4) 根据DFA的句子识别态，构造ACTION表的acc1. 分析句子 同LR(0) LALR(1)1. 拓广文法同LR(1)2. 构造LR(1)项目集规范族同LR(1)3. 判断同LR(1)4. 合并同心集5. 构造识别活前缀的DFA同LR(1)6. 构造LR(0)分析表同LR(1)7. 分析句子 同LR(0) LR分析法 自底向上分析法，即移进-归约的过程 为什么提出LR分析法比LL(k)和优先分析法 对文法的限制少 速度快 能够准确、及时地指出出错位置 缺点：构造文法分析器的工作量大LR分析器n LR(0)：无需向右查看输入符号（不适于高级语言）改进：SLR(1)n LR(1)：向右查看一个输入符号（适于高级语言）改进：LALR(1)构造识别活前缀的有穷自动机（项目集规范族法）1、概念n 核：圆点不在产生式最左边的项目，称为核。特例：SS也是核。n 闭包：CLOSURE(J)a) J的项目均在CLOSURE(J)中b) 若 AaBb 属于CLOSURE(J)，则每一形如 Bg 的项目也属于 CLOSURE(J)c) 重复b)直到 CLOSURE(J)不再扩大对核求闭包就构成了新状态的项目集。n 转换函数：GO（I，X）GO（I，X）= CLOSURE（J）其中：I为包含某一项目集的状态，X为一文法符号 J= 任何形如 AaXb 的项目，AaXb 属于I 2、利用闭包和转换函数构造文法的LR(