当前位置：文档之家 › 第4章 符号表

第4章 符号表

  • 格式：ppt
  • 大小：408.01 KB
  • 文档页数：55

下载文档原格式

  / 55

合集下载

变量名符号表

变量名符号表


ENTER过程完成。
说明部分的分析与处理（程序）
• 说明类型的定义: • object= (constant, variable,procedur) • （定义纯量/枚举类型） • 名字表的定义 table:array[0..txmax] of
record name:alfa; • case kind:object of
表也是一个栈，栈顶指针为level。当进入一个新过程时，level增加1；每当退 出一个过程时，level减1。DISPLAY(level)总是指向当前正在处理的最内层的 过程的子符号表在栈符号表中的起始位置。
．在符号表的信息栏中引入一个指针域（previous）用以链接它在同一过程内 的前一域名字在表中的下标（相对位置）。每一层的最后一个域名字，其 previous之值为0。这样，每当需要查找一个新名字时，就能通过
地址ble表的下标指针tx补充说
明:
tx 6 （9）
LE 1
V BLOCK
tx ...
0
（6）
LE 0 V BLOCK
主程
序
tx是BLOCK的 实际值参
BLOCK（LEV+1,TX, …） (递归进入分程序)
第1次调用block BLOCK（0, 0, …）
编译程序按名字的不同种属分别使用许多符号 表，如常数表、变量名表、过程名表等等。
SUBROUTINE INCWAP（M，N）
10 K＝M＋1
M＝M＋4 N＝K RETURN END
经编译头三阶段后所产生的主要表格有: 符号 名表SNT、常数表CT、入口名表ENT、标号 表LT和四元式表QT
符号名表SNT
几种通常都是需要的。 1 符号名 2 符号的类型 3 符号的存储类别 4 符号的作用域及可视性 5 符号变量的存储分配信息 6 符号的其它属性（１） 数组内情向量 （２） 记录结构型的成员信息（３） 函数及过程
第四章串A

第四章串A


（1）初始化ClearString（S）：初始化串S(串S存 在，将S清为空串)。 （2）StrAssign（&T，char）：生成串。
（3）StrCopy(&T，S)：串复制(将串S复制到串T)。5
第4 章 串
（4）Concat（&T，s1，s2）:串联接(用T返回S1,S2 联接而成的新串)。 （5）求串长StrLength（S）：返回S串的元素个数， 即S串的长度。 （6）串比较StrCompare（S，T） （7）求子串SubString（&Sub，S，pos，len）： 返回s串的第pos个字符起始的长度为len的子串。 （8）插入运算SetInsert（&S，T，pos）：把串t的 值插入到串s的第pos个字符之后。 （9）删除运算StrDelte（&S，pos，len）：将串s
可能出现如下三种情况： a. S1长度+S2长度<=T长度，则S1+S2可以完整放入T中； b. S1长度+S2长度>T长度，则S1完整放入，S2放入一部 分； c. S1长度=T长度，则S1完整放入，S2不能放入。 注意：各串长度数据放入该串的 0 单中。（如图4.1示）
11
第4 章 串
两串联结的C语言程序 (算法4.2)
{ int i; orderstribg *r ;
printf(“ r1=%s,r2=%s\n”,r1.vec,r2.vec);
if (r1.len+r2.len>m0) printf(“上溢出\n”) ; /* 若两串长度之和大于m0，则进行溢出处理*/
12
第4 章 串
else { for (i=0; i<r1.len; i++) r.vec[i]=r1.vec[i]; for (i=0; i<r2.len;i++) /*将串r2传r */ r.vec[r1.len+ i ]= r2.vec[i]; r.vec[r1.len+ i ]=“\0” ; /*最后一个位置赋给\0 */ r.len=r1.len+r2.len; } return(r); } /*r串长度等于两串长度之和*/ /*将串r1传给r */
整理符号表_变量符号说明

整理符号表_变量符号说明

符号表整理表姓名:职业工种:申请级别:受理机构:填报日期:变量符号说明福州大学2015 年硕士研究生入学考试专业课课程（考试）大纲1.考试科目名称: 《数据结构与程序设计》2.招生学院：数学与计算机科学(软件)学院说明：1、考试基本内容：一般包括基础理论、实际知识、综合分析和论证等几个方面的内容。

有些课程还应有基本运算和实验方法等方面的内容。

字数一般在300字左右。

2、难易程度：根据大学本科的教学大纲和本学科、专业的基本要求，一般应使大学本科毕业生中优秀学生在规定的三个小时内答完全部考题，略有一些时间进行检查和思考。

排序从易到难。

