编译原理 第四章语法分析 上海交通大学 张冬茉 Email: zhang-dm(acs situ. edu.cn 2004年3月
1 编译原理 第四章 语法分析 上海交通大学 张冬茉 Email:zhang-dm@cs.sjtu.edu.cn 2004年3月
本章目的 描述程序语言的语法结构,需借助 于上下文无关文法。文法是描述程序语 言的依据,也是编译的依据。识别上下 文无关文法所生成的语言的方法是语法 分析的关键。本章的目的是研究这些方 法
2 本章目的 描述程序语言的语法结构，需借助 于上下文无关文法。文法是描述程序语 言的依据，也是编译的依据。识别上下 文无关文法所生成的语言的方法是语法 分析的关键。本章的目的是研究这些方 法
第四章语法分析 §4.1语法分析概述 词法分析器按词法规则将输入字符串识别 为单词符号流,这些单词符号便是上下文无关 文法中的终结符。 语法分析器的任务,是把由这些终结符组 成的有限列序,作为语法分析器的输入串,按 文法规则,识别它是否构成了合法的句子(程 序),并对语法分析中发现的错误,作出必要的 处理
3 第四章 语法分析 §4.1 语法分析概述 词法分析器按词法规则将输入字符串识别 为单词符号流，这些单词符号便是上下文无关 文法中的终结符。 语法分析器的任务，是把由这些终结符组 成的有限列序，作为语法分析器的输入串，按 文法规则，识别它是否构成了合法的句子(程 序)，并对语法分析中发现的错误，作出必要的 处理。
语法分析器与词法分析器和语义分析 器的关系 如果语法分析器作为单独一遍,通常以分析 树的形式作为其输出,供语法分析的后续阶段 继续分析。如果语法分析与语义分析,中间代 码生成构成一遍,则每当识别一个文法结构时, 就调用相应分析程序,并生成中间代码,因此 输出为中间代码形式
4 语法分析器与词法分析器和语义分析 器的关系 如果语法分析器作为单独一遍，通常以分析 树的形式作为其输出，供语法分析的后续阶段 继续分析。如果语法分析与语义分析，中间代 码生成构成一遍，则每当识别一个文法结构时， 就调用相应分析程序，并生成中间代码，因此 输出为中间代码形式。
语法分析的方法 通常有两类,即自上而下分析方法和自下 而上分析方法,或称为自顶向下top-down)和 自底向上( bottom-up)分析方法。它们都要判断 输入串是否为一合法句子
5 语法分析的方法 通常有两类，即自上而下分析方法和自下 而上分析方法，或称为自顶向下(top-down)和 自底向上(bottom-up)分析方法。它们都要判断 一输入串是否为一合法句子。
对自上而下分析来说,能否找到从文法开始符 开始的推导序列,使得推导出的句子恰为输入 串。或者说,能否从根结点出发,向下生长出 棵语法分析树,其叶结点组成的句子恰为输 入串。显然语法分析树的每一步生长每一步推 导)都以能否与输入串匹配为准。 对自下而上分析来说,能否从输入串出发找到 个归约序列,能最终地归约为文法开始符。 或者说,能否从叶结点出发,向上归结出以文 法开始符为根结点的语法分析树,每一步的归 约,都以待处理的字符串是否已形成句柄(或最 左素短语)为准
6 •对自上而下分析来说，能否找到从文法开始符 开始的推导序列，使得推导出的句子恰为输入 串。或者说，能否从根结点出发，向下生长出 一棵语法分析树，其叶结点组成的句子恰为输 入串。显然语法分析树的每一步生长(每一步推 导)都以能否与输入串匹配为准。 •对自下而上分析来说，能否从输入串出发找到 一个归约序列，能最终地归约为文法开始符。 或者说，能否从叶结点出发，向上归结出以文 法开始符为根结点的语法分析树，每一步的归 约，都以待处理的字符串是否已形成句柄(或最 左素短语)为准。
§4,2递归下降分析方法 递归下降分析法是一种自顶向下的分 析方法,文法的每个非终结符,对应于 个递归过程。分析就是从方法开始符出发 执行一组递归过程,向下推导,直到推导 出句子。或者说从根结点出发,自上而下 为输入串寻找一个最左匹配序列,建立 棵语法分析树
7 §4.2 递归下降分析方法 递归下降分析法是一种自顶向下的分 析方法，文法的每个非终结符，对应于一 个递归过程。分析就是从方法开始符出发 执行一组递归过程，向下推导，直到推导 出句子。或者说从根结点出发，自上而下 为输入串寻找一个最左匹配序列，建立一 棵语法分析树。
试探分析法 「例41文法 S->XAy A→>ab|la 若输入串为xy时,分析过程为: (1)首先建立根结点S (2)文法关于S的产生式只有一个,所以从S生 长分析树如图4l(a)。它的第一个终结符x与输 入串待分析字符x匹配,于是下一待分析字符 为a,期待与分析树中x右的叶结点A匹配。 8
8 一、试探分析法 [例4.1] 文法 S->xAy A->ab |a 若输入串为xay时，分析过程为： (1) 首先建立根结点S。 (2) 文法关于S的产生式只有一个，所以从S生 长分析树如图4.1(a)。它的第一个终结符x与输 入串待分析字符x匹配，于是下一待分析字符 为a，期待与分析树中x右的叶结点A匹配。
(3)非终结符A有两个候选式,先选用第一个候 选式。生长分析树如图4.1(b),这时分析树第 二叶结点a恰与待分析字符a匹配 (4)输入串中下一待分析字符为y,期待与第三 叶结点b匹配。此时发觉这两个字符是不同的, 即匹配失败。问题在于在生成A的子树时选用 的是第一个候选式。 (5)于是将A的这棵子树注销,把匹配指针退回 到输入串的第二字符,也即恢复与A匹配时的 现场,即(3)之前
9 (3) 非终结符A有两个候选式，先选用第一个候 选式。生长分析树如图4.1(b)，这时分析树第 二叶结点a恰与待分析字符a匹配。 (4) 输入串中下一待分析字符为y，期待与第三 叶结点b匹配。此时发觉这两个字符是不同的， 即匹配失败。问题在于在生成A的子树时选用 的是第一个候选式。 (5) 于是将A的这棵子树注销，把匹配指针退回 到输入串的第二字符，也即恢复与A匹配时的 现场，即(3)之前。
(6)A选用第二候选式,生长分析树如图 41(c),这时第二叶结点a与输入串第二字 符匹配。 (⑦)输入串下一待分析字符指向y,分析树 指向a右叶结点y。两者恰匹配,所以,分 析树41(c)即为输入串xay语法分析树。 10
10 (6) A选用第二候选式，生长分析树如图 4.1(c)，这时第二叶结点a与输入串第二字 符匹配。 (7) 输入串下一待分析字符指向y，分析树 指向a右叶结点y。两者恰匹配，所以，分 析树4.1(c)即为输入串xay语法分析树。