自上而下的语法分析

面临的问题

文法左递归

一个文法是含有左递归的，如果存在非终结符P

$P\to P\alpha$

当产生左递归时，词法分析流没有向前进行任何的推进，而语法树却在不断地进行扩展，此时会使得分析器陷入死循环，故需要避免左递归。

回溯问题

每一步的语法分析，都面临这多个侯选式的选取问题，分析过程中，当一个非终结符用某个候选匹配成功时，这种匹配只是暂时的，当下一步出错时且无路可选时，不得不进行“回溯”操作，而这种回溯操作需要恢复先前的分析结果比较消耗性能。

构造不带回溯的自上而下的分析算法

消除文法左递归

直接左递归消除

$P\to P\alpha|\beta$

其中 $\alpha、\beta\in(V_T\cup V_N)^*$ ， $\beta$ 不以A打头

则可改写为如下右递归形式

$P\to\beta P'$

$P'\to \alpha P'|\varepsilon$

推广

假定关于P的全部产生式为

(每个 $\alpha$ 都不等于 $\varepsilon$ ，每个 $\beta$ 都不以P开头)

则可改写为如下右递归形式

$P\to \beta_1P'|\beta_2P'|...|\beta_1 P'$

$P'\to \alpha_1P'|\alpha_2P'|...|\alpha_mP'|$

习题

给定文法G(E):
$E \to E+T|T$

$T \to T*F|F$

$F\to(E)|i$

消除该文法的直接左递归：

$E\to TE'$

$E'\to +TE'|\varepsilon$

$T\to FT'$

$T'\to *FT'|\varepsilon$

$F\to(E)|i$

间接左递归消除

文法能够消除左递归的条件

不含有以 $\varepsilon$ 为右部的产生式
不含回路 $P\overset{+}\to P$ （+代表一步以上的推导，*代表任意次推导）

习题

给定文法G[S]:
$S\to Qc|c$
$Q\to Rb|b$
$R\to Sa|a$
不存在直接左递归，但S、Q、R都是左递归的

$S\to Qc \to Rbc \to Sabc$

$S\to SA|B$

$A\to abc$

$B\to abc|bc|c$

$S\to BS'\to abcS'|bcS'|cS'$

$S'\to AS'|\varepsilon \to abcS'|\varepsilon$

即消除左递归后为：

$S\to abcS'|bcS'|cS'$

$S' \to abcS'|\varepsilon$

消除回溯

对于如下推导，选取 $A\to\alpha_i$ 使得此次候选所匹配的工作结果是确信的无误的，便可以消除回溯。若其中的某次匹配错误，那么可以确定，输入的串不是S的句子。

故现在需要根据当前IP指针指向的词法Token去选取一个适当的产生式进行推导。

选取规则如下：

若产生式的推导以终结符a开头
若产生式的推导以非终结符开头，但未来能推导出以a开头

FIRST集合

故可以定义FIRST集合如下：

令G是一个不含左递归的文法，对G的所有非终结符的每个候选 $\alpha$ 定义它的终结首符集 $FIRST(\alpha)$ 为：

$FIRST(\alpha) = \{ \alpha|\alpha \overset*\Rightarrow \alpha...,\alpha \in V_T\}$

特别地，若 $\alpha\overset{*}{\Rightarrow}\varepsilon$ ，则规定 $\varepsilon\in FIRST(\alpha)$ 。

若非终结符A的所有候选首符集两两不相交，即对于A的任意两个不同的候选 $\alpha_i,\alpha_j$

$FIRST(\alpha_i)\cap FIRST(\alpha_j) = \phi$

则可以从 $A\to \alpha_1|\alpha_2|...|\alpha_n$ 中精确地选取一个候选式去执行任务。

提取公共左因子

假定关于A的规则是

那么，可以将这些规则改写为
$A\to \delta A'|\gamma_1|\gamma_2|...|\gamma_m$

$A'\to \beta_1|\beta_2|\beta_1|$
经过反复提取左因子，就能够把每个非终结符的所有候选首符集变成为两两不相交。

FOLLOW集合

未完待续