发布时间 : 星期五 文章编译原理作业集-第五章-修订更新完毕开始阅读
编译原理作业集 第五章 自下而上语法分析
五、名词解释：
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)，或两种情形都有
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM - 5 -
编译原理作业集 第五章 自下而上语法分析
与之对应，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项目是在规则右部适当位置加一个圆点得到的，用圆点的位置来标记分析过程中的某个时刻。圆点的含义为：对规则右部的符号串，已从输入串看到可由圆点左部推出的符号子串，希望能进一步看到可由圆点右部推出的符号串；如果圆点右部为?，则自然联想到可将
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM
- 6 -
编译原理作业集 第五章 自下而上语法分析
规则右部归约成规则左部。此时，圆点左部的符号子串一定是一个可归前缀。因此，项目刻画了在分析过程中一条规则的右部已有哪些成分被识别。
七、应用题：
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） a a ? ( ) , ?> ?> ?> ?> ? ( ?> , <. ?> 该文法是OPG文法. a ? ( ) , f0 1 1 1 1 1 g0 1 1 1 1 1 f1 2 2 1 3 3 g1 2 2 2 1 2 f2 3 3 1 3 3 g2 4 4 4 1 2 先给出该文法的语法树:
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM - 7 -
编译原理作业集 第五章 自下而上语法分析
S ( T ) T , S S a a
步骤 栈 优先关系 当前符号 剩余符号 动作 0 ? (a,a) ? 1 ? < ( a,a) ? 移进 2 ?( < a ,a) ? 移进 3 ?(a > , a)? 归约 4 ?(S < , a)? 移进 5 ?(S, < a ) ? 移进 6 ?(S,a > ) ? 归约 7 ?(S,S > ) ? 归约 8 ?(T = ) ? 脱括号 9 ?S = ? 接受
2. 下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。 S→Sab | bR R→S | a
2. 答案：
（1） 该文法的拓广文法G'为 (0) S' → S (1) S → Sab (2) S → bR (3) R → S (4) R → a 其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下： I0 = {S'→·S, S→·Sab, S→·bR}
西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 AM
- 8 -