new第四章语法分析.ppt

《new第四章语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理CompilerPrinciples蒋凌云Ｊｉａｎｇｌｉｎｇｙｕｎ@njupt.edu.cn南京邮电大学.计算机学院第四章语法分析compilingrunningprogramming教材：《编译技术原理及其实现方法》王汝传编著第四章语法分析本章内容§4.1引言一、语法分析任务二、语法分析方法§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法§4.3自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用§4.4语法分析程序的自动生成一、分析器的生成器YACC二、

2、用YACC处理二义性文法一、简单优先文法分析法三、优先函数及其构造1.与文法有关的一些关系定义1.优先函数定义2.构造文法关系传递闭包2.优先函数矩阵的构造和自反传递闭包3.利用优先函数矩阵进行语法分析3.文法优先关系概念四、LR分析法4.文法优先关系的构造1.LR分析法一般概述5.简单优先文法2.LR分析器工作原理6.简单优先文法分析算法3.LR（0）分析表构造二、算符优先分析法4.SLR（1）分析表构造1.算符优先关系概念5.LR（1）分析表构造2.算符优先文法6.LALR分析表构造3.算符优先关系的构造方法五、二义性文法的应用4.最左素短语1.问题的提出5.算符优先分析算法2.二义性文法

3、分析表的构造第四章语法分析§4.3自底向上语法分析一、简单优先文法分析法三、优先函数及其构造1.与文法有关的一些关系定义1.优先函数定义2.构造文法关系传递闭包2.优先函数矩阵的构造和自反传递闭包3.利用优先函数矩阵进行语法分析3.文法优先关系概念四、LR分析法4.文法优先关系的构造1.LR分析法一般概述5.简单优先文法2.LR分析器工作原理6.简单优先文法分析算法3.LR（0）分析表构造二、算符优先分析法4.SLR（1）分析表构造1.算符优先关系概念5.LR（1）分析表构造2.算符优先文法6.LALR分析表构造3.算符优先关系的构造方法五、二义性文法的应用4.最左素短语1.问题的提出5.算符

4、优先分析算法2.二义性文法分析表的构造第四章语法分析§4.3自底向上语法分析一、简单优先文法分析法三、优先函数及其构造1.与文法有关的一些关系定义1.优先函数定义2.构造文法关系传递闭包2.优先函数矩阵的构造和自反传递闭包3.利用优先函数矩阵进行语法分析3.文法优先关系概念四、LR分析法4.文法优先关系的构造1.LR分析法一般概述5.简单优先文法2.LR分析器工作原理6.简单优先文法分析算法3.LR（0）分析表构造二、算符优先分析法4.SLR（1）分析表构造1.算符优先关系概念5.LR（1）分析表构造2.算符优先文法6.LALR分析表构造3.算符优先关系的构造方法五、二义性文法的应用4.最左素

5、短语1.问题的提出5.算符优先分析算法2.二义性文法分析表的构造第四章语法分析§4.3自底向上语法分析§4.3自底向上语法分析前面我们介绍的几种语法分析方法对相应的文法都有一定的要求。例如：因此，上述这些方法在使用上有一定局限性。LR分析法是1965年由Knuth提出一种自底向上语法分析方法，可用于一大类上下文无关文法分析，这种技术叫做LR(K)分析技术。不带回溯的自顶向下分析方法要求文法不存在左递归，并且每一规则的各候选式的终结首符集两两不相交；算符优先分析方法则要求文法的各终结符号对间至多只有一种优先关系，等等。1.LR分析法一般概述§4.3自底向上语法分析（1）LR（K）分析法定义LR

6、(K)分析法意思是：L是指从左(Left)到右扫描输入符号串，R是构造最右(Rightmost)推导过程自底向上的分析方法。K是指在决定分析动作时向前看符号的个数。若K＝0，就为LR(0)分析，说明分析动作时，不向前看任何符号，LR(1)分析，说明分析动作时只向前看一个符号。这是一类对上下文无关文法进行“自左到右扫描和最左归约”的自底向上的分析方法，在这种分析过程中，它至多只向前查看Ｋ个输入符号就能确定当前的动作是移进还是归约；若动作归约，它还能唯一地选中一个规则去归约当前已识别的句柄。§4.3自底向上语法分析（2）LR分析法的特点1)LR分析器(程序)基本上可以识别所有上下文无关文法写的编程

7、语言结构，分析能力强且适用范围广2)LR分析法是当前最一般的“移进-归约”分析方法3)LR分析法在自左向右扫描输入串时能发现其中错误，并能指出出错地点。4)LR分析程序可以自动生成§4.3自底向上语法分析（3）LR分析器的组成从逻辑上说，一个LR分析器包括两部分：一个总控程序和一张分析表。一般说来，所有LR分析器总控程序是一样的，只是分析表各不相同。§4.3自底向上语法分析（4）LR分析表种类1