编译原理习题集1.docVIP

目 录 第一章 编译概述 1 第二章 文法和语言 2 第三章 词法分析 6 第四章 自顶向下语法分析方法 13 第五章 算符优先分析法 17 第六章 LR(K)分析法 22 第七章 语义分析 30 第九章 运行时刻环境 39 第十章 代码优化 46 第一章 编译概述 1、画出编译程序的总体结构图，简述其部分的主要功能。 [答案] 编译程序的总框图见下图。 图1编译程序的总体结构图 其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果上单词符号。 语法分析器对单词符号串进行语法分析（根据语法规则进行推导或归纳），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。 语义分析及中间代码产生器，按照语义规则对语法分析器归纳出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。 优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。 目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件相关的机器能识别的语言，即目标程序，才能在机器上运行。 表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断地和表格打交道。 出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户。 2、计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么? [答案] 计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。 像Basic之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反复。 总而言之，是边翻译边执行。 像C，Pascal之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上看，编译型的高级语言比解释型的高级语言更快。 第二章 文法和语言 1、文法G[S]为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 [答案] S=Ac=abc 或S=aB=abc 所以L(G[S])={abc} 2、文法G[N]为： N→D|ND D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ [答案] G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=ND=NDD.... =NDDDD...D=D......D 3、已知文法G[S]: S→dAB A→aA|a B→ε|bB 问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？ [答案] 正规式是daa*b*； 相应的正规文法为(由自动机化简来)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε 4、已知文法G[Z]： Z→aZb|ab 写出L(G[Z])的全部元素。 [答案] Z=aZb=aaZbb=aaa..Z...bbb= aaa..ab...bbb L(G[Z])={anbn|n=1} 5、写一文法，使其语言是偶正整数集合。 要求： (1)允许0开头；(2)不允许0开头。 [答案] (1)允许0开头的偶正整数集合的文法 E→NT|G|SFM T→NT|G N→D|1|3|5|7|9 D→0|G G→2|4|6|8 S→NS|ε F→1|3|5|7|9|G M→M0|0 (2)不允许0开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 6、已知文法G： E→E+T|E-T|T T→T*F|T/F|F F→(E)|i 试给出下述表达式的推导及语法树 (1)i; (2)i*i+i (3)i+i*i (4)i+(i+i) [答案] (1)E=T=F=i (2)E=E+T=T+T=T*F+T