目录第1章编译器概述第2章词法分析2.1 词法记号及属性2.1.1 词法记号、模式、词法单元2.1.2 词法记号的属性2.1.3 词法错误2.2 词法记号的描述与识别2.2.1 串和语言2.2.2 正规式2.2.3 正规定义2.2.4 状态转换图2.3 有限自动机2.3.1 不确定的有限自动机2.3.2 确定的有限自动机2.3.3 NFA到DFA的变换2.3.4 DFA的化简2.4 从正规式到有限自动机2.5 词法分析器的生成器第3章语法分析3.1 上下文无关文法3.1.1上下文无关文法的定义3.1.2 推导3.1.3 分析树3.1.4 二义性3.2 语言和文法3.2.1 正规式和上下文无关文法的比较3.2.2分离词法分析器的理由3.2.3 验证文法产生的语言3.2.4 适当的表达式文法3.2.5 消除二义性3.2.6 消除左递归3.2.7 提左因子3.2.8 非上下文无关的语言结构3.2.9 形式语言鸟瞰3.3 自上而下分析3.3.1 自上而下分析的一般方法3.3.2 LL(1)文法3.3.3 递归下降的预测分析3.3.4 非递归的预测分析3.3.5 构造预测分析表3.3.6 预测分析的错误恢复3.4 自下而上分析3.4.1 归约3.4.2 句柄3.4.3 用栈实现移进-归约分析3.4.4 移进-归约分析的冲突3.5 LR分析器3.5.1 LR分析算法3.5.2 LR文法和LR分析方法的特点3.5.3 构造SLR分析表3.5.4 构造规范的LR分析表3.5.5 构造LALR分析表3.5.6 非LR的上下文无关结构3.6 二义文法的应用3.6.1 使用文法以外的信息来解决分析动作的冲突3.6.2特殊情况产生式引起的二义性3.6.3 LR分析的错误恢复3.7 分析器的生成器3.7.1 分析器的生成器Yacc3.7.2 用Yacc处理二义文法3.7.3 Yacc的错误恢复第4章语法制导的翻译4.1 语法制导的定义4.1.1 语法制导定义的形式4.1.2 综合属性4.1.3 继承属性4.1.4 属性依赖图4.1.5 属性计算次序4.2 S属性定义的自下而上计算4.2.1 语法树4.2.2 构造语法树的语法制导定义4.2.3 S属性的自下而上计算4.3 L属性定义的自上而下计算4.3.1 L属性定义4.3.2 翻译方案4.3.3 预测翻译器的设计4.3.4 用综合属性代替继承属性4.4 L属性的自下而上计算4.4.1 删除翻译方案中嵌入的动作4.4.2 分析栈上的继承属性4.4.3 模拟继承属性的计算4.5 递归计算4.5.1 自左向右遍历4.5.2 其他遍历方法4.5.3 多次遍历第5章类型检查5.1 类型在程序设计语言中的作用5.1.1 引言5.1.2 执行错误和安全语言5.1.3 类型化语言的优点5.2 描述类型系统的语言5.2.1 定型断言5.2.2 定型规则5.2.3 类型检查和类型推断5.3 简单类型检查器的说明5.3.1 一个简单的语言5.3.2 类型系统5.3.3 类型检查5.3.4 类型转换*5.4 多态函数5.4.1 为什么要使用多态函数5.4.2 类型变量5.4.3 一个含多态函数的语言5.4.4 代换、实例和合一5.4.5 多态函数的类型检查5.5 类型表达式的等价5.5.1 类型表达式的结构等价5.5.2 类型表达式的名字等价5.5.3 记录类型5.5.4 类型表示中的环5.6 函数和算符的重载5.6.1 子表达式的可能类型集合5.6.2 缩小可能类型的集合第6章运行时存储空间的组织和管理6.1 局部存储分配策略6.1.1 过程6.1.2 名字的作用域和绑定6.1.3 活动记录6.1.4 局部数据的安排6.1.5 程序块6.2 全局存储分配策略6.2.1 运行时内存的划分6.2.2 静态分配6.2.3 栈式分配6.2.4 堆式分配6.3 非局部名字的访问6.3.1 无过程嵌套的静态作用域6.3.2 有过程嵌套的静态作用域6.3.3 动态作用域6.4 参数传递6.4.1值调用6.4.2 引用调用6.4.3 复写-恢复调用6.4.4 换名调用第7章中间代码生成7.1 中间语言7.1.1 后缀表示7.1.2 图形表示7.1.3 三地址代码7.2 声明语句7.2.1 过程中的声明7.2.2 作用域信息的保存7.2.3 记录的域名7.3 赋值语句7.3.1 符号表中的名字7.3.2 临时名字的重新使用7.3.3 数组元素的地址计算7.3.4 数组元素地址计算的翻译方案7.3.5 类型转换7.4 布尔表达式和控制流语句7.4.1 布尔表达式的翻译7.4.2 控制流语句的翻译7.4.3 布尔表达式的控制流翻译7.4.4 开关语句的翻译7.4.5 过程调用的翻译第8章代码生成8.1 代码生成器设计中的问题8.1.1 目标程序8.1.2 指令选择8.1.3 寄存器分配8.1.4 计算次序选择8.2 目标机器8.2.1 目标机器的指令系统8.2.2 指令的代价8.3 基本块和流图8.3.1 基本块8.3.2 基本块的变换8.3.3 流图8.3.4 下次引用信息8.4 一个简单的代码生成器8.4.1 寄存器描述和地址描述8.4.2 代码生成算法8.4.3 寄存器选择函数8.4.4 为变址和指针语句产生代码8.4.5 条件语句*第9章代码优化9.1 优化的主要种类9.1.1 代码改进变换的标准9.1.2 公共子表达式删除9.1.3 复写传播9.1.4 死代码删除9.1.5 代码外提9.1.6 强度削弱和归纳变量删除9.1.7 优化编译器的组织9.2 流图中的循环9.2.1 必经结点9.2.2 自然循环9.2.3 前置结点9.2.4 可归约流图9.3 全局数据流分析介绍9.3.1 点和路径9.3.2 到达-定值9.3.3 可用表达式9.3.4 活跃变量分析9.4 代码改进变换9.4.1公共子表达式删除9.4.2复写传播9.4.3 寻找循环不变计算9.4.4 代码外提9.4.5 归纳变量删除第10章编译系统和运行系统10.1 C语言的编译系统10.1.1 预处理器10.1.2 汇编器10.1.3 连接器10.1.4 目标文件的格式10.1.5 符号解析10.1.6 静态库10.1.7 可执行目标文件及装入10.1.8 动态连接10.1.9 处理目标文件的一些工具10.2 Java语言的运行系统10.2.1 Java虚拟机语言简介10.2.2 Java虚拟机10.2.3即时编译器*10.3 无用单元收集10.3.1 标记和清扫10.3.2 引用计数10.3.3 拷贝收集10.3.4 分代收集10.3.5 渐增式收集10.3.6 编译器与收集器之间的相互影响*第11章面向对象语言的编译11.1 面向对象语言的概念11.1.1 对象和对象类11.1.2 继承11.1.3 信息封装11.2 方法的编译11.3 继承的编译方案11.3.1 单一继承的编译方案11.3.2 重复继承的编译方案*第12章函数式语言的编译12.1 函数式程序设计语言简介12.1.1 语言构造12.1.2 参数传递机制12.1.3 变量的自由出现和约束出现12.2 函数式语言的编译简介12.2.1 几个受启发的例子12.2.2 编译函数12.2.3 环境与约束12.3 抽象机的系统结构12.3.1 抽象机的栈12.3.2 抽象机的堆12.3.3 名字的寻址12.3.4 约束的建立12.4 指令集和编译12.4.1 表达式12.4.2 变量的引用性出现12.4.3 函数定义12.4.4 函数应用12.4.5 构造和计算闭包12.4.6 letrec表达式和局部变量整理丨尼克本文档信息来自于网络，如您发现内容不准确或不完善，欢迎您联系我修正；如您发现内容涉嫌侵权，请与我们联系，我们将按照相关法律规定及时处理。

