随便记点防止期末烂掉
语法分析
直接左递归的消除
实际就是左递归转右递归
法1：直接替换
\[A\rightarrow A\alpha|\beta \Rightarrow \begin{cases} A\rightarrow \beta A',\\ A'\rightarrow \alpha A'|\epsilon \end{cases} \]法2：矩阵法
前置知识：
\[I = \begin{pmatrix} \epsilon & \empty\\ \empty & \epsilon \end{pmatrix}\\ A^* = I + AA^* \]原理：
\[X\rightarrow XA|B\Rightarrow X=BA^* \]例题
\[S\rightarrow AS|b, A\rightarrow SA|a\\ 解 S=AS+b,A=SA+a\\ (S,A)=(S,A) \begin{pmatrix} \empty & A\\ S & \empty \end{pmatrix} +(b, a)\\ (S,A)\rightarrow (b,a) \begin{pmatrix} \empty & A\\ S & \empty \end{pmatrix}^*\\ 令Z = \begin{pmatrix} \empty & A\\ S & \empty \end{pmatrix}^*, 则 Z=I+ \begin{pmatrix} \empty & A\\ S & \empty \end{pmatrix} Z\\ 则原文法改写为：(S,A)=(b,a)Z\\ Z=I+ \begin{pmatrix} \empty & A\\ S & \empty \end{pmatrix} Z \]求FIRST集
来点伪代码：
Set FIRST(X){
ft = ∅;
if (X in V_T) return {X};
if (X -> ε in P) ft += {ε};
forEach(X -> Y_1Y_2…Y_k in P ) {
forEach(Y_i) {
if (ε in FIRST(Y_i)) {
ft += (FIRST(Y_i) - {ε});
if (i == k) ft += {ε};
}
else {
ft + = FIRST(Yi);
break;
}
}
}
return ft;
}