非递归的预测分析法

﹏ヽ暗。殇╰゛Y 2022-02-05 13:06 195阅读 0赞

### 文章目录 ###

*  概念
 *  例子
 *  算法流程
 *  预测分析法实现步骤

# 概念 #

非递归的预测分析**不需要**为每个非终结符**编写递归下降过程**，而是根据预测分析表构造一个**自动机**，也叫**表驱动的预测分析。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

通过增加一个栈，来**增强自动机的识别能力**。

例如，`$L=\{a^nb^n|n\ge 1\}$`。

这个产生式识别一切以**先是`a`后是`b`** 的句子，**而且`a`与`b`的个数一致**。若是用有穷状态机则无法实现。**若是增加了一个栈**，则可以在每接收到一个`a`之后将`a`进栈，然后每当接收到一个`b`之后将`a`出栈，若是在接收到最后一个`b`时，最后一个`a`出栈，那么就识别成功。

# 例子 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]

# 算法流程 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]

# 预测分析法实现步骤 #

1.  构造文法
2.  改造文法：消除二义性、消除左递归、消除回溯
3.  求每个变量的FIRST集和FOLLOW集，**从而求得每个候选式的SELECT集**
4.  检查是不是`LL(1)`文法。若是，构造预测分析表。
5.  对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20220205/22dcb97c460549378fb7f96960f5edd0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20220205/3259c51b97f244609ec10d3a77d598c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]: /images/20220205/c90557a4081f4bc4a8306793e11cdbe9.png