编译原理 chapter4 语法分析学习课件.pptx

第四章语法分析;4.1自顶向下的分析

4.2预测分析法

4.3自底向上的分析

4.4LR分析法

4.5语法分析器自动生成工具;从分析树的顶部（根节点）向底部（叶节点）方向构造分析树

可以看成是从文法开始符号S推导出词串w的过程

例

每一步推导中，都需要做两个选择

替换当前句型中的哪个非终结符

用该非终结符的哪个候选式进行替换;在最左推导中，总是选择每个句型的最左非终结符进行替换

例

如果S?*lmα，则称α是当前文法的最左句型(left-sententialform);在最右推导中，总是选择每个句型的最右非终结符进行替换

例

在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范规约，而最右推导相应地称为规范推导;E?lmE+E

?lmid+E

?lmid+(E)

?lmid+(E+E)

?lmid+(id+E)

?lmid+(id+id);总是选择每个句型的最左非终结符进行替换

根据输入流中的下一个终结符，选择最左非终结符的一个候选式;文法

①E→TE’

②E’→+TE’｜ε

③T→FT’

④T’→*FT’｜ε

⑤F→(E)｜id

输入

id+id*id

;递归下降分析(Recursive-DescentParsing)

由一组过程组成，每个过程对应一个非终结符

从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析;预测分析是递归下降分析技术的一种，它不需要回溯，因此，是一种确定的自顶向下分析方法

通过在输入中向前看固定个数符号来选择正确的A-产生式。通常情况下只需向前看一个符号（即下一个输入符号）

可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k)文法类;例

文法G

S→aAd|aBe

A→c

B→b

输入

abc;例

文法G

E→E+T|E–T|T

T→T*F|T/F|F

F→(E)|id

输入

id+id*id;

A→Aα|β (α≠ε,β不以A开头)

A→βA′

A′→αA′｜ε

例

;A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

(αi≠ε,βj不以A开头)

A?β1A′|β2A′|…|βmA′

A′?α1A′|α2A???|…|αnA′|ε

;例S→Aa|b

A→Ac|Sd|ε

将S的定义代入A-产生式，得：

A→Ac|Aad|bd|ε

消除A-产生式的直接左递归，得：

A→bdA’|A’

A’→cA’|adA’|ε

;输入：不含循环推导（即形如A?+A的推导）和ε-产生式的文法G

输出：等价的无左递归文法

方法：;例

文法G

S→aAd|aBe

A→c

B→b

文法G

S→aS

S→Ad|Be

A→c

B→b

;输入：文法G

输出：等价的提取了左公因子的文法

方法：

;4.1自顶向下的分析

4.2预测分析法

4.3自底向上的分析

4.4LR分析法

4.5语法分析器自动生成工具;S_文法不含ε产生式

;;非终结符A的后继符号集

可能在某个句型中紧跟在A后边的终结符a的集合，记为

FOLLOW(A)={a|S?*αAaβ,a∈VT，α,β∈(VT∪VN)*}

例

(1)S→aBC

(2)B→bC

(3)B→dB

(4)B→ε

(5)C→c

(6)C→a

FOLLOW(B)={a,c}

;产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT(A→β)

SELECT(A→aβ)={a}

SELECT(A→ε)=FOLLOW(A)

q_文法

每个产生式的右部或为ε，或以终结符开始

具有相同左部的产生式有不相交的可选集

;串首终结符

串首第一个符号，并且是终结符。简称首终结符

给定一个文法符号串α，α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成