第章语法分析——自上而下分析.pdf

第四章 语法分析—— 自上而下分析 授课人: 高珍 gaozhen@tongji.edu.cn 内容线索 语法分析器的功能  自上而下分析方法概述  LL （1）分析方法  递归下降分析程序  预测分析程序 2 语法分析器  语法分析的任务 ： 对任一给定 w ∈VT*，判断 w ∈L(G)?  语法分析器：按照产生式规则，做识别w 的工作 源程序 词法分析器 单词符号 语法分析器 语法分析树 编译程序后续部分 取下一个 单词符号 符号表 语法分析器在编译程序中的地位 3 语法分析方法  自上(顶)而下分析 从文法的开始符号出发，反  LL （1）分析法 复使用各种产生式，寻找与  递归下降分析法 输入符号匹配的最左推导。  预测分析法  自下（底）而上分析 从输入符号串开始，逐步进  算符优先分析法 行归约（最右推导的逆过  LR分析法 程），直至归约到文法的开 始符号。 4 自顶向下分析例子 例1 文法G[Z] 例2 文法G[S] Z →aBd S →Ap|Bq B →d A →a|cA B →c B →b|dB B →bB 求符号串abcd的推导过程 求符号串ccap的推导过程 5 自底向上分析概述  从终极符串出发归约出文法的开始符 例1 文法G[Z] 例2 文法G[S] Z →aBd S →Ap|Bq B →d A →a|cA B →c B →b|dB B →bB 求符号串abcd的归约过程 求符号串ccap的归约过程 6 内容线索 语法分析器的功能  自上而下分析方法概述  LL （1）分析方法  递归下降分析程序  预测分析程序