编译原理复习(有答案)

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.acbbc B.abbcac C.abc D.acc 例：(a|b)a+(ba)* 与后面的那些串匹配? ADE A.ba B.bba C.ababa D.aa E.baa 文法的定义四元组表示文法G定义为四元组VN，VT，P，SVN ：非终结符集VT ：终结符集P：产生式规那么集合S：开始符号或识别符号例：给定文法，A:= bA | cc，下面哪些符号串可由其推

3、导出 。 cc b*cc b*cbcc bccbcc bbbcc 什么是推导 例：文法G： E->E+T|E-T|T T->T*F|T/F|F F->(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+il 句型、句子的概念例：假设G一个文法，S是文法的开始符号，如果S=>*x，那么称x是 句型 。例：对于文法G，仅含终结符号的句型称为 句子 。l 语言的形式定义例：设r=(a|b|c)(x|y|z)，那么L(r)中

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

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

6、式运算符a 表达式* a 表达式运算符表达式* a 表达式运算符a * a 表达式+ a * a a + a * a最右推导2 表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符 a 表达式运算符表达式 * a 表达式运算符a * a 表达式+ a * a a + a * al 短语、句柄、直接短语例：令文法GE为: E->E+T|E-T T->T*F|T/F|F F->(E)|i 证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。例：文法GS SaB|bA Aa|aS|bAA BaBB|bS|b 句型aabbAb的句柄是 D

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

8、174;y 转换成： A=xy A®xA½y 转换成： A=x*y A®x, A®y 转换成： A=x½y 例：给出下述文法所对应的正规式： S0A|1B A1S|1 B0S|0答： S->0A | 1B->01S | 01 | 10S | 10->(01|10)S | (01|10)-> (01|10) (01|10)* 即：r= (01|10) (01|10)*l NFA和DFA l NFA和DFA 的组成例：指出哪些串是自动机可接受的 xy xyxxy yyyx xyyxyxyxxy l NFA和DFA的相互转换例

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

10、五章 自顶向下语法分析方法语法分析常用的方法是_B_。 自顶向下 自底向上 自左向右 自右向左A. B. C. D. l 会求FIRST、FOLLOW集计算FIRST(X)： (a) 假设XVT, 那么FIRST(X)X (b) 假设XVN, 且有产生式Xa, aVT, 那么 aFIRST(X) (c) 假设XVN, Xe, 那么eFIRST(X) (d) 假设XVN, Y1, Y2, , YiVN, 且有产生式XY1Y2Yn; 当Y1Y2Yi-1都e时,(其中1in), 那么FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)的所有非e元素和FIRST(Yi)都包含在FIRST(X

11、)中 (e) 当(d)中所有Yi e, (i=1, 2, n), 那么FIRST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn)e 计算FOLLOW(A)： (a) 设S为文法中开始符号，把#参加FOLLOW(S)中(这里“#为句子括号)。 (b) 假设AaBb是一个产生式，那么把FIRST(b)的非空元素参加FOLLOW(B)中。 如果b e那么把FOLLOW(A)也参加FOLLOW(B)中。计算SELECT(A->a)：Aa, AVN, aV*, 假设a e,那么SELECT(Aa)=FIRST(a)假设ae ，那么SELECT(Aa)=(FIRST(a)-e)FOLL

12、OW(A)例：文法：SiCtS|iCtSeS|a，Cb中first(S)为 A ，follow(S)为 B 。 A. i,a； B. e,#； C. i,e,#； D. e,b l LL(1)文法的条件例：LL(1)文法的条件是_C_。A. 对形如U:=x1 | x2 | | xn 的规那么，要求First(xi) First(xj)=F,(ij);B. 对形如 U:=x1 | x2 | | xn 的规那么，假设xi=>*e, 那么要求First(xj) Follow(U)=F,(ij)C. a 和 bD. 都不是l 构造LL(1)分析表例：已给文法 GS ： S SaP | Sf |

13、P P qbP | q 将 GS 改造成 LL(1)文法，并给出 LL(1)分析表。 答：改造后的文法：S PS'S' aPS'| fS' | eP qP'P' bP | e各候选式的 FIRST 集，各非终结符的 FOLLOW 集为.产生式SELECT集FOLLOW集SPS'q#S'aPS'a#fS'fe#PqP'qa,f,#P'bPba,f,#e a,f,#LL(1) 分析表为abfq#SPS'S'aPS'fS'ePqP'P'ebPee第六章 自底

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

15、符号l LR分析器的逻辑结构及活前缀等概念l LR分析对文法的要求l 构造LR(0)分析表、SLR(1)分析表l 用SLR分析法分析非二义性的文法和二义性的文法。例：文法AaAd|aAb|e 判断该文法是否是SLR(1)文法，假设是构造相应分析表，并对输入串ab#给出分析过程。答：文法： AaAd|aAb| 拓广文法为G，增加产生式SA假设产生式排序为：0 S' A 1 A aAd2 A aAb3 A 由产生式知： First (S' ) = ,aFirst (A ) = ,aFollow(S' ) = # Follow(A ) = d,b,#G的LR(0)工程集族及识别活前缀的DFA如下列图所示： 在I0中：A .aAd和A .aAb为移进工程，A .为归约工程，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I0、I2中：Follow(A) a= d，b，# a=所以在I0、I2中的移进-归约冲突可以由Foll