编译原理复习

1、第一章引论1. 编译过程的阶段由词法分析、 语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段2. 编译程序的概念3. 编译程序的结构例：（B） 不是编译程序的组成部分。A. 词法分析器；B. 设备管理程序C. 语法分析程序；D. 代码生成程序4. 遍的概念对源程序 ( 或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。5. 编译程序与解释程序的区别例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（D ）。A. 单用户与多用户的差别B. 对用户程序的差错能力C. 机器执行效率D. 是否生成目标代码第三章文法和语言文法的概念

2、字母表、符号串和集合的概念及运算例： (ab|b) *c 与下面的那些串匹配？（ACD ）A. ababbc； B. abab；C. c；D. babc； E. aaabc例： ab* c* (a|b)c 与后面的那些串匹配？（BC）A.acbbcB.abbcacC.abcD.acc例： (a|b)a +(ba) * 与后面的那些串匹配?（ ADE）A.baB.bbaC.ababaD.aaE.baa文法的定义（四元组表示）文法 G 定义为四元组（VN，VT， P，S）VN ：非终结符集VT ：终结符集P：产生式（规则）集合S：开始符号（或识别符号）例：给定文法，A:= bA | cc ，下面哪

3、些符号串可由其推导出（ ）。 ccb*ccb*cbcc bccbcc bbbcc什么是推导例：已知文法G：E->E+T|E-T|TT->T*F|T/F|FF->(E)|i试给出下述表达式的推导：i*i+i推导过程： E->E+T->T+T->T*F+T->F*F+T->i*F+T->i*i+T->i*i+F->i*i+i句型、句子的概念例：假设 G 一个文法， S 是文法的开始符号，如果 S=>*x，则称 x 是 句型 。例：对于文法 G，仅含终结符号的句型称为句子。语言的形式定义例：设r=(a|b|c)(x|y|z)，则

4、 L(r)中元素为9个。例：文法G 产生式为 SAB，AaAb|，B cBd|cd ，则B L(G)。A. ababcd； B. ccdd； C. ab；D.aabb等价文法例：如果两个文法描述了同一个语言，则这两个文法是等价文法。文法的类型0 型：左边至少有一个非终结符1 型：右边长度 >=左边长度2 型：左边有且仅有一个非终结符3 型：形如： A->aB,A->a各类型文法都是逐级包含关系，例：文法 SabC|c ，bCd是几型文法？ 0型例：文法 SabC，bCad 是几型文法？ 1型例：文法 GA：A ，AaB ，BAb，Ba是几型文法？ 2 型例：文法Sa|bC ，

5、 Cd 是几型文法？ 3型最左（右）推导规范推导：最右推导被称为规范推导规范句型 ：由规范推导所得的句型称为规范句型规范归约 :左归约为规范归约二义性例：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。例：已知文法G1 ： P->PaP|PbP|cP|Pe|f ， G1 是（ A ）。 A 二义文法； B 无二义的例：证明下述文法 G<表达式 >是二义的。<表达式 > a|(< 表达式 >)|< 表达式 ><运算符 ><表达式><运算符 > +|-|*|/答：可为句子a+a*a 构造两

6、个不同的最右推导:最右推导 1 表达式表达式运算符表达式表达式运算符 a表达式 * a表达式运算符表达式 * a表达式运算符 a * a表达式 + a * aa + a * a最右推导 2 表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符a表达式运算符表达式* a表达式运算符 a * a表达式 + a * aa + a * a短语、句柄、直接短语例：令文法GE为:E->E+T|E-TT->T*F|T/F|FF->(E)|i证明 E+T*F 是它的一个句型 ,指出这个句型的所有短语、直接短语和句柄。例：已知文法GSS aB|bAA a|aS|bAA

7、B aBB|bS|b句型 aabbAb 的句柄是（D ）A.aB.abC.bD.bA第四章词法分析词法输出的token 表示法词法记号、模式、词法单元的概念词法输出的token 表示：二元式表示（单词种别，单词自身的值）例：扫描器的任务是从源程序中识别出一个个单词。正规式的概念及其代数性质词法分析中的单词符号的描述工具正规式代表的集合例：请描述下面正规式定义的串，字母表 S = 0, 1。1(0|1)*0答：必须以1 开头 0 结尾的串例：为下边所描述的串写正规式，字母表是0, 1。以 01 结尾的所有串答： (0|1)*01正规文法和正规式相互转换正规文法到正规式的转换规则：正规文法正规式A

8、xB, By转换成：A=xyAxA y转换成：A=x yAx, Ay转换成：A=x y例：给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0答：S->0A | 1B->01S | 01 | 10S | 10->(01|10)S | (01|10)-> (01|10)(01|10)*即： r=(01|10) (01|10)*NFA和 DFANFA和 DFA 的组成例：指出哪些串是自动机可接受的（ ） xy xyxxy yyyxxyyxyxyxxyNFA和 DFA的相互转换例：将下图确定化：答：用子集法将NFA 确定化：.01S VQ QU VQ VZ QUQUV

9、QUZVZZZVZ.QUZ VZ QUZZZZ重新命名状态子集， 令 VQ 为 A 、QU 为 B、VZ 为C、V 为 D、QUZ 为 E、Z 为 F。.01SABACBBDECFFDF.ECEFFFDFA 的状态图：正规式与 NFA 的相互转换例：构造正规式 1(0|1)*101 相应的 DFA答：先构造NFA ：用子集法将NFA 确定化.01X.AA A AB AB AC AB AC A ABYABY ACAB除 X ，A 外，重新命名其他状态，令AB 为 B、AC为 C 、ABY 为 D ，因为 D 含有 Y（NFA 的终态），所以 D 为终态。.01X.AAABBCBCADDCBDFA

10、 的状态图： :第五章自顶向下语法分析方法语法分析常用的方法是_B_。 自顶向下自底向上自左向右 自右向左A. B. C. D. 会求 FIRST、 FOLLOW集计算 FIRST(X)：(a) 若 XVT, 则 FIRST(X) X(b) 若 XVN, 且有产生式 X a , aVT, 则 a FIRST(X)(c) 若 X VN, X , 则 FIRST(X)(d) 若 XVN, Y1, Y2, , Yi VN, 且有产生式XY1Y2 Yn; 当Y1 Y2 Yi-1 都时 ,( 其 中1i n), 则FIRST(Y1) 、FIRST(Y2)、 、 FIRST(Yi-1) 的所有非 元素和

11、FIRST(Yi)都包含在 FIRST(X)中(e) 当 (d)中所有Yi, (i=1, 2,n),则 FIRST(X)=FIRST(Y1) FIRST(Y2) FIRST(Yn) 计算 FOLLOW(A)：(a) 设 S 为文法中开始符号，把 #加入FOLLOW(S)中(这里 “ #为”句子括号 )。(b) 若 A B 是一个产生式，则把FIRST( )的非空元素加入FOLLOW(B)中。如果则把FOLLOW(A)也加入FOLLOW(B)中。计算 SELECT(A-> )：A, AVN,V*,若,则 SELECT(A )=FIRST( )P' bP |各候选式的FIRST 集，

12、各非终结符的FOLLOW 集为. 产SELECT FOLLOW生集集式Sq#PS'S'a#aPS'ffS' #Pqa,f,#qP'P'ba,f,#bP若，则 SELECT(A )=(FIRST( )- ) FOLLOW(A)例：文法：SiCtS|iCtSeS|a ，Cb中 first(S)为（A ）， follow(S)为（B ）。A. i,a；B. e,#；C. i,e,#；D. e,bLL(1)文法的条件例： LL(1)文法的条件是 _C_。A.对形如 U:=x1 | x2 |的xn规则，要求 First(xi) First(xj)=,(i

13、j);B.对形如U:=x1 | x2 | 的xn规则，若 xi=>* , 则 要 求 First(xj) Follow(U)=,(i j)C. a 和 bD. 都不是构造 LL(1)分析表例：已给文法GS ：S SaP | Sf | PP qbP | q将 GS 改造成 LL(1)文法，并给出 LL(1)分析表。答：改造后的文法：S PS'S' aPS'| fS' |P qP' a,f,#LL(1) 分析表为abfq#SPS'S'aPS'fS'PqP'P'bP第六章自底向上优先分析算符文法的定义如果不

