【编译原理】 第四章 自上而下语法分析

目录

语法分析器的功能

不确定的自上而下分析

确定的自上而下分析

LL(1)文法

左递归的消除

间接左递归的消除

消除文法中全部左递归的算法

消除回溯、提左因子

FIRST集

FOLLOW集

预测分析法

递归下降分析法

---

语法分析器的功能

按照文法从源程序单词串（符号串）中识别各类语法成分，判断所给出单词串是否是给定文法的正确句子，并为语义分析和代码生成做准备

  按照语法分析树的建立方法可以将语法分析方法分为： 自上而下分析法、自下而上分析法。

不确定的自上而下分析

算法思想：        

对于任一输入符号串，试用一切可能的办法从树根 结点出发根据文法自上而下的为输入串建立一棵语法树。

对应最左推导：

以上为输入符号串建立语法树的过程，实际上也是一个 建立最左推导的过程，之所以使用最左推导，是因为我 们对输入串是从左到右扫描的，只有使用最左推导，才 能按扫描顺序去匹配输入串。

存在问题：

1.左递归问题：自顶向下分析方法，在匹配过程中，假若 用到非终结符号U去匹配输入串，而U为左递归的(例如： UU…)，那么为了用它的右部匹配输入串，又要用到非 终结符号U，循环往复，没有终止。若文法存在间接递归， 也有相同问题发生。

2.回溯问题：对某个非终结符，当有多条规则时，需采用 逐个选择的方法，若不能匹配需要回溯，代价高，效率低。

还有虚假现象、出错位置不确切等。

确定的自上而下分析

算法思想：

对于任一输入符号串，从文法的识别符号出 发，根据当前的输入符号，唯一确定一个产生式，用产 生式右部的符号串替代相应的非终结符往下推导，或构 造一棵语法树。若能推导出输入串或构造语法树成功则 输入串是句子，否则不是。

LL(1)文法

 该文法满足确定的自上而下的分析方法， 其中，第一个L表明自左(Left)向右扫描输入串，第二个L表明分析过程采用最左(Left)推导，括号中的1表明只需向右看一个符号便可决定选择哪个产生式进行推导。

左递归的消除

P=E        =+T        =T

P=T       =*F        =F

间接左递归的消除

先将间接左递归变为直接左递归， 再按消除直接左递归的方法进行。

消除文法中全部左递归的算法

前提：该文法不含回路。

消除回溯、提左因子

FIRST集

FOLLOW集

预测分析法

 预测分析程序是一种自顶向下分析程序，预测分析

要求文法是LL(1)文法，它由分析栈、分析表和分析程序 三部分组成，其中分析表的构成与文法有关。

构造预测分析表

预测分析表的构造算法

递归下降分析法

方法思想：

对源程序中每个语法成分编制一个处理子程序，即对每个非终结符号编制一个递归过程，每个 子程序的功能是识别由该非终结符号推出的串。它要 求文法满足LL(1)文法，以便当某个非终结符号有多条 产生式时，可以根据当前的输入符号唯一地确定选择 某个产生式进行匹配。