编译原理第4章 语法分析——自上而下分析

编译原理第4章 语法分析——自上而下分析


17
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。
x*y
S
IP x A y **
18
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。
x*y
S
IP x A y **
19
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
SQcRbcSabc
一个文法消除左递归的条件
丌含以为右部的产生式
丌含回路
PP
30
例 文法G(S): S→Qc|c Q→Rb|b R→Sa|a
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
SQcRbcSabc
Q
Q
ⅹ
S
R
S→Qc|c Q→Rb|b R→Sa|a
35
例 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
消除S的直接左递归后： S→abcS | bcS | cS S→abcS | Q→Sab |ab | b R→Sa|a
关于Q和R的觃则已是多余的，化简为：
S→abcS | bcS | cS
S→abcS |
(4.4)
36
注意，由于对非终结符排序的丌同，最 后所得的文法在形式上可能丌一样。但 丌难证明，它们都是等价的。
分析输入串x*y(记为)。
x*y
S
IP
15
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|*
分析输入串x*y(记为)。
数据结构第4章 串

数据结构第4章 串

ring s, SString t)
/*若串s和t相等则返回0；若s>t则返回正数；若s<t则返 回负数*/
{ int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i]) return(s.ch[i] - t.ch[i]);
初 始 条 件 : 串 S 存 在 ,1≤pos≤StrLength(S) 且 1≤len≤StrLength(S)-pos+1
操作结果:用Sub返回串S的第pos个字符起长度为len的子串
返回主目录
（11）StrIndex(S,T,pos)
初始条件: 串S和T存在,T是非空串, 1≤pos≤StrLength(S)
return(s.len); }
返回主目录
（7）清空函数
StrClear(SString *s) /*将串s置为空串*/ {
s->len=0; }
返回主目录
（8）连接函数
(1) 连接后串长≤MAXLEN，则直接将B加在A的 后面。 (2) 连接后串长>MAXLEN且LA<MAXLEN，则B 会有部分字符被舍弃。 (3) 连接后串长>MAXLEN且LA=MAXLEN，则B 的全部字符被舍弃（不需连接）。
for (i=s->len + t.len-1;i>=t.len + pos;i--)
s->ch[i]=s->ch[i-t.len];
for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i];
s->len=s->len+t.len;
第4章 指令系统(三)

第4章 指令系统(三)

在程序的开始可以用NAME或TITLE为模块取名字，NAME的格式是：
NANEmodule_name
汇编程序将已给出的module_name作为模块的名字。如果程序中没有NAME伪操作，则也可使用TITLE伪操作，其格式为：
TITLEtext
TITLE伪操作可指定每一页上打印的标题。同时，如果程序中没有使用NAME伪操作，则汇编程序将用text中的前六个字符作为模块名。Text最多可有60个字符。如果程序中既无NAME又无TITLE伪操作，则将用源文件名作为模块名。所以NAME及TITLE伪操作并不是必要的，但一般经常使用TITLE，以便在列表文件中能打印出标题来。
表示源程序结束的伪操作的格式为：
END[label]
其中标号指示程序开始执行的起始地址。如果多个程序模块相连接，则只有主程序要使用标号，其他子程序模块则只用END而不必指定标号。例4.4.8给出求两数之和的绝对值的程序实现，其中用TITLE给出标题，用END START表示程序结束。汇编程序将在遇END时结束汇编，而程序则将从START开始执行。
(4)DQ伪操作用来定义字，其后的每个操作数占有四个字。
(5)DT伪操作用定义十个字节，其后的每个操作数占有十个字节，形成压缩的BCD码。
操作数(operand)字段可为：1)数值表达式；2)ASCII字符串；3)地址表达式；4)？；5)操作数字段还可以使用复制操作符(duplication operator)来复制某个(或某些)操作数。其格式为：
(2)数值回送(Value_retuning)操作符
它有TYPE、LENGTH、SIZE、SEG五种。这些操作符把一些特征或存储器地址的一部分作为数值回送。下面分别说明各个操作符的功能。
1) TYPE
第四章词法分析器与单词符号

第四章词法分析器与单词符号


