编译原理散列符号表
‘壹’ 编译原理全部的名词解释
书上有别那么懒！。。。。
编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成
解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。
编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。
解释程序和编译程序的根本区别：是否生成目标代码
句子的二义性（这里的二义性是指语法结构上的。）:文法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)删除无用赋值
基本块定义
程序中只有一个入口和一个出口的一段顺序执行的语句序列，称为程序的一个基本块。
给我分数啊。。。
‘贰’ 编译原理中pl/0符号表中oddsym是代表什么符号
判断一个表达式的结果是否为奇数，若为奇数返回真
‘叁’ 编译原理算符优先分析法中构造分析表的时候，井号和其他符号的优先级怎么判断在线等。
首先，算符优先分析法只考虑终结符之间的优先关系。
其次，#和其他终结符之间的优先关系按如下方法来确定：
1）假设文法的开始符为E，则增加一个产生式E‘-> #E#, E'不在原文法中出现
2）#<FIRSTVT(E) ; LASTVT(E)>#
‘肆’ 编译原理对符号表进行操作有哪些
//----------------------------符号表---------------------------------------
//预定义
struct snode;
struct stable;
//符号表结点
struct snode
{
string text; //符号名称
string type; //符号类型
union {int ival;double rval;}value; //值------------
int offset; //偏移量
snode *nextn; //指向下一个节点
stable *header; //指向下属符号表的表头
};
//符号表表头
struct stable
{
stable *previous; //指向先前创建的符号表表头
snode *firstnode; //指向第一个结点
stable *ifnoelements;//如果此表为空，则用它指向下一个表头
};
//当前表头
stable *currtab;
//建立新表，返回表头指针
//参数：当前的节点的表头
stable *mktable(stable *previous)
{
stable *newtable =new stable;
newtable->previous=previous;
newtable->ifnoelements=0;
newtable->firstnode=0;
if(previous->firstnode==0)
{
previous->ifnoelements=newtable;
}
else
{
snode* ininode=previous->firstnode;
while(ininode->nextn!=0)
{
ininode=ininode->nextn;
}
ininode->header=newtable;
}
currtab=newtable;
return newtable;
}
//在node指向的符号表中为text建立一个新表项，返回新建立的结点
//参数：node为当前的节点的表头，text名称，type类型，offset偏移
snode *enter(stable *table,string text,string type,int offset,double value)
{
//创建节点
snode *newnode = new snode;
newnode->text=text;
newnode->type=type;
newnode->offset=offset;
newnode->nextn=0;
newnode->header=0;
if(type=="int")
{
newnode->value.ival=value;
}
else if(type=="real")
{
newnode->value.rval=value;
}
//判断此表是否无元素
if(currtab->firstnode==0)
{
currtab->firstnode=newnode;
currtab->ifnoelements=0;
}
else
{
snode* addnode=currtab->firstnode;
while(addnode->nextn!=0)
{
addnode=addnode->nextn;
}
addnode->nextn=newnode;
}
return newnode;
}
//初始化符号表，返回表头节点
void inittab()
{
stable *initable = new stable;
initable->firstnode=0;
initable->previous=0;
initable->ifnoelements=0;
currtab=initable;
}
//查找指针，表示结果
snode *searchresult;
//查找变量，返回指向该变量的指针
//查找变量，返回指向该变量的指针
snode* search(string name)
{
//检查表是否空
bool isempty=true;
stable* checktab=currtab;
if(checktab->firstnode!=0)
{isempty=false;}
while(checktab->previous!=0)
{
if(checktab->firstnode!=0)
{isempty=false;}
checktab=checktab->previous;
}
if(checktab->firstnode!=0)
{isempty=false;}
if(isempty)
{
return 0;
}
snode* lastnode;
if(currtab->firstnode==0)
{
//移到非空的表头
stable* notnullhead=currtab;
while(notnullhead->firstnode==0)
{
notnullhead=notnullhead->previous;
}
snode* tmpnode=notnullhead->firstnode;
//移到最后的元素
while(tmpnode->nextn!=0)
{
tmpnode=tmpnode->nextn;
}
lastnode=tmpnode;
}
else
{
lastnode=currtab->firstnode;
while(lastnode->nextn!=0)
{
lastnode=lastnode->nextn;
}
}
//移到表头
stable* fronttab=currtab;
while(fronttab->previous!=0)
{
fronttab=fronttab->previous;
}
snode* nownode=0;
while(nownode!=lastnode)
{
while(fronttab->ifnoelements!=0)
{
fronttab=fronttab->ifnoelements;
}
nownode=fronttab->firstnode;
while(nownode->nextn!=0)
{
if(nownode->text==name)
{
searchresult=nownode;
return searchresult;
}
nownode=nownode->nextn;
}
if(nownode->text==name)
{
searchresult=nownode;
return searchresult;
}
fronttab=nownode->header;
}
if(nownode->text==name)
{
searchresult=nownode;
return searchresult;
}
return 0;
}
//消毁符号表
void delNode()
{
//more codes here......
}
‘伍’ 如何建立符号表
Symbol Tables
为了维持静态作用域的程序里各个名字的轨迹，编译器需要依靠一种称为符号表的数据结构。从最基本的层次上看，符号表就是一个字典：它把名字映射到编译器已知的有关信息。这里最基本的操作是把一个新映射关系（名字对象约束）放入表里，以及（非破坏性的）用一个给定名字去提取映射下的信息，以后我们把
这两个操作分别称为insert和lookup。大部分语言里的静态作用域规则还提出了另外的复杂性，它们要求在程序里的不同部分有不同的引用环境。为了处理作用域规则，我们可能希望简单增加一个remove操作。由于编译器在语义分析阶段要从头到尾扫描代码，这样它就可以在某个作用域开始时插入新约束，在作用域最后撤销它们。但是，存在一些因素使这种直接做法并不实际。
¨ 在许多有着嵌套作用域的语言里，内层声明的效果可以遮蔽外层声明，这就意味着符号表必须有能力为一个给定名字保存任意数目的映射。lookup操作必须返回最内层的映射，到作用域结束时还必须使外层映射重新变成可见的。
¨ 类Algol语言里的记录（结构）具有某种作用域性质，但却又不享有作用域那样的良好嵌套结构。当语义分析器看到一个记录声明时，它就必须记下各个记录域的名字（它们也是递归的，因为记录可以嵌套）。在这种声明结束时，各个域的名字又必须变成不可见的。然而，在此之后，一旦这一记录类型的某个变量出现在程序的正文里（例如在my_rec.field_name），在引用中位于圆点之后的部分，这些域名又必须立即重新变成可见的。在Pascal和另一些有with语句的语言里，记录域的名字还应该在多个语句的上下文里变成可见的。
¨ 某些时候一些名字有可能在它们被声明之前使用，即使在类Algol语言里情况也如此。举例说，Algol 60和Algol 68都允许标号的向前引用。Pascal避免了这种情况，它要求标号必须在作用域开始处声明，但还是允许指针声明的向前引用：
type
company = record
CEO : ^person; (* forward reference *)
...
end;
person = record
employer : ^company;
...
end;
¨ Pascal和其他语言都允许子程序的向前声明，以便支持相互递归：
procere Q (A, B : integer); forward;
procere P (A, B : integer);
begin
...
Q (3, 4);
...
end;
procere Q; (* parameters are not repeated in Pascal *)
begin
...
P (4, 5);
...
end;
在看到这段代码里的向前声明时，语义分析器必须记住Q的参数，以便后面可以在Q的体里使它们重新变成可见的，但在此期间又必须使它们成为不可见的。这种操作类似于记住记录域的名字。
¨ 虽然我们有可能希望在作用域结束时忘记有关的名字，甚至回收这些名字在符号表里占据的空间，但有关它们的信息仍需要保存起来，以便符号纠错系统（symbolic debugger）使用。这种纠错系统是非常有用的工具，用户可以借助它方便地操纵程序，如启动程序，停住它，读出或者修改程序里的数据等等。为了分析来自用户的高级名字（例如，要求打印出my_firm^.revenues[1999] 的值），符号纠错程序必须能访问编译器的符号表。为了使符号表在运行时也可以用，编译器通常会把这个表保存到最后的机器语言程序里的某个隐蔽的部分。
静态作用域的大部分变化都可以通过扩充基本符号表的方式处理，通过增加一对enter_scope和leave_scope操作维持可见性的轨迹。任何东西都不会从符号表里删除，在整个编译阶段所有的结构都保留着，最后还要为纠错系统使用而保存起来。带有可见性处理的符号表可以以多种不同方式实现，下面描述的方式归功于LeBlanc和Cook [CL83]。
在遇到每个作用域时赋给它一个序列号。给定最外层的作用域（其中包含着预定义的标识符）编号0，包含用户定义全局名字的作用域给以编号1。其他作用域按遇到它们的顺序进行编号。所有的编号互不相同，它们并不表示词法嵌套的层次，但也有一点，嵌套于内部的子程序的编号自然会大于它们的外围作用域的编号。
所有的名字都被放入一个大的散列表里，以名字作为关键码，无论其作用域如何。表里的每项都包含一个符号名，其类属（变量、常量、类型、过程、域名字、参数等等），作用域编号，类型（一个指向另一符号表项的指针），以及另一些特定类属所拥有的信息。
除了这一散列表之外，符号表还包含一个作用域堆栈，它按顺序指明组成当前引用环境的所有作用域。在语义分析器扫描程序的过程中，在进入或退出程序时分别压入或者弹出这个堆栈。作用域堆栈的项里包含着作用域编号，指明这一作用域是否为闭的，有些情况下还可以有另外一些信息。
图3.13 LeBlanc-Cook符号表的lookup算法。
当需要到表里查找名字时，我们会顺着某个适当的散列表链向下找，这样就会找到要找的名字所对应的一些项。对于每个匹配项，我们都向下扫描作用域堆栈，看看这个项所在的作用域是否可见。这种堆栈查看的深度不应超过最上面的闭作用域。要把导入项和导出项变为在它们的作用域之外可见的，方法就是在表里建立另外的项，让这些项里包含着指向实际项的指针。对于所有带有作用域编号0的项，我们都不需要去检查作用域堆栈，因为它们是渗透性的。图3.13里是lookup算法的伪代码。
图3.14的右下角是一个Mola-2程序的梗概，图中其余部分展现的是在过程P2里with语句处的引用环境的符号表配置情况。作用域堆栈里包含4个项，分别表示那个with语句，过程P2，模块M和全局作用域。with语句的作用域指明了在这一特定作用域里的（域）名字属于哪个记录变量。最外面的渗透性作用域没有显式表示。
图3.14 一个Mola-2例子程序的LeBlanc-Cook符号表。作用域堆栈表示在过程P2里with语句的引用环境。为清楚起见，许多指向符号表里对应于integer和real的项都用带括号的 (1) 和 (2) 表示，没有画出箭头。
因为这里的散列表以名字作为关键码，特定名字的所有项都出现在同一个散列链里。在这个例子里，散列冲突导致A2、F2和T出现在同一个链里。变量V和I（M的I）有另外的项，使它们跨过闭作用域M的边界后仍为可见的。当我们处于P2里时，对于I的查找操作将找到P2的I，M的I里的两个项都不可见。类型T的项指明了在with语句期间放入作用域堆栈的作用域编号。每个子程序的项里包含了一个头指针，指向子程序参数的链接表，以便做调用分析时使用（图中没有给出这些链的一些链接）。在代码生成过程中，许多符号表项还可能包含另外的域，表示例如对象大小和运行时地址等等信息。
图片信息，看参考资料。。。
‘陆’ 编译程序包括哪几个主要组成部分
数据结构 分析和综合时所用的主要数据结构，包括符号表、常数表和中间语言程序。符号表由源程序中所用的标识符连同它们的属性组成，其中属性包括种类（如变量、数组、结构、函数、过程等）、类型（如整型、实型、字符串、复型、标号等），以及目标程序所需的其他信息。常数表由源程序中用的常数组成，其中包括常数的机内表示，以及分配给它们的目标程序地址。中间语言程序是将源程序翻译为目标程序前引入的一种中间形式的程序，其表示形式的选择取决于编译程序以后如何使用和加工它。常用的中间语言形式有波兰表示、三元组、四元组以及间接三元组等。
分析部分 源程序的分析是经过词法分析、语法分析和语义分析三个步骤实现的。词法分析由词法分析程序（又称为扫描程序）完成，其任务是识别单词（即标识符、常数、保留字，以及各种运算符、标点符号等）、造符号表和常数表，以及将源程序换码为编译程序易于分析和加工的内部形式。语法分析程序是编译程序的核心部分，其主要任务是根据语言的语法规则，检查源程序是否合乎语法。如不合乎语法，则输出语法出错信息；如合乎语法，则分解源程序的语法结构，构造中间语言形式的内部程序。语法分析的目的是掌握单词是怎样组成语句的，以及语句又是如何组成程序的。语义分析程序是进一步检查合法程序结构的语义正确性，其目的是保证标识符和常数的正确使用，把必要的信息收集和保存到符号表或中间语言程序中，并进行相应的语义处理。
综合部分 综合阶段必须根据符号表和中间语言程序产生出目标程序，其主要工作包括代码优化、存储分配和代码生成。代码优化是通过重排和改变程序中的某些操作，以产生更加有效的目标程序。存储分配的任务是为程序和数据分配运行时的存储单元。代码生成的主要任务是产生与中间语言程序符等价的目标程序，顺序加工中间语言程序，并利用符号表和常数表中的信息生成一系列的汇编语言或机器语言指令。
结构编译过程分为分析和综合两个部分，并进一步划分为词法分析、语法分析、 语义分析、 代码优化、存储分配和代码生成等六个相继的逻辑步骤。这六个步骤只表示编译程序各部分之间的逻辑联系，而不是时间关系。编译过程既可以按照这六个逻辑步骤顺序地执行，也可以按照平行互锁方式去执行。在确定编译程序的具体结构时，常常分若干遍实现。对于源程序或中间语言程序，从头到尾扫视一次并实现所规定的工作称作一遍。每一遍可以完成一个或相连几个逻辑步骤的工作。例如，可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍。反之，为了适应较小的存储空间或提高目标程序质量，也可以把一个逻辑步骤的工作分为几遍去执行。例如，代码优化可划分为代码优化准备工作和实际代码优化两遍进行。
一个编译程序是否分遍,以及如何分遍,根据具体情况而定。其判别标准可以是存储容量的大小、源语言的繁简、解题范围的宽窄，以及设计、编制人员的多少等。分遍的好处是各遍功能独立单纯、相互联系简单、逻辑结构清晰、优化准备工作充分。缺点是各遍之中不可避免地要有些重复的部分，而且遍和遍之间要有交接工作，因之增加了编译程序的长度和编译时间。
一遍编译程序是一种极端情况，整个编译程序同时驻留在内存,彼此之间采用调用转接方式连接在一起(图2)。当语法分析程序需要新符号时，它就调用词法分析程序；当它识别出某一语法结构时，它就调用语义分析程序。语义分析程序对识别出的结构进行语义检查，并调用“存储分配”和“代码生成”程序生成相应的目标语言指令。
随着程序设计语言在形式化、结构化、直观化和智能化等方面的发展，作为实现相应语言功能的编译程序，也正向自动程序设计的目标发展，以便提供理想的程序设计工具。
参考书目
陈火旺、钱家骅、孙永强编：《编译原理》，国防工业出版社，北京，1980
‘柒’ 编译原理中的词法分析器的输入与输出是什么
编译原理中的词法分析器的输入是源程序，输出是识别的记号流。
词法分析器编制一个读单词的程序，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符和分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。
(7)编译原理散列符号表扩展阅读
词法分析器的作用：
1、与符号表进行交互，存储和读取符号表中的标识符的信息。
2、读入源程序的输入字符，将他们组成词素，生成并输出一个词法单元序列，每个词法单元序列对应一个于一个词素。
3、过滤掉程序中的注释和空白。
4、将编译器生成的错误消息与源程序的位置联系起。
‘捌’ 正在学习编译原理，语法图应该用什么软件画会比较简单一点
一般用YACC画，不过建议用GOLD PARSER。画起来最快，不要编程。
步骤：
1）写出正确的文法。
2）在测试窗口中输入要分析的字符串。