Semantic Analysis & Runtime Environment

语法分析 知识点: 运行环境 知识点: 活动记录、控制栈 栈式存储分配 非局部名字的访问 参数传递方式 7.1 程序运行时的存储组织 7.1.1 程序运行空间的划分 活动与过程的概念 过程:静态概念 活动:一次过程的每次执行,是动态概念 两者可以为1:1或1:m的关系,递归过程中可能一若干个活动活着。 活动的生存期 活动的生存期要么是不重叠的,要么是嵌套的(区别于进程的地方!活动不可以并发执行!) 对于一个程序,它会向操作系统申请一块内存空间: 活动记录会在控制栈中根据栈式存储分配策略来实现。 7.1.2 活动记录与控制栈 控制栈 局部数据的安排 编址限制的影响(padding) 7.1.3 名字的作用域及名字绑定 名字的作用域: 最近嵌套原则 名字绑定: note: 对于递归程序中定义的名字,即使是同一个名字也可能映射到不同的存储空间。 左值:存储空间的地址 右值:存储空间的内容 7.2 存储分配策略 7.2.1 静态存储分配 条件:源程序中声明的各种数据对象所需存储空间的大小在编译时都可以确定。 存储分配:编译时,为他们分配固定的存储空间。 地址绑定:程序装入内存时进行。 运行期间:名字的左值保持不变 不允许递归调用和建立动态数据结构 7.2.2 栈式存储分配(重点) 递归调用:同一个过程在不同存储位置出现。 调用序列 返回序列 其中top_sp = top_ep' - C1 - C2; P是通过top_sp找到返回值并放入局部数据域中。

Syntax-directed Translation

语法制导翻译技术 整体思路: 首先,根据翻译目标来确定每个产生式的语义; 其次,根据产生式的含义,分析每个符号的语义; 再次,把这些语义以属性的形式附加到相应的文法符号上(即把语义和语言结构联系起来); 然后,根据产生式的语义给出符号属性的求值规则 (即语义规则),从而形成语法制导定义。 ==翻译目标决定产生式的含义、决定文法符号应该具有的属性,也决定了产生式的语义规则。== 两种描述语法制导翻译的形式: 语法制导定义:是对翻译的高层次说明,它隐蔽了一些实现细节,无须指明翻译时语义规则的计算次序 L-属性可以一遍扫描,省去分析树和依赖图的步骤。 翻译方案:指明了语义规则的计算次序,规定了语义动作的执行时机。 5.1 语法制导定义以及翻译方案 5.1.1 语法制导定义 对上下文无关文法的推广 综合属性 左部符号的综合属性是从该产生式右部文法符号的属性值计算出来的;在分析树中,一个内部结点的综合属性是从其子结点的属性值计算出来的。 在分析树中,若一个结点的某一属性由其子节点属性决定,则为综合属性 若在一个语法制导定义仅仅使用综合属性,则称之为S-属性定义。而对于这种属性,通常采用自底向上的方法进行注释。 继承属性 出现在产生式右部的某文法符号的继承属性是从其所在产生式的左部非终结符号和/或右部文法符号的属性值计算出来的;在分析树中,一个结点的继承属性是从其兄弟结点和/或父结点的属性值计算出来的。 在分析树中,一个结点的继承属性由其父节点属性或它的兄弟节点属性值决定。 可以用继承属性表示程序设计语言中的上下文之间的依赖关系。 当一个语义规则的唯一目的是产生某个副作用,则通常写成过程调用或程序段,看成是产生式左部非终结符的虚拟综合属性 5.1.2 依赖图 在依赖图中: 为每个属性设置一个结点 如果属性b依赖于c,那么从属性c的结点有一条有向边连 到属性b的结点。 5.1.3 拓扑排序 首先找到入度为0的节点,删除该点及其边,重复该过程至所有点均被删除。 5.1.4 计算顺序 根据拓扑排序的顺序进行求值得到翻译。 总结:最基本的文法用于建立输入符号串的分析树; 为分析树构造依赖图; 对依赖图进行拓扑排序; 从这个序列得到语义规则的计算顺序; 照此计算顺序进行求值,得到对输入符号串的翻译。 5.1.5 S-属性与L-属性 S属性定义:仅仅涉及综合属性,是L属性的子集 L属性定义:要么是综合属性,要么是由父节点和左兄弟节点决定的继承属性。(右边的不行) 对于L属性计算顺序:深度优先遍历分析树 进入节点前,计算它的继承属性 从节点返回时,计算它的综合属性 5.

Lexcial Analysis & Parsing

I. 词法分析 词法分析器作用: 扫描源程序字符流 按照源语言的词法规则识别出各类单词符号 产生用于语法分析的记号序列 词法检查 创建符号表 — 为语法分析使用 接口:跳过注释、标注错误信息 一、词法分析程序与语法分析程序的关系 1.1 词法分析程序作为独立的一遍 1.2 词法分析程序作为语法分析程序的子程序 词法分析相当于函数,语法分析每一次需要记号时即调用词法分析函数获得记号。 这种操作的好处可以避免中间文件、省去取送记号的工作。 1.3 词法分析程序与语法分析程序作为协同程序 这种方法不常用。 二、词法分析程序的输入与输出 2.1 配对缓冲区 哨兵!!!(EOF) 把一个缓冲器分为大小相同的两半,每半各含N个字符,一般N=1KB或4KB。为了使得判断更为优化,在每个半区后面加上EOF。 这种做法是为了让缓冲区可以处理超出其范围的字符串。 2.2 词法分析程序的输出——记号 记号:某一类单词符号的类别编码,如id,num 模式:某一类单词符号的构成规则,如“有字母开头的字母字符串” 单词:某一类单词符号的具体实例,如hello 记号的属性 作用:记号影响语法分析的决策,属性影响记号的翻译。 三、记号的描述和识别 3.1 词法与正规文法 描述语言的标识符、常数、运算符和标点符号等记号的文法 3.2 记号的文法 标识符 描述标识符集合的正则表达式: 标识符的正规文法(右线性文法) 常数 整数 描述整数结构的正则表达式: 无符号数 运算符 分界符 关键字 四、词法分析程序的设计与实现 五、软件工具LEX II.