编译原理 第4章1.ppt

第四章语法分析
本章讨论程序语言的语法分析方法,以及语法分析程序的设计原理和实现技术。
第四章语法分析
语法分析程序的功能和语法分析方法
自顶向下语法分析法
自底向上算符优先分析法
LR分析法
语法分析程序的功能
语法分析程序的功能
语法分析器
词法分析后的单词串
语法成分构成的语法树
或错误表
语法分析程序的功能
语法分析的方法
自顶向下语法分析法
(自上而下语法分析法)
自底向上语法分析法
(自下而上语法分析法)
语法分析程序的功能
1. 自上而下的分析法
从文法的开始符号出发,根据文法规则正向推导出给定句子的一种方法;或者说,从树根开始,往下构造语法树,直到建立每个叶的分析方法。
语法分析程序的功能
2. 自下而上的分析法
从给定的输入串开始,根据文法规则逐步进行归约,直至归约到文法开始符号的一种方法;或者说,从语法树的未端开始,步步向上归约,直至根结点的分析方法。
自上而下语法分析法
非确定的自上而下分析法的基本思想是:
对任何输入串W试图用一切可能的办法,从文法的开始符号出发,自上而下地为它建立一棵语法树。或者说,为输入串寻找一个最左推导。如果试探成功,则W为相应文法的一个句子,否则W就不是文法句子。
非确定的自上而下分析法的思想
也就是说,这种分析过程本质上是一种穷举试探过程,是反复使用不同规则,谋求匹配输入串的过程。
试探发生回溯。
非确定的自上而下分析法的思想
例设有文法G[S]:
S→ aAb
A→ de | d
输入串 W=adb
S
a A b
d e
匹配失败、这时应回溯,选择A的其它可能的规则重新匹配。
非确定的自上而下分析法的思想
d
匹配成功
S→ aAb
A→ de | d
S
a A b
输入串 W=adb