ch4语法分析自上而下分析

《ch4语法分析自上而下分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理第四章语法分析---自上而下分析程序设计语言2021/8/291Ch4.语法分析---自上而下分析本章在编译程序中的地位表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理2回顾：语法分析任务：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位，如“短语”、“句子”、“子句”、“程序段”等，为语法正确的输入构造语法树(或分析树)。语法分析依据的是语言的语法规则，即描述程序结构的规则，通过语法分析确定整个输入串是否构成一个语法上正确的程序。语法规则通常用上下

2、文无关文法描述。语法分析方法有自上而下和自下而上两类。本章和下一章将介绍编译程序构造中的一些典型的语法分析方法。3典型的语法分析方法自上而下语法分析方法第四章介绍递归子程序法预测分析法，即LL(1)法自下而上语法分析方法第五章介绍算符优先分析法规范归约法LR方法：LR(0)、SLR(1)、LR(1)、LALR(1)2021/8/294Ch4.语法分析---自上而下分析CH.4语法分析---自上而下分析掌握：消除文法左递归，消除回溯，计算FIRST集、FOLLOW集，LL(1)分析条件，LL(1)文法的概念，预测分析表的构造。了解理解：自上而下分析方法的基

3、本思想,自上而下分析的过程。教学内容：4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序的构造4.5预测分析程序*4.6LL(1)分析中的错误处理重点难点54.1语法分析器的功能语法分析是编译程序的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定一串单词符号的语法结构是否符合语法规则,是否文法的一个句子。分析判定的方法：建立输入串αn的从文法开始符号S出发的推导Sα1…αn即建立以S为根的与输入串αn相匹配的语法树图4.1表明语法分析器在编译程序中的地位64.2自上而下分析面临的问题本节

4、主要是通过例子1.说明自上而下分析方法的思想和步骤2.认识自上而下分析时所遇到的主要困难自上而下分析的主要困难是:文法的左递归性，使分析陷入无限循环回溯的不确定性，要求将已经完成工作推倒重来为解决这些问题，考虑要消除文法左递归和避免回溯。2021/8/297Ch4.语法分析---自上而下分析自上而下分析方法的思想从文法的开始符号出发，向下推导，试图推出句子，匹配输入符号串，寻找输入串的最左推导，并按与最左推导相对应的顺序，自上而下从左到右地建立输入串的语法分析树。推导过程中，试图根据当前的输入符号判断使用非终结符的哪个候选式去替换。分析过程是一种穷尽一切

5、可能的试探过程；是反复使用不同产生式谋求匹配输入串的过程。用例子说明，P67.例4.18自上而下分析(1)例4.1文法：⑴S→xAy⑵A→**⑶A→*输入串α=x*y，分析α是否文法的句子？序号ip指向　语法树　最左推导　说明x*yS根结S,当前符x①x*y③x得匹配,移动ipSxAySxAy用S→xAy展开S欲用xAy匹配输入串SxAy②x*y9自上而下分析(2)序号ip指向语法树　最左推导　说明Sx*yxAy试用A→**展开ASxAyx**y④**x*y⑤*得匹配,移动ip但y得不到匹配SxAy**用A→**展开失败回溯:回到第③步⑥SxAyS

6、xAyx*y10自上而下分析(3)序号ip指向　语法树　最左推导　说明x*ySxAy试用A→*展开ASxAyx*y⑦*x*y⑧*得匹配,移动ipSxAy*A完成匹配,y得匹配,移动ip,输入串匹配成功,结束⑨SxAySxAyx*yx*y*11自上而下分析：说明注:自上而下分析过程是带回溯的试探过程⑴遇非终结符标记的结,就试图用某个候选式展开,期望此候选能匹配输入串,若不能匹配,则要回溯。⑵遇终结符号的结，就进行匹配，然后移动输入串指针ip指向下一个符号。⑶回溯是一项复杂而费时的工作，须废弃已做的许多工作，恢复到前面的某一情况，效率很低。下面讨论

7、自上而下分析法存在的困难和缺点左递归、回溯、虚假匹配、当报告分析不成功时难于知道输入串中出错的确切位置，等12文法的左递归问题文法的左递归性直接左递归：文法存在产生式P→Pα间接左递归：存在推导P+Pα文法具有左递归性，采用自上而下方法分析，可能会陷入无限循环，分析不下去。例如：文法有左递归产生式A→Ax分析中会遇到试图展开A，却又立即遇到A，并将永远循环下去。在没有识别任何输入符号的情况下又得重新要求A去进行新的匹配---消左递归！SAxAxAx……13候选式的确定与回溯问题自上而下分析是一种反复用可能的候选式去进行试探的过程，不能预知本次试探是否会

8、成功，若不成功则需要回溯。例如文法：S→xAyA→**

9、*判定句子x*y是否该文