第五章语法分析—自下而上分析
本章要点
1. 自下而上语法分析法的基本概念：
2. 算符优先分析法；
3. LR分析法分析过程；
4. 语法分析器自动产生工具Y ACC；
5. LR分析过程中的出错处理。
本章目标
掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。
本章重点
1．自下而上语法分析的基本概念：归约、句柄、最左素短语；
2．算符优先分析方法：FirstVT, LastVT集的计算，算符优先表的构造，工作原理；3．LR分析器：
（1）LR(0)项目集族，LR(1)项目集簇；
（2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造；
（3）LR分析的基本原理，分析过程；
4．LR方法如何用于二义文法；
本章难点
1. 句柄的概念；
2. 算符优先分析法；
3. LR分析器基本；
作业题
一、单项选择题：
1. LR语法分析栈中存放的状态是识别________的DFA状态。
a. 前缀；
b. 可归前缀；
c. 项目；
d. 句柄；
2. 算符优先分析法每次都是对________进行归约：
(a)句柄（b）最左素短语(c)素短语(d)简单短语
3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。
a. LL(1)文法；
b.二义性文法；
c.算符优先文法；
d.SLR(1)文法；
4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LL(1)分析法属于自顶向下分析；
a. 深度分析法
b. 宽度优先分析法
c. 算符优先分析法
d. 递归下降子程序分析法
5. 自底向上语法分析采用分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。
a. 递归
b. 回溯
c. 枚举
d. 移进－归约
6. 一个LR(k)文法，无论k取多大，。
a. 都是无二义性的；
b. 都是二义性的；
c. 一部分是二义性的；
d. 无法判定二义性；
7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LR分析法属于自底向上分析。
a. 深度分析法
b. 宽度优先分析法
c. 算符优先分析法
d. 递归下降子程序分析法
8. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自顶向下分析试图为输入符号串构造一个；
a. 语法树
b. 有向无环图
c. 最左推导
d. 最右推导
9. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自底向上分析试图为输入符号串构造一个。
a. 语法树
b. 有向无环图
c. 最左推导
d. 最右推导
10. 采用自顶向下分析方法时，要求文法中不含有。
a. 右递归
b. 左递归
c. 直接右递归
d. 直接左递归
11. LR分析是寻找右句型的；而算符优先分析是寻找右句型的。
a. 短语；
b. 素短语；
c. 最左素短语；
d. 句柄
12. LR分析法中分析能力最强的是；分析能力最弱的是。
a. SLR(1)；
b. LR(0)；
c. LR(1)；
d. LALR(1)
13. 设有文法G：
T->T*F | F
F->F↑P | P
P->(T) | a
该文法句型T*P↑(T*F)的最左直接短语是下列符号串________。
a. (T*F)，
b. T*F，
c. P，
d. P↑(T*F)
14. 在通常的语法分析方法中，（）特别适用于表达式的分析。
a．算符优先分析法b．LR分析法c．递归下降分析法d．LL(1)分析法
15. .运算符的优先数之间有几种关系。
a.3种
b. 2种
c. 4种
d. 1种
16. 算符优先法属于（）
a.自上而下分析法
b.LR分析法
c.ＳLR分析法
d.自下而上分析法
17. 在LR分析法中，分析栈中存放的状态是识别规范句型的DFA状态。
a.句柄
b. 前缀
c. 活前缀
d. LR(0)项目
一．答案：
1. b；
2. b；
3. b；
4. d；
5. d；
6. a；
7. c；
8. c；
9. d；10. b；11. d，c；12. c，b；13. a；14. a 15. a；16. d；17. c；
二、填空题：
1. 规范归约的关键问题是________ 。
2. LR(k)分析法中，L 的含义是____________________，R 的含义是_______________________，k 的含义是 。
3. 移进一归约分析对符号串的使用有四类操作：移进、__________、_________和出错处理。
4. 设文法G （E 为其开始符号）产生式如下：
E→E+T|T
T→T*F|F
F→（E ）|i
则句型E+T*F+i 的句柄是_________________。
5. 自下而上分析方法的基本思想是：从输入符号串开始，利用文法规则逐步进行归约，直至归约到文法的 。
6. 在算符优先分析中，用 来刻画“可归约串”；在规范归约分析中，用 来刻画“可归约串”。
7. 在LR(0)分析中，相容的项目集，必须满足的条件是_______，_______。
8. LR 语法分析栈中存放的状态是识别_______的DFA 状态。
9. 在LR 分析过程中的任何时候，栈里的文法符号从下往上应该构成 ，把输入串的剩余部分配上之后应成为 。
10. 对于LR(0)分析法来说，项目A→β1?β2对活前缀αβ1是有效的，其条件是存在规范推导 。
11. 形式上我们说一个LR(1)项目[A→α?β，a]对于活前缀γ是有效的，如果存在规范推导 。
12. LR(k)分析方法中项目类型可分为四类 、 、 和 。
13. 所谓算符优先分析法就是仿照算术四则运算的运算过程设计的一种语法分析方法。它首先要规定 ，然后利用这种关系确定 ，并进行 。
14. 如图所示的语法树中，a ，b 不在同一句柄中， 先归约，所以 的优先级高于 。 P
b
R …… a … Q
15. 对于句型η的语法树，若它的一棵子树的根标记为A ，且将此子树的末端结点标记从左至右排列起来所形成的符号串为β，则β是 ；此时文法中必有推导 。
16. LR(0)每个项目中圆点的左部表示在分析过程中，要用该产生式归约时， ，右部表示 。
17. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别 的NFA 的一个状态。
二．答案：
1. 寻找或确定一个句型的句柄；
2. 从左到右扫描输入串，构造一个最右推导的逆过程；
3. 归约，接受；
4. T*F ；
5. 开始符号；
6. 最左素短语，句柄；
7. 移进项目和归约项目并存，多个归约项目并存；
8. 文法活前缀和可归前缀；
9. 活前缀，规范句型；10. ωβαβωα21*'R R A S ??；11. δαβωωδR R A S ??*
'，其中γ=δα，a 是ω的第一个符号，或者a 是#而ω为ε。12. 归约项目，接受项目，移进项目，待约项目；13. 运算符之间的优先关系；句型的“句柄”， 归约；14. a ，a ，b ；15. 句型η相对于A 的一个短语；A==>+ β；16. 句柄已识别的部分(进入符号栈)，等待识别的部分；17. 活前缀
三、判断题
1. 一个二义性文法可以是SLR 文法或LALR 文法。（ ）
2. LL(1)文法不能用LR （1）分析器来分析。（ ）
3. LR 分析器在自左至右扫描输入串时就能发现其中的任何错误，并能准确地指出出错地点。( ）
4. 在归约过程的任一时刻，一个上下文无关文法的任何句型的直接短语一般都不是唯一的。
( )
5. 算符优先分析法不是一种规范规约法。 ( )
6. 存在有左递归规则的文法是LL(1)的。 ( )
7. 任何算符优先文法的句型中不会有两个相邻的非终结符号。 ( )
8. 算符优先文法中任何两个相邻的终结符号之间至少满足三种关系(＜·，·＞，＝·)之一。 ( )
9. 任何LL(1)文法都是无二义性的。 ( )
10. 每一个SLR(1)文法也都是LR(1)文法。 ( )
11. 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( )
12. 任何一个LL(1)文法都是一个LR(1)文法，反之亦然。 ( )
13. LR(1)分析中括号中的1是指，在选用产生式A→α进行分析，看当前读入符号是否在FIRST(α)中。 ( )
14. 若某一个句型中出现了某一产生式的右部，则此右部不一定是该句型的句柄。（ ）
15. 算符优先关系表不一定存在对应的优先函数。 （ ）
16. 简单优先文法允许任意两个产生式具有相同右部。 （ ）
17. 一个句型的句柄一定是文法某产生式的右部。 （ ）
18. 若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。 （ ）
19. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别活前缀的DFA 的一个状态。 （ ）
四．答案：1. ×；2. ×；3. √；4. √；5. √；6. ×；7. √；8. ×；9. √；10. √；11. √；12. ×；13. √；
14. ×；15. √；16. ×；17. √；⒙ ×；19. ×；
五、名词解释：
1. 短语，直接短语，句柄；
2. 规范归约，规范推导；
3. 算符文法，算符优先文法；
4. 素短语，最左素短语；
5. 前缀，活前缀；
6. LR(0)项目，LR(0)项目集规范族；
五. 答案：
1. 设G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有：S=>*αAδ且A=>*β，则称β是句型αβδ相对于非终结符A的短语。
特别地，如果A=>β，则称β是句型αβδ相对于规则A->β的直接短语。
一个句型的最左直接短语称为该句型的句柄。
2. 在形式语言中，最右推导常称规范推导。规范归约是最右推导的逆过程，也称最左归约。
3. 一个文法，如果它的任何一个产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：……QR……，则我们称该文法为算符文法。
在一个算符文法中的任何终结符对（a，b），至多只满足下述三个关系之一：a?=b，ab，则称G是一个算符优先文法。
4. 所谓素短语是指这样的一个短语，它至少含有一个终结符，并且，除自身之外不再含任何更小的素短语。
所谓最左素短语是指处于句型最左边的哪个素短语。
5. 一个字的前缀是指该字的任意首部。活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
6. 文法G的每一个产生式的右部添加一个小圆点，称为G的一个LR(0)项目。
构成识别一个文法活前缀的DFA的项目集（状态）的全体，称为该文法的项目集规范族。
六、简答题：
1. 说明任何SLR(1)文法都是LR(1)文法。
2. 为什么移进－归约法不是一种语法分析方法？
3. LR(k)分析法是如何做到严格地自左向右进行分析的？
4. 使用状态有限的识别可归前缀的有穷自动机，为什么可以识别语言的无穷多个句子？
5. LR项目的含义是什么？
六．答案：
1. 假设有一个SLR(1)文法G不是LR(1)文法，那么在G的LR(1)项目集规范族中，或有下面的(i)，或有下面的(ii)，或两种情形都有
与之对应，G的LR(0)项目集规范族或有下面的(i)，或有下面的(ii)，或两者皆有：
因为G是SLR(1)文法，因此有：
a不属于FOLLOW(A)，FOLLOW(A)∩FOLLOW(B)＝Φ
根据G的LR(1)项目集，有
a∈FOLLOW(A)，FOLLOW(A)∩FOLLOW(B)≠Φ
这和假设矛盾。因此，任何SLR(1)文法都是LR(1)文法。
2. 自底向上分析技术采用移进－归约法实现句型分析，但移进－归约法决不是一种分析技术，它本身不能解决自底向上分析计数所必须解决的两个基本问题，移进－归约法仅仅是适用于各种自底向上技术的一种实现方法。
3. 自底向上分析的关键是寻找句柄。简单优先分析法、算符优先分析法都是自左向右地向前查看若干个输入符号，找出句柄（或其变型－最左素短语）的尾，然后回头（从右到左）找出句柄（或其变型－最左素短语）的头，这已不是严格地从左到右查看源程序来进行归约了。
LR(k)分析法则严格地从左到右地读入输入符号串中的符号，且最多向貌似句柄的符号串后看确定个数的符号，就能一点不回溯地识别该貌似句柄的符号串是否真正的句柄。它的基本思想是：在规范归约的过程中，一方面记住已移进和归约出的符号串，即记住“历史”，另一方面根据所用的产生式（规则）推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶部时，能够根据所记载的“历史”、“展望”的信息以及“现实”中的输入符号三方面的材料，来确定符号栈顶部的符号串是否构成相对于某一规则左部的句柄，从而确定将要做的工作。
为了记住分析的“历史”和汇集全新的“展望”信息，LR分析技术这样来处理：将归约过程的“历史”和“展望”材料综合地抽象成某些状态，存放在一个状态栈中，栈中每个状态都概括了从分析开始直到某一归约阶段的全部“历史”和“展望”材料。因此，任何时候栈顶的状态都代表了整个“历史”和已推测出的“展望”信息，都可以从栈顶状态得知所要了解的一切，而无需自底向上翻阅整个栈。LR分析程序的每一步工作都是由栈顶状态和现行输入符号惟一确定的。根据文法，可以将各种状态下面临不同输入符号所要做的工作用一张表表示出来，然后用这张表直到整个分析过程的进行。
4. 这是因为，许多句型在归约过程中虽然分析的步数和过程不一样，但它们所处的状态有一些是一样的，而这些同样的状态在有穷自动机中只需要出现一个即可。
5. LR项目是在规则右部适当位置加一个圆点得到的，用圆点的位置来标记分析过程中的某个时刻。圆点的含义为：对规则右部的符号串，已从输入串看到可由圆点左部推出的符号子串，希望能进一步看到可由圆点右部推出的符号串；如果圆点右部为 ，则自然联想到可将
规则右部归约成规则左部。此时，圆点左部的符号子串一定是一个可归前缀。因此，项目刻画了在分析过程中一条规则的右部已有哪些成分被识别。
七、应用题：
1. 文法如下：
S→a | Λ | (T)
T→T, S | S
(1) 计算该文法的Firstvt和Lastvt；
(2) 构造算符优先关系表,并说明该文法是否是OPG文法；
(3) 计算优先函数；
(4) 给出串(a,a)#和(a,(a,a)) #的算符优先分析过程。
1.答案：
（1）Firstvt(S)={a, Λ, ( }，Firstvt(T)={a, , , Λ, ( }，Lastvt(S)={a, Λ, ) }，Lastvt(T)={a, , , Λ, ) } （2）
该文法是OPG文法.
先给出该文法的语法树:
S
T
)
T , S
S a
a
2. 下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。
S→Sab | bR
R→S | a
2. 答案：
为
其LR(0)项目集规范族和goto 函数(识别活前缀的DFA)如下：
I0 = {S'→·S, S→·Sab, S→·bR}
I1 = {S'→S·, S→S·ab}
I2 = {S→b·R, R→·S, R→·a, S→·Sab, S→·bR}
I3 = {S→Sa·b}
I4 = {S→bR·}
I5 = {R→S·, S→S·ab}
I6 = {R→a·}
I7 = {S→Sab·}
求FOLLOW集：
FOLLOW(S')={＄}
FOLLOW(R)=FOLLOW(S)={a,＄}
在I5中，出现移进－归约冲突，且FOLLOW(R)∩{a}={a}
因此，此文法不是SLR(1)文法。
3. 证明下面文法是SLR(1)文法，并构造其SLR分析表。
E→E+T|T
T→TF|F
F→F*|a|b
输入串b+ab*是该文法的句子吗？给出对该串的分析过程。答案：3. 该文法的拓广文法G'为
其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下: I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*,
F→·a, F→·b}
I1 = {E'→E·, E→E·+T}
I2 = {E→T·, T→T·F, F→·F*, F→·a, F→·b}
I3 = {T→F·, F→F·*}
I4 = {F→a·}
I5 = {F→b·}
I6 = {E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b}
I7 = {T→TF·, F→F·*}
I8 = {F→F*·}
I9 = {E→E+T·, T→T·F, F→·F*, F→·a, F→·b}
求FOLLOW集：
FOLLOW(E)={＋, ＄}
FOLLOW(T)={＋, ＄, a, b}
FOLLOW(F)={＋, ＄, a, b, *}
构造的SLR分析表如下：
显然，此分析表无多重定义入口，所以此文法是SLR文法。
4. 下面文法属于哪类LR文法？试构造其分析表。
S→(SR|a
R→,SR|)
输入串（a,a）是文法的句子吗？给出分析过程。
4.答案：
该文法的拓广文法G'为
goto函数(识别活前缀的DFA)如下: I0 = {S'→·S, S→·(SR, S→·a}
I1 = {S'→S·}
I2 = {S→(·SR, S→·(SR, S→·a}
I3 = {S→a·}
I4 = {S→(S·R, R→·,SR, R→·)}
I5 = {S→(SR·}
I6 = {R→)·}
I7 = {R→,·SR, S→·(SR, S→·a}
I8 = {R→,S·R, R→·,SR, R→·)}
I9 = {R→,SR·}
每个LR(0)项目集中没有冲突。因此，此文法是LR(0)文法。其分析表如下：
5. 设文法G为
S → A
A → BA | ε
B → aB | b
（1）证明它是LR(1)文法；
（2）构造它的LR(1)分析表；
（3）给出输入符号串abab的分析过程。
G'的产生式为
构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下：
I0 = { [S'→·S, $], [S→·A, $], [A→·BA, $], [A→·, $], [B→·aB, a/b/$], [B→·b, a/b/$]} I1 = {[S'→S·, $]}
I2 = {[S→A·, $]}
I3 = {[A→B·A, $], [A→·BA, $], [A→·, $], [B→·aB, a/b/$], [B→·b, a/b/$]}
I4 = {[B→b·, a/b/$]}
I5 = {[B→a·B, a/b/$], [B→·aB, a/b/$], [B→·b, a/b/$]}
I6 = {[A→BA·, $]}
I7 = {[B→aB·, a/b/$]}
该文法的LR(1)项目集规范族中没有冲突，所以该文法是LR(1)文法。
(2)构造LR(1)分析表如下：
以上分析表无多的定义入口，所以该文法为LR(1)文法。
(3)对于输入串abab，其分析过程如下：
6. 为下面的文法构造LALR(1)分析表
S→E
E→E+T | T
T→(E) | a
并给出对输入串(a+a)的分析过程。
6. 答案：
其拓广文法G'：
goto函数(识别活前缀的DFA)如下：
I0 = {[S’→·S, $], [S→·E, $],[E→·E+T, $/+], [E→·T, $/+], [T→·(E), $/+], [T→·a, $/+]} I1 = {[S’→S·, $]}
I2 = {[S→E·, $], [E→E·+T, $/+]}
I3 = {[E→T·, $/+]}
I4 = {[T→(·E), $/+], [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I5 = {[T→a·, $/+]}
I6 = {[E→E+·T, $/+], [T→·(E), $/+], [T→·a, $/+]}
I7 = {[T→(E·), $/+], [E→E·+T, )/+]}
I8 = {[E→T·, )/+]}
I9 = {[T→(·E), )/+}, [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I10 = {[T→a·, )/+]}
I11 = {[E→E+T·, $/+]}
I12 = {[T→(E)·, $/+]}
I13 = {[E→E+·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I14 = {[T→(E·), )/+], [E→E·+T, )/+]}
I15 = {[E→E+T·, )/+]}
I16 = {[T→(E)·, )/+]}
合并同心的LR(1)项目集，得到LALR的项目集和转移函数如下：
I0 = {[S’→·S, $], [S→·E, $], [E→·E+T, $/+], [E→·T, $/+], [T→··(E), $/+], [T→·a, $/+]} I1 = {[S’→S·, $]}
I2 = {[S→E·, $], [E→E·+T, $/+]}
I3,8 = {[E→T·, $/+/)]}
I4,9 = {[T→(·E), $/+/)], [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I5,10 = {[T→a·, $/+/)]}
I6,13 = {[E→E+·T, $/+/)], [T→·(E), $/+/)], [T→·a, $/+/)]}
I7,14 = {[T→(E·), $/+/)], [E→E·+T, )/+]}
I11,15 = {[E→E+T·, $/+/)]}
I12,16 = {[T→(E) ·, $/+/)]}
LALR分析表如下：
7. 已知文法
S →L.L
S →L
L →LB
L →B
B →0
B →1
用LR分析法说明符号串101.110是否文法的句子。
（1）拓广文法为G′，增加产生式S′→S
若产生式排序为：
0 S' →S
1 S →L.L
2 S →L
3 L →LB
4 L →B
5 B →0
6 B →1
由产生式知：
FIRST (S' ) = {0,1}
FIRST (S ) = {0,1}
FIRST (L ) = {0,1}
FIRST (B ) = {0,1}
FOLLOW(S' ) = {#}
FOLLOW(S ) = {#}
FOLLOW(L ) = {0,1,#}
FOLLOW(B ) = {0,1,#}
G′的LR(0)项目集族及识别活前缀的DFA如下图所示：
在I2中：
B →.0和B →.1为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。
在I2、I8中：
FOLLOW(S) ∩{0，1}= { #} ∩{0，1}=
所以在I2 、I8中的移进-归约冲突可以由FOLLOW集解决，所以G是SLR(1)文法。（2）构造的SLR(1)分析表如下：
对输入串101.110#的分析过程
分析成功，说明输入串101.110是文法的句子。
8. 对于文法
S→AB
A→aB
B→b
(1) 构造LR(1)分析表；
(2) 给出用LR(1)分析表对输入符号串abab的分析过程。
9. 给定文法G[Z]：
①Z→C S
②C→if E then
③S→A＝E
④E→E∨A
⑤E→A
⑥A→i
其中：Z、C、S、A、E∈V N；if、then、＝、∨、i∈V T
a) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。
b) 构造其SLR（1）分析表。
9. 答案：
1.首先拓广文法：在G中加入产生式0．Z'→Z，然后得到新的文法G'，再求G'的识别全部活前缀的DFA：
I0：Z′→.Z
Z→.C S
C→.if E then
I1：Z′→Z.
I2：Z→C .S
S→.A＝E
A→.i
I3：C→if .E then
E→.E∨A
E→.A
A→.i
I4：Z→C S.
I5：S→A.＝E
I6：A→i.
I7：C→if E .then
E→E.∨A
I9：S→A＝.E
E→.E∨A
E→.A
A→.i
I10：C→if E then.
I11：E→E∨.A
A→.i
I12：S→A＝E.
E→E.∨A
I13：E→E∨A.
Follow(Z)＝{#}
Follow(C)＝{i}
Follow(S)＝{#}
Follow(E)＝{#,∨,then} Follow(A)＝{＝,# ,∨,then }
则可构造SLR（1）分析表为：
10. 设有文法G[S]：
S→aA
A→Ab
A→b
求识别该文法所有活前缀的DFA；构造合适的LR分析表，并给出对输入串abb的分析过程。
解答：
(1).首先拓广文法：
在G中加入产生式0.S′→S，然后得到新的文法G′:
0.S′→S
1.S→aA
2.A→Ab
3.A→b
(2).再求G′的识别全部活前缀的DFA：
11.给定文法G[S] ：
S →SaA|a
A →AbS|b
⑴请构造该文法的以LR(0) 项目集为状态的识别规范句型活前缀的DFA 。
⑵请构造该文法的LR(0) 分析表。
⑶什么是LR(0) 文法？该文法是LR(0) 文法吗？为什么？
⑷什么是SLR(1) 文法？该文法是SLR(1) 文法吗？为什么？
12. 下面文法属于哪类LR文法？试构造其分析表。
S→aSAB | BA
A→aA | B
B→ b
输入串abababb是文法的句子吗？给出分析过程。
12. 答案：
该文法的拓广文法G'为
其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下：I0 = {S'→·S, S→·aSAB, S→·BA, B→·b}
I1 = {S'→S·}
I2 = {B→b·}
I3 = {S→a·SAB, S→·aSAB, S→·BA, B→·b}
I4 = {S→B·A, A→·aA, A→·B, B→·b}
I5 = {S→aS·AB, A→·aA, A→·B, B→·b}
I6 = {S→aSA·B, B→·b}
I7 = {A→a·A, A→·aA, A→·B, B→·b}
I8 = {A→B·}
I9 = {S→BA·}
I10 = {S→aSAB·}
I11 = {A→aA·}
求FOLLOW集：
FOLLOW(S')={＄}
FOLLOW(S)={a,b,＄}
FOLLOW(A)={a,b,＄}
FOLLOW(B)={a,b,＄}
第一章习题解答 2.编译程序有哪些主要构成成分？各自的主要功能是什么？ 编译程序的主要构成成分有：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序及出错处理程序。 （1）词法分析程序：从左到右扫描源程序，识别单词及其有关属性； （2）语法分析程序：分析源程序的结构, 判别它是否为相应程序设计语言中的一个合法程序； （3）语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息； （4）中间代码生成程序：将源程序变成一种内部表示形式； （5）代码优化程序：对前阶段产生的中间代码进行变换或进行改造，使生成的目标代码更为高效； （6）目标代码生成程序：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码； （7）表格管理程序：保存编译过程中的各种信息； （8）出错处理程序：若编译过程中发现源程序存在错误，则报告错误的性质和错误发生的地点，有些还可以自动校正错误。 3.什么是解释程序？它与编译程序的主要不同是什么？ 解释程序接受某个语言的程序并立即运行这个源程序。它的工作模式是一个个的获取、分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员交互方式的工作情况。 而编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序，这个二进制代码程序再机器上运行以生成结果。 它们的主要不同在于：解释程序是边解释边执行，解释程序运行结束即可得到该程序的运行结果，而编译程序只是把源程序翻译成汇编或者二进制程序，这个程序再执行才能得到程序的运行结果。（当然还有其他不同，比如存储组织方式不同）
编译原理作业答案 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】
《编译原理》第一次作业参考答案 一、下列正则表达式定义了什么语言（用尽可能简短的自然语言描述） 1.b*(ab*ab*)* 所有含有偶数个a的由a和b组成的字符串. 2.c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一：所有至少含有1个a和1个b的由a，b和c组成的字符串. 答案二：所有含有子序列ab或子序列ba的由a，b和c组成的字符串. 说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交 流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更 “自然”. 二、设字母表∑={a,b}，用正则表达式（只使用a，b，?，|，*，+，）描述下列语言： 1.不包含子串ab的所有字符串. b*a* 2.不包含子串abb的所有字符串. b*(ab)* 3.不包含子序列abb的所有字符串. b*a*ba* 注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容. ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ 《编译原理》第二次作业参考答案
一、考虑以下NFA： 1.这一NFA接受什么语言（用自然语言描述） 所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串. 2.构造接受同一语言的DFA. 答案一（直接构造通常得到这一答案）： 答案二（由NFA构造DFA得到这一答案）： 二、正则语言补运算
第五章 练习5.1.1： 对于图5-1中的SDD，给出下列表达式对应的注释语法分析树： 1）（3+4）*（5+6）n 练习5.2.4： 这个文法生成了含“小数点”的二进制数： S->L.L|L L->LB|B B->0|1 设计一个L属性的SDD来计算S.val，即输入串的十进制数值。比如，串101.101应该被翻译为十进制的5.625。提示：使用一个继承属性L.side来指明一个二进制位在小数点的哪一边。 答： 元文法消除左递归后可得到文法： S->L.L|L L->BL’ L’->BL’|ε B->0|1 使用继承属性L.side指明一个二进制位数在小数点的哪一边,2表示左边，1表示右边 使用继承属性m记录B的幂次 非终结符号L和L’具有继承属性inh、side、m和综合属性syn
练习5.3.1：下面是涉及运算符+和整数或浮点运算分量的表达式文法。区分浮点数的方法是看它有无小数点。 E-〉E+T|T T-〉num.num|num 1）给出一个SDD来确定每个项T和表达式E的类型 2）扩展（1）中得到的SDD，使得它可以把表达式转换成为后缀表达式。使用一个单目运算符intToFloat把一个整数转换为相等的浮点数 答： 练习5.4.4：为下面的产生式写出一个和例5.10类似的L属性SDD。这里的每个产生式表
示一个常见的C语言中的那样的控制流结构。你可能需要生成一个三地址语句来跳转到某个标号L，此时你可以生成语句goto L 1）S->if (C) S1 else S2 2）S->do S1 while (C) 3）S->’{’ L ‘}’; L -> LS|ε 请注意，列表中的任何语句都可以包含一条从它的内部跳转到下一个语句的跳转指令，因此简单地为各个语句按序生成代码是不够的。 第六章 练习6.1.1：为下面的表达式构造DAG （（x+y）-（（x+y）*（x-y）））+（（x+y）*（x-y）） 答：DAG如下
《编译原理》第一次作业参考答案 一、下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？ 1.b*(ab*ab*)* 所有含有偶数个a的由a和b组成的字符串. 2.c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一：所有至少含有1个a和1个b的由a，b和c组成的字符串. 答案二：所有含有子序列ab或子序列ba的由a，b和c组成的字符串. 说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更“自然”. 二、设字母表∑={a,b}，用正则表达式（只使用a，b， ，|，*，+，？）描述下列语言： 1.不包含子串ab的所有字符串. b*a* 2.不包含子串abb的所有字符串. b*(ab?)* 3.不包含子序列abb的所有字符串. b*a*b?a* 注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容. ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ ~\(≧▽≦)/~ 《编译原理》第二次作业参考答案 一、考虑以下NFA： 1.这一NFA接受什么语言（用自然语言描述）？ 所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串. 2.构造接受同一语言的DFA. 答案一（直接构造通常得到这一答案）：
答案二（由NFA构造DFA得到这一答案）： 二、正则语言补运算 3.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串. 1.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.
编译原理第4章作业 答案 本页仅作为文档封面，使用时可以删除 This document is for reference only-rar21year.March
第四章 习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a* (3)给出这个串的一棵语法分析树 习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆： rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 1)对这个文法提取公因子 2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？ 3)提取公因子之后，原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗？ 解
1)提取左公因子之后的文法变为 rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法 3)消除左递归后的文法
rexpr -> rterm rexpr’ rexpr’-> + rterm rexpr’|ε rterm-> rfactor rterm’ rterm’-> rfactor rterm’|ε rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|ε rprimary-> a | b 4)该文法无左递归，适合于自顶向下的语法分析 习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归 (3)S->S(S)S|ε (5)S->(L)|a L->L,S|S 解 (3) ①消除该文法的左递归后得到文法 S->S’ S’->(S)SS’|ε ②计算FIRST和FOLLOW集合 FIRST(S)={(,ε} FOLLOW(S)={),$} FIRST(S’)={(,ε} FOLLOW(S’)={),$} ③构建预测分析表
第一章编译概述 2.典型的编译程序可划分为几部分？各部分的主要功能是什么？每部分都是必不可少的吗？ 答：编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。 各部分的主要功能如下： 词法分析程序又称扫描器。进行词法分析时，依次读入源程序中的每个字符，依据语言的构词规则，识别出一个个具有独立意义的最小语法单元，即“单词”，并用某个单词符号来表示每个单词的词性是标识符、分界符还是数； 语法分析程序的功能是：对词法分析的结果，根据语言规则，将一个个单词符号组成语言的各种语法类； 语义分析的功能是确定源程序的语义是否正确； 中间代码生成程序的功能是将源程序生成一种更易于产生、易于翻译成目标程序的中间代码； 代码优化程序的功能是将中间代码中重复和冗余部分进行优化，提高目标程序的执行效率； 目标代码生成程序的功能是将中间代码生成特定机器上的机器语言代码； 符号表管理程序的功能是记录源程序中出现的标识符，并收集每个标识符的各种属性信息； 错误处理程序的功能是应对在编译各个阶段中出现的错误做适当的处理，从而使编译能够继续进行。 编译程序的每部分都是必不可少的。 3.解释方式和编译方式的区别是什么？ 答：解释方式最终并不生成目标程序，这是编译方式与解释方式的根本区别。解释方式很适合于程序调试，易于查错，在程序执行中可以修改程序，但与编译方式相比，执行效率太低。 4.论述多遍扫描编译程序的优缺点？ 答：优点：（1）可以减少内存容量的需求，分遍后，以遍为单位分别调用编译的各个子程序，各遍程序可以相互覆盖；（2）可使各遍的编译程序相互独立，结构清晰；（3）能够进行充分的优化，产生高质量的目标程序；（4）可将编译程序分为“前端”和“后端”，有利于编译程序的移植。 缺点是每遍都要读符号、送符号，增加了许多重复性工作，降低了编译效率。
精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************
第一章习题解答 2．编译程序有哪些主要构成成分？各自的主要功能是什么？ 编译程序的主要构成成分有：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序及出错处理程序。 （1）词法分析程序：从左到右扫描源程序，识别单词及其有关属性； （2）语法分析程序：分析源程序的结构, 判别它是否为相应程序设计语言中的一个合法程序； （3）语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息； （4）中间代码生成程序：将源程序变成一种内部表示形式； （5）代码优化程序：对前阶段产生的中间代码进行变换或进行改造，使生成的目标代码更为高效； （6）目标代码生成程序：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码； （7）表格管理程序：保存编译过程中的各种信息； （8）出错处理程序：若编译过程中发现源程序存在错误，则报告错误的性质和错误发生的地点，有些还可以自动校正错误。 3．什么是解释程序？它与编译程序的主要不同是什么？ 解释程序接受某个语言的程序并立即运行这个源程序。它的工作模式是一个个的获取、分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员交互方式的工作情况。 而编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序，这个二进制代码程序再机器上运行以生成结果。 它们的主要不同在于：解释程序是边解释边执行，解释程序运行结束即可得到该程序的运行结果，而编译程序只是把源程序翻译成汇编或者二进制程序，这个程序再执行才能得到程序的运行结果。（当然还有其他不同，比如存储组织方式不同）
编译 原理 课后题答案 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导:
E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/******************************** E E F T E + T F F T +i i i E E F T E -T F F T -i i i E E F T +T F F T i i i *i+i+i i-i-i i+i*i *****************/ P36-9 句子iiiei 有两个语法树： S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ???????? P36-10 /************** ) (|)(|S T T TS S →→ ***************/ P36-11 /*************** L1: ε ||cC C ab aAb A AC S →→→ L2:
第 1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
《编译原理》习题答案： 第一次： P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？ 答：被翻译的程序称为源程序； 翻译出来的程序称为目标程序或目标代码； 将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序； 把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序； 解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行； 编译程序是将高级语言写的源程序翻译成目标语言的程序。 关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。 P14 3、编译程序是由哪些部分组成？试述各部分的功能？ 答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。 P14 4、语法分析和语义分析有什么不同？试举例说明。 答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量 x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。 P15 5、编译程序分遍由哪些因素决定？ 答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。 补充： 1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？ 答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。 补充： 2、赋值语句： A：= 5 * C的语法和语义指的是什么？ 答：语法分析将检查该语句是否符合赋值语句规则，语义是指将 5 * C 的结果赋值为 A 。
第1章引言 1、解释下列各词 源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。 源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序 （结果程序）一般可由计算机直接执行。 低级语言：机器语言和汇编语言。 高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。 翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目 标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。 编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言）， 然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。 解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。 2、什么叫“遍” 指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。
3、简述编译程序的基本过程的任务。 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。 词法分析：输入源程序，进行词法分析，输出单词符号。 语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。 中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。 优化：对中间代码进行优化处理。 目标代码生成：把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别 编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。 5、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗 编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码。 6、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。
第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。
一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a) 《编译原理》课后习题答案第一章 第 1 章引论 第 1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第 2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构图。 答案： 一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式 的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的 各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源 第一次作业答案： 3.12 词法单元描述 3.3.5 b)a*b*……z* c) /\*([^*”]|\*[^/]|\”([^”]*)\”)*\*/ h)b*(a|ab)* 3.7.3d F转G错误，F跳转后的状态子集应包含9 第二次作业答案： 4.2.2 最左推导 S->SS S->S*S S->(S)*S S->(S+S)*S S->(a+S)*S S->(a+a)*S S->(a+a)*a Parse tree: 最右推导： S->SS S->S*a S->(S)*a S->(S+S)*a S->(S+a)*a S->(a+a)*a 无二义性，只能画出一棵语法树。 4.3.2 提取左公因子： S->SS’|(S)|a S’->+S|S|* 消除左递归： S->(S)A|aA , A->BA|?B->S|+S|* FIRST(S) = { a , ( } FIRST(A) = {* , a , ( , + , ?} FIRST(B) = {* , a , ( , +} FOLLOW(S) = { ( , ) , a , * , + , $} LL1 parse table: 转换表如下： match stack input action S$ (a+a)*a$ (S)A$ (a+a)*a$ S->(S)A ( S)A$ a+a)*a$ match( ( aA)A$ a+a)*a$ S->aA (a A)A$ +a)*a$ match a (a BA)A$ +a)*a$ A->BA (a +SA)A$ +a)*a$ B->+S (a+ SA)A$ a)*a$ match + (a+ aAA)A$ a)*a$ S->aA (a+a AA)A$ )*a$ match a (a+a A)A$ )*a$ A->? (a+a )A$ )*a$ A->? (a+a) A$ *a$ match ) (a+a) BA$ *a$ A->BA (a+a) *A$ *a$ B->* (a+a)* A$ a$ match * (a+a)* BA$ a$ A->BA (a+a)* SA$ a$ B- >S (a+a)* aAA$ a$ S->aA (a+a)*a AA$ $ match a (a+a)*a $ $ A->? 第二章 2.3叙述由下列正规式描述的语言 (a) 0(0|1)*0 在字母表{0, 1}上,以0开头和结尾的长度至少是2的01 串 (b) ((ε|0)1*)* 在字母表{0, 1}上,所有的01串,包括空串 (c) (0|1)*0(0|1)(0|1) 在字母表{0, 1}上,倒数第三位是0的01串 (d) 0*10*10*10* 在字母表{0, 1}上,含有3个1的01串 (e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 在字母表{0, 1}上,含有偶数个0和偶数个1的01串 2.4为下列语言写正规定义 C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。 ［解答］ other → a | b | … other指除了*以外C语言中的其它字符 other1 → a | b | … other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */ (f) 由偶数个0和偶数个1构成的所有0和1的串。 ［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况： x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）；所以， x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1） x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1） 因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图： 由此可以写出其正规文法为： S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1 在不考虑S0 →ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1 所以： S0 = (00|11) S0 + (01|10) S3 + 11 + 00 (1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10 (2) 解(2)式得： S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得： S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00| 11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|1 第1 章 1、编译过程包括哪几个主要阶段及每个 阶段的功能。 答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5 个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。 第2 章 1、写一上下文无关文法G，它能产生配 对的圆括号串（如：(),(()),()(())等，甚至 包括0 对括号） 文法为：S→(L)|LS|L L→S| ε 2 、已知文法G ：E→E+T|E-T|T T→T*F|T/F|F F→(E) |i （1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。 （2）i-i+i 哪个算符优先。 【解答】 （1）最左推导：E?E+T?T+T? F+T ? i+T ? i+T*F ? i+F*F ?i+i*F ?i+i*i E?T?T*F? F*F ? i*F ? i*(E) ? i*(E-T) ? i*(T-T) ? i*(F-T) ? i*(i-T) ? i*(i-F) ?i*(i-i) 最右推导：E?E+T?E+T*F? E+T*i ? E+F*i ? E+i*i ? T+i*i ? F+i*i ? i+i*i E?T?T*F? T*(E) ? T*(E-T) ? T*(E-F) ? T*(E-i) ? T*(T-i) ? T*(F-i) ?T*(i-i) ? F*(i-i) ?i*(i-i) i+i*i 以及i*(i-i)的语法树如下所示： （2）i-i+i 的语法树如下图所示。 从上图的语法树可知：“-”的位置位 于“+”的下层，也就是前面两个i 先进 行“-”运算，再与后面的i 进行“+” 运算，所以“-”的优先级高于“+”的 优先级。 3 、文法G: E→ET+|T T→TF*|F F→FP↑|P P→E|i （1）试证明符号串TET+*i↑是G 的一 个句型(要求画出语法树). （2）写出该句型的所有短语,直接短语和句柄. 【解答】（1）采用最右推导： E?T?F? FP↑? Fi↑? Pi↑? Ei↑ ? Ti↑? TF*i↑? TP*i↑? TE*i↑? TET+*i↑ 语法树如下图所示。 从文法G 的起始符号出发，能够推导 出符号串TET+*i↑，所以给定符号串是文法G的句型。 (2) 该句型的短语有： ET+,TET+*,i ,TET+*i↑ 直接短语有：ET+, i 句柄是：ET+ 4、已知文法G：S→iSeS|iS|i ，该文法 是二义文法吗？为什么？ 【解答】该文法是二义文法。 因为对于句子iiiei 存在两种不同的最 左推导： 第 1 种推导：S? iSeS? iiSeS? iiieS? iiiei 第2种推导：S?iS?iiSeS?iiieS?iiiei 第3 章 1、用正规式描述下列正规集： （1）C 语言的十六进制整数； （2）以ex 开始或以ex 结束的所有小写字母构成的符号串； （3）十进制的偶数。 【解答】 （1）C 语言十六进制整数以0x 或者0X 开头，所以一般形式应该为（+|-|ε） (0x|0X)AA*，其中前面括号表示符号， 可以有正号、负号，也可以省略（用ε表示）默认是正数，A 表示有资格出现在十六进制整数数位上的数字，AA*表示一位或者多位（一个或者多个数字的 例1设有文法G[S]: S →a|（T ）| T →T,S|S （1） 试给出句子(a,a,a)的最左推导。 （2） 试给出句子(a,a,a)的分析树 （3） 试给出句子(a,a,a)的最右推导和最右推导的逆过程(即最左规约)的每一步的句柄。 【解】(1) (a,a,a)的最左推导 S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a) （2）(a,a,a)的分析树 S ( T ) T ， S S a T ， S a (3) (a,a,a)最右推导 最左规约每一步的句柄 S=>(T) 句柄为：(T) =>(T,S) 句柄为：T,S =>(T,a) 句柄为：a =>(T,S,a) 句柄为：T,S =>(T,a,a) 句柄为：第一个a =>(S,a,a) 句柄为：S =>(a,a,a) 句柄为：第一个a 例2已知文法G[Z]: Z →0U|1V U →1Z|1 V →0Z|0 （1） 请写出此文法描述的只含有４个符号的全部句子。 （2） G [Z]产生的语言是什么？ （3） 该文法在Chomsky 文法分类中属于几型文法？ 【解】（1）0101，0110，1010， 1001 （2）分析G[Z]所推导出的句子的特点：由Z 开始的推导不外乎图1所示的四种情形。 图 1文法G[Z]可能的几种推导 Z 1 U Z U Z 1 Z 1 V Z 1 V 由Z 推导出10或01后就终止或进入递归，而Z 的每次递归将推导出相同的符号串：10或 01。所以 G[Z]产生的语言L(G[Z])={x|x∈(10|01)+ } (3)该文法属于3型文法。 例3 已知文法G=({A,B,C}，{a,b,c}，P，A), P由以下产生式组成: A→abc A→aBbc Bb→bB Bc→Cbcc bC→Cb aC→aaB aC→aa 此文法所表示的语言是什么？ 【解】 分析文法的规则： 每使用一次Bc→Cbcc，b、c的个数各增加一个； 每使用一次aC→aaB或aC→aa, a的个数就增加一个； 产生式Bb→bB、 bC→Cb起连接转换作用。 由于A是开始符号，由产生式A→abc推导得到终结符号串abc；由产生式A→aBbc推导得到B后，每当使用产生式Bb→bB、Bc→Cbcc、bC→Cb、aC→aaB就会递归调用B一次，所产生的a、b、c的个数分别增加一个，因此推导所得的终结符号串为abc、aabbcc、aaabbbccc、…所以文法描述的语言为{ a n b n c n|n>0}. 例4 构造描述语言L(G[S])={（n）n|n≥0} 的文法。 【解】(1)找出语言的一些典型句子: n=0 ε n=1 ( ) n=2 (()) … 所以, L(G[S])={ ε、( ) (())、((()))、…} (2)分析句子的特点: 只含有(和),(和)的个数相同且对称, 句子中所含的符号数可无限, 句子的个数可无限。 (3)凑规则:由 S→ε|() 得到ε|()，由 A→ (S) 得到 (())，(()) 是在（）的两边再加上一对（）得到，((()))是在(())的两边再加上一对（）得到，…所以将上述产生式合并为S→(S) |ε。 (4)得到文法 G[S]: S→(S) |ε (5)检验:语言所有的句子均可由文法G[S]推导出来, 文法G[S]推导出来的所有终结符号串均为语言的句子. 例5 构造描述语言L(G[S])={a m b n |n>m>0} 的文法。 【解】找出语言的一些典型句子:abb、abbb、…、aabbb、aabbbb、…,语言的句子的特点是仅含有a、b, a在b的左边，b的个数大于a的个数，a的个数至少是1。 单独生成c k, k>1 可用产生式 C→c |Cc 句子中要求b的个数大于a的个数，所以得到文法：编译原理第二版课后习答案
编译原理作业答案最终版
编译原理课后答案
编译原理课后习题答案
编译原理第一章练习和答案
相关主题
文本预览