loading作 业
一、选择题
1.、程序中出现的错误常数 3.14.15属于__(A)__。
(A) 语法错误 (B) 词法错误 (C) 语义错误 (D) 警告错误
2、表达式α0
α
n 代表____(B)____
。
(A) 直接推导 (B) 广义推导 (C) 推导 (D) 间接推导
3、文法G2?({i,?,*,(,)},{E,T,F},E,?) 其中：产生式P为：
E?E?T|TT?T*F|F F?(E)|i则句型T+T*i+F中的句柄是__(A)___。
(A) T (B) i (C) T*i (D) i+F
4、文法S?AB|AS,A?aA|a,B?b与下列哪个正规式等价__(B)___。
(A)aa*b? (B)aa*b (C)(ab)* (D) a(ab)*；
第二题：（清华大学年考研试题）已知文法G[S]为： S → dAB A → aA | a B → Bb | ε
G[S]产生的语言是什么？（请用自然语言或表达式描述语言特征） 答案：da+b*
第三题：（1） 构造一个文法G，使得：L(G)={a2mbm|m>0}
（2） 构造一个文法G，使得：L(G)={an#bn | n>0} （3） 写出以0开头的8进制无符号整数的文法。
答案：(1) S→ aaSb | aab
(2) S→ aSb | a#b (3) S→ 0 N N→ DN | D D→0|1|2|3|4|5|6|7
四、有文法G[S]： S → a | ( T ) |ε T → T，S | S
（1）请给出句子 (a，(a，a)) 的最左、最右推导。 （2）请给出句子 (a，(a，a)) 的短语、直接短语和句柄。 答案：（1）最左推导：
S=>（T）
=>（T,S） =>（S，S） =>（a，S） =>（a，（T）） =>（a，（T，S）） =>（a，（S，S）） =>（a，（a，S）） =>（a，（a，a））
最右推导：
S=>（T）
=>（T，S） =>（T，（T）） =>（T，（T，S）） =>（T，（T，a）） =>（T，（S，a）） =>（T，（a，a）） =>（S，（a，a）） =>（a，（a，a））
（2）画出语法树：
短语：a、a、a、a,a、(a,a)、a,(a,a)、(a，(a，a))
直接短语：a、a、a 句柄：a (最左一个)
五、（复旦大学考研试题）给定文法G[E]： E → ?EE E → ?E E → a E → b E → c
答案： ? ? a ? bc 是G[E]的句子。 (1) (2) E=>-E
E=>-EE =>--EE =>--EE =>--aE =>--aE =>--a-EE =>--a-EE =>--a-bE =>--a-bE =>--a-bc =>--a-bc
(3) E=>-EE =>-Ec =>--EEc =>--E-Ec =>--E-bc =>--a-bc
（2）b