出错处理
对定义外的（ 对定义外的（如，对首字符不是字母的，不是数字的， 对首字符不是字母的，不是数字的， 不是运算符和分界符的）单词进行出错处理。 不是运算符和分界符的）单词进行出错处理。
2、状态转换图
利用状态转换图可以设计词法分析器。 利用状态转换图可以设计词法分析器。状态转换图是 一个有向图，仅包含有限个结点， 一个有向图，仅包含有限个结点，每个结点表示一 个状态，其中有一个初态结点，至少有一个终态结 个状态，其中有一个初态结点， 点，结点间弧的标记可以是输入字符或字符类。 结点间弧的标记可以是输入字符或字符类。
字母|数字 0 字母 数字 + * / < 1 数字 3 5 6 7 8 = 9 > 11 : 13 ; 其它 16 17 = 13 10 其它 其它 4 2
举例
开始 滤掉空格 是字母? 是字母? Y 读标识符 查关键字表 查到否? 查到否? Y 保留字类码⇒ 保留字类码⇒sy N 是数字? 是数字? Y 取数 N
属性字序列 源程序 词法分析程序 语法分析程序 ….
单词符号
单词符号是程序语言的基本语法单位， 单词符号是程序语言的基本语法单位，一般分为下 面 5 种： 关键字（基本字）：（个数确定，可全体编为一类， ）：（个数确定 关键字（基本字）：（个数确定，可全体编为一类， 也可一字一类) 也可一字一类) 标识符： 个数不确定，作为一类） 标识符：（个数不确定，作为一类） 常数： 个数不确定， 常数：各种类型的常数 。(个数不确定，按类型分 类) 运算符： 个数确定， 运算符：如+、-、*、/、<等。(个数确定，一符一 类) 界符： ，、；、（、）、: 个数确定, 界符：如，、；、（、）、: 等。(个数确定,一符 一类) 一类) 注意：一种语言的单词如何分类、怎样编码，主要取 注意：一种语言的单词如何分类、怎样编码，主要取 决于技术上的方便。 决于技术上的方便。
符号表与错误处理

符号表与错误处理


第8章 符号表与错误处理
分程序表中的每一登记项由三个字段组成: OUTERN字段用来指明该分程序的直接外层分
程序的编号；COUNT字段用来记录该分程 序符号表登记项的个数；POINTER字段是一个 指示器，它指向该分程序符号表的起始位置。
第8章 符号表与错误处理
下面, 我们给出建造满足上述要求符号表的算法 。为了使各分程序的符号表登记项连续地排列在一 起, 并结合在扫描具有嵌套分程序结构的源程序时 总是按先进后出的顺序来扫描其中各个分程序的特 点, 可设置一个临时工作栈, 每当进入一层分程序时 , 就在这个栈的顶部预造该分程序的符号表, 而当遇 到该层分程序的结束符END时(此时该分程序的全 部登记项都出现在栈的顶部), 再将该分程序的全部 登记项移至正式符号表中。
加1且使POINTER指向新的栈顶。
第8章 符号表与错误处理
③ 当扫描到分程序的结束符END时, 将记入临 时工作栈的本层分程序全部登记项移至正式 的符 号表中, 且修改POINTER值使其指向本层 分程 序全部名字登记项在符号表中的起始位置。此外, 在退出此层分程序时, 还应使它的直接 外层分程 序成为当前的分程序。
第8章 符号表与错误处理
根据编译程序工作阶段的不同划分, 名字表中 的各种信息将在编译程序工作过程中的适当时候填
入。对于在词法分析阶段就建立符号表的编译 程序, 当扫描源程序识别出一个单词(名字)时, 就以 此名 字查找符号表；若表中无此名的登记项, 就将 此名 字填入符号表中；至于与此名相关的其它信 息, 可 视工作方便分别在语法分析、语义分析及中 间代码 生成等阶段陆续填入。
第8章 符号表与错误处理
例8.1 一示意性源程序如下: PROGRAM PP (input,output); COUNT norw=13;
第四章 程序语言的性质

第四章 程序语言的性质

6
1型文法—上下文有关文法

产生式的形式为： , 其中任意非终结符 串， 是终结符和非终结符的任意序列，但 中的符号个数应不多于的符号个数


从开始符开始导出的串的长度是递增的 在生成串时，需要使用固定数量的存储空间，例如 识别上下文无关文法无法识别的串ancnbn 上下文有关文法太复杂，很难用于程序设计语言 人们对上下文有关文法的很多特征还不太清楚

这是综合属性，包含程序中声明的名字集合。该属性 可以沿树向下传递，成为继承属性，用于正确地生成 数据的代码。
28
属性文法的使用


首先创建语法分析树。属性文法假设你已经知道表达 式是如何推导出来的，它并不关心是如何分析推导出 来的。 定义属性的函数可以是任意给定的，因此定义属性的 过程完全是手工完成的。 如果只有综合属性，并且文法是 LR(k)，那么，属性 文法可以用来在语法分析时自动产程中间代码。 这就是 YACC 如何工作的，它利用属性文法来计算所 有非终结符的值。
25
属性文法

例：考虑算术表达式的简单文法。
E→T|E+T T→P|T×P P→I|(E)

其语义通过文法中非终结符间的关系集合定义。如： 下面函数生成该文法生成的任意表达式的值：
产生式 E→E+T E→ T T→T×P T→P P→ I P→(E) 属性 Value(E1)=V(E2)+V(T) V(E)=V(T) V(T1)=V(T2)×V(P) V(T)=V(P) V(P)=数I的值 V（P）=V（E）

如Hoare的公理语义。
22
语义建模（5）—规约模型


描述实现程序的各个函数的关系，只要 我们可以证明一个实现符合了所有的函 数间的关系，则称实现相对于规约是正 确的。 代数数据类型是形式规约的一种形式。
第4章 语义分析-编译原理及实践教程(第3版)-黄贤英-清华大学出版社

第4章 语义分析-编译原理及实践教程(第3版)-黄贤英-清华大学出版社


