下载文档原格式
(1) 简述规范归约的基本思想。
（第五章课件第5张）用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。
(2) 阐述编译程序各个组成部分主要完成的工作。
（课本P2~P4）词法分析的任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。
语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位。
语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译。
优化：在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。
目标代码生成：把中间代码变换成特定机器上的低级语言代码。
(3) 什么是编译器的前端和后端，这样划分有何意义？（课本P7）编译器粗略分为词法分析，语法分析，类型检查，中间代码生成，代码优化，目标代码生成，目标代码优化。
把中间代码生成及之前阶段划分问编译器的前端，那么后端与前端是独立的。
后端只需要一种中间代码表示，可以是三地址代码或四元式等，而这些都与前端生成的方式无关。
也就是不论你前端是用fortran 还是c/c++,只要生成了中间代码表示就可以了，后端是不管你是用哪种语言生成的。
(4) 乔姆斯基把文法分为哪几种类型？对这几种类型文法作简要说明。
（课本P34）把文法分成四种类型：0，1，2，3型。
与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。
0型(短语文法，图灵机)：产生式形如：α→β其中：∈α (VT ⋃ VN)*且至少含有一个非终结符；∈β (VT ⋃ VN)*1型(上下文有关文法，线性界限自动机)：产生式形如：α→β其中：|α| ≤ |β|。
仅Sε→例外，但此时S不得出现在任何产生式的右部。
2型(上下文无关文法，非确定下推自动机)：产生式形如： A →β其中：A∈ VN；∈β (VT ⋃ VN)*。
编译原理复习重点含答案编译原理复习重点编译原理是计算机科学中的一门重要课程，它研究的是如何将高级语言程序转化为机器语言的过程。
在编译原理的学习中，我们需要掌握一些重要的概念和技术，以便能够理解和应用编译器的工作原理。
本文将重点介绍编译原理的几个重要主题，并提供相应的答案供参考。
一、词法分析词法分析是编译器的第一个阶段，它的任务是将输入的字符序列划分为一个个有意义的词素（token）。
词法分析器通常使用有限自动机（DFA）来实现，其工作原理是将输入字符序列逐个读入，并根据事先定义好的词法规则进行匹配和识别。
常见的词法单元包括关键字、标识符、常量、运算符等。
常见的词法规则包括：1. 关键字：例如if、while、for等。
2. 标识符：由字母、数字和下划线组成，且以字母或下划线开头。
3. 常量：包括整数常量、浮点数常量、字符常量和字符串常量等。
4. 运算符：例如加法运算符+、减法运算符-等。
5. 分隔符：例如逗号、分号等。
词法分析的结果是一个个词法单元，每个词法单元包含一个词素和对应的词法单元类型。
例如，对于输入程序"int a = 10;"，词法分析的结果可能是[("int", "关键字"), ("a", "标识符"), ("=", "运算符"), ("10", "整数常量"), (";", "分隔符")]。
二、语法分析语法分析是编译器的第二个阶段，它的任务是将词法分析器输出的词法单元序列转化为抽象语法树（AST）。
语法分析器通常使用上下文无关文法（CFG）来描述语言的语法结构，并使用递归下降、LL(1)分析、LR分析等算法进行分析。
常见的语法规则包括：1. 表达式：例如算术表达式、布尔表达式等。
第1部分一简答题1．编译程序按功能分为哪几个阶段？各个阶段的主要功能？2．实现高级语言程序的途径有哪几种？它们之间的区别？3．给出描述非0数字作为开始符的奇数字符串的正则表达式或正则式。
4．判断字符串a n b n（n >0）是否可用确定自动机识别？如果能，则画出自动机，否则说明原因5．对如下文法：G[S]：S → a b S | a a B | a dB → b b B | b分别给出句子abaabbb和ad的句柄6．有如下文法，给出每个产生式的Predict集。
P → begin S endS → id := E ; S |E → n | id7．什么是可规约活前缀？举一例说明。
8．通过合并LR（1）文法中的同心状态得到的LALR(1)文法可能会产生哪些冲突？一定不会产生哪些冲突？9．设对偶表（L，N）分别表示程序在当前位置的层数和偏移量，确定下面程序段中括号部分的内容。
假设系统规定整型(int)变量占1个单元，实型(real)变量占2个单元。
(L, N) Type at = array of [1..10] of int;(①) var x ：real;(②) function f ( ( ？,M) var a: at,(③) b: at,(④) var x: real ) : int10．给出活动记录空间结构?并给出各部分的存储对象？11．有如下文法：G[S]：S → ( L ) | aL → S PP → , S P |给出该文法的动作文法打印每个a的嵌套深度。
例如（a，（a），（a））打印1，2，2。
12．文法可分为几类；各举一例。
13．Display表的作用？14．如下是当前执行某个过程时的活动记录，设变量x的层数和偏移量分别为L和Off，说明如何访问变量x。
15．当实参为变量，形参分别为变参和值参时，传参的区别。
二、说明如下文法是否是LL（1）文法，若不是，将其转换为LL（1）文法。
编译原理期末总结复习编译原理期末总结复习篇一：一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。
将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。
2.请写出文法的形式定义？答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S）–其中Vn表示非终结符号– Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ– S是开始符号，–P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*)3.语法分析阶段的功能是什么？答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。
确定整个输入串是否构成语法上正确的程序。
4.局部优化有哪些常用的技术？答：优化技术1—删除公共子表达式优化技术2—复写传播优化技术3—删除无用代码优化技术4—对程序进行代数恒等变换（降低运算强度）优化技术5—代码外提优化技术6—强度削弱优化技术7—删除归纳变量优化技术简介——对程序进行代数恒等变换（代数简化）优化技术简介——对程序进行代数恒等变换（合并已知量）5．编译过程分哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。
每个阶段把源程序从一种表示变换成另一种表示。
6. 什么是文法？答：文法是描述语言的语法结构的形式规则。
是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。
7. 语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。
8.代码优化须遵循哪些原则？答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果9.词法分析阶段的功能是什么？答：逐个读入源程序字符并按照构词规则切分成一系列单词任务：读入源程序，输出单词符号—滤掉空格，跳过注释、换行符—追踪换行标志，指出源程序出错的行列位置—宏展开，……10.什么是符号表？答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。
编译原理总复习总复习■第1章1、编译程序是⼀种翻译程序，它将⾼级语⾔所写的源程序翻译成等价的机器语⾔或者汇编语⾔的⽬标程序。
2、编译程序是计算机系统中重要的系统软件！3、解释程序与编译程序的主要区别是解释程序在执⾏过程中不产⽣⽬标程序。
4、编译的各个阶段。
答：整个编译过程可以分为5个阶段：词法分析，语法分析，语义分析及中间代码⽣成，代码优化和⽬标代码⽣成。
5、编译程序的结构框图或步骤。
6、遍（趟）：是对源程序或源程序的中间结果从头到尾扫描⼀遍，并作有关加⼯处理，⽣成新的中间结果或⽬标程序的过程。
■第2章1、符号串的基本运算。
2、简单的说⽂法由产⽣式组成；产⽣式中的符号分为两类：终结符号和⾮终结符号。
3、推导（最左、最右）、句型、句⼦、短语、句柄4、乔姆斯基层次中：L3 ? L2 ? L1 ? L0■第2章例题已知⽂法G[E]：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i（1）该⽂法的开始符号是什么？（2）请给出该⽂法的终结符号集合VT和⾮终结符号集合VN。
（3）找出句型T+T*F+i的所有短语、直接（简单）短语、句柄。
■第3章1、词法分析程序的输出是单词符号序列。
2、DFA的三种表⽰形式——状态转移图、状态转换表和五元组表⽰（Q, ∑, f, S, Z ）；3、正规式向DFA的转换：（1）正规式——NFA;（转换原则见下页）（2）NFA——DFA；（3）DFA的最⼩化。
4、DFA向正规式的转换。
正则式向NFA转换的原则：例：构造与正则表达式R=ba(a|b)*等价的状态最少的DFA，并写出该DFA的五元组形式或状态转换表。
■第4章1、语法分析⽅法的各种分类；2、LL(1)分析⽅法。
提⽰：在此算法中注意First集和Follow集的求法。
并且⼀定要注意分析过程中步骤要完整。
（分析步骤见下页总结）例：⽂法：S?a|^|(T) T?T,S|S试判断该⽂法是否是LL(1)⽂法。
习题4：P100 4.3 4.7 4.9■LL(1)分析⽅法相关知识总结1、消除⽂法中的左递归或提取左因⼦；（1）简单直接左递归的消除A →βA’A →Aα| β→A’ →αA’| ε（2）将⽂法G：A→αβ|αγ提取左因⼦。
编译原理的复习提纲1.编译原理=形式语言+编译技术2.汇编程序：把汇编语言程序翻译成等价的机器语言程序3.编译程序：把高级语言程序翻译成等价的低级语言程序4.解释执行方式：解释程序，逐个语句地模拟执行翻译执行方式：翻译程序，把程序设计语言程序翻译成等价的目标程序5.计算机程序的编译过程类似，一般分为五个阶段：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成词法分析的任务：扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等）语法分析是：在词法分析的基础上的，语法分析不考虑语义。
语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。
语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。
语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。
所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序编译程序结构包括五个基本功能模块和两个辅助模块6.编译划分成前端和后端。
编译前端的工作包括词法分析、语法分析、语义分析。
编译前端只依赖于源程序，独立于目标计算机。
前端进行分析编译后端的工作主要是目标代码的生成和优化后端进行综合。
独立于源程序，完全依赖于目标机器和中间代码。
把编译程序分为前端和后端的优点是：可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。
7.汇编器把汇编语言代码翻译成一个特定的机器指令序列第二章1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，X n，2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20 A0 ={ε}3.重写规则，简称规则。
1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。
（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。
（4）优化器，对中间代码进行优化处理。
（5）目标代码生成器，把中间代码翻译成目标程序。
（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。
（7）出错管理，把错误信息报告给用户。
编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。
（2）。
语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。
（3）语义分析与中间代码产生。
任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
（4）优化。
任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
（5）目标代码生成。
任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。
2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。
b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。
复习汇总一、第一章概述1.文法与自动机的等价1)0型文法—图灵机2)1型文法—线性有界非确定图灵机3)2型文法—非确定下推自动机4)3型文法—有限状态自动机2.编译技术的应用1)语法制导的结构化编辑器2)程序格式化工具3)软件测试工具4)程序理解工具5)高级语言的翻译工具6)等等3.从面向机器的语言到面向人类的语言（结合第二章第9小点理解）1)面向机器的语言：机器指令，汇编语言2)面向人类的语言：通用程序设计语言，数据查询语言，形式化描述语言（正规式,产生式）等等。
4.各语言的分类（结合第二章第9小点理解）1)过程式语言，面向对象语言：通用程序设计语言。
2)函数语言：面向特点领域的，递归特性。
例如LISP语言3)说明性，非算法式语言：LEX/YACC,SQL。
4)脚本式语言：Shell语言5.语言之间的转换（李静PPT41）1)高级语言之间的转换一般称为预处理或转换。
2)高级语言翻译成汇编语言或机器语言称之为编译。
3)把汇编语言翻译成机器语言称之为汇编。
4)将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之为交叉汇编。
5)把机器语言翻译成汇编语言称之为反汇编。
6)把汇编语言翻译成高级语言称之为反编译。
6.编译器和解释器1)编译器●源程序的翻译和翻译后的程序的运行是两个不同的阶段。
◆编译阶段：用户输入源程序，经过编译器的处理，生成目标程序。
◆目标程序的运行阶段：根据要求输入数据，得出结果。
2)解释器（凡是可以采用编译器的地方均可以采用解释器）●解释器把翻译和运行结合到一起，编译一段源程序，紧接着就执行它。
这种方式称为解释。
7.解释器的优点（对比与编译器）1)具有较好的动态特性。
2)具有较好的移植特性。
8.解释器的缺点（对比于编译器）1)相比于编译器需花费大量的时间。
2)占用更多的内存空间。
9.编译器的工作阶段（结合第二章6小点红色部分理解）1)源程序->词法分析器->语法分析器->语义分析器->中间代码生成器->代码优化器->目标代码生成器->目标代码2)工作过程中的每个阶段均采用了符号表管理器，出错处理器。
编译原理复习《编译原理》第⼀章：绪论1.翻译器：把⼀种语⾔变换到另外⼀种语⾔的软件。
这两种语⾔分别称为源语⾔和⽬标语⾔。
2.编译器：⼀种翻译器，它的⽬标语⾔⽐源语⾔低级。
3.典型的编译器可以划分成6个逻辑阶段：词法分析，语法分析，语义分析，中间代码⽣成，代码优化，代码⽣成。
4.按照对⽬标机器的依赖性，把编译过程分成前端（依赖于源语⾔，独⽴于⽬标机器）和后端（依赖于⽬标机器，独⽴于源语⾔,只与中间语⾔有关（从中间代码⽣成⽬标代码））。
5.前端包括：词法分析，语法分析，语义分析，中间代码⽣成。
6.后端包括：代码优化，代码⽣成。
7.解释器：不同于编译器的另⼀类语⾔处理器，直接执⾏源程序所指定的运算。
解释器的执⾏效率⽐编译器低，因为解释器⽆法解开循环。
8.遍：编译的⼏个阶段常⽤⼀遍（pass）扫描实现，⼀遍扫描包括读⼀个输⼊⽂件和写⼀个输出⽂件。
《编译原理》第⼆章：词法分析⼀些概念：1.词法单元：⼜称单词，是编程语⾔中合法的字符串。
2.词法记号：满⾜某种规则的词法单元，采⽤同⼀种记法——词法记号。
该规则称为模式。
3.模式：描述词法单元与词法记号对应关系的规则。
是描述源程序中某个记号的词法单元集合的规则。
4.字母表：符号的有限集合，例：∑={0,1}串：符号的有穷序列，例：0110,ε语⾔：字母表上的⼀个串集{ε,0,00,000,…},{ε},?正规式（运算符的优先级：*>连接运算>|）N F A是这样⼀个数学模型，包括1)状态集合S2)输⼊字母表∑3)转换函数m o v e:S?(∑?{ε})→P(S)4)唯⼀的初态s∈S5)终态集合F?SD F A是这样⼀个数学模型，包括1)状态集合S2)输⼊字母表∑3)转换函数m o v e:S?∑→S4)唯⼀的初态s∈S5)终态集合F?S第三章语法分析3.1 上下⽂⽆关⽂法上下⽂⽆关⽂法是四元组（V T , V N, S , P ）1) V T: 终结符集合(⾮空有限集合，记号名是其同义词)2) V N: ⾮终结符集合（⾮空有限集合）3) S : 开始符号4) P : 产⽣式集合，产⽣式形式 : A →α上下⽂⽆关⽂法没有强制的顺序关系。
编译原理复习《编译原理》复习README来源⽹络&书本&PPT整理截取了⽼师课上讲解or布置的题⽬⼀些题⽬懒得贴答案了，写了些注意事项第1 章引论运⾏编译程序的计算机：宿主机运⾏编译程序所产⽣的⽬标代码的计算机：⽬标机第1 题解释下列术语：（1）编译程序：如果源语⾔为⾼级语⾔，⽬标语⾔为某台计算机上的汇编语⾔或机器语⾔，则此翻译程序称为编译程序。
（2）源程序：源语⾔编写的程序称为源程序。
（3）⽬标程序：⽬标语⾔书写的程序称为⽬标程序。
（4）编译程序的前端：它由这样⼀些阶段组成：这些阶段的⼯作主要依赖于源语⾔⽽与⽬标机⽆关。
通常前端包括词法分析、语法分析、语义分析和中间代码⽣成这些阶段，某些优化⼯作也可在前端做，也包括与前端每个阶段相关的出错处理⼯作和符号表管理等⼯作。
（5）后端：指那些依赖于⽬标机⽽⼀般不依赖源语⾔，只与中间代码有关的那些阶段，即⽬标代码⽣成，以及相关出错处理和符号表操作。
（6）遍：是对源程序或其等价的中间语⾔程序从头到尾扫视并完成规定任务的过程。
第2 题⼀个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。
(区别编译程序的六个阶段)答案：⼀个典型的编译程序通常包含8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码⽣成程序、中间代码优化程序、⽬标代码⽣成程序、表格管理程序和错误处理程序。
其各部分的主要功能简述如下。
词法分析程序：输⼈源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。
语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。
语义分析程序：进⾏语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
中间代码⽣成程序：按照语义规则，将语法分析程序分析出的语法单位转换成⼀定形式的中间语⾔代码，如三元式或四元式。
中间代码优化程序：为了产⽣⾼质量的⽬标代码，对中间代码进⾏等价变换处理。
教材资料授课顺序：1教学目的：正确理解什么是编译程序；了解编译程序工作的基本过程及其各阶段的基本任务；熟悉编译程序总框；了解编译程序的生成过程和构造工具。
教学重点与难点：编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。
授课学时：2学时教学方式：多媒体讲授教学内容：第一章引论1.1什么是编译程序一、基本概念1、翻译程序：是指这样的一种程序，它能够把一种语言程序(源语言程序)转换成另一种功能等价的语言程序(目标语言程序)。
2、编译程序是一种翻译程序，其源程序是高级语言，目标语言程序是低级语言。
通常是一次性翻译方式。
如TC等高级语言编译程序。
3、解释程序也是一种翻译程序，它与编译程序的区别：立即执行源程序，通常是逐句翻译执行。
如BASIC、SQL、JA V A的BYTECODE解释程序等。
二、高级语言程序的处理过程高级程序设计语言程序的典型处理过程如下图所示：1.2编译过程和编译程序结构一、编译过程的阶段划分一般编译程序的工作过程按阶段进行，每个阶段将源程序从一种表示形式转换成另一种表示形式。
典型的阶段划分方法是将整个编译过程分为如下六个阶段：1、词法分析：任务：对构成源程序的字符串进行扫描和分解，识别出单词(如标识符等)符号。
输入：源程序输出：单词符号序列例子：有待分析源程序：main(){int x=10,y;}词法分析后的输出：1）保留字：main2）界符：左圆括号(3）界符：右圆括号)4）界符：左大括号{5)保留字：int6)标识符：x7)运算符：=8)常数：10 ，界符：，9)标识符：y10)界符：；11）界符：右大括号}2、语法分析任务：根据语言的语法规则对单词符号串(符号序列)进行语法分析，识别出各类语法短语(可表示成语法树的语法单位)，判断输入串在语法上是否正确。
输入：单词序列输出：语法分析后的单词序列3、语义分析任务：按语义规则对语法分析器归约出的语法单位进行语义分析，审查有无语义错误，为代码生成阶段收集类型信息，并进行类型审查和违背语言规范的报错处理。
一、问答题（共25分）1．什么是翻译程序？什么是编译程序？（4分）2．简述编译过程各阶段的主要任务。
（5分）3．什么是上下文无关文法？（3分）4．什么是语法制导翻译法? （3分）5．写出下列状态转换图对应的词法分析程序。
（5分）字母或数字6．写出下面表达式的逆波兰表示和四元式序列（5分）–(A-B)/D*(C/D+E)二、构造正规式1(0|1)*101相应的DFA.（共15分）三、语法分析题（50分）1．简述确定的和不确定的自顶向下语法分析的基本思想。
（10分）2．已知文法G(P)：（10分）P→begin d；X endX→d；X|sYY→；sY|ε（1）画出句型begin d；s；s Y end的语法树（2）写出该句型的短语、直接短语、句柄。
3．设文法G(S)：（30分）S→SaB | bBA→SaB→Ac（1）将此文法改造为LL(1)文法。
（2）构造各非终结符的First集和Follow集。
（3）为改造后的文法构造递归下降分析程序。
四、语义分析（10分）已知下列文法及其对应的语义动作，采用自下而上的翻译过程，分析当输入串是aacbb时，其输出是什么，写出分析过程。
1. A→aB { print “1”}2. A→c { print “10” }3. B→Ab { print “100”}一、问答题：1． 将一种语言翻译成另外一种语言的程序成为翻译程序。
将高级语言翻译成低级语言的程序称为编译程序。
2． 分为词法分析、语法分析、中间代码生成、代码优化、目标代码生成几个阶段（任务略） 3． 由一组终结符号，一组非终结符号、一个开始符号、一组产生式构成。
其中每个产生式形如：A →β，A 是非终结符，β是由终结符和非终结符构成的符号串。
4． 根据每个产生式所对应的语义子程序进行翻译的办法。
5．If （IsLetter （）） BeginWhile (IsLetter() or IsDigit())Begin Concat();GetChar();EndRetract();Code:=Reserve(); If (code=0)Begin Value:=InsertId(strToken);return ($ID,value);End Else return (code,-); end6．答：–(A-B)/D*(C/D+E) 逆波兰式：AB-@D/CD/E+*四元式序列： (-,A,B,T1) (-,T1,_,T2) (/,T2,D,T3) (/,C,D,T4) (+,T4,E,T5) (*,T3,T5,T6)二、解：确定化重新命名，令AB 为B 、AC 为C 、ABY 为DDFA ： 1三、1．（1）确定的自顶向下语法分析的基本思想：从文法的开始符号出发，根据当前的输入符号和其它信息，唯一地确定选用哪个产生式替换相应的非终结符往下推导，构造分析树。
可编辑修改精选全文完整版1.编译程序的工作过程一般可包括词法分析、语法分析、语义分析、中间代码产生与优化和目标代码生成等几个阶段，同时还有表格管理和出错处理。
2.LEX是用于词法分析的工具，Y ACC是用于语法分析的工具。
3.解释程序和编译程序的区别在于是否生成目标代码。
4.任一文法终结符集合和非终结符集合的交集是空集。
5.描述程序设计语言语法的BNF方法中，“：：=”表示定义为，“|”表示或，[W]表示W可出现0或1次，｛W｝表示W可出现n（n≥0）次。
6.已知文法G[G]: S→aSb|ab|ε，该文法描述的语言L(G)=｛a n b n|n≥0｝。
7.单词的描述工具有正规文法、正规式和有穷自动机，他们之间存在等价性。
8.高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符和界符。
9.正则式中的“|“表示或，“*”表示闭包。
10.自顶向下语法分析方法会遇到的主要问题有回溯，以及左递归带来的无限循环。
11.算符优先分析法每次归约当前句型的最左素短语，规范归约中每次归约的是当前句型的句柄。
12.对文法G[G]: S→a|b|cTc，T→S|TdS而言，FIRSTVT(T)=｛a,b,c,d｝。
13.活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
14.对文法G[G]: E→E*T|T, T→T+i|i的句子1+2*8+6进行归约后的结果为42（23，42）。
15.在LR(0),SLR(1),LR(1),LALR(1),四种文法中，描述能力最强的是LR(1)。
1.0型文法中每条规则左部至少包含一非终结符（√）。
2.3型文法一定是2型、1型、0型文法（√）。
3.对无二义性文法而言，无论最左推导还是最右推导，同一个句子的语法树是一样的。
4.若一个文法是递归的，则其语言中句子的个数必定是无穷个。
（√）5.文法规则右部的符号一定是终结符。
（×）6.语法树描述的是一个文法。
编译原理复习资料1、某操作系统下合法的文件名为：device:name.extension，其中第一部分(device:)和第三部分(.extension )可缺省，若device, name和extension都是字母串，长度不限，但至少为1,画出识别这种文件名的DFA。
用标记d表示任意字母。
d d图1接受文件名的DFA2、用两个不同最左推导来说明下面的文法是二义的。
S A S | bA S A | a答：句型aSAS的两个不同最左推导如下：S AS aS aAS aSASS AS SASASAS aSAS3、证明下面的文法S S A | AA a不是LL(1)文法，但是SLR(1)文法，并画出SLR(1)分析表。
答：该文法的第一个产生式表现出直接左递归，因此该文法不是LL(1)。
接受该文法的活前缀的DFA见下面右边；Follow( S) = {$}，Follow( S) = {$, a}，Follow( A)SLR(1)的。
5、下面是int i, j, k这样的类型声明的两种不同语法:T int | real TL L , id | id L如果用LL(1)分析方法，应该选择哪个文法？如果用某种简要说明理由。
答：对于LL(1)分析方法，两个文法都不合适，左边的文法是左递归的，右边文法有公共左因子。
修改右边文法来适应LL(1)分析的要求，相对来说比较容易一些，因为只要提公共左因子。
对于LR的各种分析方法，两个文法都适用，但是采用左边的文法更好一些。
用左边的文法时，分析器一边扫描一边归约，占用分析栈的空间较少。
而用右边的文法时，分析器要把所有的标识符都移进栈后才进行归约，因此使用较多的分析栈空间。
(结合语法制导的翻译，采用左边的文法还有好处：便于确定T的类型属性在栈中的位置。
) 6、在C语言中，3++和(id + id )++这样的表达式被编译时，编译器都会报告如下的错误：in valid lvalue in in creme nt说明左值不能为数值或表达式。
现有如下简化的C语言表达式文法： E E + E | (E ) | E ++ | id | num请写一个语法制导定义或翻译方案，检查++的运算对象是否合法。
答：给非终结符 E 一个综合属性v,其值可取lvalue或rvalue，分别表示E是左值标识符和右值表达式，那么语法制导定义如下(无输出则表示无错) ：E id E.v := lvalueE num E.v := rvalueE E+T | TT num.num | num给出一个语法制导定义以确定每个子表达式的类型int/real 。
答：E E1+T { if ( E1.type=real or T.type=real )4、用SLR(1)文法能定义的语言集合、定义的语言集合之间有什么关系？答：用SLR⑴文法能定义的语言集合用LR(1)文法能定义的语言集合和用LALR(1)文法能用LALR(1)文法能定义的语言集合，用LALR⑴文法能定义的语言集合用LR(1)文法能定义的语言集合。
int | realid , L | idLR分析方法，选择哪个文法更好?E EE E i + E2 E ( E i ) E E i ++ E.v := rvalueE.v := E i.vif E i.v = rvalue then printf(E.v := rvaluein valid lvalue in in creme nt ”);7、then E.type=real else E.type=integer } E T { E.type = T.type;}T num .num {T.type = real;}T num {T.type = integer;}8、把下列 C 语言程序的可执行语句翻译为：main(){int i; int a[10];while (i<=10) a[i] = 0; }(a) 三地址代码(b) 后缀式答：(a) L0: if i<=10 goto L1goto L2L1: a[i]:=0goto L0L2:(b) 后缀式：i 10 <= a[i] 0 assign while9、试构造下面的程序的流图，并找出其中所有回边及循环。
read Px := 1 c := P * P if c < 100 goto L1 B := P * P x := x + 1 B := B + x write x halt L1: B:= 10x := x + 2 B := B + x write B if B < 100 goto L2 halt L2: x := x + 1goto L1答：程序的流图如下10、对本题中所示的流图，求出其各结点n 的控制结点集 D(n)、回边及循环(n o 为首结点) 答：各结点n 的控制结点集D(n)如下：D(n 0)= ={n o }D(n 1)= ={n 0, n 1}D(n 2)= ={n 0, n 1, n 2}D(n 3)= ={n 0, n 1, n 2, n 3} D(n 4)={n 0, n 1, n 2, n 4} D(n 5)= ={n 0, n 1, n 2, n 5}D(n 6)= ={n 0,n 1, n 2,n 5, n 6}D(n 7)={n 0, n 1, n 2, n 5, n 6, n 7}回边和循环：因为D(n 5) = {n o , n 1, n 2, n 5}，且n 5 -> n 2,所以n 5 -> n 2为一条回边。
根据它 求出的循环 Li = {n 2, n 5, n 3, n 4}。
因为 D(n 6)= {n 0, n 1, n 2, n5, n 6}，且 n 6 -> n 1，所以 n 6 -> n 1 为一条回边。
根据这条回边，求出的循环 L 2 = {n 6, n 1, n 5, n 3, n 4, n 2}。
11、考虑下面求矩阵 A B 成绩的程序片段：BEGINFOR i := 1 TO n DOFOR j := 1 TO n DOFOR k = 1 TO n DOc[i, j] := c[i, j] + A[i, k} * B[k, j]END (1)假定对数组A 、B 、C 采用静态存储分配，每个字占用 4个字节，存储器以字节为单位编址。
给出该程序的三地址代码序列。
(2) 构造该程序相应的流图。
(3) 删除流图中各基本块内的公共子表达式(4)指出流图中所有回边及其相应循环，并且进行循环优化。
答：(1)设数组元素按行存放，A、B C数组都是n*n的二维数组，各维的下界均为0，每个元素占一个字(4个字节)，则数组元素(如A[i, j])的地址计算公式为：D(A[i, j]) = addr(A) + ((i - 0) * n + (j - 0)) * 4=addr(A) + 4 * ( i * n + j )该程序的三地址代码序列被划分成基本块后如下：(105) if k > 门ecrta 130Bp (130) J := J + 1(131)goto 103(3 )仅基本块B7中有公共子表达式，删除公共子表达式后基本块B7变换成:(106)鼻：二I 半n(107)T：:二 J + J(108)T2 := addr (0(109)T t：= 4 + T”(110)T5:二T2[T t](111)T&:二几+ K(112)T r:二addr (A)(113)T e;= 4 * T6(114)T fi:二T?[t s] ill5) T, ：= K * n(116)Tg ：二Tg + J(117)T lQ:二吕療r(B)(118)T?:二4 * T9(119)T lt - T®[TJ(120)T12:= T3加T n(121)T； T5十T12(122)T JTJ :二(123)K ;= K + 1(124)goto 105(4)根据(2)的程序流图，每个结点的控制结点集如下:D(B i) = { B i }D(B2) = { B 1, B2 }D(B3) = { B 1, B 2, B 3 }D(B4) = { B 1, B 2, B 3, B 4 }D(B5) = { B 1, B 2, B 3, B 4, B 5 }D(B6) = { B 1, B 2, B 3, B 4, B 5, B 6 }D(B7) = { B 1, B 2, B 3, B 4, B 5, B 6, B 7 } D(B8) = { B 1, B 2, B 3, B 4, B 5, B 6, B 8 } D(B9) = { B 1, B 2, B 3, B 4, B 9 }根据回边B7 -> B 6 ，循环L i为：L1 = { B 7, B 6 }根据回边B8 -> B 4 ，循环L2为：L2 = { B 8, B 6, B 7, B 5, B 4 }根据回边B9 -> B2, 循环:L3为：L3 = { B 9, B 4, B 5, B 6, B 7 , B 8, B 3, B 2 } 经循环优化后三地址代码序列变为Sy. 4(2)经理度削弱后的梳圈(3)删除归纳变量：变换循环控制条件，删除归纳变量 I 后的流图显示在图12、试求出如下四元式程序中的循环并进行循环优化 I := 1 read J, K L: A := K * I B := J * IC := A * B write C I := I + 1 if I < 100 goto Lhalt 答：把本题的三地址代码划分成基本块并画出其程序流图显示在图 9.4(1)中 其中有三个基本块B1, B2, B3,有一条回边 B2 -> B2，相应的循环是｛B2｝。
I 1Tead J, KE ;= J * [C - * 8WLL lU €I ：二 I + 1i£ I < 各口丄口 Lhalt 国9. 4(1〕程序毓国 (1 )代码外提：由于循环中没有不变运算，故不做此项优化 (2)强度削弱: B2中A 和B都是 I 的归纳变量。
优化结果显示在图 9.4(2)中。
h 丹】t 9.4(3)中A 用静态分配存储单元，且下届为 0；/* 置初值*/4/* 第一个for 语句*/T 2[T 1] := true i := i + 1图9.4(3)删除归纳变量的程序流图 13、下面是应用筛法求 2到N 之间素数的程序: beginread N; for i := 2 to N do A[i] := true; /*置初值*/ 表幕乘*/ for i := 2 to N**0.5 do/*运算符**代T 2 := addr(A) T 1:= 2 * T 1 /* 数组A 的基地址*/the n/*i false/*j 可被i 除尽*/endif A[i]是一个素数*/for j := 2 * i to N by i doA[j]:=(1)试写出其四元式中间代码，假设对数组 (2 )作出流图并求出其中的循环； (3 )进行代码外提；(4)进行强度削弱和删除归纳变量；答：采用字节地址，两个字节作为一个机器字。
