LL(1) 语法分析及抽象语法树的构建

#PL

左递归的消除

对于文法

AAα1Aα2...β1β2...A \rightarrow A\alpha_1 | A\alpha_2|...|\beta_1|\beta_2|...

其最左推导会产生左递归(AAα1AAα1...A\rightarrow A\alpha_1 \rightarrow AA\alpha_1...),导致推导无法终止。

为消除左递归,注意到 AA 的每个最终推导的起始(非)终结符号必然是 β1,β2...\beta_1,\beta_2... 中的一个;因而这里引入中间产生式

RAα1RAα2RA...ϵR_A \rightarrow \alpha_1R_A|\alpha_2R_A|...|\epsilon

同时将产生式 AA 改写为

Aβ1RAβ2RA...A \rightarrow \beta_1R_A|\beta_2R_A|...

这样便消除了左递归。

(间接左递归略去)

Todo