(b)为该文法写一个等价的非二义文法。它给予算符*、连接和|的优先级和结合性同2.2节中定义
的一致。
(c)按上面两个文法构造句子ab|b*a的分析树。
3.5 下面的条件语句文法
stmt→ifexprthenstmt|matched stmt
matched stmt→ifexprthenmatched stmtelsestmt|other
试图消除悬空else的二义性,请你证明该文法仍然是二义的。
3.6 为字母表 Σ={a,b}上的下列每个语言设计一个文法,其中哪些语言是正规的?
(a)每个 a后面至少有一个b跟随的所有串。
(b)a和b的个数相等的所有串。
(c)a和b的个数不相等的所有串。
(d)不含 abb作为子串的所有串。
*(e)形式为xy且x≠y的所有串。
3.7 我们可以在文法产生式的右部使用类似正规式的算符。方括号可以用来表示产生式的可选部
分,例如可以用
stmt→ifexprthenstmt[elsestmt]
表示 else子句是可选的。通常,A→α[β]γ等价于两个产生A→αβγ和A→αγ。
花括号用来表示短语可重复出现若干次(包括零次),例如
stmt→beginstmt{;stmt}end
表示处于begin和end之间的由分号分隔的语句表。通常,A→α{β}γ等价于A→αβγ和B→βB|ε。
概念上,[β]代表正规式 B|ε,{β}代表β
*
,现在我们把它们推广为允许文法符号的任何正规式出现在
产生式的右部。
(a)修改上面的stmt产生式,使得每个语句都以分号终止的语句表出现在产生式右部。
(b)给出上下文无关的产生式,它和 A→B
*
a(C|D)产生同样的串集。
(c)说明如何用一组有限的上下文无关产生式来代替产生式A→γ,其中 γ是正规式。
3.8 (a)消除习题3.1文法的左递归。
(b)为(a)的文法构造预测分析器。
3.9 为习题3.3的文法构造预测分析器。
·601· 第3章 语 法 分 析
2021-10-10 20:38:30
2.05MB
编译原理
1