编译原理

2014—2015学年第二学期第四单元测试试卷

（闭卷考试） 时间：45分钟 满分：100分

姓名 班级 出题人 班级 软件12-4

题目 一 二 三 四 五 总分 得分 一、选择题（5*2分）（每题1分，共10分）

1. 下列文法中，_______是LL(1)文法。

A. S→aSb|ab B. S→ab|Sab C. S→aS|b D. S→aS|a

2. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于 分析法。

A. 自左至右 B. 自顶向下 C. 自底向上 D. 自右向左

3. 自上而下分析面临的四个问题中，不包括 。

A. 需消除左递归；B. 存在回朔；C. 虚假匹配；D. 寻找可归约串

4. 语法分析器接收以________为单位的输入，并产生有关信息供以后各阶段使用。

A. 表达式；B. 产生式； C 单词；D. 语句；

5. 自上而下分析的主旨是，对任何单词符号串，试图用一切可能的办法，从文法开始符号（根结点）出发，________。

A. 为输入串寻找最右推导； B. 为输入串寻找最左直接子树；

C. 为输入串建立最右直接子树；D. 为输入串寻找最左推导；

二、简答题（2*10分）（每题10分，共20分）

6. 词法分析和语法分析都是对字符串进行识别的，二者有何区别？

7. 为什么要消除回溯？

三、分析题（4题共70分）

8.设有文法G[S]：

S→AB A→bB|Aa B→Sb|a

试消除该文法的左递归。（15分）

9.已知文法G[E]：

G[E]：E→E+T|T

T→T*F|F F→i|(E)

请按递归子程序法为其构造语法分析程序。（20分）

10．文法G[M]是否是LL(1)文法，说明理由。（G[M]：M→TB

T→Ba|ε B→Db|eT|ε D→d|ε

15分）

11. 已知文法G[S]： S → uBDz B → Br | w D → EF E → y | ? F → x | ?

(1) 求每个非终结符的FIRST和Follow集。 (2) 构造这个文法的LL(1)分析表 (3) 说明这个文法不是LL(1)的;

(3) 尽可能少地修改此文法,使其成为能产生相同语言的LL(1)文法.（20分）

第四章答案

1-5

B D D C D

6. 答：词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子。词法分析的一个输入符号串是由单个符号组成的单词；语法分析的输入符号串是由词法分析得来的单词组成的句子。

7. 假定当前轮到非终结符A去执行匹配任务，A共有n个候选?1、?2、???n，这时候该用哪一个候选去替换A，原始的办法是采用对所有候选采取“试探”的方法。如果某个候选不成功就需要“回退”。这个回退的过程会导致前次匹配的许多工作推到重来，效率低。而且，最终匹配不成功的时候，难以直到输入串中出错的确切位置。

8.解：本题考查消除左递归的方法。

应用消除文法左递归的算法对文法G[S]消除左递归的过程如下：

（1） 将非终结符排序为：U1=S，U2=A，U3=B （2） 进入算法排序：

i=1时，对文法无影响

i=2，j=1时：A→Aa有直接左递归，消去该直接左递归，得

A→bBA’ A’→aA’|ε

i=3，j=1时：改写文法，有

B→ABb|a

j=2时：改写文法，有 B→bBA’Bb|a无左递归。

（3） 所以文法G[S]消除左递归后变为：

G’[S]：S→AB

A→bBA’ A’→aA’|ε B→bBA’Bb|a

9.解：本题考查递归子程序的构造方法。

…… 此处隐藏0字 ……

本题所给文法存在左递归，不满足递归子程序法对文法的要求，必须首先消除文法左递归，然后再构造分析程序。

因为文法只有左递归，采用扩充的BNF范式消除文法左递归得到：

G[E]：E→T{+T}

T→F{*F} F→i|(E)

然后再应用书中介绍的方法即可求解。

假定用“ADVANCE;”表示对读取下一个单词的过程的调用。 相应的递归子程序为： PROCEDURE P(E); BEGIN P(T);

WHILE SYM=’+’ DO BEGIN