复习题已看编译原理试题.pdf

编译原理试题及答案

一、对于文法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集；

⑵(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()

{int*i=f();

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

}

程序运行结果为：theresultis26157,

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

本课程的试题和答案