B0
B1 B2
char g_c1; char *g_ch2; int func1(int a, int b) {
int g_i1 = 5; for(;;){
char g_i1 = ‘b’; int *var1; printf(“Input numbers”); …… printf(“the result is %d”,*var1); } }
4.1语义分析概述
语义分析：在进行翻译之前，必须对这些语法上正确的语法 单位的内部逻辑含义是否正确进行检查。
语义分析的地位和作用
语法树 语法分析
语义分析
建立 符号表
静态语 义检查
语法树
语义错误
编译的后续阶段
符号表
语义分析的任务 对结构上正确的源程序进行上下文有关性质的审查，审查源 程序有无语义错误，为代码生成阶段收集类型信息。
B3 B4
变量表保存源程序中的所有变量定义。 如果语言没有作用域的限制，就可以将所有的变量记录在变量 表中，这种情况下，不允许定义同名变量。
入口 1 2 3 4
……
变量名 g_i1 var1 g_c1 g_ch2 ……
变量长度 变量类型 值 地址
4
int
4
int
4
char
5
char *
……
有作用域的限制的，将从最外层开始到当前作用域的编号组合 起来，其内部元素是每个作用域的编号，即：作用域路径
声明与定义语义检查
（1）变量未声明就使用、变量重定义； （2）函数未声明就定义和调用、函数重定义、函数声明与定
义不匹配、函数调用与声明不匹配、函数和变量重名等； （3）数组长度必须是正整数、数组名不能和变量名、函数名
编译原理 符号表和词法分析

编译原理 符号表和词法分析


三、存储分配&符号表的组织（续一） 存储分配 符号表的组织 续一）
静态分配：编译时能够确定所需存储空间的大小， 静态分配：编译时能够确定所需存储空间的大小，并进行
存储分配。 存储分配。
1、同一分程序的不同分量分配在不同单元。 2、内外层中的不同量分配在不同的单元。 形参的分配。 eg. Procedure sum1(var sum:integer,I:integer); begin sum:=sum+I; end;
四、标识符的处理
Program summ(input,output) var I,sum:integer; procedure xxx( I:integer) begin … end; begin sum:=0; for I:=1 to 100 do sum:=sum+I; end.
四、标识符的处理
续一） 二、符号表的内容（续一）
标准类型标识符： 标准类型标识符：integer,char,real
eg. const pi=3.1415926 4 标 识 符 的 属 性
常量标识符 名字、 名字、值、类型
简单变量标识符
var i,j,k:integer;
名字、类型、 名字、类型、地址
var a:array[1..10]of integer;
三、存储分配&符号表的组织（续二） 存储分配 符号表的组织 续二）
形参的分配。
eg. Procedure sum1(var sum:integer,I:integer); begin sum:=sum+I; end;
原则： 原则：
1、如果形参是按值调用，则分配一个单元存放实参的值 、如果形参是按值调用， 2、如果形参是按名调用，则分配一个单元存放实参的地址。 、如果形参是按名调用，则分配一个单元存放实参的地址。

第六章(2)符号表的管理


}
} a = 1, b = 1 printf(“a = %d, b = %d\n”, a, b);
}
33
2.在语言程序的局部化单位中，标识符的出现分为定 义性出现和使用性出现。
⑴定义性出现的标识符：局部化单位的声明部分出现 的标识符，其作用是确定该标识符的属性信息，如 名字，类型，存储位置等。一个标识符在一个局部 化单位只能被声明一次。
28
❖对于散列表，新符号的登录是通号表的目的:
判断该符号的存在性; 获取该符号的语义属性. ❖符号表的查找算法：顺序查找、折半查找、杂凑查 找.
30
6.3.3 符号表的局部化处理
一、问题的引出
1.源语言程序的局部化单位 程序中允许有声明的 部分称为一个局部化单位,通常是一个子程序(函数、 过程)或分程序：
19
6.3.1 符号表的建立和查找
一.符号表的初始化 在编译过程中某个时刻，符号表的状态反
映了该时刻被编译的语言程序正被编译的位置 的状态.具体来说主要是反映了在该时刻被编译 的语言程序中可视标识符的状态. 符号表的初始化，在对语言程序开始编译的时刻， 定义建立符号表的初始状态.
20
1.符号表的表长是渐增变化的情况： ❖线性组织和二分法组织的符号表，其表的长度在编译开始时 通常为0,而随着符号的逐步登录，表长增长. ❖按这类方法组织的符号表，其初始化方法只需将表尾推向表
一、符号表的总体组织
符号表的每一项包含两部分：标识符的名字；该名字的信 息。
不同类别的标识符所包含的信息是不同的。 符号表的总体组织既可以采用多表结构，也可以采用单表
结构,也可以二者折中。究竟采用哪种结构并没有统一的规 定，编译程序可根据实际处理语言的需要进行选择。

《操作系统》习题集：第4章文件系统

《操作系统》习题集第4章文件系统第1页共4页2013-5，2014-10 北理珠“操作系统”课题组第4章文件系统-习题集一、选择题1.文件系统是指（）。

【＊，联考】A. 文件的集合B. 文件的目录C. 实现文件管理的一组软件D. 文件、管理文件的软件及数据结构的总体2.文件系统的主要目的是（）。

【＊，★，联考】A. 实现对文件的按名存取 B. 实现虚拟存储C. 提高外存的读写速度D. 用于存储系统文件3.目录文件所存放的信息是（）。

【＊＊，★，联考】A. 某一文件存放的数据信息B. 某一文件的文件目录C. 该目录中所有数据文件目录D. 该目录中所有子目录文件和数据文件的目录4.在文件系统中，文件访问控制信息存储的合理位置是（）。

