非递归下降的预测分析

博主： admin
发布时间：2020 年 04 月 28 日
325次浏览
3 条评论
2994字数
分类：编译原理

## 组成

* 存放当前分析进程的栈,栈底为`$`
* 以`$`结尾的输入语句
* 分析表，起决策作用
* 预测分析程序，执行决策
* 输出，语法分析数

## 流程

假设当前栈顶元素为***X***，输入符号为***a***，有三种可能性：

* 如果***X***=**a**=`$`，分析器宣布分析完成成功而停机。
* 如果***X***=**a**≠`$`，分析器弹出栈顶元素，并推进输入指针，使之指向限一个输入符号。
* 如果***X***是非终结符号，程序访问分析表**M**,若**M[*X*,a]**是***X***的产生式，例如**M[*X*,a]**={***X***→***UVM***}，那么分析器就会用***UVM***替代栈顶的***X***，并让***U***置于栈顶。作为输出，在此假定分析器打印出所用的产生式，当然也可以执行其他代码。如果**M[*X*,a]**提示错误，则分析其启动错误恢复例程。

## 例

假设有：

输入语句**id \* id + id $**

文法***G***的预测分析表***M***，表**M**如下：

|         |     **id**     |      **+**      |      **\***      |     **(**     |     **)**     |     **$**     |
| :--------: | :--------------: | :----------------: | :-----------------: | :--------------: | :--------------: | :--------------: |
| ***E*** | ***E*→*TE'*** |                 |                   | ***E*→*TE'*** |               |               |
| ***E'*** |               | ***E'*→+*TE'*** |                   |               | ***E'*→*ε*** | ***E'*→*ε*** |
| ***T*** | ***T*→*FT'*** |                 |                   | ***T*→*FT'*** |               |               |
| ***T'*** |               |  ***T'*→*ε***  | ***T'*→\**FT'*** |               | ***T'*→*ε*** | ***T'*→*ε*** |
| ***F*** |  ***F*→id**  |                 |                   | ***F*→(*E*)** |               |               |

执行流程如下：

| step |       栈       |        输入        |       输出       |     决策依据     |
| :----: | :--------------: | :-------------------: | :-----------------: | :-----------------: |
|  0  |    **$*E***    | **id \* id + id $** |       **-**       |  ***E*→*TE'***  |
|  1  |   **$*E'T***   | **id \* id + id $** |  ***E*→*TE'***  |  ***T*→*FT'***  |
|  2  |  **$*E'T'F***  | **id \* id + id $** |  ***T*→*FT'***  |    ***F*→id**    |
|  3  | **$*E'T'*id** | **id \* id + id $** |    ***F*→id**    |      *equal*      |
|  4  |  **$*E'T'***  |  **\* id + id $**  |    **匹配id**    | ***T'*→\**FT'*** |
|  5  | **$*E'T'F*\*** |  **\* id + id $**  | ***T'*→\**FT'*** |      *equal*      |
|  6  |  **$*E'T'F***  |    **id + id $**    |    **匹配id**    |    ***F*→id**    |
|  7  | **$*E'T'*id** |    **id + id $**    |    ***F*→id**    |      *equal*      |
|  8  |  **$*E'T'***  |     **+ id $**     |    **匹配id**    |  ***T'*→*ε***  |
|  9  |   **$*E'***   |     **+ id $**     |  ***T'*→*ε***  | ***E'*→+*TE'*** |
|  10  |  **$*E'T*+**  |     **+ id $**     | ***E'*→+*TE'*** |      *equal*      |
|  11  |   **$*E'T***   |      **id $**      |    **匹配id**    |  ***T*→*FT'***  |
|  12  |  **$*E'T'F***  |      **id $**      |  ***T*→*FT'***  |    ***F*→id**    |
|  13  | **$*E'T'*id** |      **id $**      |    ***F*→id**    |      *equal*      |
|  14  |  **$*E'T'***  |        **$**        |    **匹配id**    |  ***T'*→*ε***  |
|  15  |   **$*E'***   |        **$**        |  ***T'*→*ε***  |  ***E'*→*ε***  |
|  16  |     **$**     |        **$**        |  ***E'*→*ε***  |   ***Success***   |

**容易看出，执行流程实际上就是从根长出语法分析树的过程(最左推导)**

最后修改：2021 年 09 月 09 日 02 : 23 PM

如果觉得我的文章对你有用，请随意赞赏

3 条评论

najvtmqvbt
December 8th, 2024 at 06:01 am

《三屈式》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/60842.html

回复
bviotfdvjs
November 30th, 2024 at 06:19 pm

《豆腐西施杨七巧》国产剧高清在线免费观看：https://www.jgz518.com/xingkong/39184.html

回复
czpibuvihm
November 23rd, 2024 at 07:29 pm

《酷儿们》欧美剧高清在线免费观看：https://www.jgz518.com/xingkong/111714.html

回复