编译原理试题及答案——加强版 .pdfVIP

编译原理试题及答案

高级版

一、对于文法G[S]：

S→1A|0B|εA→0S|1AAB→1S|0BB

⑴(3分)请写出三个关于G[S]的句子；

⑵(4分)符号串11A0S是否为G[S]的句型？试证明你的

结论。

⑶(3分)试画出001B关于G[S]的语法树。

二、请构造一个文法，使其产生这样的表达式E：表达式中只含有

双目运算符+、*，且+的优先级高于*，+采用右结合，*采

用左结合，运算对象只有标识符i，可以用括号改变运算符优先级。

要求给出该文法的形式化描述。

三、设有语言L={α|α∈{0,1}+，且α不以0开头，但以00

结尾}。

⑴试写出描述L的正规表达式；

⑵构造识别L的DFA（要求给出详细过程，并画出构造过程中

的NDFA、DFA的状态转换图，以及DFA的形式化描述)。

四、给定文法G[S]：

S→AB

A→aB|bS|c

B→AS|d

⑴(6分)请给出每一个产生式右部的First集；

1

⑵(3分)请给出每一个非终结符号的Follow集；

⑶(8分)请构造该文法的LL(1)分析表；

⑷(8分)什么是LL(1)文法？该文法是LL(1)文法吗？为

什么？

五、给定文法G[S]：

S→SaA|a

A→AbS|b

⑴请构造该文法的以LR(0)项目集为状态的识别规范句型活前

缀的DFA。

⑵请构造该文法的LR(0)分析表。

⑶什么是LR(0)文法？该文法是LR(0)文法吗？为什么？

⑷什么是SLR(1)文法？该文法是SLR(1)文法吗？为什么？

六、给定下列语句：

ifa+bc

thenx:=a*(b-c)+(b*c-d)/e

⑴写出其等价的逆波兰表示；

⑵写出其等价的四元式序列。

七、已知下列C语言程序：

int*f()

{inta=100;returna;

}

main()

2

{int*i=f();

chara[]=“compiler”;printf(“theresultis%d\n”,

*i);

}

程序运行结果为：theresultis26157,

请解释为什么程序运行的结果不是期望的“theresultis

100”？

1.1三个0和1数量相等的串

1.2S=1A=11AA=11A0S

1.3

第二题构造文法如下:

G[E]=({+,*,(,),i},{E,F,T},P,E)，其中P为：

E→E*F|FF→T+F|TT→(E)|i

第三题（1）正规表达式：1(0|1)*00

（2）第一步：将正规表达式转换为NDFA

3

第二步：将NDFA确定化为DFA：

造表法确定化（3分）确定化后DFAM的状态转换表(2分)

状态输入I0I1t01

[S]—[A,D,B]q0—q1

[A,D,B][D,B,C][D,B]重新命名q1