编译原理符号表与类型表

① 编译原理中的词法分析器的输入与输出是什么

编译原理中的词法分析器的输入是源程序，输出是识别的记号流。

词法分析器编制一个读单词的程序，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符和分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。

(1)编译原理符号表与类型表扩展阅读

词法分析器的作用：

1、与符号表进行交互，存储和读取符号表中的标识符的信息。

2、读入源程序的输入字符，将他们组成词素，生成并输出一个词法单元序列，每个词法单元序列对应一个于一个词素。

3、过滤掉程序中的注释和空白。

4、将编译器生成的错误消息与源程序的位置联系起。

② 编译原理全部的名词解释

书上有别那么懒!.
编译过程的六个阶段：词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成
解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序,然后再执行目标程序.解释方式是接受某高级语言的一个语句输入,进行解释并控制计算机执行,马上得到这句的执行结果,然后再接受下一句.
编译程序：就是指这样一种程序,通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序).
解释程序和编译程序的根本区别：是否生成目标代码
句子的二义性（这里的二义性是指语法结构上的.）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导),或者存在两棵不同的语法树,则称这个句子是二义性的.
文法的二义性:一个文法如果包含二义性的句子,则这个文法是二义文法,否则是无二义文法.
LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归)
第1个L：从左到右扫描输入串 第2个L：生成的是最左推导
1 ：向右看1个输入符号便可决定选择哪个产生式
某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归
文法符号的属性:单词的含义,即与文法符号相关的一些信息.如,类型、值、存储地址等.
一个属性文法(attribute grammar)是一个三元组A=(G, V, F)
G：上下文无关文法.
V：属性的有穷集.每个属性与文法的一个终结符或非终结符相连.属性与变量一样,可以进行计算和传递.
F：关于属性的断言或谓词(一组属性的计算规则)的有穷集.断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性.
综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属
继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性.
(1)非终结符既可有综合属性也可有继承属性,但文法开始符号没有继承属性.
(2) 终结符只有综合属性,没有继承属性,它们由词法程序提供.
在计算时： 综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递.
语法制导翻译：是指在语法分析过程中,完成附加在所使用的产生式上的语义规则描述的动作.
语法制导翻译实现：对单词符号串进行语法分析,构造语法分析树,然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算.
中间代码（中间语言）
1、是复杂性介于源程序语言和机器语言的一种表示形式.
2、一般,快速编译程序直接生成目标代码.
3、为了使编译程序结构在逻辑上更为简单明确,常采用中间代码,这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理,并且可以在中间代码一级进行优化工作,使得代码优化比较容易实现.
何谓中间代码：源程序的一种内部表示,不依赖目标机的结构,易于代码的机械生成.
为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言.
(2)便于移植,便于修改,便于进行与机器无关的优化.
中间代码的几种形式：逆波兰记号 ,三元式和树形表示 ,四元式
符号表的一般形式：一张符号表的的组成包括两项,即名字栏和信息栏.
信息栏包含许多子栏和标志位,用来记录相应名字和种种不同属性,名字栏也称主栏.主栏的内容称为关键字（key word）.
符号表的功能：（1）收集符号属性 (2) 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性.(3)作为目标代码生成阶段地址分配的依据
符号的主要属性及作用：
1. 符号名 2. 符号的类型 （整型、实型、字符串型等））3. 符号的存储类别（公共、私有）
4. 符号的作用域及可视性 （全局、局部） 5. 符号变量的存储分配信息 （静态存储区、动态存储区）
存储分配方案策略：静态存储分配；动态存储分配：栈式、 堆式.
静态存储分配
1、基本策略
在编译时就安排好目标程序运行时的全部数据空间,并能确定每个数据项的单元地址.
2、适用的分配对象：子程序的目标代码段；全局数据目标（全局变量）
3、静态存储分配的要求：不允许递归调用,不含有可变数组.
FORTRAN程序是段结构,不允许递归,数据名大小、性质固定. 是典型的静态分配
动态存储分配
1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间,那么,就需要采用动态存储管理技术.
2、两种动态存储分配方式：栈式,堆式
栈式动态存储分配
分配策略：将整个程序的数据空间设计为一个栈.
【例】在具有递归结构的语言程序中,每当调用一个过程时,它所需的数据空间就分配在栈顶,每当过程工作结束时就释放这部分空间.
过程所需的数据空间包括两部分
一部分是生存期在本过程这次活动中的数据对象.如局部变量、参数单元、临时变量等；
另一部分则是用以管理过程活动的记录信息(连接数据).
活动记录（AR）
一个过程的一次执行所需要的信息使用一个连续的存储区来管理,这个区 (块)叫做一个活动记录.
构成
1、临时工作单元；2、局部变量；3、机器状态信息；4、存取链；
5、控制链；6、实参；7、返回地址
什么是代码优化
所谓优化,就是对代码进行等价变换,使得变换后的代码运行结果与变换前代码运行结果相同,而运行速度加快或占用存储空间减少.
优化原则：等价原则：经过优化后不应改变程序运行的结果.
有效原则：使优化后所产生的目标代码运行时间较短,占用的存储空间较小.
合算原则：以尽可能低的代价取得较好的优化效果.
常见的优化技术
(1) 删除多余运算(删除公共子表达式) (2) 代码外提 +删除归纳变量+ (3)强度削弱; (4)变换循环控制条件 (5)合并已知量与复写传播 (6)删除无用赋值
基本块定义
程序中只有一个入口和一个出口的一段顺序执行的语句序列,称为程序的一个基本块.
给我分数啊.

