编译原理-第一、二章测验(答案)

编译原理第一、二章单元测验（答案）姓名学号班级一．填空（40分）1.编译系统一般可以分为①词法分析②语法分析③语义分析及中间代码生成④优化处理⑤目标代码生成等5大部分组成，其中①词法分析②语法分析⑤目标代码生成是每个编译程序必不可少的，而③语义分析及中间代码生成④优化处理则是可有可无的。这5个部分在工作过程中都会涉及到⑥表格处理⑦出错处理2.中间代码生成所依据的是语言的语义规则3.在使用高级语言编程时，首先可以通过编译程序发现源程序的全部语法错误和语义错误。4.由于受到具体机器主存容量限制，编译程序几个阶段的工作往往被组合成遍。5.编译程序绝大多数时间花在管理表格/扫描上。6.语法分析的依据是语法/语义规则。7.高级语言源程序执行有两种方式：即编译和解释。8.编译程序各阶段的工作往往是穿插进行的。9.文法G产生的句子的全体构成该文法所描述的语言。10.乔姆斯基定义的4种形式的文法中，0型又称短语结构文法可由图灵机识别，1型又称前后文（或上下文）有关文法可由线性限界自动机识别，2型又称前后文（或上下文）无关文法可由非确定下推自动机识别，3型包括左线性文法和右线性文法，可由有限自动机识别。11.最左推导是指对于一个推导序列中的每个直接推导，被替换的总是当前符号串中的最左非终结符号。12.产生式是用于定义语法范畴的一种书写规则。13.高级语言经过编译生成的语言一般是机器语言和汇编语言。14.句柄是指当前句型的最左直接短语。15.简单地说，文法中无用符号和无用产生式的删除必须满足：1.是否被用到过2.可否推出终结符号。16.规范推导是指最右推导，规范归约是指最左归约，二者互为逆过程。二．写一个语言，使其语言是奇数集，且每个奇数不以0开头。（20分）解法1：G=({S,A},{0,1,2,3,4,5,6,7,8,9},P,S)P:S→d1A∣d3A→d2A∣d3d1代表1-9的数字，d2代表0-9的数字，d3代表1，3，5，7，9中的任意一个。解法2：G=({N,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)P:N→AB∣BA→AC∣DB→1∣3∣5∣7∣9D→2∣4∣6∣8∣BC→0∣D三．证明下列文法是二义性文法：S→iSeS∣iS∣i（20分）解：1.不同最左（右）推导推导出相同的符号串2.对同一符号串有两颗不同语法树(答案多样化)四．写出下面语言的上下文无关文法：}0,1{1incbaLinn(20分)解：1.G1：N→S∣SAS→aSb∣abA→c∣Ac（或者A→c∣cA）2.G1：N→S∣SAS→aSb∣abA→Ac∣ε（或者A→cA∣ε）再消除ε，得到答案1