【＊＊，★，09考研】A. 文件控制块B. 文件分配表C. 用户口令表D. 系统注册表5.索引文件由逻辑文件和（）组成。

【＊＊，联考】A. 符号表 B. 索引表 C. 交叉访问表D. 链接表6.文件系统在创建一个文件时，为它建立一个（）。

【＊＊，联考】A. 文件目录项B. 目录文件C. 逻辑结构D. 逻辑空间7.通常对文件系统来说，文件名及属性可以集中在（）中，以便查找。

【＊＊，★，联考】A. 目录文件 B. 索引文件C. 字典D. 作业控制块8.文件绝对路径名是指（）。

【＊，★，联考】A. 文件名和文件扩展名 B. 一系列的目录文件名和该文件的文件名C. 从根目录到该文件所经历的路径中各符号名的集合 D. 目录文件名和文件名的集合9.设置当前工作目录的主要目的是（）。

【＊＊，★，10考研】A. 节省外存空间B. 节省内存空间C. 加快文件的检索速度D. 加快文件的读写速度10.文件系统可以采用两级目录结构，这样可以（）。

【＊，★，联考】A. 缩短访问文件存储器的时间B. 实现文件共享C. 节省内存空间D. 解决不同用户之间的文件名冲突问题11.文件系统采用多级目录结构后，对于不同用户的文件，其文件名（）。

编译原理考试知识点复习

第一章：编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。

解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。

编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。

解释程序和编译程序的根本区别：是否生成目标代码第三章：Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG）◊ 0型语言或短语结构语言文法Ｇ的每个产生式α→β中：若α∈Ｖ*ＶNＶ*, β∈(ＶN∪ＶT)* ，则Ｇ是0型文法，即短语结构文法。

1型文法（CSG）◊ 1型语言或上下文有关语言在0型文法的基础上：若产生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外，则Ｇ是１型文法,即：上下文有关文法另一种定义：文法G的每一个产生式具有下列形式：αAδ→αβδ，其中α、δ∈V*，A∈VN，β∈V+；2型文法（CFG）◊ 2型语言或上下文无关语言文法Ｇ的每个产生式A→α，若A∈ＶN ,α∈(ＶN∪ＶT)*，则Ｇ是２型法，即：上下文无关文法。

3型文法（RG）◊ 3型语言或正则(正规)语言若Ａ、Ｂ∈ＶN，ａ∈ＶT或ε，右线性文法：若产生式为Ａ→ａＢ或Ａ→ａ左线性文法：若产生式为Ａ→Ｂａ或Ａ→ａ都是３型文法（即：正规文法）最左（最右）推导在推导的任何一步α⇒β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换规范推导：即最右推导。

规范句型：由规范推导所得的句型。

句子的二义性（这里的二义性是指语法结构上的。

）文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。

文法的二义性一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。

编译原理第四章语法分析-自上而下分析


• 例 4.4
4.4 递归下降分析程序构造
• 递归下降分析器：
这个分析程序由一组递归过程组成的，每个过程对应 文法的一个非终结符。 E→TE’ E’→+TE’| T→FT’ T’→*FT’| F→(E)|i
PROCEDURE E BEGIN T ; E’ END PROCEDURE E’ IF SYM=‘＋’THEN BEGIN ADVANCE ; T ; E’ END
4.2 自上而下分析面临的问题
• 例4.1 假定有文法
(1) SxAy (2)A**|*
对输入串x*y，构造语法树。 • 构造过程：
(1)把S作为根 (2)用S的产生式构造子树 (3)让输入串指示器IP指向输入串的第一个符号。
S x A y x
S
A y x
S
A y
*
*
*
(4)调整输入串指示器IP与叶结点进行匹配。 (5)如果为非终结符，用A的下一个产生式构建子树。 (6)如果匹配成功则结束；否则，回溯到步骤(4)。
• 一个反例：
– 文法：SQc|c；QRb|b；RSa|a虽然不是直接 左递归，但S、Q、R都是左递归。
• 消除左递归算法：
– 算法的思想是：
• • • • 首先构造直接左递归； 再利用一般转换规则，消除直接左递归 化简文法。 下面算法在不含PP，也不含在右部产生式时可以消除 左递归。
• 消除一个文法的左递归算法：
(1) 把文法 G 的所有非终结符按任一种顺利排列成 P1…Pn；按此顺序执行； (2) FOR i:=1 TO n DO
BEGIN FOR j:=1 TO i-1 DO 把形如Pj+1→Pj 的规则改写成 Pj+11|1|…k| 。其中 Pj1|1|…k 是关于 Pj 的 所有规则； 消除关于Pi规则的直接左递归性。 END 化简由（２）所得的文法。即去除那些从开始符号出发永 远无法到达的非终结符的产生规则。

编译原理教程课后习题答案——第四章

第四章语义分析和中间代码生成4.1 完成下列选择题：(1) 四元式之间的联系是通过实现的。

a. 指示器b. 临时变量c. 符号表d. 程序变量(2) 间接三元式表示法的优点为。

