自底向上语法分析

短语：可由一个非终结符推导出的串，即语法分析树上的一颗子树的叶子
直接短语：可由一个非终结符一步推导出的串，即高度为 2 的子树的叶子
句柄：一个右句型最左侧的直接短语
- 当 G 无二义时，对于合法的句型，句柄是唯一的

移进-归约分析

借助一个下推栈完成，每步可能采取以下动作之一，然后进入新状态

Reduce，根据某个产生式归约
Shift：从输入序列移进一个单词
Error：发现语法错误，进行错误处理
Accept：分析成功对应一个最右推导

分析过程确定化需要解决两类冲突：

移进-归约冲突：下一步应该移进还是归约？
归约-归约冲突：可能选择多个短语进行归约

LR 分析表

分为 ACTION 和 GOTO 两张表：

ACTION 表的表头是所有终结符加上结束符 #
- 表项分 4 种情况：si 为将状态 i 压入栈，rj 为用第 j 条产生式规约，acc 为分析完成，err 为出错
GOTO 表的表头是所有非终结符 - GOTO[i,A]=j 意为，在用产生式 $A \to β$ 归约后，将栈顶的 $∣ β ∣$ 个状态弹出后，如果栈顶为状态 i，将状态 j 压入栈

LR 分析算法

ip 为指向当前输入字符 a 的指针，初始栈顶状态为 0

if (ACTION[i,a]==sj) {
	PUSH j;
	ip++;
}
else if (ACTION[i,a]==rj) {
	// j-th production rule is A -> \beta
	POP num; // num is the length of \beta
	k = TOP;
	PUSH GOTO[k,A];
}
else if (ACTION[i,a]==acc) return;
else error;

E E T T F F F \to E + T \to T \to T * F \to F \to (E) \to v \to d

该文法的 LR 分析表如上所示，分析 $v + v * d$ 输入串的过程如下：

{
	"versionAtEmbed": "0.3.4",
	"filepath": "Attachments/Ink/Writing/2026.6.7 - 15.04pm.writing"
}

如何获得 LR 分析表？