lexp → atom | list
atom → number | identifier
list → ( lexp-seq )
lexp-seq → lexp-seq , lexp | lexp
a) 该文法的语言是什么?(1分)
逗号表达式
b) 消除左递归,得到新文法G'[lexp]。(1分)
lexp → atom | list
atom → number | identifier
list → (lexp-seq)
lexp-seq → lexp lexp-seq'
lexp-seq' → lexp lexp-seq' |
c) 为新文法的每个非终结符构造First集合和Follow集合。(2分)
First(lexp) = {number, identifier, ( }
First(atom) = {number, identifier}
First(list) = { ( }
First(lexp-seq) = {number, identifier, ( }
First(lexp-seq’) = {, number, identifier, ( }
Follow(lexp) = {number, identifier, (, ), $}
Follow(atom) = {number, identifier, (, ), $}
Follow(list) = {number, identifier, (, ), $}
Follow(lexp-seq) = { ) }
Follow(lexp-seq’) = { ) }
a) 写出表达该集合的正规表达式。(1分)
a(a|b)*a
b) 将该正规表达式转换成NFA。(1分)
c) 将得到的NFA转换成等价的DFA。(1分)
设DFA为D,则其转换表Dtran为\
NFA状态 | DFA状态 | a | b |
---|---|---|---|
{0} | A | B | 空 |
{1,2,3,4,6,9,10} | B | C | D |
{3,4,5,6,8,9,10,11} | C | C | D |
{3,4,6,7,8,9,10} | D | C | D |
如图:
d) 将得到的DFA转换成等价的正规文法。(1分)
A0→aA1
A1→aA1|bA1|aA2
A2→
\
a)L(G1) = { | n≥1, i≥0} (1分)
S→AB
A→aAb|ab
B→cB|
\\
b)L(G2) = { | m, n≥0} (1分)
S→1S1|1A1
A→0A0|
S → aSbS | bSaS |
是二义性文法,如对abab,有两个最左推导:
只考虑:八进制、十进制和十六进制整数,单精度与双精度的浮点数。考虑用正则定义简化表达式。(4分)
a)请写出相应的上下文无关文法。(1分)
E→E+T|E-T|T
T→T*F|T/F|F
F→(E)|dight
b)请对该文法进行适当改变,以满足递归下降算法的需要。(1分)
E→TE'
E'→+TE'|-TE'|
T→FT'
T'→*FT'|'FT'|
F→(E)|id
c)为修改后的整个文法写出其递归下降算法的所有过程。(2分)