2. 推导和直接推导；
3. 句型，句子和语言；
4. 上下文无关文法；
5. 语法；
6. 正规文法（左线性文法和右线性文法）； 解答: 1. 2. 3. 4. 5. 6.
五.简答题
1. 作为描述程序语言的上下文无关文法，对它有哪些限制？
2. 什么是二义性文法？从输入串abab来说明下面文法二义吗？ S→aSbS|bSaS|ε 该文法产生的语言是什么？
3. 文法 G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？
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 此文法所表示的语言是什么？
5. 已知文法G[Z]:
Z→0U|1V U→1Z|1 V→0Z|0 （1）请写出此文法描述的只含有４个符号的全部句子。 （2）G[Z]产生的语言是什么？ （3）该文法在Chomsky文法分类中属于几型文法？
解答: 1. 2. 3. 4. 5.
六.应用题
1. 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else(e lse悬挂)文法的二义性： 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，试说明此文 法仍然是二义性的。
2. 考虑文法G[bexpr]： bexpr→bexpr or bterm | bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor| ( bexpr ) | true | false (a) 请指出此文法的终结符号、非终结符号和开始符号。 (b) 试对于句子not(true or false)构造一棵分析树。 (c) 试说明此文法所产生的语言是全体布尔表达式。
3. 已知文法G[S],其产生式为：S→(S)| ε? （a）L(G)是什么？ （b）对于(a)的结果，请给出证明。
4. 试构造生成下列语言的上下文无关文法： (1) { anbnci | n≥1, i≥0 } (2) { w | w∈{a,b}+，且w中a的个数恰好比b多1 } (3) { w | w∈{a,b}+，且|a|≤|b|≤2|a| } (4) { w | w是不以0开始的奇数集 }
5. 已知文法G[S]: S→AB A→aA|a B→bB|b 求该文法所定义的语言。
6. 考虑下面上下文无关文法G[S]： S→SS*|SS+|a (1) 对于符号串aa+a*分别给出最左推导和最右推导过程，并为该串构造语法树。 (2)G[S]的语言是什么？
7. 令文法G为 N→ D | ND D→ 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9 (1) G的语言L（G）是什么？ (2) 给出句子0127、34和568的最左推导和最右推导。
8. 写一个文法，使其语言是奇数集，且每个奇数不以0开头。
9. 写一个上下文无关文法CFG，使其语言是能被5整除且不以0开头的无符号整数的集合。（
如｛5,10,15，?.｝）
10. 证明下面的文法是二义的： S→ｉSｅS |ｉS | ｉ 11. 某程序设计语言的表达式由运算符θ1、θ2、θ3、 标识符、（、）组成，其中θ1和θ2的优先级相同，θ3
的优先级低于θ1、θ2的优先级，优先级相同的运算符从右往左 计算，可以用括号改变运算的顺序，则下述四种文法中哪一个可以描述上述的表达式文法？ 设E为识别符号，终结符号集={θ1、θ2、θ3、 （、）、I}，非终结符号集={E、T、F}。 a. E→T|Eθ1T|Eθ2T T→F|Tθ3F F→(E)|I b. E→T|Tθ1E|Tθ2E T→F|Fθ3T
F→(E)|I
c. E→T|Eθ3T
T→F|Tθ1F|Tθ2F F→(E)|I
d. E→T|Tθ3 E
T→F|Fθ1T|Fθ2T F→(E)|I
解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
第三章 词法分析
一.填空题
1. 词法分析器对扫描缓冲区进行扫描时一般用两个指示器，一个_______________________ __________；另一个_____________________________________。 ————————————————————————————；————————— —————————————————___________________________;
2. 一个确定性有限自动机DFA M的化简是指：寻找一个状态数比M少的DFA M’，使得______
__________。
3. 词法分析器所的输出常表示成如下形式的二元式：（______________，_______________ __）。
4. 一个状态转换图只包含有限个状态，其中有一个被认为是________，而且实际上至少有 一个________。
5. 把状态转换图用程序实现时，对于含有回路的状态结点来说，可以让它对应一个_______ ______________________________程序段。
6. 词法分析阶段的任务式从左到右扫描_____________，从而逐个识别______________ 。
7. 如果一个种别只含有一个单词符号，那么，对于这个单词符号，__________就可以完全 代表它自身了。
8. 单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比 如，对于某个标识符，常将_________________________________________________作为其属 性值。
9. 单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比 如，对于常数，常将__________________________________________作为其属性值。
10. 如果一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码以 外，还应给出有关__________________________ 。
11. 如果_______________________________，则认为这两个正规式等价。
12. 对于?*中的任何符号串?，如果存在一条从初态结点到某一终态结点的通路，且________ ___________________________，则称?被该自动机所接受（识别）。
13. 一个Lex源程序主要包括两部分，一部分是___________________________，另一部分是_
______________________________ 。
14. 一个DFA可用一个矩阵表示，该矩阵的行表示______________，列表示_______________ ，矩阵元素表示_____________ 。这个矩阵叫状态转换矩阵。
15. 对于词法分析程序来说，当程序到达“错误处理”时，意味着现行状态i和当前所面临的
输入串不匹配。如果后面还有状态图，出现在这个地方的代码应该为： _____________________________________________________________________________
______________。
