目录
自底向上语法分析
自底向上的语法分析是编译原理中的一个重要概念，它与自顶向下的语法分析相对应。自底向上的语法分析是从输入串的底部（叶子节点）开始，逐步进行归约，直到达到文法的开始符号，从而构造出一棵语法树。这种分析方法采用的是最左归约方式，也就是反向构造最右推导。
自底向上语法分析的核心思想是使用移入-归约法。在这个过程中，使用一个寄存符号的先进后出栈来辅助分析。输入符号一个一个地被移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。这种替换过程被称为归约，它基于文法的产生式规则。
归约的关键在于选择哪个子串进行归约。这通常涉及到句柄的概念。句柄是一个与某产生式体相匹配的特定子串，它可以被替换成该产生式头部的非终结符号。在选择归约子串时，需要确保从句柄继续逆推一定能得到开始符号。否则，这样的产生式不能构成句柄。
自底向上语法分析还包括了一些解决冲突的策略。例如，在LR(0)分析法中，如果存在归约-归约冲突或移入-归约冲突，就需要采取一些措施来解决这些冲突。SLR(1)文法是一种能够消除所有冲突的LR(0)文法，它通过向前看一个输入符号来选择分析动作，从而解决了一些S-R和RR冲突。
总的来说，自底向上的语法分析是一种从输入串的底部开始逐步归约到文法开始符号的过程。它采用移入-归约法，通过选择适当的子串进行归约来构造语法树。同时，还需要解决可能出现的冲突以确保分析的正确性。
移入－规约法
移入-规约法（Shift-Reduce Method）是自底向上语法分析中的一种主要方法。它使用一个寄存符号的栈（通常称为分析栈）来进行语法分析。在这个过程中，输入符号被逐个移入栈中，并根据一定的规则进行规约操作，直到栈中只剩下文法的开始符号，此时语法分析成功完成。
移入-规约法的基本思想如下：
- 移入（Shift）：将下一个输入符号移入到栈的顶端。如果输入符号与栈顶的符号可以形成某个产生式的候选式，则进行规约操作；否则，继续移入下一个输入符号。
- 规约（Reduce）：当栈顶形成某个产生式的候选式时，将栈顶的这一部分替换成（归约为）该产生式的左部符号。规约操作是自底向上语法分析中的关键步骤，它使得语法分析器能够逐步构造出语法树。
在移入-规约过程中，语法分析器会根据当前栈顶和输入符号的情况选择适当的动作。这些动作包括移入、规约、接受和报错。移入动作将输入符号压入栈中，规约动作将栈顶的符号串替换为某个产生式的左部符号，接受动作表示语法分析成功完成，而报错动作则表示发现了一个语法错误。
需要注意的是，移入-规约法中的规约操作是基于文法的产生式规则进行的。产生式规则定义了如何从非终结符号和终结符号的组合推导出其他的符号串。在进行规约操作时，语法分析器会根据当前栈顶的符号串和产生式规则来决定如何进行替换。
总的来说，移入-规约法是一种有效的自底向上语法分析方法，它通过不断地移入和规约操作来逐步构造出语法树，从而实现对输入串的语法分析。
标签：底向上,语法分析,符号,规约,归约,移入 From： https://www.cnblogs.com/yubo-guan/p/18027453