用户工具

站点工具


01-基础学习:课程:编译原理:期中考试

编译原理期中考试

1. 考虑以下文法G[lexp]:

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' | epsilon

c) 为新文法的每个非终结符构造First集合和Follow集合。(2分)

First(lexp) = {number, identifier, ( }
First(atom) = {number, identifier}
First(list) = { ( }
First(lexp-seq) = {number, identifier, ( }
First(lexp-seq’) = {epsilon, number, identifier, ( }
Follow(lexp) = {number, identifier, (, ), $}
Follow(atom) = {number, identifier, (, ), $}
Follow(list) = {number, identifier, (, ), $}
Follow(lexp-seq) = { ) }
Follow(lexp-seq’) = { ) }

2.对语言集合:以a开头与结尾的、由a和b组成的字符串的集合:

a) 写出表达该集合的正规表达式。(1分)

a(a|b)*a

b) 将该正规表达式转换成NFA。(1分)

c) 将得到的NFA转换成等价的DFA。(1分)

设DFA为D,则其转换表Dtran为😕\

NFA状态 DFA状态ab
{0} A B
{1,2,3,4,6,9,10} B CD
{3,4,5,6,8,9,10,11} C CD
{3,4,6,7,8,9,10} D CD

如图:
d) 将得到的DFA转换成等价的正规文法。(1分)

A0→aA1
A1→aA1|bA1|aA2
A2→epsilon

\

3.请给出以下语言对应的上下文无关文法

a)L(G1) = {{a^n}{b^n}{c^i} | n≥1, i≥0} (1分)

S→AB
A→aAb|ab

B→cB|epsilon

 \\

b)L(G2) = {{1^n}{0^m}{0^m}{1^n} | m, n≥0} (1分)

S→1S1|1A1
A→0A0|epsilon

4.请说明以下文法是否是二义性文法:(2分)

S → aSbS | bSaS | epsilon

是二义性文法,如对abab,有两个最左推导:

5.请写出由所有C语言数值常量组成的集合的LEX格式的正规表达式。

只考虑:八进制、十进制和十六进制整数,单精度与双精度的浮点数。考虑用正则定义简化表达式。(4分)

6.考虑整数的加、减、乘、除四种算术运算表达式集合

a)请写出相应的上下文无关文法。(1分)

E→E+T|E-T|T
T→T*F|T/F|F
F→(E)|dight

b)请对该文法进行适当改变,以满足递归下降算法的需要。(1分)

E→TE'
E'→+TE'|-TE'|epsilon
T→FT'
T'→*FT'|'FT'|epsilon
F→(E)|id

c)为修改后的整个文法写出其递归下降算法的所有过程。(2分)

01-基础学习/课程/编译原理/期中考试.txt · 最后更改: 2020/04/07 06:34 由 annhe