编译原理-自底向上优先分析概述
前言
-
前面学了自顶向下的分析方法，它是使用推导的方式进行语法分析。这里学的自底向上优先分析是使用规约进行的语法分析 自底向上优先分析的原理：从输入串开始，朝着文法的开始符号进行规约，直到到达开始符号。这是一个最左规约的过程 自底向上优先分析的分类：简单优先分析法、算符优先分析法 自底向上分析所使用的自动机是PDA（下推自动机）
工作方式“移进-规约”
-
从左至右让输入串进栈，在移动的过程中不断查看栈顶符号，一旦形成某个句型的句柄就进行替换，直到栈顶不再形成句柄为止。然后继续读入符号，重复上述过程。直到栈顶剩下S#，输入串只有#为止。 注意 初态时，栈内只有#，读头指向最左边的单词 程序的执行动作 1）移入：读最左边的单词 2）规约：对栈顶进行规约，并输出产生式的编号 3）识别成功：栈顶剩下S#，输入串只有#
例子
-
存在如下文法
1. S → aAcBe 2. A → b 3.A → Ab 4.B → d
问：abbcde是不是该文法的合法句子
解： 1）为了便于后续分析，我们先画出语法树
2）进行操作，在规约的时候，按句柄（树的最左的一步推导得到的叶子）规约
3）进过上述操作后，最后得到栈内元素为 #S，输入串为#，表示识别成功。所以abbcde是该文法的合法句子
-
注意：这里有个前提，是我们已经把语法树给画出来了，所以可以从图中方便的找到句柄。计算机该如何找到句柄呢？这是后面学习的内容
上一篇：
IDEA上Java项目控制台中文乱码