③ 编译程序包括哪几个主要组成部分

数据结构 分析和综合时所用的主要数据结构，包括符号表、常数表和中间语言程序。符号表由源程序中所用的标识符连同它们的属性组成，其中属性包括种类（如变量、数组、结构、函数、过程等）、类型（如整型、实型、字符串、复型、标号等），以及目标程序所需的其他信息。常数表由源程序中用的常数组成，其中包括常数的机内表示，以及分配给它们的目标程序地址。中间语言程序是将源程序翻译为目标程序前引入的一种中间形式的程序，其表示形式的选择取决于编译程序以后如何使用和加工它。常用的中间语言形式有波兰表示、三元组、四元组以及间接三元组等。

分析部分 源程序的分析是经过词法分析、语法分析和语义分析三个步骤实现的。词法分析由词法分析程序（又称为扫描程序）完成，其任务是识别单词（即标识符、常数、保留字，以及各种运算符、标点符号等）、造符号表和常数表，以及将源程序换码为编译程序易于分析和加工的内部形式。语法分析程序是编译程序的核心部分，其主要任务是根据语言的语法规则，检查源程序是否合乎语法。如不合乎语法，则输出语法出错信息；如合乎语法，则分解源程序的语法结构，构造中间语言形式的内部程序。语法分析的目的是掌握单词是怎样组成语句的，以及语句又是如何组成程序的。语义分析程序是进一步检查合法程序结构的语义正确性，其目的是保证标识符和常数的正确使用，把必要的信息收集和保存到符号表或中间语言程序中，并进行相应的语义处理。

综合部分 综合阶段必须根据符号表和中间语言程序产生出目标程序，其主要工作包括代码优化、存储分配和代码生成。代码优化是通过重排和改变程序中的某些操作，以产生更加有效的目标程序。存储分配的任务是为程序和数据分配运行时的存储单元。代码生成的主要任务是产生与中间语言程序符等价的目标程序，顺序加工中间语言程序，并利用符号表和常数表中的信息生成一系列的汇编语言或机器语言指令。

结构编译过程分为分析和综合两个部分，并进一步划分为词法分析、语法分析、 语义分析、 代码优化、存储分配和代码生成等六个相继的逻辑步骤。这六个步骤只表示编译程序各部分之间的逻辑联系，而不是时间关系。编译过程既可以按照这六个逻辑步骤顺序地执行，也可以按照平行互锁方式去执行。在确定编译程序的具体结构时，常常分若干遍实现。对于源程序或中间语言程序，从头到尾扫视一次并实现所规定的工作称作一遍。每一遍可以完成一个或相连几个逻辑步骤的工作。例如，可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍。反之，为了适应较小的存储空间或提高目标程序质量，也可以把一个逻辑步骤的工作分为几遍去执行。例如，代码优化可划分为代码优化准备工作和实际代码优化两遍进行。

一个编译程序是否分遍,以及如何分遍,根据具体情况而定。其判别标准可以是存储容量的大小、源语言的繁简、解题范围的宽窄，以及设计、编制人员的多少等。分遍的好处是各遍功能独立单纯、相互联系简单、逻辑结构清晰、优化准备工作充分。缺点是各遍之中不可避免地要有些重复的部分，而且遍和遍之间要有交接工作，因之增加了编译程序的长度和编译时间。

一遍编译程序是一种极端情况，整个编译程序同时驻留在内存,彼此之间采用调用转接方式连接在一起(图2)。当语法分析程序需要新符号时，它就调用词法分析程序；当它识别出某一语法结构时，它就调用语义分析程序。语义分析程序对识别出的结构进行语义检查，并调用“存储分配”和“代码生成”程序生成相应的目标语言指令。

随着程序设计语言在形式化、结构化、直观化和智能化等方面的发展，作为实现相应语言功能的编译程序，也正向自动程序设计的目标发展，以便提供理想的程序设计工具。

参考书目

陈火旺、钱家骅、孙永强编：《编译原理》，国防工业出版社，北京，1980