人工智能_编译new第四章自上而下语法分析.ppt
《人工智能_编译new第四章自上而下语法分析.ppt》由会员分享,可在线阅读,更多相关《人工智能_编译new第四章自上而下语法分析.ppt(60页珍藏版)》请在启牛文库网上搜索。
1、第四章 语法分析自上而下分析,本章内容语法分析的任务与分类自上而下分析面临的问题递归下降分析程序构造预测分析程序LL(1)文法,一、语法分析的任务与分类 语法分析的任务:对任一给定 w VT*,判断 w L(G)语法分析器:是一个程序,它按照P,做识别w的工作,词法分析器,语法分析器,编译程序后续部分,符号表,图4.1 语法分析器在编译程序中的地位,二、自上而下分析面临的问题,1、主旨:从文法开始符号出发,自上而下的为输入串建立一棵语法树,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
2、 d;与 IP c匹配;,3)IP aA扩展,第一式ab,IP a与ab匹配;IP d,但d与b不匹配;,4)报告失败,撤销A的子树,回到A;指针回退到IP a;A还有替换式未试过,而又可能匹配;,语法树的形成,上述分析方法的实现:,每一非终结符对应一个递归子程序,在只生成两个串的文法,过程无须递归,而对生成无数个串的文法,递归是不可避免的;,递归子程序:是一个布尔过程,一旦发现它的某个候选式与输入串匹配,它就按此式扩充语法树,并返回true,指针移过已匹配子串。否则,返回false,保持原来的语法树和指针不变。,程序实现:,使用记号:input_symbol:当前符号内容input_poin
3、ter:输入字符指针使用过程:ADVANCE():把input_pointer移到下一输入符号位置,置input_symbol是当前符号内容;,使用两个过程:S()和A(),它们送回true or false,决定于它们是否在输入串中找到相应的非终结符所构成的串。,procedure S();begin if input_symbol=cthen beginADVANCE();if A()then if inputSymbol=d thenbegin ADVANCE();return trueend end;return false;end;,procedure A();begin isave
4、:=input_pointer;if input_symbol=a then beginADVANCE();if inputSymbol=b then begin ADVANCE();return true;end end/*failure to find ab*/input_pointer:=isave;if inputSymbol=a thenbegin ADVANCE();return true;end else return false;end;,2、困难和问题,文法的左递归回溯用替换符的顺序会影响所接受的语言 如:A ab|a 改为 A a|ab 难以报告出错的确切位置穷举试探法低效
5、的分析方法,三、自上而下分析的问题解决,消除文法的左递归克服回溯问题,1、区分三种类型的左递归,-直接左递归 即形如:N-N-间接左递归 即形如:N-A A-B B-N,-潜在左递归即形如:N-N 而,2、直接左递归的消除,候选式:A-A|,A-AA-A|,消除方法:若:A A|,其中不以A开头则修改规则为:A A A A|,消去直接左递归后:E TE E+TE|T FT T*FT|F(E)|i,例4.2 文法:E E+T|TT T*F|FF(E)|i,消除方法:若:A A|,(不以P开头)则修改规则为:A A A A|,3、间接和潜在左递归的消除,代入法 将一个产生式规则右部的中的非终结符N
6、替换为N的候选式。如果N有 n个候选式,右边的重复n次,而且每一次重复都有N的不同候选式来代替N。,例4.3 N-a|Bc|在S-pNq中的代入结果为S-paq|pBcq|pq,间接和潜在左递归通常通过代入能转换为直接左递归,4、消除一个文法的一切左递归算法,对文法G的所有非终结符进行排序按上述顺序对每一个非终结符Pi依次执行:for(j=1;j i-1;j+)将Pj代入Pi的产生式(若可代入的话);消除关于Pi的直接左递归;化简上述所得文法。,5、消除回溯、提左因子,回溯原因,若当前符号=a,对 A 展开,而 A-1|2|m,那么,要知道哪一个i是获得以a开头的串的唯一替换式。即:选择哪一个
7、i,亦即通过查看第一个(当前)符号来发现合适的替换式i。,怎样选择i?以a为头的i如有多个i以a为头的,这是文法的问题,例如,有产生式:语句-if 条件 then 语句 else 语句|while 条件 do 语句|begin 语句表 end,若要寻找一个语句,那么关键字 if,while,begin就提示我们哪一个替换式是仅有可能成功的替换式。,抽象地看问题:若要求不得回溯,文法G(当然G不含左递归)的必要条件是什么,也即对文法有什么要求?,若由i a,选该必中,但若j a,就会导致无法百发百中,解决办法是对文法本身提出要求:“不会出现以上情况”,把这些阐明清楚是用一个FIRST()。,定义
8、FIRST():FIRST()=a|a,aVT 若,规定FIRST(),定理,若一个 AVN,就有许多FIRST(i),如果A的任何两个候选式i和j,均有FIRST(i)FIRST(j)=意味着,A的每一候选式推导后所得的字符串第一个VT均不同。于是,对输入符号a,如果aFIRST(i),则a notFIRST(j),(ji),因此,对A的展开无疑应选候选式i,才有可能命中。,消除回溯目的:非终结符A的所有侯选式的首符集两两不相交方法:提取公共左因子,若:A 1|2|n|1|2|m(其中,每个不以开头)那么,可以把这些规则改写成 A A|1|2|m A1|2|n,四、递归下降分析程序构造,在不
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 编译 new 第四 自上而下 语法分析