西理工编译原理试题集1-7(8)

（２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

15已知Σ=,a，b}上正则表达式为(a|b)*abb(a|b)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

第四章 语法分析—自上而下分析

本章要点

1. 语法分析器的功能；

2. 自上而下分析方法，LL(1)文法 3. 递归下降分析程序构造；

4. 预测分析表的构造及预测分析过程； 5. LL(1)分析中的错误处理。

本章目标

理解和掌握语法分析器的功能、自上而下分析所面临的问题、LL（1）分析法、递归下降分析的构造过程、预测分析程序等内容。

本章重点

1．语法分析器的功能，自上而下的基本概念

2．LL（1）文法的条件及其判别，计算first集和follow集 3．递归下降分析方法、预测分析表的构造及其预测过程。

本章难点

1. 非终结符的First集合，产生式候选的First集合，非终结符的follow集合的求解； 2. 左递归消除；

3. 递归下降分析程序的编写；

作业题

一、单项选择题：

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

a. 自左至右 b. 自顶向下 c. 自底向上 d. 自右向左 2. 上下文无关文法可以用 来描述。

a. 正则表达式 b. 正规文法 c. 扩展的BNF d. 翻译模式 3. 自上而下分析面临的四个问题中，不包括

a. 需消除左递归；b. 存在回朔；c. 虚假匹配；d. 寻找可归约串

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

a. 表达式；b. 产生式； c. 单词；d. 语句；

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

a. 为输入串寻找最右推导； b. 为输入串寻找最左直接子树； c. 为输入串建立最右直接子树；d. 为输入串寻找最左推导；

6. 把规则T→F | T*F表示成扩展的巴克斯范式以后，画出它的语法图应该是 。 T F F * 图a T T F * F 图b F * F 图c T F * F 图d

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

a. S→aSb|ab 8. 设有文法G： S→Ap|Bq A→a|cA

B→b|dB

b. S→ab|Sab c. S→aS|b d. S→aS|a

则，First(Ap)={_______________} a. a,c b. b,d c. p, q d. A, p

一．答案：1. b；2. c；3. d；4. c；5. d；6. 图a；

二、填空题：

1. 语法分析器的工作本质上就是按____________________，识别输入符号串是否为一个句子。这里所说的输入串是指由____________________组成的有限序列。

2. 自顶向下分析会遇到的主要问题是____________________和__________________。 3. 自上而下地为输入串建立一棵语法树，就是为输入串寻找一个______________。 4. 在扩充的巴科斯范式中，用______________表示符号或串α的出现可有可无。

5. 对于一个文法，当给出一串符号时，怎么能知道它是不是该文法的一个句子呢？这就要判断，看是否能 。

6. 文法exp → exp addop term | term 消除左递归的结果为 。 7. 写出E→T | E+T的EBNF范式为 。 8. 扩展的巴克斯范式描述语法的好处是，直观易懂，便于表示 。

二．答案：1. 文法的产生式，单词符号（文法的终结符）2. 左递归，回溯；3.最左推导；4. 方括号（或[?]）；5. 从文法的开始符号出发推导出这个输入串。（或：能否建立一棵与输入串相匹配的语法分析树。）6. exp → term exp′；exp′→ addop term exp′| ?；7. E→T{+T}；8. 左递归消去和左因子提取。

三、判断题：

1. LL(k)文法都不是二义性的。（ ）

2. 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( ) 3. 一个文法是含有左递归的，如果存在非终结符P，使得P?*?P。（ ） 4. 提取公共左因子的副产品是引进了大量的非终结符和ε产生式。 ( )

5. 把一个文法改造成任何非终结符的所有后选终结首符集两两不相交的办法是消除左递归。( )

6. 若X∈VT，则FIRST(X)={ X }。 ( )

7. 一个文法的预测分析表含有多重定义入口，说明该文法是LL(1)的。（ ） 8. 自上而下分析及自下而上分析中的“下”是指被分析的源程序串。（ ） 三．答案：1. ?；2. ?；3. ×；4. ?；5. ×；6. ?；7. ×；8. ?；

四、名词解释：

1. 左递归；

2. 递归下降分析器； 3. LL(1)文法； 4. 预测分析表 5. 自上而下分析

四．答案：

1.一个文法如果存在非终结符P，P=>+P?，则称该文法是左递归的。

2. 当一个文法满足LL(1)条件时，可以为它构造一个不带回溯的的自上而下分析程序，该程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的分析程序称为递归下降分析器。

3. 一个文法G，如果满足以下条件，则称为LL(1)文法： （1）文法不含左递归；

（2）对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交； （3）对文法中的每个非终结符A，若它存在某个候选首符集包含?，则A的First集合和Follow集合的交集为空。

4. 预测分析表是一个M[A, a]形式的矩阵。其中A为非终结符，a是终结符或“#”。矩阵元素M[A, a]中存放着一条关于A的产生式，指出当A面临输入符号a时所应采取的候选。M[A, a]中也可能存放一个“出错标志”，指出A根本不该面临输入符号a。

5. 自上而下分析是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。

五、简答题：

1. 词法分析和语法分析都是对字符串进行识别的，二者有何区别？ 2. 试说明没有一个左递归文法是LL(1)的。 3. 试说明没有一个LL(1)文法是二义性的。 4. 为什么要消除回溯？ 5. 为什么要提取左因子？

6. 下面文法是有左递归吗？若有，提取左递归。 Declist→Declist; Decl | Decl Decl→idList:Type IdList→Idlist, id | id

Type→ScalarType | array (ScalarTypeList) of Type ScalarType→id | Bound..Bound Bound→Sign IntLiteral | id Sign→+ | - | e

ScalarTypeList→ScalarTypeList, ScalarType | ScalarType

五．答案：

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

2. 对于任一个左递归文法来说，存在一个A?VN，有A规则序列：

A → A1... A1 → A2... ..................... An→ Aα|β Aα

β。显然，FIRST(Aα)∩FIRST(β)≠Φ。因此，没有一个左递归文法是LL(1)的。

A...，因此，在文法中必有如下的

3. 解：

设有一个LL(1)文法G是二义性的，那 …… 此处隐藏：2381字，全部文档内容请下载后查看。喜欢就下载吧 ……