Index

lex

直接按照几个基本模板分解推导

将 NFA 的初始状态的 closure 记录下来, 遍历每个输入, 得到新状态; 对新状态也依次遍历, 直到没有新状态产生

subset

将 accepting state 和 non-accpecting state 分开

组内的状态是 indistinguishable 的

如果两个状态 $s', t'$ 接收相同输入到达 $s,t$, $s,t$ 是 indistinguishable 的, 那么 $s', t'$ 也是 indistinguishable 的

遇到能匹配的 next-k token 就直接推导

计算 $FIRST, FOLLOW, NULL$

$FIRST$ 根据生成规则 $Y\to X_1\cdots X_k$, 对每个 $F_i$ 取并集, 如果前面的 $X_1\cdots X_{i-1}$ 都可空

$FOLLOW$ 根据生成规则 $Y\to X_1\cdots X_k$, 对每个 $X_i$, 取 $FOLLOW(Y)$ 和 $FIRST(X_{i+1}\cdots X_{k})$

匹配时看某个规则, $FIRST(RHS)$ 中的字符都可以作为 next-k token 进推导, 或者 $RHS$ 可空, $FOLLOW(LHS)$ 中的字符可以作为 next-k token 进行推导. 建表也是按照这个

解析时维护一个栈, 假设 next token $w$, 当前栈顶 $X$, 匹配表中 $X, w$ 的规则 $X\to Y_1\cdots Y_k$, $w\in FIRST(Y_1)$, 则将 $X$ 弹出, 将 $Y_1\cdots Y_k$ 压入栈中

暂存 input tokens, 匹配到某个规则结尾再 reduce, 所以需要维护一个转移图

从初始规则开始, 根据 $.$ 后面的非终止符 $X$, 找出 $X\to Y$ 规则, 将 $X\to .Y$ 加入当前状态, 直到加满不变

之后根据终止符 $x$ 进行 shift, 非终止符 $Z$ 进行 goto

最后如果 $.$ 后面为空, 则进行 reduce, 对于当前规则 $X\to Y_1\cdots Y_k.$, 将 $Y_1\cdots Y_k$ 弹出栈, 将 $X$ 压入栈中, 同时状态回退 $k$ 次

有时一个规则到了结尾另一个还能 shift, 所以要看 reduce 后的 symbol 的 $FOLLOW$, 包含在 $FOLLOW$ 中才可以 reduce

有时 SLR 也会有冲突, 所以提前看一个 input token

对于初始 $S'\to S\$$ (或者有的 grammar 有多个 $S'$ 开头的规则), 记录 next token $?$

之后求闭包, 对于 $A\to \alpha .X\beta, z$, next token 为 $FIRST(\beta z)$, 对于 $X\to \gamma$, $w\in FIRST(\beta z)$, 以 $X\to \gamma, w$ 的形式加入当前状态

$w$ 可能和 $z$ 不同, 即对于 $S'\to .S\$, ?$, 新产生的闭包中 $S\to .\gamma, \$$ 的 next token 更新, 因为 $w=FIRST(\beta z)=FIRST(\$?)=\$$

对于 goto/shift, 对于 $A\to \alpha .X\beta, z$ 将 $A\to \alpha X.\beta, z$ 加入下一状态, 并对下一状态求闭包

只有求闭包时 next token 会改变

LR(1) 中合并除了 next token 都一样的状态

这样可能会导致同一个状态的两个规则有相同 next token, 从而冲突