第五章_自顶向下语法分析方法

编译原理第五章PPT

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

指导教师:杨建国 二零零七年十一月1

编译原理第五章PPT

词法分析内容回顾 功能输入源程序，输出单词流盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

手工设计词法分析器的主要工作 正规式：定义词法规则 把正规式描述的规则转化为NFA NFA进行确定化得到DFA 简化DFA 通过程序实现DFA

词法分析器的自动生成Lex2

编译原理第五章PPT

第5章 自顶向下语法分析方法语法分析技术概况不确定的 自顶向下分析法盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

递归下降分析法 确定的

第5 章

语法分析方法

预测分析法LL(1) 简单优先分析法 优先分析法 算符优先分析法 第6章LR分析法第7章

自底向上分析法LR(0)分析法 SLR(1)分析法 LR(1)分析法 LALR(1)分析法3

编译原理第五章PPT

学习目标盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

1.自上而下语法分析的基本思想 2.求FIRST、FOLLOW、SELECT集合的方法 3.提取左公因子与消除左递归的方法 4.递归下降分析程序的构造 5.LL(1)文法的判定，分析表的构造与输入串 的分析过程

编译原理第五章PPT

教学内容 第一节盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

确定的自顶向下分析思想 LL(1)文法的判别 某些非LL(1)文法到LL(1)文法的等价变换 不确定的自顶向下分析思想 确定的自顶向下分析方法 典型例题及解答

第二节 第三节 第四节 第五节 第六节

编译原理第五章PPT

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

知 识 结 构

编译原理第五章PPT

由于正规式与正规文法是等价的，盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

它们的描述能力有限，而高级程序语 言的语法结构适合用上下文无关文法 描述，因此我们把上下文无关文法作 为语法分析的基础。

编译原理第五章PPT

引言

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

1、语法分析的地位 –是编译程序的核心部分。

2、语法分析的任务 –识别由词法分析得出的单词序列是否是给定文法 的句子。3、语法分析的理论基础 –上下文无关文法和下推自动机

编译原理第五章PPT

4、语法分析的方法按照语法分析树的建立方法，我们可以粗略地把语法分析分 成两类，一类是自顶向下分析法，另一类是自底向上分析法。盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

自顶向下分析法：从文法的开始符号出发，通过推导过程试图产生与输入串匹配的句子。 从树根开始，往下构造语法树，直到建立每个树叶 的分析方法。 自底向上分析法：从输入串出发，通过归约过程试图归 约到文法的开始符。 从语法树的末端开始，向上归约，直至根结点的分 析方法。 不论是哪一种方法，语法分析器都是自左向右地扫描输入字 符串。9

编译原理第五章PPT

自顶向下分析算法的

基本思想为： 若Z SG[Z]盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

+

则 S L(G[Z])

否则 S L(G[Z])

存在主要问题: 左递归问题 回溯问题

主要方法: 递归子程序法 LL分析法

自底向上分析算法的基本思想为：

若Z SG[Z]

+

则 S L(G[Z])

否则 S L(G[Z])

存在主要问题: 句柄的识别问题

主要方法: 算法优先分析法 LR分析法10

编译原理第五章PPT

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

自顶向下分析法通常分为确定的和不 确定的两种，确定的分析方法对文法有一 定限制，但由于实现方法简单、直观，便 于手工构造或自动生成语法分析器，是目 前常用的分析方法之一；相反，由于不确 定的分析方法带有回溯，效率低、代价高， 因而极少使用。

编译原理第五章PPT

§5.1 确定的自顶向下分析思想一.确定分析的条件盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

从文法的开始符号出发，如能根据当前的输 入符号(单词符号)唯一地确定选用哪个产生式 进行推导，则分析是确定的。 特征——根据下一个输入符号为当前要处理的 非终结符选择产生式 要求——文法是LL(1)的 第一个L从左到右扫描输入串 第二个L 生成的是最左推导 向前看一个输入符号(lookahead)12

编译原理第五章PPT

例1

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

设有文法G1[S]: S→pA|qB A→cAd|a B→dB|b 若输入串W=pccadd。自顶向下的推导过程为:S G1[S]有如下特点： 每条产生式的右部由终结符开头; A d 同一非终结符的不同产生式的右 A d 部由不同的终结符开头。 A a

