《【精选】编译原理复习(有答案)》由会员分享，可在线阅读，更多相关《【精选】编译原理复习(有答案)（6页珍藏版）》请在金锄头文库上搜索。
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 定义为四元组（V N，V T，P，S）VN ：非终结符集VT ：终结符集P：产生式（规则）集合S：开始符号（或识别符号）例
3、：给定文法，A:= 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+i 句型、句子的概念例：假设 G 一个文法，S 是文法的开始符号，如果 S=*x，则称 x 是 句型 。例：对于文法 G，仅含终结符号的句型称为 句子 。 语言的形式定义例：设 r=(a|b|c)(x|y|z)，则 L(r)中元素为 9 个。
4、例：文法 G 产生式为SAB，AaAb|，BcBd|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，Cd 是几型文法？3型 最左（右）推导规范推
5、导 ：最右推导被称为规范推导规范句型 ：由规范推导所得的句型称为规范句型规范归约:左归约为规范归约 二义性例：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 二义的 。例：已知文法 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 表达式表达式 运算
6、符 表达式表达式 运算符 表达式 运算符 表达式表达式 运算符 表达式 运算符 a 表达式 运算符 表达式 * a 表达式 运算符a * a 表达式+ a * aa + a * a 短语、句柄、直接短语例：令文法 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 第四章 词法分析 词法输出的 token 表示法 词法记号、模式、词法单元的概念 词法输出的
7、token 表示 ：二元式表示（单词种别，单词自身的值）例：扫描器的任务是从 源程序 中识别出一个个 单词 。 正规式的概念及其代数性质词法分析中的单词符号的描述工具正规式代表的集合例：请描述下面正规式定义的串，字母表 S = 0, 1。1(0|1)*0答：必须以 1 开头 0 结尾的串例：为下边所描述的串写正规式，字母表是 0, 1。以 01 结尾的所有串答：(0|1)*01 正规文法和正规式相互转换正规文法到正规式的转换规则：正规文法 正规式AxB, By 转换成： A=xy AxAy 转换成： A=xy Ax, Ay 转换成： A=xy 例：给出下述文法所对应的正规式： S0A|1BA1
8、S|1 B0S|0答： S-0A | 1B-01S | 01 | 10S | 10-(01|10)S | (01|10)- (01|10) (01|10)* 即：r= (01|10) (01|10)* NFA 和 DFA NFA 和 DFA 的组成例：指出哪些串是自动机可接受的 （）xy xyxxy yyyx xyyxyxyxxy NFA 和 DFA 的相互转换例：将下图确定化：答：用子集法将 NFA 确定化：. 0 1S VQ QUVQ VZ QUQU V QUZVZ Z ZV Z .QUZ VZ QUZZ Z Z重新命名状态子集，令 VQ 为 A、QU 为 B、VZ为 C、V 为 D、QU
9、Z 为 E、Z 为 F。. 0 1S A BA C BB D EC F FD F .E C EF F FDFA 的状态图： 正规式与 NFA 的相互转换例：构造正规式 1(0|1)*101 相应的 DFA 答：先构造 NFA：用子集法将 NFA 确定化 . 0 1X . AA A ABAB AC ABAC A ABYABY AC AB除 X，A 外，重新命名其他状态，令 AB 为B、AC 为 C、ABY 为 D，因为 D 含有 Y（NFA的终态），所以 D 为终态。. 0 1X . AA A BB C BC A DD C BDFA 的状态图：:第五章 自顶向下语法分析方法语法分析常用的方法是_
10、B _。 自顶向下 自底向上 自左向右 自右向左A. B. C. D. 会求 FIRST、 FOLLOW 集计算 FIRST(X)：(a) 若 XV T, 则 FIRST(X)X(b) 若 XV N, 且有产生式 Xa, aV T, 则 aFIRST(X)(c) 若 XV N, X, 则 FIRST(X)(d) 若 XV N, Y1, Y2, , YiV N, 且有产生式 XY1Y2Yn; 当 Y1Y2Yi-1 都 时,(其中 1in), 则 FIRST(Y1)、FIRST(Y 2)、FIRST(Y i-1)的所有非元素和FIRST(Yi)都包含在 FIRST(X)中(e) 当(d) 中所有
11、Yi , (i=1, 2, n), 则FIRST(X)=FIRST(Y1)FIRST(Y2) FIRST(Yn) 计算 FOLLOW(A)：(a) 设 S 为文法中开始符号，把# 加入FOLLOW(S)中(这里 “#”为句子括号)。(b) 若 AB 是一个产生式，则把FIRST()的非空元素加入 FOLLOW(B)中。如果 则把 FOLLOW(A)也加入FOLLOW(B)中。计算 SELECT(A-)：A, AV N, V *, 若 ,则 SELECT(A)=FIRST()若 ，则 SELECT(A)=(FIRST()-)FOLLOW(A)例：文法：SiCtS|iCtSeS|a ，Cb 中fi
12、rst(S)为（ A ） ， follow(S)为（ B ） 。A. i,a； B. e,#； C. i,e,#； D. e,b LL(1)文法的条件例：LL(1) 文法的条件是 _C_。A. 对形如 U:=x1 | x2 | | xn 的规则，要求 First(xi) First(xj)=,(ij);B. 对形如 U:=x1 | x2 | | xn 的规则，若 xi=*, 则要求 First(xj) Follow(U)=,(ij)C. a 和 bD. 都不是 构造 LL(1)分析表例：已给文法 GS ： S SaP | Sf | P P qbP | q 将 GS 改造成 LL(1)文法，并给
13、出 LL(1)分析表。 答：改造后的文法：S PSS aPS| fS | P qPP bP | 各候选式的 FIRST 集，各非终结符的 FOLLOW 集为.产生式SELECT集FOLLOW集SPS q #SaPS a #fS f#PqP q a,f,#PbP b a,f,# a,f,#LL(1) 分析表为a b f q #S PSS aPS fS P qPP bP 第六章 自底向上优先分析 算符文法的定义如果不含空产生式的上下文无关文法 G 中没有形如 ABC的产生式，其中 B, CV N，则称 G 为算符文法（OG） 。 最左素短语的概念设有文法 GS，其句型的素短语是一个短语，它至少包含
14、一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语例：给定文法 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 分析 LR(K)的含义 L 从左至右扫描输入符号串 R 构造一个最右推导的逆过程 K 向右顺序查看输入串的 K 个符号 LR 分析器的逻辑结构及活前缀等概念 LR 分析对文法的要求 构造 LR(0)分析表、SLR(1)分析表 用 SLR 分析法分析非二义性的文法和二义性的文法。例：已知文法AaAd|aAb| 判断该文法是否是 SLR(1)文法，若是构造相应分析表，并对输入串 ab#给出分析过程。答：文法： AaAd|aAb| 拓广文法为 G，增加产生式 SA若产生式排序为：0 S A 1 A aAd2 A aAb3 A