14、含空产生式的上下文无关文法G中没有形如ABC 的产生式，其中 B, C VN，则称 G 为算符文法（ OG）。最左素短语的概念设有文法 GS，其句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语例：给定文法G 如下：EE+T|T；TT*F|F ；F P F|P； P（E） |i句型 P*P+i 的最左素短语为（A ）。A.P*P ；B.P；C. P+i；D. P*P+i第七章LR 分析LR(K)的含义L 从左至右扫描输入符号串R 构造一个最右推导的逆过程K 向右顺序查看输入串的 K 个符号LR 分析器的逻辑结构及活前缀等概念LR 分析

15、对文法的要求构造 LR(0)分析表、 SLR(1)分析表用 SLR分析法分析非二义性的文法和二义性的文法。例：已知文法A aAd|aAb|判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab# 给出分析过程。答：文法：AaAd|aAb| 拓广文法为G，增加产生式SA若产生式排序为：0S' A1A aAd2A aAb3A 由产生式知：First (S' ) = ,aFirst (A ) = ,aFollow(S' ) = #Follow(A ) = d,b,#决，所以 G 是 SLR(1)文法。构造的 SLR(1)分析表如下：状态（ State） Action GotoadAb#S2r31r3r3 .30acc1S2r32r3r33 S44 S55r1r1r1r2r2r2对输入串 ab# 的分析过程剩余输状态栈 文法入串动作（ state 符号（ input （action）stack）栈le