new第四章语法分析.ppt

编 译 原 理Compiler Principles蒋凌云南京邮电大学.计算机学院 第四章第四章 语法分析语法分析compilingcompilingrunningrunningprogrammingprogramming教材：编译技术原理及其实现方法王汝传教材：编译技术原理及其实现方法王汝传教材：编译技术原理及其实现方法王汝传教材：编译技术原理及其实现方法王汝传 编著编著编著编著第四章第四章 语法分析语法分析本章内容本章内容本章内容本章内容4.1 4.1 引言引言引言引言 一、语法分析任务一、语法分析任务一、语法分析任务一、语法分析任务 二、语法分析方法二、语法分析方法二、语法分析方法二、语法分析方法4.2 4.2 自顶向下语法分析自顶向下语法分析自顶向下语法分析自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法一、自顶向下分析方法的问题及其解决办法一、自顶向下分析方法的问题及其解决办法一、自顶向下分析方法的问题及其解决办法 二、递归子程序分析法（递归下降分析法）二、递归子程序分析法（递归下降分析法）二、递归子程序分析法（递归下降分析法）二、递归子程序分析法（递归下降分析法）三、三、三、三、LLLL（1 1）分析法）分析法）分析法）分析法4.3 4.3 自底向上语法分析自底向上语法分析自底向上语法分析自底向上语法分析 一、简单优先文法分析法一、简单优先文法分析法一、简单优先文法分析法一、简单优先文法分析法 二、算符优先分析法二、算符优先分析法二、算符优先分析法二、算符优先分析法 三、优先函数及其构造三、优先函数及其构造三、优先函数及其构造三、优先函数及其构造 四、四、四、四、LRLR分析法分析法分析法分析法 五、二义性文法的应用五、二义性文法的应用五、二义性文法的应用五、二义性文法的应用4.4 4.4 语法分析程序的自动生成语法分析程序的自动生成语法分析程序的自动生成语法分析程序的自动生成 一、分析器的生成器一、分析器的生成器一、分析器的生成器一、分析器的生成器YACCYACC 二、用二、用二、用二、用YACCYACC处理二义性文法处理二义性文法处理二义性文法处理二义性文法 一、简单优先文法分析法一、简单优先文法分析法 三、优先函数及其构造三、优先函数及其构造 1.1.与文法有关的一些关系定义与文法有关的一些关系定义 1.1.优先函数定义优先函数定义 2.2.构造文法关系传递闭包构造文法关系传递闭包 2.2.优先函数矩阵的构造优先函数矩阵的构造 和自反传递闭包和自反传递闭包 3.3.利用优先函数矩阵进行语法分析利用优先函数矩阵进行语法分析 3.3.文法优先关系概念文法优先关系概念 四、四、LRLR分析法分析法 4.4.文法优先关系的构造文法优先关系的构造 1.LR 1.LR分析法一般概述分析法一般概述 5.5.简单优先文法简单优先文法 2.LR 2.LR分析器工作原理分析器工作原理 6.6.简单优先文法分析算法简单优先文法分析算法 3.LR 3.LR（0 0）分析表构造）分析表构造二、算符优先分析法二、算符优先分析法 4.SLR4.SLR（1 1）分析表构造）分析表构造 1.1.算符优先关系概念算符优先关系概念 5.LR 5.LR（1 1）分析表构造）分析表构造 2.2.算符优先文法算符优先文法 6.LALR 6.LALR分析表构造分析表构造 3.3.算符优先关系的构造方法算符优先关系的构造方法 五、二义性文法的应用五、二义性文法的应用 4.4.最左素短语最左素短语 1.1.问题的提出问题的提出 5.5.算符优先分析算法算符优先分析算法 2.2.二义性文法分析表的构造二义性文法分析表的构造 第四章第四章 语法分析语法分析4.3 4.3 自底向上自底向上自底向上自底向上语语法分析法分析法分析法分析 一、简单优先文法分析法一、简单优先文法分析法 三、优先函数及其构造三、优先函数及其构造 1.1.与文法有关的一些关系定义与文法有关的一些关系定义 1.1.优先函数定义优先函数定义 2.2.构造文法关系传递闭包构造文法关系传递闭包 2.2.优先函数矩阵的构造优先函数矩阵的构造 和自反传递闭包和自反传递闭包 3.3.利用优先函数矩阵进行语法分析利用优先函数矩阵进行语法分析 3.3.文法优先关系概念文法优先关系概念 四、四、LRLR分析法分析法 4.4.文法优先关系的构造文法优先关系的构造 1.LR 1.LR分析法一般概述分析法一般概述 5.5.简单优先文法简单优先文法 2.LR 2.LR分析器工作原理分析器工作原理 6.6.简单优先文法分析算法简单优先文法分析算法 3.LR 3.LR（0 0）分析表构造）分析表构造二、算符优先分析法二、算符优先分析法 4.SLR4.SLR（1 1）分析表构造）分析表构造 1.1.算符优先关系概念算符优先关系概念 5.LR 5.LR（1 1）分析表构造）分析表构造 2.2.算符优先文法算符优先文法 6.LALR 6.LALR分析表构造分析表构造 3.3.算符优先关系的构造方法算符优先关系的构造方法 五、二义性文法的应用五、二义性文法的应用 4.4.最左素短语最左素短语 1.1.问题的提出问题的提出 5.5.算符优先分析算法算符优先分析算法 2.2.二义性文法分析表的构造二义性文法分析表的构造 第四章第四章 语法分析语法分析4.3 4.3 自底向上自底向上自底向上自底向上语语法分析法分析法分析法分析 一、简单优先文法分析法一、简单优先文法分析法 三、优先函数及其构造三、优先函数及其构造 1.1.与文法有关的一些关系定义与文法有关的一些关系定义 1.1.优先函数定义优先函数定义 2.2.构造文法关系传递闭包构造文法关系传递闭包 2.2.优先函数矩阵的构造优先函数矩阵的构造 和自反传递闭包和自反传递闭包 3.3.利用优先函数矩阵进行语法分析利用优先函数矩阵进行语法分析 3.3.文法优先关系概念文法优先关系概念 四、四、LRLR分析法分析法 4.4.文法优先关系的构造文法优先关系的构造 1.LR1.LR分析法一般概述分析法一般概述 5.5.简单优先文法简单优先文法 2.LR 2.LR分析器工作原理分析器工作原理 6.6.简单优先文法分析算法简单优先文法分析算法 3.LR 3.LR（0 0）分析表构造）分析表构造二、算符优先分析法二、算符优先分析法 4.SLR4.SLR（1 1）分析表构造）分析表构造 1.1.算符优先关系概念算符优先关系概念 5.LR 5.LR（1 1）分析表构造）分析表构造 2.2.算符优先文法算符优先文法 6.LALR 6.LALR分析表构造分析表构造 3.3.算符优先关系的构造方法算符优先关系的构造方法 五、二义性文法的应用五、二义性文法的应用 4.4.最左素短语最左素短语 1.1.问题的提出问题的提出 5.5.算符优先分析算法算符优先分析算法 2.2.二义性文法分析表的构造二义性文法分析表的构造 第四章第四章 语法分析语法分析4.3 4.3 自底向上自底向上自底向上自底向上语语法分析法分析法分析法分析4.3 4.3 自底向上语法分析自底向上语法分析前面我们介绍的几种语法分析方法对相应的文法都有一定的要求。例如：前面我们介绍的几种语法分析方法对相应的文法都有一定的要求。例如：前面我们介绍的几种语法分析方法对相应的文法都有一定的要求。例如：前面我们介绍的几种语法分析方法对相应的文法都有一定的要求。例如：因此，上述这些方法在使用上有一定局限性。因此，上述这些方法在使用上有一定局限性。因此，上述这些方法在使用上有一定局限性。因此，上述这些方法在使用上有一定局限性。LR LR分析法是分析法是分析法是分析法是19651965年由年由年由年由KnuthKnuth提出一种自底向上语法分析方法，可用于一大类上下文无关文法分析，这种提出一种自底向上语法分析方法，可用于一大类上下文无关文法分析，这种提出一种自底向上语法分析方法，可用于一大类上下文无关文法分析，这种提出一种自底向上语法分析方法，可用于一大类上下文无关文法分析，这种技术叫做技术叫做技术叫做技术叫做LR(K)LR(K)分析技术。分析技术。分析技术。分析技术。不带回溯的自顶向下分析方法要求文法不存在左递归，不带回溯的自顶向下分析方法要求文法不存在左递归，不带回溯的自顶向下分析方法要求文法不存在左递归，不带回溯的自顶向下分析方法要求文法不存在左递归，并且每一规则的各候选式的终结首符集两两不相交；并且每一规则的各候选式的终结首符集两两不相交；并且每一规则的各候选式的终结首符集两两不相交；并且每一规则的各候选式的终结首符集两两不相交；算符优先分析方法则要求文法的各终结符号对间至多只算符优先分析方法则要求文法的各终结符号对间至多只算符优先分析方法则要求文法的各终结符号对间至多只算符优先分析方法则要求文法的各终结符号对间至多只有一种优先关系，等等。有一种优先关系，等等。有一种优先关系，等等。有一种优先关系，等等。1.LR1.LR分析法一般概述分析法一般概述分析法一般概述分析法一般概述4.3 4.3 自底向上语法分析自底向上语法分析（1 1）LRLR（KK）分析法定）分析法定）分析法定）分析法定义义 LR(K)LR(K)分分分分 析析析析 法法法法 意意意意 思思思思 是是是是：L L是是是是 指指指指 从从从从 左左左左(Left)(Left)到到到到 右右右右 扫扫扫扫 描描描描 输输输输 入入入入 符符符符 号号号号 串串串串，R R是构造是构造是构造是构造最右最右最右最右(Rightmost)(Rightmost)推导过程自底向上的分析方法。推导过程自底向上的分析方法。推导过程自底向上的分析方法。推导过程自底向上的分析方法。KK是是是是指指指指在在在在决决决决定定定定分分分分析析析析动动动动作作作作时时时时向向向向前前前前看看看看符符符符号号号号的的的的个个个个数数数数。若若若若KK0 0，就就就就为为为为LR(0)LR(0)分分分分析析析析，说说说说明明明明分分分分析析析析动动动动作作作作时时时时，不不不不向向向向前前前前看看看看任任任任何何何何符符符符号号号号，LR(1)LR(1)分分分分析析析析，说明分析动作时只向前看一个符号。说明分析动作时只向前看一个符号。说明分析动作时只向前看一个符号。说明分析动作时只向前看一个符号。这这这这是是是是一一一一类类类类对对对对上上上上下下下下文文文文无无无无关关关关文文文文法法法法进进进进行行行行“自自自自左左左左到到到到右右右右扫扫扫扫描描描描和和和和最最最最左左左左归归归归约约约约”的的的的自自自自底底底底向向向向上上上上的的的的分分分分析析析析方方方方法法法法，在在在在这这这这种种种种分分分分析析析析过过过过程程程程中中中中，它它它它至至至至多多多多只只只只向向向向前前前前查查查查看看看看个个个个输输输输入入入入符符符符号号号号就就就就能能能能确确确确定定定定当当当当前前前前的的的的动动动动作作作作是是是是移移移移进进进进还还还还是是是是归归归归约约约约；若若若若动动动动作作作作归归归归约约约约，它还能唯一地选中一个规则去归约当前已识别的句柄。它还能唯一地选中一个规则去归约当前已识别的句柄。它还能唯一地选中一个规则去归约当前已识别的句柄。它还能唯一地选中一个规则去归约当前已识别的句柄。4.3 4.3 自底向上语法分析自底向上语法分析（2 2）LRLR分析法的特点分析法的特点分析法的特点分析法的特点 1)LR分析器分析器(程序程序)基本上可以识别所有上下文无关文法写的编程语言结基本上可以识别所有上下文无关文法写的编程语言结构，分析能力强且适用范围广构，分析能力强且适用范围广 2)LR分析法是当前最一般的分析法是当前最一般的“移进移进-归约归约”分析方法分析方法 3)LR分析法在自左向右扫描输入串时能发现其中错误，并能指出出错地分析法在自左向右扫描输入串时能发现其中错误，并能指出出错地点。点。4)LR分析程序可以自动生成分析程序可以自动生成4.3 4.3 自底向上语法分析自底向上语法分析（3 3）LRLR分析器的分析器的分析器的分析器的组组成成成成 从从逻逻辑辑上上说说，一一个个LR分分析析器器包包括括两两部部分分：一一个个总总控控程程序序和和一一张张分析表。分析表。一一般般说说来来，所所有有LR分分析析器器总总控控程程序序是是一一样样的的，只只是是分分析析表表各各不相同。不相同。4.3 4.3 自底向上语法分析自底向上语法分析（4 4）LRLR分析表种分析表种分析表种分析表种类类 1)最简单分析表最简单分析表LR(0)：局限性大，但它是建立其它分析表的基础：局限性大，但它是建立其它分析表的基础 2)简单分析表简单分析表SLR：比较容易实现，：比较容易实现，SLR分析表的功能比分析表的功能比LR(0)稍强些稍强些 3)LR(K)分析表：分析能力最强，但实现代价高。主要讨论分析表：分析能力最强，但实现代价高。主要讨论LR(1)4)LALR分析表：称为向前看分析表：称为向前看LR分析表，功能介于分析表，功能介于SLR(1)和和LR(1)之间，适用于大多数程序设计语言的结构，并且可以比较有效地实现。之间，适用于大多数程序设计语言的结构，并且可以比较有效地实现。一、简单优先文法分析法一、简单优先文法分析法 三、优先函数及其构造三、优先函数及其构造 1.1.与文法有关的一些关系定义与文法有关的一些关系定义 1.1.优先函数定义优先函数定义 2.2.构造文法关系传递闭包构造文法关系传递闭包 2.2.优先函数矩阵的构造优先函数矩阵的构造 和自反传递闭包和自反传递闭包 3.3.利用优先函数矩阵进行语法分析利用优先函数矩阵进行语法分析 3.3.文法优先关系概念文法优先关系概念 四、四、LRLR分析法分析法 4.4.文法优先关系的构造文法优先关系的构造 1.LR 1.LR分析法一般概述分析法一般概述 5.5.简单优先文法简单优先文法 2.LR2.LR分析器工作原理分析器工作原理 6.6.简单优先文法分析算法简单优先文法分析算法 3.LR 3.LR（0 0）分析表构造）分析表构造二、算符优先分析法二、算符优先分析法 4.SLR4.SLR（1 1）分析表构造）分析表构造 1.1.算符优先关系概念算符优先关系概念 5.LR 5.LR（1 1）分析表构造）分析表构造 2.2.算符优先文法算符优先文法 6.LALR 6.LALR分析表构造分析表构造 3.3.算符优先关系的构造方法算符优先关系的构造方法 五、二义性文法的应用五、二义性文法的应用 4.4.最左素短语最左素短语 1.1.问题的提出问题的提出 5.5.算符优先分析算法算符优先分析算法 2.2.二义性文法分析表的构造二义性文法分析表的构造 第四章 语法分析 4.3 4.3 自底向上自底向上自底向上自底向上语语法分析法分析法分析法分析4.3 自底向上语法分析S Smm.S S1 1S S0 0总控程序总控程序总控程序总控程序分析表分析表分析表分析表a1al#S Smm.S S2 2S S1 1S S0 0X Xmm.X X2 2X X1 1#(1)(1)LRLR分析器的逻辑结构分析器的逻辑结构分析器的逻辑结构分析器的逻辑结构 在在在在逻逻逻逻辑辑辑辑上上上上，一一一一个个个个LRLR分分分分析析析析器器器器结结结结构构构构如如如如下下下下图图图图所所所所示示示示。它它它它是是是是由由由由一一一一个个个个输输输输入入入入符符符符号号号号串，一个下推状态栈，以及一个总控程序和分析表组成。串，一个下推状态栈，以及一个总控程序和分析表组成。串，一个下推状态栈，以及一个总控程序和分析表组成。串，一个下推状态栈，以及一个总控程序和分析表组成。实实实实际际际际上上上上在在在在分分分分析析析析时时时时读读读读入入入入符符符符号号号号是是是是不不不不进进进进栈栈栈栈的的的的。为为为为使使使使分分分分析析析析解解解解释释释释更更更更清清清清楚楚楚楚，我我我我们们们们另设一个符号栈（实际上只有一个状态栈用于存放状态）。另设一个符号栈（实际上只有一个状态栈用于存放状态）。另设一个符号栈（实际上只有一个状态栈用于存放状态）。另设一个符号栈（实际上只有一个状态栈用于存放状态）。状态栈状态栈状态栈状态栈 符号栈符号栈 输入串输入串2.LR2.LR分析器工作原理分析器工作原理分析器工作原理分析器工作原理LR分析器核心是分析表，分析表由两个子表组成：分析器核心是分析表，分析表由两个子表组成：1)分析动作表分析动作表 其中：其中：S，S2，Sn 为分析器各状态为分析器各状态 a,a2 am 为文法的全部终结符号和句子界限符为文法的全部终结符号和句子界限符 ACTIONSi,aj 指明，当状态指明，当状态Si面临输入符号面临输入符号aj时应采取的分析动作。时应采取的分析动作。有如下四个取值：有如下四个取值：ACTION Si,aj=S 移进动作，当前输入符号进桟移进动作，当前输入符号进桟 ACTION Si,aj=rj 按第按第j个产生式进行归约个产生式进行归约 ACTION Si,aj=acc 接受接受 ACTION Si,aj=ERROR 出错出错a1a2amS1ACTIONS1,a1ACTIONS1,a2ACTIONS1,amS2ACTIONS2,a1ACTIONS2,a2ACTIONS2,amSnACTIONSn,a1ACTIONSn,a2ACTIONSn,am2 2）状态转换表状态转换表 其中：其中：，p是文法字汇表中全部非终结符号和终结符号是文法字汇表中全部非终结符号和终结符号 S，S，Sn为分析器各状态为分析器各状态 GOTO Si,Xj指明当状态指明当状态Si面对文法符号面对文法符号Xj时下一状态是什么时下一状态是什么X1X2XPS1GOTOS1,X1GOTOS1,X2GOTOS1,XpS2GOTOS2,X1GOTOS2,X2GOTOS2,XpSnGOTOSn,X1GOTOSn,X2GOTOSn,Xp（2）LR分析器基本工作过程分析器基本工作过程 1）分析实例分析实例 下面我们通过一个例子来说明下面我们通过一个例子来说明LR分析器分析过程分析器分析过程 例例4.15设已知文法设已知文法GE：(首先对每个文法规则要编号）首先对每个文法规则要编号）=E+T =T*=（E）=i 为了节省空间，我们将文法分析动作表（为了节省空间，我们将文法分析动作表（ACTION）和状态转换表）和状态转换表（GOTO）关于终结符的各列对应地进行合并，合并之后分析表如下表所示。）关于终结符的各列对应地进行合并，合并之后分析表如下表所示。（关于表的构造方法以后再讨论）（关于表的构造方法以后再讨论）2.LR2.LR分析器工作原理分析器工作原理分析器工作原理分析器工作原理 实例实例实例实例LRLRLRLR分析表分析表分析表分析表表表表表中中中中所引用所引用所引用所引用记记记记号的意号的意号的意号的意义义义义是：是：是：是：a.a.S Sj j 把下一个状把下一个状把下一个状把下一个状态态态态j j和和和和现现现现行行行行输输输输入符号入符号入符号入符号a ai i移移移移进栈进栈进栈进栈b.rb.rj j 按第按第按第按第j j个个个个规则进规则进规则进规则进行行行行归约归约归约归约c.accc.acc接受接受接受接受d.d.空白格出空白格出空白格出空白格出错标错标错标错标志，志，志，志，报错报错报错报错GOTOGOTO表仅对所有非终结符表仅对所有非终结符表仅对所有非终结符表仅对所有非终结符A A列出列出列出列出GOTOGOTOS Smm,A,A的值，表明所要到达的值，表明所要到达的值，表明所要到达的值，表明所要到达的状态的值。的状态的值。的状态的值。的状态的值。状态状态ACTION（动作）（动作）GOTO（状态转换）（状态转换）i+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5 实例分析过程实例分析过程实例分析过程实例分析过程现以输入串为现以输入串为现以输入串为现以输入串为i+i*ii+i*i为例，给出分析器对它进行分析过程如下表为例，给出分析器对它进行分析过程如下表为例，给出分析器对它进行分析过程如下表为例，给出分析器对它进行分析过程如下表步骤步骤 状态栈状态栈 符号栈符号栈 输入串输入串 分析动作分析动作 下一状态下一状态 1 0#i+i*i#S 1 0#i+i*i#S5 5 5 5 2 05#i +i*i#r 2 05#i +i*i#r6 6 GOTO0,F=3GOTO0,F=3 3 03#F +i*i#r 3 03#F +i*i#r4 4 GOTO0,T=2GOTO0,T=2 4 02#T +i*i#r 4 02#T +i*i#r2 2 GOTO0,E=1GOTO0,E=1 5 01#E +i*i#S 5 01#E +i*i#S6 6 6 6 6 016#E+i*i#S 6 016#E+i*i#S5 5 5 5 7 0165#E+i *i#r 7 0165#E+i *i#r6 6 GOTO6,F=3 GOTO6,F=3 8 0163#E+F *i#r 8 0163#E+F *i#r4 4 GOTO6,T=9 GOTO6,T=9 9 0169#E+T *i#S 9 0169#E+T *i#S7 7 7 7 10 01657#E+T*i#S 10 01657#E+T*i#S5 5 5 5 11 016575#E+T*i#r 11 016575#E+T*i#r6 6 GOTO7,F=10 GOTO7,F=10 12 01657 12 016571010#E+T*F#r#E+T*F#r3 3 GOTO6,T=9 GOTO6,T=9 13 0169#E+T#r 13 0169#E+T#r1 1 GOTO0,E=1 GOTO0,E=1 14 01#E#acc 14 01#E#acc2 2）LRLR分析器基本工作过程分析器基本工作过程分析器基本工作过程分析器基本工作过程 LR LR分析器的工作是在总控程序控制下进行，其过程如下：分析器的工作是在总控程序控制下进行，其过程如下：分析器的工作是在总控程序控制下进行，其过程如下：分析器的工作是在总控程序控制下进行，其过程如下：分分分分析析析析开开开开始始始始时时时时，首首首首先先先先将将将将初初初初始始始始状状状状态态态态S S及及及及句句句句子子子子左左左左界界界界限限限限符符符符#推推推推入入入入分分分分析析析析栈栈栈栈和和和和输输输输入串构成一个三元式为入串构成一个三元式为入串构成一个三元式为入串构成一个三元式为 （S S ，#，a a1 1a a2 2aan n#）其其其其中中中中S S为为为为初初初初态态态态，#为为为为句句句句子子子子左左左左界界界界限限限限符符符符，a a1 1a a2 2aan n是是是是输输输输入入入入串串串串，其其其其后后后后#为为为为句句句句子右界限符。子右界限符。子右界限符。子右界限符。设在分析的某一步，分析栈和余留输入符号串表示为设在分析的某一步，分析栈和余留输入符号串表示为设在分析的某一步，分析栈和余留输入符号串表示为设在分析的某一步，分析栈和余留输入符号串表示为 （S S0 0S S1 1SSmm，#X#X1 1X X2 2XXmm，a ai ia ai+1i+1aan n#）这这这这时时时时用用用用当当当当前前前前栈栈栈栈顶顶顶顶状状状状态态态态S Smm及及及及正正正正扫扫扫扫视视视视的的的的输输输输入入入入符符符符号号号号a ai i组组组组成成成成符符符符号号号号对对对对去去去去查查查查分分分分析析析析动动动动作作作作表，并根据分析表中元素表，并根据分析表中元素表，并根据分析表中元素表，并根据分析表中元素ACTIONACTIONS Smm,a,ai i所规定的动作进行分析。所规定的动作进行分析。所规定的动作进行分析。所规定的动作进行分析。2.LR2.LR分析器工作原理分析器工作原理分析器工作原理分析器工作原理 a.若若ACTIONSm，ai移移进进S，这这表表明明句句柄柄尚尚未未在在栈栈顶顶部部形形成成，正正期期待待着着移移进进输输入入符符号号以以形形成成句句柄柄，故故将将当当前前输输入入符符号号ai推推入入栈栈中中，其其三三元式变为元式变为 （S0S1Sm,#X1X2Xmai,ai+1ai+2an#）然后以符号对（然后以符号对（Sm，ai）查状态转换表，若相应表元素为）查状态转换表，若相应表元素为 GOTOSm,aiSm+1 再将此新状态再将此新状态Sm+1推入栈中，则推入栈中，则 三元式变为三元式变为 （S0S1SmSm,#X1X2Xmai,ai+1ai+2 an#）分分分分析析析析动动动动作作作作表表表表每每每每一一一一元元元元素素素素ACTIONSACTIONSmm,a,ai i所所所所规规规规定定定定动动动动作作作作不不不不外外外外是下列四种可能之一：是下列四种可能之一：是下列四种可能之一：是下列四种可能之一：2.LR2.LR分析器工作原理分析器工作原理分析器工作原理分析器工作原理b.若若ACTIONSm，ai归约归约rj，其中，其中rj是指文法中第是指文法中第j个规则个规则，r是规则右部长度。此时按规则是规则右部长度。此时按规则 执行一次归约动作，执行一次归约动作，这表明栈顶部的符号串这表明栈顶部的符号串m-r+1m-r+2m已是当前句型（对非终结符）已是当前句型（对非终结符）的句柄。按第的句柄。按第j个产生式进行归约，此时将分析栈从顶向下的个产生式进行归约，此时将分析栈从顶向下的r个符号个符号退出，使状态退出，使状态Sm-r变成栈顶状态，再将文法符号推入栈中，变成栈顶状态，再将文法符号推入栈中，其三元式为其三元式为 （S0S1Sm-r,#X1X2Xm-r,aiai+1an#）然后再以（然后再以（Sm-r，）查状态转换表，设，）查状态转换表，设 GOTOSm-r，Sk，将此新状态推入栈中则三元式变为将此新状态推入栈中则三元式变为 （S0S1Sm-rSk,#X1X2Xm-RA,aiai+1an#）归约动作不改变现行输入符号，输入串指示器不向前推进，它仍然指向归约动作不改变现行输入符号，输入串指示器不向前推进，它仍然指向动作前的位置。动作前的位置。2.LR2.LR分析器工作原理分析器工作原理分析器工作原理分析器工作原理 c.若若ACTIONSm,ai接受接受acc，则表明当前输入串已被成功地分析，则表明当前输入串已被成功地分析 完毕，则三元式不再变化，宣布分析成功。完毕，则三元式不再变化，宣布分析成功。d.若若ACTIONSm,ai报错报错ERROR，则三元式变化过程终止，报告错误。，则三元式变化过程终止，报告错误。重重复复上上述述 ，直直到到在在分分析析某某一一步步，栈栈顶顶出出现现“接接受受状状态态”或或“出出错错状状态态”为止。为止。对于前者，其三元式变为对于前者，其三元式变为（SSz，），）其其中中为为文文法法开开始始符符号号，Sz则则为为使使ACTIONSz，“接接受受”的的唯唯一一状状态。态。一一个个分分析析器器工工作作过过程程就就是是一一步步一一步步地地变变换换三三元元式式，直直至至执执行行“接接受受”或或“报错报错”为止。为止。2.LR2.LR分析器工作原理分析器工作原理分析器工作原理分析器工作原理 实例分析过程实例分析过程实例分析过程实例分析过程现以输入串为现以输入串为现以输入串为现以输入串为i+i*ii+i*i为例，给出分析器对它进行分析过程如下表为例，给出分析器对它进行分析过程如下表为例，给出分析器对它进行分析过程如下表为例，给出分析器对它进行分析过程如下表步骤步骤 状态栈状态栈 符号栈符号栈 输入串输入串 分析动作分析动作 下一状态下一状态 1 0#i+i*i#S 1 0#i+i*i#S5 5 5 5 2 05#i +i*i#r 2 05#i +i*i#r6 6 GOTO0,F=3GOTO0,F=3 3 03#F +i*i#r 3 03#F +i*i#r4 4 GOTO0,T=2GOTO0,T=2 4 02#T +i*i#r 4 02#T +i*i#r2 2 GOTO0,E=1GOTO0,E=1 5 01#E +i*i#S 5 01#E +i*i#S6 6 6 6 6 016#E+i*i#S 6 016#E+i*i#S5 5 5 5 7 0165#E+i *i#r 7 0165#E+i *i#r6 6 GOTO6,F=3 GOTO6,F=3 8 0163#E+F *i#r 8 0163#E+F *i#r4 4 GOTO6,T=9 GOTO6,T=9 9 0169#E+T *i#S 9 0169#E+T *i#S7 7 7 7 10 01657#E+T*i#S 10 01657#E+T*i#S5 5 5 5 11 016575#E+T*i#r 11 016575#E+T*i#r6 6 GOTO7,F=10 GOTO7,F=10 12 01657 12 016571010#E+T*F#r#E+T*F#r3 3 GOTO6,T=9 GOTO6,T=9 13 0169#E+T#r 13 0169#E+T#r1 1 GOTO0,E=1 GOTO0,E=1 14 01#E#acc 14 01#E#acc一、简单优先文法分析法一、简单优先文法分析法 三、优先函数及其构造三、优先函数及其构造 1.1.与文法有关的一些关系定义与文法有关的一些关系定义 1.1.优先函数定义优先函数定义 2.2.构造文法关系传递闭包构造文法关系传递闭包 2.2.优先函数矩阵的构造优先函数矩阵的构造 和自反传递闭包和自反传递闭包 3.3.利用优先函数矩阵进行语法分析利用优先函数矩阵进行语法分析 3.3.文法优先关系概念文法优先关系概念 四、四、LRLR分析法分析法 4.4.文法优先关系的构造文法优先关系的构造 1.LR 1.LR分析法一般概述分析法一般概述 5.5.简单优先文法简单优先文法 2.LR 2.LR分析器工作原理分析器工作原理 6.6.简单优先文法分析算法简单优先文法分析算法 3.LR3.LR（0 0）分析表构造）分析表构造二、算符优先分析法二、算符优先分析法 4.SLR4.SLR（1 1）分析表构造）分析表构造 1.1.算符优先关系概念算符优先关系概念 5.LR 5.LR（1 1）分析表构造）分析表构造 2.2.算符优先文法算符优先文法 6.LALR 6.LALR分析表构造分析表构造 3.3.算符优先关系的构造方法算符优先关系的构造方法 五、二义性文法的应用五、二义性文法的应用 4.4.最左素短语最左素短语 1.1.问题的提出问题的提出 5.5.算符优先分析算法算符优先分析算法 2.2.二义性文法分析表的构造二义性文法分析表的构造 第四章 语法分析4.3 4.3 自底向上自底向上自底向上自底向上语语法分析法分析法分析法分析4.3 自底向上语法分析 LR（0）分析就是）分析就是LR（K）分析当的情况，就是指在分析每一步，只要根）分析当的情况，就是指在分析每一步，只要根据当前栈顶状态，就能确定应采取何种分析动作，而无需向前查看输入符号。为了据当前栈顶状态，就能确定应采取何种分析动作，而无需向前查看输入符号。为了构造构造LR分析表，首先引入规范句型活前缀的概念。分析表，首先引入规范句型活前缀的概念。（1）规范句型的活前缀规范句型的活前缀 字的字的前缀前缀：是指字的任意首部。如字：是指字的任意首部。如字abc的前缀有的前缀有,a,ab,abc.活活 前前 缀缀：规范句型（右句型）的一个前缀，如果它不含句柄后任何符号，则称它：规范句型（右句型）的一个前缀，如果它不含句柄后任何符号，则称它是该规范句型的一个活前缀。也就是说在活前缀右边增添一些终结符号之后，就可是该规范句型的一个活前缀。也就是说在活前缀右边增添一些终结符号之后，就可以成为规范句型。以成为规范句型。在在在在LRLR分析过程中的任何时候，栈里的文法符号分析过程中的任何时候，栈里的文法符号分析过程中的任何时候，栈里的文法符号分析过程中的任何时候，栈里的文法符号X1X2XmX1X2Xm应该构成活前应该构成活前应该构成活前应该构成活前缀，把输入串的剩余部分配上之后即成为规范句型（如果整个输入串确实缀，把输入串的剩余部分配上之后即成为规范句型（如果整个输入串确实缀，把输入串的剩余部分配上之后即成为规范句型（如果整个输入串确实缀，把输入串的剩余部分配上之后即成为规范句型（如果整个输入串确实构成一个句子的话。）构成一个句子的话。）构成一个句子的话。）构成一个句子的话。）如：如：S+abcdef,其中其中cd是句柄，则是句柄，则,a,ab,abc,abcd是该规范句型的活前缀，而是该规范句型的活前缀，而abcd是包含句柄的活前缀。是包含句柄的活前缀。3.LR(0)3.LR(0)分析表的构造分析表的构造分析表的构造分析表的构造 实例分析过程实例分析过程实例分析过程实例分析过程现以输入串为现以输入串为现以输入串为现以输入串为i+i*ii+i*i为例，给出分析器对它进行分析过程如下表为例，给出分析器对它进行分析过程如下表为例，给出分析器对它进行分析过程如下表为例，给出分析器对它进行分析过程如下表步骤步骤 状态栈状态栈 符号栈符号栈 输入串输入串 分析动作分析动作 下一状态下一状态 1 0#i+i*i#S 1 0#i+i*i#S5 5 5 5 2 05#i +i*i#r 2 05#i +i*i#r6 6 GOTO0,F=3GOTO0,F=3 3 03#F +i*i#r 3 03#F +i*i#r4 4 GOTO0,T=2GOTO0,T=2 4 02#T +i*i#r 4 02#T +i*i#r2 2 GOTO0,E=1GOTO0,E=1 5 01#E +i*i#S 5 01#E +i*i#S6 6 6 6 6 016#E+i*i#S 6 016#E+i*i#S5 5 5 5 7 0165#E+i *i#r 7 0165#E+i *i#r6 6 GOTO6,F=3 GOTO6,F=3 8 0163#E+F *i#r 8 0163#E+F *i#r4 4 GOTO6,T=9 GOTO6,T=9 9 0169#E+T *i#S 9 0169#E+T *i#S7 7 7 7 10 01657#E+T*i#S 10 01657#E+T*i#S5 5 5 5 11 016575#E+T*i#r 11 016575#E+T*i#r6 6 GOTO7,F=10 GOTO7,F=10 12 01657 12 016571010#E+T*F#r#E+T*F#r3 3 GOTO6,T=9 GOTO6,T=9 13 0169#E+T#r 13 0169#E+T#r1 1 GOTO0,E=1 GOTO0,E=1 14 01#E#acc 14 01#E#acc（2 2）LRLR（）项目（）项目（）项目（）项目 1)1)活前缀与句柄之间的关系活前缀与句柄之间的关系活前缀与句柄之间的关系活前缀与句柄之间的关系 作作作作为为为为规规规规范范范范句句句句型型型型的的的的活活活活前前前前缀缀缀缀不不不不含含含含有有有有句句句句柄柄柄柄后后后后任任任任何何何何符符符符号号号号。因因因因此此此此，前前前前缀缀缀缀与与与与句句句句柄柄柄柄的的的的关关关关系系系系可能有三种情况：可能有三种情况：可能有三种情况：可能有三种情况：活前缀已包含句柄全部符号，这表明规则活前缀已包含句柄全部符号，这表明规则活前缀已包含句柄全部符号，这表明规则活前缀已包含句柄全部符号，这表明规则 的右部符号串的右部符号串的右部符号串的右部符号串 已已已已在分析栈顶，因此相应的分析动作应是用此规则进行归约，称可归约在分析栈顶，因此相应的分析动作应是用此规则进行归约，称可归约在分析栈顶，因此相应的分析动作应是用此规则进行归约，称可归约在分析栈顶，因此相应的分析动作应是用此规则进行归约，称可归约的活前缀。我们用的活前缀