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

1. 一棵语法树表示了一个句型所有的不同推导过程，包括最右推导和最左推导。 （ ） 2. 可能有两个不同的文法G和G′，期中一个是二义的而另一个是无二义的，但是却有L(G)＝L(G′)。（ ） 3. 变量既持有左值又持有右值，而常数和带有算符的表达式一般认为只持有右值。（ ） 4. 文法G:

S→bA A→aA|a

定义的语言是所有以b开头的后跟至少一个a的字符串的集合。（ ） 5. 设有文法G：

S→S*S | S+S | (S) | a 该文法是二义的。（ ）

6. 正则文法一定不是二义的。（ ）

7. 上下文无关文法可以产生语言L={ anbnci | i>=1,n>=1 }。（ ） 8. 不存在任何正规文法能产生语言L={anbn | n>=1}。（ ）

9. 对于每一个左线性文法G1，都存在一个右线性文法G2，使得L(G1)=L(G2)。（ ） 10. 正规文法产生的语言都可以用上下文无关文法来描述。（ ） 11. 上下文无关文法比正规文法有更强的描述能力。（ ）

12. 文法的二义性和语言的二义性在概念上是相同的，也就是说，对于某个语言，不可能存在两个以上的文法来描述它。（ ） 13. 二义性是可以判定的，也就是说，可以编这么一个程序，输入该文法后，该程序能确切地给出该文法是否二义的答案。（ ） 14. 说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否一致。实际上，许多说明语句并不能翻译成相应的目标代码。（ ） 15. C语言是一个允许子程序嵌套定义的语言。（ ）

三．答案：1. √；2. √；3. √；4. √；5. √；6. ×；7. √；8. √；9. √；10. √；11. √；12. ×；13. ×；14. √；15. ×；

四、名词解释：

（按照组卷方案，至少3道小题）

1. 二义性文法；2. 推导和直接推导；3. 句型，句子和语言；4. 上下文无关文法；

5. 语法；6. 正规文法（左线性文法和右线性文法）； 四．答案：

1. 如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是是二义性文法。 2. 设A→?是一个产生式，且?、??(VT?VN)*，若?A?=>???，则称?A?直接推出???；或者说，???是?A?的一个直接推导。

如果?1=>?2=>……=>?n，则称这个序列是从?1到?n的一个推导。

3. 设G是一个文法，S是它的开始符号。如果S=>*?，则称?是一个句型。 仅含终结符的句型叫句子。

文法G所产生的句子的全体叫文法G的语言，记为L(G)，L(G)={?| S=>*?，?∈VT*｝。 4. 上下文无关文法G是一个四元式(VT，VN，S，P)，其中： VT是一个非空有限集合，其中的每一个元素称为终结符；

VN是一个非空有限集合，其中的每一个元素称为非终结符，VN∩VT=?； S是一个非终结符，称为开始符号；

P是一个产生式有限集合，每个产生式的形式是P→?，其中P?VN，?∈(VT?VN)*。开始符号S至少必须在某个产生式的左部出现一次。

5. 若文法G= (VT，VN，S，P)的任何产生式为A→?B或A→?，其中，??VT*，A，B∈VN，则称G是右线性文法；

若文法G= (VT，VN，S，P)的任何产生式为A→B?或A→?，其中，??VT*，A，B∈VN，则称G是左线性文法；

左线性文法和右线性文法均为正规文法。

五、简答题：

（按照组卷方案，至少3道小题）

1. 作为描述程序语言的上下文无关文法，对它有哪些限制？ 答：

第一点：文法中不含任何下面形式的产生式：P→P；

第二点：每个非终结符P都必须有用处。也就是说，必须存在含P的句型；或者说，对P不存在永不终结的回路。

2. 什么是二义性文法？从输入串abab来说明下面文法二义吗？

S→aSbS|bSaS|ε

该文法产生的语言是什么？ 答：

如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是二义的。 例如输入串abab，它有两棵语法树如下：

S S a S b S ? a S ? b S b S ? a S ? a S ? b S ?

所以，该文法是二义的。

此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。 3. 文法 G[S]为：

S→Ac|aB A→ab B→bc

该文法是否为二义的？为什么？ 答： 对于串 abc

(1)S=>Ac=>abc (2)S=>aB=>abc

即存在两不同的最右推导。所以，该文法是二义的。 或者：

对输入字符串 abc，能构造两棵不同的语法树，所以它是二义的。

4已知文法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、?所以文法描述的语言为{ anbncn|n>0}. 5已知文法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所示的四种情形。

Z 0 1 U Z 0 Z U 1 1 Z V 0 Z 1 Z V 0 图 1文法G[Z]可能的几种推导 由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出相同的符号串：10或01。所以G[Z]产生的语言L(G[Z])={x|x∈(10|01)+ } (3)该文法属于3型文法。

七、应用题：

1. 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else(else悬挂)文法的二义性：

stmt → if expr then stmt | matched-stmt

matched-stmt→ if expr then matched-stmt else stmt | other expr→e

考虑句子if e then if e then other else if e then other else other，试说明此文法仍然是二义性的。 答：

1. 考虑句子if e then if e then other else if e then other else other 它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other