编译原理课程设计之第四章自上而下的语法分析.ppt

课程内容 第一章 概论 第二章 词法分析 第三章上下文无关文法及分析 第四章自上而下的语法分析 第五章自下而上的语法分析 第六章语义分析 第七章运行时环境 第八章代码生成 语法分析以词法分析程序输出的单词序列为输入，分析源程序的语法结构，判断它是否为相应程序设计语言的合法程序。 通常我们将语法分析的结果表示为分析树（parse tree）或语法树(syntax tree)。 第四章 自上而下的语法分析 4.1 分析树与抽象语法树 4.2 自上而下的语法分析算法概述 4.3 递归下降分析 4.3 LL(1)分析 4.1 分析树与抽象语法树 句子的每一个推导过程都对应一个分析树，分析树的定义： 文法G=(VT,VN,P,S)对应的分析树是一个作了标记的树： (1)每个节点都用终结符、非终结符或ε标出； (2)根结点用开始符号S标出； (3)每个叶结点都用终结符或ε标出； (4)每个非叶结点都用非终结点标出； (5)每一步直接推导对应一个子树：如果分析树中标记为A∈VN的节点有n个标记为X1，X2,…Xn的孩子(可以是终结符也可以是非终结符),则文法G中有对应的产生式 A→X1X2…Xn∈P； exp?exp op exp ?number op exp ?number + exp ?number + number exp?exp op exp exp op number exp + number number + number 分析树对于显示程序的各语法单位或程序的单词序列很有帮助，但是相比纯粹为编译生成可执行代码所需的信息而言，分析树却包括了更多的信息。 所以语法分析程序更趋向于生成抽象语法树，抽象语法树是分析树中所含信息的浓缩，这种树是源代码单词序列的抽象表示。它却包含了进一步分析所需的所有信息。而且比分析树效率更高。 注：各语法单位对应的抽象语法树的结构可以规定，没有标准，但可以参考现有编译器的做法。 第四章 自上而下的语法分析 4.1 分析树与抽象语法树 4.2 自上而下的语法分析算法概述 4.3 递归下降分析 4.3 LL(1)分析 4.2 自上而下的语法分析算法概述 自上而下的语法分析算法： 从文法的开始符号出发，反复使用文法的产生式规则，试图寻找与输入符号串匹配的推导。 从语法树的构造过程来看，是从文法的开始符号出发，将它做为语法树的根，试图向下逐步建立语法树，语法树的叶子节点是输入符号串； 4.1.1 递归下降分析的基本方法 递归下降分析法是一种自上而下的语法分析方法，在这种方法中，执行一组递归函数来处理输入串。 对文法的每一个非终结符A，都根据其相应的产生式(即文法规则)为其编写一个函数(子程序)，用来识别该非终结符所表示的语法范畴。 如果语法分析使用递归下降分析程序,为了避免重复扫描词法分析输出的单词序列(提高效率)，需要先将文法G采用EBNF表示法，然后写出递归下降分析程序。 4.1.2 文法规则使用EBNF表示法 选择的情况 重复的情况 选择的情况 EBNF使用[ ]表示选择： 文法G： S → cAd A → a A → ab viod ifStmt(void) { match(if); match((); exp(); match()); statement(); if token = else then { match(else); statement(); } } 解决问题的办法是使用EBNF规则： viod exp(void) { term( ); while token=+ or token=- { match(token); term( ); } } 语法分析的基本步骤 根据语言的语法描述形式，定义各种基本语法结构的抽象语法树形式； 选择一种合适的语法分析算法； 生成句子语法分析的结果(抽象语法树或错误报告)。 第四章 自上而下的语法分析 4.1 递归下降分析 4.2 LL(1)分析 LL (1)分析方法如下： 通过栈来‘记忆‘针对当前句型中的哪一个非终结符进行推导,首先将文法的开始符号S入栈； 如果栈的顶部是终结符a,则将其与当前输入记号匹配(出栈)。 如果栈的顶部是非终结符A,则利用A对应的某个文法规则A?α将栈顶部的非终结符A(出栈)替换成串α(将串α自右至左入栈)。 构造一个终结符和非终结符索引的二维表格M[N,T]可以表达出用哪一个产生式进行进行下一步推导,其中N是非终结符的集合，T是终结符的集合，即构造一个LL(1)分析表，通过该表格引导用哪一个产生式进行推导