什么是自底向上解析？
自下而上的解析可以表示为尝试通过反向发现ω的最右侧推导来将输入字符串ω简化为文法的起始符号。这类似于为输入字符串ω生成解析树，从叶子开始并朝根前进，即尝试从底向上生成解析树。
这包含搜索连接任何语法产生式右侧的子串。如果这个替换导致在最右边的派生前一步生成句子形式，则该子串由产生式左侧的非终结符恢复。
这种用左侧非终结符代替产生式右侧的过程称为归约。因此，归约无非是反向执行推导。
自底向上解析器的类型
共有三种类型的自底向上解析器，如下所示-
ShiftReduceParser-ShiftReduce解析器是一种自底向上的解析器。它可能需要一个堆栈来影响语法符号。解析器继续将输入符号移到堆栈上，直到句柄出现在堆栈顶部。当一个句柄出现在栈顶时，它实现了归约。
运算符优先级解析器-可以为一小类语法手动生成移位减少解析器。这些文法的性质是右边没有产生式是ϵ或有两个相邻的非终结符。具有后一特性的语法称为运算符语法。
LRParsers-LRParser是一个移位归约解析器，它创建了确定性有限自动机的使用，通过从下到上读取堆栈来识别所有可行前缀的集合。它决定可用的句柄（如果有）。
正确顺序形式的可行前缀是包含句柄但在句柄右侧没有符号的前缀。因此，如果生成识别正确句子形式的可行前缀的有限状态机，它可以指导移位归约解析器中的句柄选择。
LR解析器共有三种类型，如下所示-
SimpleLRParser(SLR)：它很容易实现，但它无法为某些类的语法生成表。
CanonicalLRParser(CLR)：它是最强大的，适用于大量语法。
LookAheadLRParser(LALR)：它的功能介于SLR和CLR之间。