自底向上分析方法（LR分析算法）bottom-up parsing
- 引言
- . 运算符
- LR(0)
- LR(0)的项（构建有穷自动机的状态）
- LR(0)的项目闭包（构建有穷自动机的状态）
- GOTO函数
- 有效项目
- LR(0)有穷自动机的构建
- SLR
- LR(1)
- LALR
引言
LR的含义：
L：算法由左向右的处理输入符号（tokens）。
R：它为输入串描绘出一个最右推导。（由最右推导构造分析树）
数字：算法使用输入中的“多少个符号”来作预测分析。与之对应的有LR(0)，SLR(1)，LR(1)等算法。
LR分析法是自底向上分析算法中最重要，也是应用最广泛的一类算法。
优点：效率高、有现成工具（YACC(Unix)、bison(Linux)、Java CUP、以及C#YACC），因此应用广泛。
与LL分析法相比较
相同点：都是表驱动的分析算法。
不同点：
| - | LL | LR |
|---|---|---|
| 表内元素 | 文法规则 | 移进、规约 |
| 表格的纵列 | 非终结符号 | 状态 |
| 状态转移 | 否 | 是（goto） |
. 运算符
标记语法分析器已经读入了多少个输入，引入点记号“·”
两个关键步骤：
-
移进 将一个记号移入栈。
-
归约：弹出栈顶n个符号，恰好组成某个产生式的右部，压入该产生式的左部。例如：对于某个产生式A → β 1 β 2 … … β n \beta 1 \beta 2 …… \beta n β1β2……βn，从栈顶依次弹出 β \beta βn， β \beta βn-1，……， β \beta β 1，压入非终结符A。
拓广文法：如果G是一个以S为开始符号的文法, 那么G的拓广文法G’就是在G中加上新开始符号S’和产生式S’ → S而得到的文法。
LR(0)
LR(0)的项（构建有穷自动机的状态）
定义：一个文法G的LR(0)项（简称项，item）是G的一个产生式，同时加上它右部体中某处的点。（在文法产生式右部某个位置标有“·”的产生式）
例如： A → XYZ 的项包括：
A → · XYZ
A → X · YZ
A → XY · Z
A → XYZ
A → ε 的项包括： A → ·
格式是：已识别的·期望识别的，前面是已处理的，后面是待输入的
非终结符、终结符均可状态转移
形如 A→ · α \alpha α 的项目称为初始项目；
形如 A→ α \alpha α · 的项目称为归约项目（完整项目）；
形如 A→ · B β \beta β 的项目称为待约项目（基本项目） B∈N；
形如 A→ α \alpha α · a β \beta β 的项目称为移进项目（基本项目） a∈T
LR(0)的项目闭包（构建有穷自动机的状态）
设I是文法G的一个LR(0)项目集合，I的项目闭包CLOSURE(I)定义如下:
- I ⊆ \subseteq ⊆ CLOSURE(I)。
- 若项目A -> α \alpha α · B β ∈ \beta \in β∈ CLOSURE(I)，且 B -> η \eta η 是G的产生式，则项目B -> · η ∈ \eta \in η∈ CLOSURE(I)。(有几条闭包几条，可以一直往后闭包）
- CLOSURE(I)仅包含上述两条规则确定的LR(0)项目。
GOTO函数
若I是文法G的一个LR(0)项目集，X是G中的文法符号
GOTO(I, X) = CLOSURE(J) 其中J ={A − > α ->\alpha −>αX · β \beta β | A-> α \alpha α · X β ∈ I \beta \in I β∈I }，称函数GOTO(I, X)为转移函数
项目A − > α ->\alpha −>αX · β \beta β称为项目A-> α \alpha α · X β \beta β后继
有效项目
右句型：最右推导中的终结符和非终结符的每个中间串称为右句型（最右推导形成的剖面）
右句型的可行前缀（活前缀）：当前栈和输入串之间发生了间隔，分析栈的符号序列被称为右句型的可行前缀。（也就是点的前半部分）
右句型的句柄：在右句子格式中发生的位置以及用来归约它的产生式被称为右句型的句柄。
LR(0)有穷自动机的构建
NFA->DFA 子集构造法
熟练工可以直接写出DFA
