编译原理蒋宗礼课件第4章.ppt

《编译原理蒋宗礼课件第4章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章自顶向下的语法分析4.1语法分析概述4.2自顶向下的语法分析面临的问题与文法的改造4.3预测分析法4.4递归下降分析法4.5本章小结7/24/20211语法分析的功能和位置语法分析(syntaxanalysis)是编译程序的核心部分，其任务是检查词法分析器输出的单词序列是否是源语言中的句子，亦即是否符合源语言的语法规则。图4.1语法分析器在编译器中的位置7/24/202124.1语法分析概述递归子程序法自顶向下预测分析法(LL(1))算符优先分析法自底向上LR(0)、SLR(1)、LR(1)、L

2、ALR(1)TopDownBottomUp从文法产生语言的角度从自动机识别语言的角度从根开始，逐步为某语句构造一棵语法树相反，将一句子归约为开始符号问题：解决确定性问题！假定文法是压缩的：即删除了单位产生式和无用产生式。7/24/202134.2自顶向下的语法分析面临的问题与文法的改造自顶向下语法分析的基本思想从文法的开始符号出发，寻求所给的输入符号串的一个最左推导。从树根S开始，构造所给输入符号串的语法树例:设有G：S→xAyA→**

3、*，输入串：x**ySxAyx**ySxAy**7/24/2

4、02144.2.1自顶向下分析面临的问题1.二义性问题对于文法G，如果L(G)中存在一个具有两棵或两棵以上分析树的句子，则称G是二义性的。也可以等价地说：如果L(G)中存在一个具有两个或两个以上最左(或最右)推导的句子，则G是二义性文法。如果一个文法G是二义性的，假设wL(G)且w存在两个最左推导，则在对w进行自顶向下的语法分析时，语法分析程序将无法确定采用w的哪个最左推导。Gexp：EE+T

5、E-T

6、TTT*F

7、T/F

8、FFF↑P

9、PPc

10、id

11、(E)解决办法：改造文法，引入新的文法变量7

12、/24/202154.2.1自顶向下分析面临的问题2.回溯问题文法中每个语法变量A的产生式右部称为A的候选式，如果A有多个候选式存在公共前缀，则自顶向下的语法分析程序将无法根据当前输入符号准确地选择用于推导的产生式，只能试探。当试探不成功时就需要退回到上一步推导，看A是否还有其它的候选式，这就是回溯(backtracking)。Ge：ETEE+TEE-TTFTT*FTT/FF(E)Fid例如：考虑为输入串id+id*id建立最左推导7/24/202164.2.1自顶向下分析面临的问题2

13、.回溯问题ET(4.1)ETF(4.2)ETF(E)(4.3)ETFid(4.4)ETT*F(4.5)............4.2.2节我们将采用提取左因子的方法来改造文法，以便减少推导过程中回溯现象的发生，当然，单纯通过提取左因子无法彻底避免回溯现象的发生。7/24/202174.2.1自顶向下分析面临的问题3.左递归引起的无穷推导问题假设A是文法G的某个语法变量，如果存在推导AαAβ，则称文法G是递归的，当α=ε时称之为左递归；如果AαAβ至少需要两步推导，则称文法G是间接

14、递归的，当α=ε时称之为间接左递归；如果文法G中存在形如AαAβ的产生式，则称文法G是直接递归的，当α=ε时称之为直接左递归。Ger：ETEE+TEE-TTFTT*FTT/FF(E)Fid考虑为输入串id+id*id建立一个最左推导EE+TE+T+TE+T+T+T……7/24/202184.2.2对上下文无关文法的改造1.消除二义性改造的方法就是通过引入新的语法变量等，使文法含有更多的信息。其实，许多二义性文法是由于概念不清，即语法变量的定义不明确导致的，此时通过引入新的语法

15、变量即可消除文法的二义性。→ifthen

16、ifthenelse

17、other(4.7)根据if语句中else与then配对情况将其分为配对的语句和不配对的语句两类。上述if语句的文法没有对这两个不同的概念加以区分，只是简单地将它们都定义为，从而导致该文法是二义性的。7/24/202194.2.2对上下文无关文法的改造引入语法变量来表示不配对语句，表示配对语句<

18、stmt>→

19、→ifthenelse

20、other→ifthen

21、ifthenelse7/24/2021104.2.2对上下文无关文法的改造2.消除左递归直接左递归的消除