第五章语法分析—一自上而下分析 本章内容 ●语法分析的任务与分类 ●自上而下分析面临的问题 ●递归下降分析程序构造 ●预测分析程序 ●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， 保持原来的语法树和指针不变
●程序实现： 使用两个过程：S()和A(),它们送回true or false,决定于它们是否在输入串中找到相应的非终结 符所构成的串。 ●使用记号： input_symbol:当前符号内容 input_pointer:输入字符指针 ●使用过程： ADVANCE():把input_pointer移到下一输入符号 位置，置input_symbol是当前符号内容；
⚫程序实现： ⚫使用记号： input_symbol：当前符号内容 input_pointer：输入字符指针 ⚫使用过程： ADVANCE( )：把input_pointer移到下一输入符号 位置，置input_symbol是当前符号内容； 使用两个过程：S( )和A( )，它们送回true or false，决定于它们是否在输入串中找到相应的非终结 符所构成的串
procedure S(); procedure A(); begin begin isave:=input_pointer; if input symbol='c'then if input_symbol=a'then begin begin ADVANCE(); ADVANCE(); if A()then if inputSymbol=‘b' then begin if inputSymbol=‘d' ADVANCE();return else; then end begin end ADVANCE(); /*failure to find ab*/ return true input_pointer:=isave; end if inputSymbol=‘a' then end; begin ADVANCE();return true; return false; end end; else return false; end;
procedure S( ); begin if input_symbol =‘c’then begin ADVANCE( ); if A( ) then if inputSymbol=‘d’ then begin ADVANCE( ); return true end end; return false; end; procedure A( ); begin isave:= input_pointer; if input_symbol= ‘a’ then begin ADVANCE( ); if inputSymbol = ‘b’ then begin ADVANCE( ); return else; end end /*failure to find ab*/ input_pointer:=isave; if inputSymbol = ‘a’ then begin ADVANCE( ); return true; end else return false; end;
2、困雅和问题 ●文法的左递归 ●回溯 ●用替换符的顺序会影响所接受的语言 如：A一>ab/a改为A一>a/ab ●雅以报告出错的确切位置 ●穷举试探法—低效的分析方法
2、困难和问题 ⚫文法的左递归 ⚫回溯 ⚫用替换符的顺序会影响所接受的语言 如：A —＞ ab|a 改为 A —＞ a|ab ⚫难以报告出错的确切位置 ⚫穷举试探法——低效的分析方法
三、自上而下分析的问题解决 >消除文法的左递归 >克服回湖问题
三、自上而下分析的问题解决 ➢消除文法的左递归 ➢克服回溯问题
1、区分三种类型的左递归 -直接左递归 ~潜在左递归 即形如：N->Na 即形知：N->aN 间接左递归 而u吉e 即形如：N->Aa A->BB B->NY
1、区分三种类型的左递归 -直接左递归 即形如：N->Nα -间接左递归 即形如：N->Aα A->Bβ B->Nγ -潜在左递归 即形如：N->αN 而α ε