[第11讲-语法分析-VI.ppt

中国科大 编译原理和技术 大连理工软件学院 胡 彦 huyan.ssdut@ 本讲纲要 自下而上分析概述 自下而上分析方法 LR分析器 自下而上分析概述 重要概念 归约 句柄 归约 归约，是自下而上分析中的重要动作 归约，对应着最右推导的逆过程 句柄 句柄的非形式定义 句型的句柄，是该句型中与一个产生式右部匹配的字符串 句柄 句柄的精确定义 右句型γ的句柄是一个产生式的右部β，并且该句柄β在用A替换γ中的句柄β之后，得到的是最右推导中的前一个句型 令γ=αβω，则γ可以通过产生式A- β归约为句型αAω 句柄 句柄的特性 句柄的右边都是终结符（或者句柄右边没有任何符号） 句柄 句柄的特性 句柄的右边都是终结符（或者句柄右边没有任何符号） 在文法有二义的时候，句柄可能不唯一（因为对某个句子，可能存在两个最右推导） 本讲纲要 自下而上分析概述 自下而上分析方法 LR分析器 分析的方法 处理的对象：句子（由终结符组成的串） 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 分析的过程 所有的步骤与动作 3.4 自下而上分析 3.4.3 用栈实现移进?归约分析 分析器的四种动作： 移进动作 把下一个输入符号压栈。 归约动作 分析器知道整个句柄已经完全出现在栈顶，它确定句柄的左端在栈中的位置，再决定采用哪个非终结符来代替句柄（即确定使用哪个产生式）。 接受动作 分析器宣告分析成功。 报错动作 分析器发现了语法错误，调用错误恢复例程。 3.4 自下而上分析 使用移进?归约方式，即使知道了应该进行归约，也还有两个问题必须解决，他们是 确定右句型中将要归约的子串 如何确定选择哪一个产生式 3.4 自下而上分析 3.4.4 移进?归约分析的冲突 移进?归约冲突 3.4 自下而上分析 归约?归约冲突 stmt ? id (parameter_list) | expr := expr parameter_list ? parameter_list, parameter | parameter parameter ? id expr ? id (expr_list) | id expr_list ? expr_list, expr | expr 本讲纲要 自下而上分析概述 自下而上分析方法 LR分析器 LR分析器 LR分析器处理的是一类LR(k)文法 k指的是决定分析动作的时候向前看的符号个数 k=1时可以省略，表示分析的时候只要往前看1个符号 LR分析器采用的方法称为LR分析方法 LR分析方法是自下而上分析的一种，也是最为有效的一种 在深入LR分析方法的探讨之前，我们需要引入一个新的概念 活前缀 文法例子 活前缀与句柄的关系 文法例子 活前缀与句柄的关系 文法例子 活前缀与句柄的关系 文法例子 LR分析的核心工作 构建识别活前缀的DFA 基于DFA构建分析表 总结 归约、句柄 自下而上分析过程 移进-归约冲突 活前缀 作业 3.15 S ? aABe A ? Abc | b B ? d 栈中可能出现的串： a ab aA aAb aAbc aAd aAB aABe S ① 活前缀已含有句柄的全部符号，表明产生式A→β的 右部β已出现在栈顶。 出现符号A推出的符号串 ② 活前缀只含句柄的一部分符号如β1表明A→β1β2的右部子串β1 已出现在栈顶，当前期待从输入串中看到β2推出的符号。 出现产生式A-Abc右端的一部分， 期望从输入串中看到c ③ 活前缀不含有句柄的任何符号，此时期望产生式A→β的右部所推出 的符号串。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. * * * */35 Evaluation only. Created wi