编译原理试题一、填空题 1、汇编程序将________翻译成________；编译程序将________翻译成________。 2、编译程序工作工程可以划分为______、______、______、______和______等5个基本阶段，同时还会伴有______和______。
3、对编译程序而言，输入数据是______，输出数据是______。
4、已知文法G[E]：E—>T|E+T|E-F，T－>F|T*F|T/F，F—>(E)|I，(“,”是间隔符号，不是文法中的符号)。该文法的开始符号（识别字符）是______，终结符号集合VT是______，非终结符号结合VN是______，句型T+T*F+i的短语有____________。该文法消除直接左递归，改写后的文法为E－>________，T－>________，F－>________。
5、Chomsky定以来寺中形式语言的文法分别为：________文法（又称________文法）、________文法（又称________文法）、________文法（又称________文法）、________文法（又称________文法）。 6、编译过程中扫描器所完成的任务是从________中识别出一个个具有________。 7、确定的有穷自动机是一个________，通常表示为________。
8、LL(k)分析中，第一个L的含义是________，第二个L的含义是________，“k”的含义是________。
9、LL(1)分析中，第一个L的含义是________，第二个L的含义是________，“1”的含义是________。
10、LR(0)分析中，“L”的含义是________，“R”的含义是________，“0”的含义是________。
11、SLR(1)分析中，“L”的含义是________，“R”的含义是________，“1”的含义是________。
12、LR(1)分析中，“L”的含义是________，“R”的含义是________，“1”的含义是________。
13、算术表达式：a*(-b+c)的逆波兰式表示为：________。
14、算术表达式：a＋b*(c+d/e)的逆波兰式表示为：____________。
15、在编译程序中安排中间代码生成的目的是__________和___________。 16、语法制导的翻译程序能同时进行________分析和________分析。
17、根据所涉及的程序范围，优化可分为________、________、________三种。 二、简答题
1、有人认为编译程序的词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成五个组成部分是缺一不可的，这种看法正确吗？说明理由。 2、多边扫描的程序是高质量的编译程序，优于单遍扫描的编译程序，对吗？为什么？
3、LR分析器与优先分析器在识别被归约串时的主要异同时什么？ 三、给出生成下述语言的上下文无关的文法 {1n0m1m0n|n，m>=0}
{WaWr|W属于{0|1}*，Wr表示W的逆} 四、给出生成下列语言的三型文法： {an|n>=0}
{anbm|n，m>0}
{anbmck|n，m，k>=0}
五、构造正规式1(0|1)*101相应的最小DFA。 六、构造正规式b(a|b)*bab相应的最小DFA。
七、已知文法G[S]：S－>aH；H－>aMd|d；M－>Ab|ε；A－>aM|e。 1、求每个非终结符号的FIRST集和FOLLOW集；
2、判定该文法是否为LL(1)文法，如是，构造LL(1)预测分析表； 3、若是LL(1)文法，请给出输入串aaabd＃的预测分析过程，并说明该输入是G[S]的句子。
八、已知文法G[B]：B－>BoT|T；T－>TaF|F；F－>nF|(B)|t|f。 1、计算G[B]的FIRSTVT和LASTVT；
2、构造G[B]的算符优先关系表并说明G[B]是否为算符有限文法；
3、若是算符优先文法，请给出输入ntofat#的分析过程，并说明该输入是G[B]的句子。
九、文法G[S]：S－>AB；A－>aBa|ε；B－>bAb|ε。
1、引入产生式S’->S，对文法进行改造为G[S’],计算G[S’]的First和Follow集，由此判断该文法是否是SLR(1)文法；
2、构造G[S’]的项目集族和识别活前缀的DFA； 3.若是SLR(1)文法，请构造它的分析表； 4.给出输入baab#的SLR(1)分析过程。 十、对下图的流图：
1、求出流图个节点的n的必经节点集D(n)； 2、求出流图的回边； 3、求出流图中的循环。
十一、将下面的程序段划分为基本块并作出其程序流图。 Read A，B F:=1 C:=A*A D:=B*B
If C L1: E:=B*B F:=F+2 Write E If E>100 goto L2 Halt L2: F:=F-1 Goto L1 十二、有下面基本块： S0:=2 S1:=3/S0 S2:=T-C S3:=T+C R:=S0/S3 H:=R