编译原理自顶向下语法分析方法.ppt

该【编译原理自顶向下语法分析方法 】是由【wxq362】上传分享，文档一共【102】页，该文档可以免费在线阅读，需要了解更多关于【编译原理自顶向下语法分析方法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第四章自顶向下语法分析方法
第1页,共102页。
学****目标:
掌握:LL(1)文法的判别,预测分析法,递归子程序的构造方法
理解:LL(1)文法
了解:不确定的自顶向下分析
第2页,共102页。
语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子
语法分析
自顶向下分析
自底向上分析
确定的
不确定的
算法优先分析(第六章)
LR分析(第五章)
自顶向下基本思想:
从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.
分类:
第3页,共102页。
回顾——自上而下的分析方法
定义:
从文法的开始符号出发,反复使用文法的产生式,寻找与输入符号串匹配的推导。
语法树的构造:
将文法的开始符号作为语法树的根,向下逐步建立语法树,使语法树的末端结点符号串正好是输入符号串。
自上而下分析的主要问题
选定产生式
第4页,共102页。
例文法G:S→cAdA→abA→a识别输入串w=cabd是否为该文法的句子
S
c
A
d
a
b
=>cabd
S
=>cAd
回顾——自上而下的分析方法
S
c
A
d
a
成功
不成功
=>cad
S
=>cAd
第5页,共102页。
确定的自顶向下分析思想
LL(1)文法的判别
某些非LL(1)文法到LL(1)文法的等价变换
不确定的自顶向下分析思想
确定的自顶向下分析方法
本章内容
第6页,共102页。

1确定分析的条件
2开始符号集FIRST(α)的定义
3后跟符号集FOLLOW(A)的定义
4选择集合SELECT(A→α)的定义
5LL(1)文法的定义
第7页,共102页。

从文法的开始符出发,如能根据当前的输入符号(单词符号)唯一地确定选用哪个产生式进行推导,则分析是确定的。
第8页,共102页。
例1设有文法G1[S]:
S→pA|qB
A→cAd|a
B→dB|b
若输入串W=pccadd。自顶向下的推导过程为:
S
S
A
p
c
A
d
c
A
d
a
=>pA
=>pcAd
=>pccAdd
=>pccadd
G1[S]有如下特点:
(1)每个产生式的右部由终结符开头;
(2)同一非终结符的不同产生式的右部由不同的终结符开头。
对于这种文法,在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导,即分析过程是确定的。
第9页,共102页。
例2:设有文法G2[S]为:
S→Ap|Bq
A→a|cA
B→b|dB
p
A
S
c
A
c
A
a
=>ccap
S
=>cAp
=>ccAp
=>Ap
该例说明,当
(1)产生式右部以终结符或非终结符开头(无空产生式);
(2)同一非终结符的不同产生式的右部由不同的符号开头。
若输入串W=ccap,自顶向下的推导过程为:
对于这种文法,在推导过程选用哪个产生式不直观,关键是判断产生式右部推出的开始符号(集),分析过程可能是确定的
第10页,共102页。