编译原理讲义(第五章:语法分析--自底向上分析技术)南京大学计算机系赵建华概论从输入符号出发试图把它归约成识别符号每一步都寻找特定得某个类型的短语(一般是简单短语)进行归约在分析过程中每次归约的都是最左边的简单短语(或其它短语)从语法树的角度以输入符号为树的末端结点试图向根结点方向往上构造语法树基本问题如何找出进行直接归约的简单短语将找到的简单短语归约到哪个非终结符号讨论前提和自顶向下技术同样不考
第四章 自顶向下语法分析方法语法分析是编译过程的核心部分语法分析的任务是:按照文法从源程序符号串中识别出各类语法成份同时进行语法检查为语义分析和代码生成作准备执行语法分析任务的程序称为分析程序也称为语法分析器它是编译程序的主要子程序之一在第二章中我们已经介绍过通过语法分析可建立起相应的语法树按语法树的建立方法我们将语法分析方法分成两大类即自顶向下分析和自底向上分析下面我们先介绍自顶向下分析本章重
#
使用 自底向上语法分析概述动作becAbcb归约(5)成功Z ?rm ABb ? rm AbBb ? rm Abcb ?rm abcb一些相关概念P:(1) E ? T(2) E ? E T(3) T ? F(4) T ? T F(5) F ? (E)(6) F ? i(7) F ? nEE一些相关概念规范活前缀:满足如下条件之一的规范前缀称为规范活前缀:该规范前缀不包含
自顶向下分析法也称面向目标的分析方法也就是从文法的开始符号出发企图推导出与输入的单词串完全匹配的句子若输入串是给定的句子则必能推出反之必然出错自顶向下分析法又分为确定的和不确定的两种若有文法G[S]:S?aAS?dA?bASA??若输入串W=abd则试图推导出abd串的推导过程为:S=>aA=>abAS=>abS=>abd第1个L指的是由左向右地处理输入第2个L指的是它为输入串描绘出一个最左推导括
属性值分类据计算的依赖关系分成不相交的两类:综合属性(synthesized attribute)在分析树中一个结点的综合属性值是从其子结点的属性值计算出来的继承属性(inherited attribute)一个结点的继承属性值是由该结点兄弟结点和父结点的属性值计算出来的36digit?lexval:=3F?val:=4在建立每一个结点处 语法树 产生式s→if B then S
单击34单击单击34自底向上的语法分析. 移进归约的概念 自下而上分析 .1 归约例S ? aABe A ? Abc bB ? d 自下而上分析 .1 归约例S ? aABe A ? Abc bB ? dabbcde(读入ab)ab 自下而上分析 .1 归约例S ? aABe A ? Abc bB ? dabbcdeaAbcde(归约)abA 自下而上分析 .1 归约例S ? aABe
单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级第五章 语法分析——自底向上语法分析自底向上语法分析5.1 自底向上分析的一般过程5.2 算符优先分析5.3 LR分析若Z ? S 则 S ? L(G[Z]) 否则 S ? L(G[Z]) G[Z]存在主要问题: 左递归问题 回溯问题 主要方法: 递归子程序法
实验二:自底向上语法分析算法程序设计实验内容:根据讲授的自底向上语法分析方法可以根据简单优先语法分析算法算符优先语法分析算法或LR语法分析算法设计语法分析程序针对文法:G[E]E→ET TT→TF FF→( E ) i设计过程:自底向上语法分析含义:自底向上分析过程是从所给输入串出发对其进行最左归约的过程自底向上归约的过程也是自底向上构建语法树的过程设计主要思想:从输入串出发尽可能
单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级第三章 词法分析3.1 对于词法分析器的要求3.2 词法分析器的设计3.3 正规表达式与有限自动机3.4 词法分析器的自动产生3.1 对于词法分析器的要求词法分析的功能和输出形式:词法分析器的功能是接收输入源程序输出单词符号单词符号分五种:关键字标识符常数运算符界符词法分析器所输出的单词符号常常表示成如下的二元式: (
违法有害信息,请在下方选择原因提交举报