编译原理第二次作业

1.理解符号串与集合运算。

　　L={A,B, … ,Z,a,b, … ,z}

　　D={0,1, … ,9}

　　说明下表示的含义：

　　LUD:全部字母和数字的集合

　　LD：由一个字母跟一个数字组成的所有符号串的集合

　　L4：由4个字母组成的所有符号串的集合

　　L*：由字母组成的所有符号串的集合

　　D+：由一个或若干个数字组成的所有字符串的集合

　　L(LUD)*：以字母开头，后跟字母，数字注册的所有符号串的集合

2.文法G(Z):Z->aZb|ab定义的是什么样的语言？

　　因为Z—>aZb丨ab

所以Z—>ab —>aZb —>aaZbb —>aaa.....Zbbb....—>aaaa.....bbbb.......—>aⁿbⁿ(n>=1)

　　所以 L（G）={aⁿbⁿ丨n>=1}

3.写出教材22页例2.2中标识符的文法四元组形式(VN,VT,P,S)。

　　G=(VN,VT,P,S)

　　VN ={L(标识符)，D(字母)，H(数字)}，VT ={a,b,c,d,~~~,y,z,0,1,2,~~~,9} 　　

　　P={

　　　　<D>->a

　　　　<D>->b

　　　　<D>->c

　　　　……

　　　　<D>->z

　　　　<H>->1

　　　　<H>->2

　　　　<H>->3

　　　　……

　　　　<H>->9

　　}

　　S=<L>

4.写出下列表达式的最左推导、最右推导。

G(E):

E=> E + T | T

T=>T * F | F

F=>（E）| i

i*i+i
i+i*i
i+(i+i)

注意观察最左和最右推导过程的不同。

(1)

　　最左：

　　E -> E+T -> T+T - > T*F+T -> F*F+T -> i*F+T -> i*i+T -> i*i+F -> i*i+i

　　最右：

　　E -> E + T -> E+F -> E+i -> T+i -> T*F+i -> T*i+i -> F*i+i -> i*i+i

(2)

　　最左：

　　E -> E+T -> T+T - > F+T -> i+T -> i+T*F -> i+F*F -> i+i*F -> i+i*i

　　最右：

　　E -> E + T -> E+T*F -> E+T*i -> E+F*i-> E+i*i -> T+i*i -> F+i*i -> i+i*i

(3)

　　最左：

　　E-> E+T -> T+T-> F+T -> i+T-> i+F-> i+(E) -> i+(E+T) -> i+(T+T) -> i+(F+T) -> i+(i+T) -> i+(i+F) -> i+(i+i)　　

　　最右：

　　E-> E+T -> E+F -> E+(E) -> E+(E+T) -> E+(E+F) -> E+(E+i) -> E+(T+i) -> E+(F+i) -> E+(i+i) -> T+(i+i) -> F+(i+i) ->i+(i+i)