第五章语法分析—一自上而下分析 本章内容 ●语法分析的任务与分类 ●自上而下分析面临的问题 ●递归下降分析程序构造 ●预测分析程序 ●LL()文法
第五章 语法分析——自上而下分析 本章内容 ⚫语法分析的任务与分类 ⚫自上而下分析面临的问题 ⚫递归下降分析程序构造 ⚫预测分析程序 ⚫LL(1)文法
、 语法分析的任务与分类 ●语法分析的任务： 对任一给定w∈V-*,判断w∈L(G) 语法分析器：是一个程序，它按照P,做识别W的工作 单词符号 源程序 语法分折 词法分析器 语法分析器 编译程序后续部分 取下一个 草词符号 符号表 图4.1语法分析器在编译程序中的地位
一、 语法分析的任务与分类 ⚫ 语法分析的任务： 对任一给定w ∈ VT *，判断 w ∈ L（G） ⚫ 语法分析器：是一个程序，它按照P，做识别w的工作 词法分析器 语法分析器 编译程序后续部分 符号表 源程序 单词符号 取下一个 单词符号 语法分析 图4.1 语法分析器在编译程序中的地位
语法分析的分类： 自下而上 自上而下 二、自上而下分析面临的问题 1、主旨：从文法开始符号出发，自上而下的为输入 串建立一棵语法树 例5.1文法G1: S —> cAd A> aba 输入串：w=cad,为它建立语法树
二、自上而下分析面临的问题 1、主旨：从文法开始符号出发，自上而下的为输入 串建立一棵语法树 ⚫ 语法分析的分类：自下而上 自上而下 ⚫ 例5.1 文法G1： S —＞ cAd A —＞ ab|a 输入串：w=cad，为它建立语法树
文法G:S一>cAd A->ab A->a 输入串W: c a d IP 分析过程： 孕2贝荷美1争的子 秒聚拿 指针退到二 gc "与a6匹配； 语法树的形成 等式装梵不品 可能匹配
S c A d a b a S —＞ cAd A —＞ ab A —＞ a 输入串w : 文法G: IP 分析过程： 1）w——输入串； IP—> ‘c’ S——扩充； c a d 2）α=c A d； 与 IP—> ‘c’ 匹配； 3）IP—> ‘a’ A扩展，第一式ab, IP—> ‘a’与ab匹配； IP—> ‘d’ ,但d与b不匹配; 4）报告失败，撤销A的子 树，回到A; 指针回退到IP—> ‘a’; A还有替换式未试过，而又 可能匹配； 语法树的形成
●上述分析方法的实现： ①每一非终结符对应一个递归子程序，在只生成 两个串的文法，过程无须递归，而对生成无数个串的文 法，递归是不可避免的； ②递归子程序：是一个布尔过程，一旦发现它的 某个候选式与输入串匹配，它就按此式扩充语法树， 并返回true,指针移过已匹配子串。否则，返回false, 保持原来的语法树和指针不变
⚫上述分析方法的实现： ①每一非终结符对应一个递归子程序，在只生成 两个串的文法，过程无须递归，而对生成无数个串的文 法，递归是不可避免的； ②递归子程序：是一个布尔过程，一旦发现它的 某个候选式与输入串匹配，它就按此式扩充语法树， 并返回true，指针移过已匹配子串。否则， 返回false， 保持原来的语法树和指针不变