非递归的预测分析法

比眉伴天荒 2022-02-13 09:27 241阅读 0赞

### 文章目录 ###

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

# 概念 #

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

![image][]

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

例如， L = \{ a n b n ∣ n ≥ 1 \} L=\\\{a^nb^n|n\\ge 1\\\} L=\{ anbn∣n≥1\}。

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

# 例子 #

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

# 算法流程 #

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

# 预测分析法实现步骤 #

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

[image]: http://note.youdao.com/yws/res/10513/463CB42C469B4D48912C56EC0CF92FBC
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20220213/d2616c31d080475e9ac843bece10d0be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20220213/b92529a54d3949588266a355907b1b6d.png