a. 采用间接码表，便于优化处理b. 节省存储空间，不便于表的修改c. 便于优化处理，节省存储空间d. 节省存储空间，不便于优化处理(3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。

a. ┐AB∨∧CD∨b. A┐B∨CD∨∧c. AB∨┐CD∨∧d. A┐B∨∧CD∨(4) 有一语法制导翻译如下所示：S→bAb {print″1″}A→(B {print″2″}A→a {print″3″}B→Aa) {print″4″}若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为。

a. 32224441 b. 34242421c. 12424243d. 34442212【解答】(1) b (2) a (3) b (4) b4.2 何谓“语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一简例予以说明。

【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。

也即在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。

用语法制导翻译(SDTS)生成中间代码的要点如下：(1) 按语法成分的实际处理顺序生成，即按语义要求生成中间代码。

(2) 注意地址返填问题。

(3) 不要遗漏必要的处理，如无条件跳转等。

例如下面的程序段：if (i>0) a=i+e-b*d; else a=0;在生成中间代码时，条件“i>0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。

此外，按语义要求，当处理完(i>0)后的语句(即“i>0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。

第四章 MATLAB符号计算


Ezpolar函数实现极坐标中二维曲 线图象的绘制,它的调用格式:
ezpolar(f,[a,b])
说明: 绘图表达式为rho=f(theta)极坐标曲线,
theta的取值范围为,缺省时为[0,2*pi]
例:p83
4.5.2三维绘图函数
ezplot3是实现三维绘图的函数,它的 调用格式:
ezplot3(x,y,z,[tmin,tmax]) ezplot3(x,y,z,[tmin,tmax ],'animate')
3.符号表达式的提取分子和分母运算
在matlab中可利用numden函数来提取符号表达式 中的分子或分母。其一般调用格式为:
[n,d]=numden(s)
说明:
参数s是符号表达式是一个 有理分式或可以展开为有理
例: s=sym('2/5+3/7')
n= 29
分式,numden函数把有理分 式的分子返回给n,分母返回
dsolve在求常微分方程组时 的调用格式为:
dsolve('eq1,eq2,...','cond1,cond2...','v')
说明: 该函数求解常微分方程组eq1,…,eqn在初值条件或边界 条件为cond1,…,condn下的符号特解，若不给出初值 条件，则求方程组的通解，v为指定的返回值中的变量 表示。
例4-9解超越方程组
sin(x+y)-y*exp(x)=0 x^2-y=2
syms x y
[x,y]=solve('sin(x+y)-y*exp(x)=0','x^2-y=2')
x =-.66870120500236202933135901833637
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

4.2 符号的主要属性及作用
4、作用域及可视性 一个符号变量在程序中起作用的范围，称谓其作用域。 一般来说，定义该符号的位置及存储类关键字决定了 该符号的作用域。 一般来说变量的作用域就是该变量可以出现的场合， 也就是说在某个变量作用域范围内该变量是可引用的， 这就是变量可视性的作用域规则。 变量可视性不仅仅取决于它的作用域，还有两种情况 影响到一个变量的可视性。 – 函数的形式参数 – 分程序（或复合语句）结构
第4章 符号表
编译原理课程组 计算机工程学院
第4章 符号表
4.1 符号表的作用和地位 4.2 符号的主要属性及作用 4.3 符号表的组织 4.4 符号表的管理
思考题
1. 什么是符号表? 2. 标识符符号通常有那些属性？ 3.你认为符号表是怎样进行组织的？ 4.你认为符号表是怎样进行管理的？
【学习目标】
4.4 符号表的管理
符号表的行为通常主要是符号表的初始化、符 号的登录、符号的查找和有关分程序结构的符 号表层次管理。 对符号表的这些管理除初始化之外，都是动态 进行的。
一、符号表的初始化
符号表的初始化，就是在对语言程序开始编译 的时刻，定义建立符号表的初始状态。 符号表的不同组织方法，要求不同的初始化方 法。编译开始时符号表的状态应该是没有任何 可视标识符的状态。反映这种状态的方式通常 有以下两种情况：
其次，是根据变量出现的次序。 一般说来，决定变量在某个区中所处的具体位置，这通 常使用在该区域中相对区头的相对位置来确定。 而有关 区域的标志及相对位置都是作为该变量的语义信息被收 集在该变量的符号表属性中。
二、符号表的操作
往表中填入一个新的名字； 对给定名字，查询名字是否已在表中； 对给定名字，访问它的某些信息； 对给定名字，填写或更新它的某些信息； 删除一个或一组无用的项。
2、上下文语义的合法性检查的依据
通过符号表中属性记录可进行相应上下文的语义检查。
例如：在C语言中同一个标识符可作引用说明也可作定义说明
…… int i [3][5]; //定义说明i
语义检查可发现
…… extern float i; //引用说明i
其不一致错误。
……
又例如：在C语言中同一个标识符可作引用说明也可作定义说明
在编译程序中符号表用来存放语言程序中出现 的有关标识符的属性信息，这些信息集中反映 了标识符的语义特征属性。本章目的使学生深 刻全面地了解符号表的地位和作用；掌握符号 表的组织和管理方法；以及编译过程中符号表 的操作活动过程。
【难重点】
◇ 符号表总体组织的选择原则。 ◇ 变量的类型和存储类别等属性的重要性。 ◇ 采用单表结构时,如何解决分程序构造中同名名
复习
词法分析程序的功能是读入源程序，输出单词符号。 单词符号是一个程序设计语言的基本语法符号，一般分为下列五种： – 保留字，关键字：如if, else, while等 – 标识符：变量名、程序名、函数名等 – 常数（量） – 运算符 – 界符 词法分析程序所输出的单词符号常常采用以下二元式表示：
…a…
｝ ｝ ｝
图中第3层所引用的a，既 不是第4层的float a；也 不是第1层int a；而是第 2层char a
4.2 符号的主要属性及作用
5、存储分配信息
根据符号变量的存储类别定义及它们出现的位置和次 序来确定每一个变量应分配的存储区及在该区中的具 体位置，用相对区头的位移量表示。 通常一个编译程序有两类存储区： – 静态存储区 – 动态存储区
……
int i [3][5];
……
重定义冲突的语义错误。
float i[4][2];
……
int i [3][5];
3、作为目标代码生成阶段地址分配的依据
每个符号变量在目标代码生成时需要确定其在 存储分配的位置（主要是相对位置）。
首先，要确定其被分配的区域。 例如，在C语言中首先要确定该符号变量是分配在公共区 （extern)、文件静态区（extern static)、函数静态区 （函数中static)、还是函数运行时的动态区（auto)等。
1、符号表的表长是渐增变化的情况
线性组织和二分法组织的符号表初始化方法 只需将表尾推向表头即可。
2、符号表的表长是确定的情况
散列组织的符号 表，表长并不反 映已登录的表项 个数，其表长通 常是确定的，对 这类符号表的初 始化方法，需要 将表中全部表项 值清除。
二、符号的登录（填表）
当编译程序从语言程序中获得一个标识符符号 并确定该符号在符号表中尚不存在时，就要将 此符号登录到符号表中。 登录符号到符号表中，首先要确定登录的位置。
(单词类别，单词自身的值)。 单词的类别是语法分析需要的信息，而单词自身的值则是编译其它阶段 需要的信息。 对于标识符来说，还需要记载它的类别、层次还有其他属性，如果这些 属性统统收集在符号表中，那么可以将单词的二元式表示设计成如下形 式（标识符，指向该标识符所在符号表位置的指针）
复习
例 ：对语句if i=5 then x:=y的词法分析结果
符号表的操作主要为查表和填表。
4.2 符号的主要属性及作用
不同的语言定义的标识符属性不尽相同，我们主要讨论符号 表中的标识符一般设置的属性项目以及它们的功能。
1、符号名：符号表中符号名作为表项之间的唯一区别一般不允许重名。 允许操作重载的语言中，函数名、过程名是可以重名的，对于这类 重载的标识符要通过它们的参数个数和类型以及函数返回值类型来 区别，以达到它们在符号表中的惟一性。
关于排序表的表项建立及符号查找，通常采用
"二分法"。 符号
属性
h
A
B
C
D
p
3、散列组织
一个符号在散列表中的位置，是由对该符号 （即字符代码串）进行某种函数操作（通常称 为“杂凑函数”）所得到的函数值来确定的。 所得到的函数值与该表项在表中位置的对应关 系，是通过对函数值的“求整”以及相对于表 长的“求余”得到的。
2、符号的类型：符号表中设置一个符号类型域，存放该符号的类型。
3、存储类别：存储类别定义采用二种方式，一种是用关键字指定（例 如C语言中用Static定义是属于文件的静态存储变量或属于函数内部 的静态存储变量，用regist定义使用寄存器存储的变量）；另一种方 式是根据定义变量说明在程序中的位置来决定。（例如C语言中，在 函数体外默认存储类关键字所定义的变量是外部变量，而在函数体 内默认存储类关键字所定义的变量是内部变量）
符号表属性域的组织，根据属性性质大致分成 两类： 等长属性值域组织 不等长属性值域的组织
五、下推链域的组织
在程序语言的结构中，分程序的分层结构允许 同名标识符具有的生存期发生重叠。为实现这 种同名标识符的语义功能，符号表中需要设立 下推链域的组织。 下推链域组织要求在进入一个内层结构并发生 重名标识符定义时，需把当前符号表中外层的 该符号表项下推到下推链中而在符号表被下推 的表项处建立内层的同名标识符的表项。
五、下推链域的组织
符号
内情向 量指针 型
层次
下推 指针
… int 3 …
… int 0 … … int 1 … … int(0) func() {
…; float i;…………….(1) …; { …;
int i[5];…………(2) …; { …;
int i;………….(3) … } … } … }
– 保留字if
（3，‘if’）
– 标识符i
（1，指向i的符号表入口）
– 等 号=
（4，‘=’）
– 常 数5
（2，‘5’）
– 保留字then
（3，‘then’）
– 标识符x
（1，指向x的符号表入口）
– 赋值号:=
（4，‘:=’）
– 标识符y
（1，指向y的符号表入口）
– 分 号；
（5，‘；’）
一、符号表的作用和地位
二、符号表项的排列
在编译程序中，符号表项的组织传统上采用三 种构造方法。即线性法，二分法及散列法。
1、线性组织
这种方法规定符号表中表项按它的符号被扫描 到的先后顺序登录。
符号
h
A
B
D
C
p
属性
2、排序组织及二分法
排序组织的符号表，就是在符号表中的表项按 其符号的字符代码串（可以看成一个整数值） 的值的大小从大到小（或从小到大）排列的。
三、关键字域的组织
符号表的关键字域就是符号本身，它可以是语 言的保留字，操作符号或标识符（包括变量名， 函数名，记录结构标志等）。 – 等长关键字域（段）符号表 – 不等长关键字段符号表——关键字池组织
等长关键字域（段）符号表
•编译程序中标识符的内部规则是符号表关键字组织的基础和依据。 •用户程序中的标识符，考虑到习惯和可读性，长度是从1到内部规则 规定长度之间任意字符个数。 •符号表中存放标识符的关键字段等长，具有统一的最大长度。譬如C 语言的关键字段长度可以是32个（其中31个是存放名字，余一个是
4.2 符号的主要属性及作用
1）函数的形式参数：影响变量可视性的举例
int a；
int func(a,b)
float a；
int b； {
其中int a与float a重名，而函数体中可看到的 a是float a，int a在函数中是看不到的。
…
…a… //引用float a
… }
4.2 符号的主要属性及作用
符号表的基本结构如下：
符号
属性
一、符号表的总体组织（1）
1、第一种方法 把属性种类完全相同的那些符号组织在一起，构造出 表项是分别为等长的多个符号表。
2、第二种方法 把所有语言中的符号都组织在一张符号表中。 假设有下列三类符号及其所需之属性。 符号 属性值1 属性值2 属性值3