p c

c

S =>pA =>pcAd =>pccAdd =>pccadd

编译原理第五章PPT

例2 设有文法G2[S]为: S→Ap|Bq 若输入串W=ccap,自顶向下的推导过程为： A→a|cA盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

B→b|dBS A c c A A a p

该例说明: (1)产生式右部以终结符或非终结符开头(无空 产生式); (2)同一非终结符的不同产生式的右部由不同的 符号开头。 对于这种文法，在推导过程选用哪条产生 式不直观，关键是判断产生式右部推出的开始 符号(集),分析过程可能是确定的

S =>Ap =>cAp =>ccAp =>ccap

编译原理第五章PPT

分析能确定推导原因：① 前提：2型文法中无空产生式 ② 在文法中，对于每个非终结符A的定义 A→α1|α2|...|αn 任给i,j(1≤i,j≤n,i<>j),从αi和αj推导 出来的第一个终结符号集合(称为开始符号集 FIRST)不相交,即:FIRST(αi)∩FIRST(αj)=Φ ③ 结论：在推导过程中完全可以根据向前看符号是 属于哪条产生式右部的开始符号集合而决定选择 相应的产生式进行推导，因此，分析过程是完全 确定的。

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

编译原理第五章PPT

二.串 开始符号集FIRST设G=(VT,VN,S,P)是2型文法， * FIRST(α)={a|α

aβ,a∈VT,α,β∈V*} 若α* ε,则规定ε∈FIRST(α)

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

直观定义理解： * FIRST(α)={a|α a……,a∈VT} FIRST(α)包含了α对应的串的所有可能的首 终结符号集(选择产生式的依据)

编译原理第五章PPT

例3 文法G2[S]:S→Ap S→Bq盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

FIRST(Ap)={a,c} FIRST(Bq)={b,d}

A→aA→cA

FIRST(a)={a}FIRST(cA)={c}

B→bB→dB

FIRST(b)={b}FIRST(dB)={d}

由于同一非终结符的两个产生式的右部推导出 来的开始符号集不相交，因此可根据当前输入符号 属于哪条产生式右部的开始符号集而决定选哪条产 生式进行推导，可以进行确定的自顶向下分析。17

编译原理第五章PPT

例4 设有文法G3[S]S→aA|d A→bAS|ε盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

若输入串W=abd,自顶向下的推导过程为： S 文法的特点是:包含空产生式 对于空产生式左部的非终结符，关键 a A 是判断该非终结符的后跟符号(集), 分析过程可能是确定的。 b A S

ε

d

S =>aA =>abAS =>abS =>abd18

编译原理第五章PPT

选择A的产生式的依据 FIRST(bAS)={b} FIRST(ε)={ε} 分析：盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

无d,但若A为ε,则A的后面能推出d思考：若A有一条产生式能推出ε,则需要寻找什么？ 寻找A后面的符号串能否推出首字符是d的符号串， 即：寻找紧跟在A后面的符号有哪些。

编译原理第五章PPT

三.非终结符A的后跟符号集FOLLOW设G=(VT,VN,S,P)是上下文无关文法，A∈VN,S是开始 符号。 * FOLLOW(A)={a|S A 且a∈FIRST( ), ∈VT*, ∈V+} * * 若S A ,且 ε,则规定#∈FOLLOW(A)

盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

直观定义理解：

* FOLLOW(A)={a|S …Aa…,a∈VT } * 若S ……A,则规定#∈FOLLOW(A)

#作为输入串的结束符，或称为句子括号，如： #输入串# FOLLOW(A)表示句型中可能紧跟在A后面的终结符号20

编译原理第五章PPT

例5 文法G3[S]: S→aA|d A→bAS|ε 由S * aA得#∈FOLLOW(A)盛 威 网 ： 专 业 的 计 算 机 学 习 网 站

由S * abAS * abAaA 得 a∈FOLLOW(A) … * abAd FOLLOW(A)={#,a,d} 得 d∈FOLLOW(A)

由S * S 得#∈FOLLOW(S)由S=>aA=>abAS=>abbASS=>abbASaA …=>abbASd FOLLOW(S)={#,a,d}21

本文来源：https://www.bwwdw.com/article/bwp4.html