编译原理复习(有答案)

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，S）VN ：非终结符集VT ：终结符集P：产生式（规则）集合S：开始符号（或识别符号）例：给定文法，A:=

3、 bA | cc，下面哪些符号串可由其推导出（ ）。 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)中元素为 9 个。例：文法G产生式为SAB，AaAb|

4、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 表达式表达式运算符表达式表达式运算符a 表达式* a 表达式运算符表达式* a 表达式运算符a * a 表达式+ a * a a + a * a最右推导2 表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符 a 表达式运算符表达式

6、* 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 ）A.a B.ab C.b D.bA 第四章 词法分析l 词法输出的token表示法 l 词法记号、模式、词法单元的概念 l 词法输出的token表示 ：二元式表示（单词种别，单词自身的值）例：扫描器的任务是从 源程序 中识别出一个个 单词 。l 正

7、规式的概念及其代数性质词法分析中的单词符号的描述工具正规式代表的集合例：请描述下面正规式定义的串，字母表S = 0, 1。1(0|1)*0答：必须以1开头0结尾的串例：为下边所描述的串写正规式，字母表是 0, 1。以01 结尾的所有串答：(0|1)*01l 正规文法和正规式相互转换正规文法到正规式的转换规则：正规文法 正规式AxB, By 转换成： A=xy AxAy 转换成： A=x*y Ax, Ay 转换成： A=xy 例：给出下述文法所对应的正规式： S0A|1B A1S|1 B0S|0答： S-0A | 1B-01S | 01 | 10S | 10-(01|10)S | (01|10)

8、- (01|10) (01|10)* 即：r= (01|10) (01|10)*l NFA和DFA l NFA和DFA 的组成例：指出哪些串是自动机可接受的 （）xy xyxxy yyyx xyyxyxyxxy l NFA和DFA的相互转换例：将下图确定化：答：用子集法将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：用

9、子集法将NFA确定化 .01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。.01X.AAABBCBCADDCBDFA的状态图：:第五章 自顶向下语法分析方法语法分析常用的方法是_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

10、, Y1, Y2, , YiVN, 且有产生式XY1Y2Yn; 当Y1Y2Yi-1都e时,(其中1in), 则FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)的所有非e元素和FIRST(Yi)都包含在FIRST(X)中 (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

11、(A)也加入FOLLOW(B)中。计算SELECT(A-a)：Aa, AVN, aV*, 若a e,则SELECT(Aa)=FIRST(a)若ae ，则SELECT(Aa)=(FIRST(a)-e)FOLLOW(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

12、| | xn 的规则，若xi=*e, 则要求First(xj) Follow(U)=F,(ij)C. a 和 bD. 都不是l 构造LL(1)分析表例：已给文法 GS ： S SaP | Sf | P P qbP | q 将 GS 改造成 LL(1)文法，并给出 LL(1)分析表。 答：改造后的文法：S PSS aPS| fS | eP qPP bP | e各候选式的 FIRST 集，各非终结符的 FOLLOW 集为.产生式SELECT集FOLLOW集SPSq#SaPSa#fSfe#PqPqa,f,#PbPba,f,#e a,f,#LL(1) 分析表为abfq#SPSSaPSfSePqPPeb

13、Pee第六章 自底向上优先分析l 算符文法的定义如果不含空产生式的上下文无关文法 G 中没有形如 ABC的产生式，其中B, CVN，则称G 为算符文法（OG）。l 最左素短语的概念设有文法GS，其句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语例：给定文法G如下：EE+T|T；TT*F|F； FPF|P；P（E）|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 向右顺序

14、查看输入串的K个符号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中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文