文档介绍：自上而下语法分析方法
第四章(1)
本节要求
主要内容:
1. 语法分析的任务和设计
2. 自上而下语法分析方法及其相关概念
重点掌握:
1. 语法分析的任务和接口
2. 自顶向下语法分析面临的问题及解决方法
3. LL(1)文法的判定及分析表的构造
5. 能够使用递归下降分析方法和预测分析方法实现语法分析器,并对给定的输入串进行分析
高级语言的语法结构适合用上下文无关文法来描述,上下文无关文法是语法分析的基础。
语法分析是编译过程的核心,其任务是在词法分析识别出正确的单词符号串的基础上,分析并判定输入的符号串的语法结构是否符合语法规则。
语法分析概述
问题:
在上一章词法分析中讲解了如何判断源程序中单词的正确性,并输出了正确的单词符号。那么如何知道这些正确的单词是否能构成正确的语法单位(表达式、语句或程序)呢?
语法分析的任务
在词法分析识别出正确的单词符号串的基础上,分析并判定这些输入符号串是否符合语法规则(即,是否是给定文法的一个句子)。
语法分析在编译系统中所处的位置
语法分析器的输入
Token序列:词法分析的输出,是各个单词都正确的源程序的变换形式,是一个有限序列
语法分析器的输出
分析树:表示方法?线索树
错误处理信息:定位、继续编译
语法分析的接口设计
语法分析器的功能
按照语言的语法构成规则, 识别输入符号串能否构成一个句子。这些规则是用文法的产生式来定义的。
问题
对给定的一个输入符号串,如何判定它是不是一个句子?
方法
根据文法的产生式规则,看能否建立与输入串匹配的语法树。(第二章使用“推导”)
G = ({E}, {i, +, *, (, ) } , P , E) P: E E + E
E E * E
E ( E )
E i
解:使用最左推导:
E E*E (E)*E (E + E)*E (i + E)*E
(i + i)*E (i + i)*i
例:判定输入串(i+i)*i是否是下述文法的句子?
结论:能够从开始符号出发推导出给定的输入串,
因此,是句子。
常用的语法分析方法(根据建立语法树的方向):
自顶向下分析法: 从文法的开始符号出发,向下推导(使用最左推导) ,尽可能使用各种产生式,推导出与输入串匹配的句子,从而建立语法树。
自底向上分析法: 从输入符号串开始,逐步进行归约(最右推导的逆过程),直至归约到文法的开始符号,从而建立语法树。
具体分类:
自顶向下分析
递归下降分析
预测分析(LL)
自底向上分析
算符优先分析
LR分析
自上而下语法分析面临的问题及其解决方法
自上而下分析:对任何输入串,试图用一切可能的办法,从文法的开始符号出发,自上而下地为输入串建立一个语法树。
从推导的角度看,从开始符号出发,使用最左推导,试图推导出与输入符号串相同的句子。
从语法树的角度看,从根节点出发,反复使用所有可能的产生式,谋求输入串的匹配,试图向下构造一棵语法树,其末端节点正好与输入符号串相同。
需要反复试探。