1、编译原理 期末总复习 2 选择、填空 3 计算机执行高级语言的方式有编译和解释 方式。 对于编译程序而言，输入数据是源程序， 输出结果是目标程序。 程序语言主要由语法和语义两方面定义。 4 上下文无关文法G是一个四元式（VT，VN ，S，P），其中VN 代表非终结符号集。 词法分析阶段的主要任务是扫描源程序， 识别出一个个的单词符号 自上而下分析方法会遇到的主要问题有左 递归和回溯。 设G是一个给定的文法，S是文法的开始符 号，如果S x，则称x是文法G的一个句型。 5 已知文法G：Ei | EAE，A+|* ，其中的 终结符号集包括i，+，* 编译程序是将高级语言程序翻译成汇编语 言或机器语
2、言程序。 文法G所产生的句子的全体是该文法所描述 的语言。 6 乔姆斯基定义的四种文法分别为0，1，2， 3四种类型或者（短语文法、上下文有关文 法、上下文无关文法、正规文法）。 自上而下语法分析方法的基本思想是：从 开始符号（根节点）出发，自上而下的为 输入串建立一棵语法树。 常见的中间语言形式有后缀式和三地址代 码、DAG图等。 五元式不属于常用的中间语言形式。 7 只含有综合属性的属性文法称S-属性文法 。 算符优先分析方法每次都是对最左素短语 进行规约。 LL（1）文法中第一个L的含义是从左到右 扫描输入串。 用高级语言书写的程序经编译后产生的程 序叫目标程序. 上下文无关文法G是一个
3、四元式（VT，VN ，S，P），其中S 代表开始符号 。 8 汇编程序是将汇编语言翻译成机器语言。 DMA 的五元式定义中S的含义是状态的集 合。 文法G所产生的句子的全体是该文法所描述 的语言 。 优化阶段的主要任务是对于前段产生的中 间代码进行加工变换，以期在最后产生高 效的目标代码。 9 算符优先分析方法每次都是对最左素短语 进行规约。 LL（1）文法中第二个L的含义是最左推导 。 10 简答题 11 编译程序的工作过程主要包括5个阶段，分 别为词法分析、语法分析、语义分析与中 间代码产生、优化和目标代码生成等。 12 有限自动机中DFA的定义：DFA M是一个 五元式 M=（S， ，S
4、0，F）， 1. S有限集，其中的每个元素称为一个 状态 2. 有穷字母表，其中的每个元素称为 一个输入字符 3. ：SS（即状态 sS，a， （S，a）唯一的确定下一状态） 4. s0S，唯一的初态 5. FS，是一个终态集（可空） 13 LL(1)文法满足的基本条件: （1）文法不含左递归； （2）对于文法中每一个非终结符号A的各个 产生式的候选首符集两两不相交。 14 属性文法以及属性的两个类别: 在上下文无关文法的基础上为每个文法符 号引入一组属性并配备属性的计算规则， 这样的文法就是属性文法。属性分综合和 继承属性。 15 高级语言执行有解释方式和编译方式，本 质区别是编译方式会产生
5、目标代码。 自上而下语法分析方法的基本思想是对于 任何输入串，试图用一切可能的办法从文 法的开始符号出发，自上而下的为输入串 建立一棵语法树 一个上下文无关文法的定义包含4部分即VT ，代表终结符号集；VN非终结符号集；S文 法的开始符号；P一组产生式。 16 设计题 17 构造正规式 1(0|1)*101 相应的DFA。 解析： （1）构造NFA： 18 （2）确定化： 19 令文法GS为： ST|S+T|S-T TF|T*F|T/F F(S)|k 给出k*(k+k)的最左推导和最右推导。 解析：（1）最左推导 S=T=T*F=F*F=k*F=k*(S)=k*(S+T)=k*(T+ T)=k
6、*(F+T)=k*(k+T)=k*(k+F)=k*(k+k) 20 最右推导： S=T=T*F=T*(S)=T*(S+T)=T*(S+F)=T*(S+k )=T*(T+k)=T*(F+k)=T*(k+k)=F*(k+k)=k*(k +k) 21 试写出表达式a*(b+c)的逆波兰式（要求写出详细 分析过程）。 解析： 先考虑b+c的后缀式为bc+ 然后将a加入，最终的后缀式为abc+* 22 一个简单台式计算器的属性文法如下表所示，请按 照该属性文法，构造表达式（3*7+2）*5的附注语 法树。 23 解析： 24 试写出表达式(A+B)*(C+D)的逆波兰式（要求写 出详细分析过程）。 解析： (A+B)*(C+D)的逆波兰式 先分析A+B的后缀式：AB+ C+D的后缀式为：C D + 然后综合：AB+ C D +*
