第一章引论 1.
编译过程的阶段
由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段 2. 编译程序的概念 3.
编译程序的结构
例：（B）不是编译程序的组成部分。 A. 词法分析器；B. 设备管理程序 C. 语法分析程序；D. 代码生成程序 4.
遍的概念
对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 5.
编译程序与解释程序的区别
例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（D）。
A. 单用户与多用户的差别B. 对用户程序的差错能力
C. 机器执行效率D. 是否生成目标代码 第三章文法和语言 文法的概念
字母表、符号串和集合的概念及运算 例：(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::= 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个。
例：文法G产生式为S→AB，A→aAb|?，B→cBd|cd，则B∈L(G)。
A. ababcd；B. ccdd；C. ab；D. aabb
? 等价文法
例：如果两个文法描述了同一个语言，则这两个文法是等价文法。 ? 文法的类型
0型：左边至少有一个非终结符 1型：右边长度>=左边长度 2型：左边有且仅有一个非终结符 3型：形如：A->aB,A->a 各类型文法都是逐级包含关系，
例：文法S→abC|c，bC→d是几型文法？0型
例：文法S→abC，bC→ad是几型文法？1型
例：文法G[A]：A→?，A→aB，B→Ab，B→a是几型文法？2型
例：文法S→a|bC，C→d是几型文法？3型
? 最左（右）推导
规范推导：最右推导被称为规范推导
规范句型：由规范推导所得的句型称为规范句型 规范归约:左归约为规范归约 ? 二义性
例：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
例：已知文法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 〈表达式〉〈运算符〉〈表达式〉 * a 〈表达式〉〈运算符〉a * a 〈表达式〉+ a * a a + a * a
? 短语、句柄、直接短语 例：令文法G[E]为:
E->E+T|E-T T->T*F|T/F|F F->(E)|i
证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。
例：已知文法G[S]
S→aB|bA A→a|aS|bAA B→aBB|bS|b
句型aabbAb的句柄是（D）
A.a B.ab C.b D.bA
第四章词法分析
? 词法输出的token表示法
? 词法记号、模式、词法单元的概念 ?
词法输出的token表示：二元式表示（单词种别，单词自身的值） 例：扫描器的任务是从源程序中识别出一个个单词。
? 正规式的概念及其代数性质 词法分析中的单词符号的描述工具 正规式代表的集合
例：请描述下面正规式定义的串，字母表S = {0, 1}。 1(0|1)*0
答：必须以1开头0结尾的串
例：为下边所描述的串写正规式，字母表是{0, 1}。 以01 结尾的所有串
答：(0|1)*01
? 正规文法和正规式相互转换
正规文法到正规式的转换规则： 正规文法正规式
A?xB, B?y 转换成： A=xy
A?xA?y 转换成： A=x?y
A?x, A?y 转换成： A=x?y
例：给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|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 1 S VQ QU VQ VZ QU QU V QUZ VZ Z Z V Z . QUZ VZ QUZ Z Z Z 重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。 . 0 1 S A B A C B B D E C F F D F . E C E F F F DFA的状态图：
? 正规式与NFA的相互转换
例：构造正规式1(0|1)*101相应的DFA
答：先构造NFA：
用子集法将NFA确定化 . 0 1 X . A A A AB AB AC AB AC A ABY ABY AC AB 除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。 . 0 1 X . A A A B B C B C A D D C B DFA的状态图：:
第五章自顶向下语法分析方法
语法分析常用的方法是__B___。
①自顶向下②自底向上③自左向右④自右向左
A.①②③④ B.①② C.③④ D.①②③
? 会求FIRST、FOLLOW集
计算FIRST(X)：
(a) 若X∈VT, 则FIRST(X)＝{X} (b) 若X∈VN, 且有产生式X→a…, a∈
VT, 则a∈FIRST(X)
(c) 若X∈VN, X→?, 则?∈FIRST(X) (d) 若X∈VN, Y1, Y2, …, Yi∈VN, 且有产生式X→Y1Y2…Yn; 当Y1Y2…Yi-1都
?
时,(其中1≤i≤n), 则FIRST(Y1)、
FIRST(Y2)、…、FIRST(Yi-1)的所有非{?}元素和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→?, A∈V*
N, ?∈V, 若??,则SELECT(A→?)=FIRST(?) 若?
?，则SELECT(A→?)=(FIRST(?)-{?})
∪FOLLOW(A)
例：文法：S→iCtS|iCtSeS|a，C→b中first(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)=?,(i≠j);
B. 对形如U::=x1 | x2 | … | xn 的规则，若
xi=>*?,
则
要
求
First(xj)∩
Follow(U)=?,(i≠j) C. a 和b D. 都不是
? 构造LL(1)分析表 例：已给文法G[S] ：
S → SaP | Sf | P P → qbP | q
将G[S] 改造成LL(1)文法，并给出LL(1)分析表。
答：改造后的文法：
S → PS' S' → aPS'| fS' | ? P → qP'
P' → bP | ?
各候选式的 FIRST 集，各非终结符的 FOLLOW 集
为 .产生SELECTFOLLOW式 集 集 S→PS' {q} {#} S'→aPS' {a} {#} →fS' {f} →? {#} P→qP' {q} {a,f,#} P'→{b} {a,f,#} bP →? { a,f,#} LL(1) 分析表为 a b f q # S PS' S' aPS' fS' ? P qP' P' ? bP ? ? 第六章自底向上优先分析 ? 算符文法的定义
如果不含空产生式的上下文无关文法G 中没有形如A?…BC…的产生式，其中B, C∈VN，则称G 为算符文法（OG）。
? 最左素短语的概念
设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语
例：给定文法G如下：E→E+T|T；T→T*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个符号
构造的SLR(1)分析表如下： 状态（State） Action Goto ? LR分析器的逻辑结构及活前缀等概念 ? LR分析对文法的要求
? 构造LR(0)分析表、SLR(1)分析表
? 用SLR分析法分析非二义性的文法和二义性
的文法。 例：已知文法 A→aAd|aAb|?
判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。 答：文法： A→aAd|aAb|ε
拓广文法为G′，增加产生式S′→A 若产生式排序为： 0 S' →A 1 A →aAd 2 A →aAb 3 A →ε 由产生式知： First (S' ) = {ε,a} First (A ) = {ε,a} Follow(S' ) = {#} Follow(A ) = {d,b,#}
G′的LR(0)项目集族及识别活前缀的DFA如下图所示：
0 0 2 a d A b # S2 r3 1 r3 r3 . 3 0 1 2 3 4 5 acc S2 r3 r3 r3 S4 S5 r1 r1 r1 r2 r2 r2 对输入串ab#的分析过程
状态栈文法（state 符号stack） 栈 剩余输入串 动作（input （action） left） 移进 # #a ab# 归约:A b# →ε b# 移进 # 归约 :A # →aAb acc 0 2 3 #aA 0 2 35 #aAb 0 1 #A 分析成功，说明输入串ab是文法的句子
在I0中：
A →.aAd和A →.aAb为移进项目，A →.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。 在I0、I2中：
Follow(A) ∩{a}= {d，b，#} ∩{a}=决，所以G是SLR(1)文法。
所以在I0、I2中的移进-归约冲突可以由Follow集解
