预测解析算法

简介

根据接下来的输入流预测所需的语法

优点：无需回溯

该算法接受​​LL(K)​ ​文法

LL->代表两个left，从左向右处理输入流+最左推导，k代表向前查看k个token，而事实上，也是现实中，k几乎总是等于1, 所以本文也只讨论LL(1)​的情况

核心思想：消除为一个非终结符提供的多个产生式中存在的公共前缀

算法大致步骤

1. 重写文法

   ​​

   ‍

2. 生成LL(1)​解析表（下一小节讨论如何生成）

   $符号在这里仅仅作为输入流结束和栈为空的标记而已

   ​​

   ‍

3. 运用转换表加栈解析输入流

   ​​

   ‍

构建解析表

有且仅有两种情况下，我们希望$[A, t] = \alpha$​

注：->*​ 代表n次推导的意思， t是终结符

1. 我们称t为$First(\alpha)$

   ​​

2. 我们称t为$Follow(\alpha)$​

   ​​

构建First集

​​

构建Follow集

​​

​​

​​

构建解析表步骤

1. 条件

   ​​

   ‍

2. 案例

   ​​

   ‍

‍