清华大学：《编译原理》课程教学资源_第五章 LL（1）文法及其分析程序

第5章LL(1)文法及其分析程序 5.1自上而下的语法分析 5.2预测分析程序 递归下降子程序 表驱动的预测分析程序 5.3LL(1)分析程序的生成 LL(1)文法 FIRST和 FOLLOW集定义和计算 54非LL(1)文法的改造

1 第5章 LL(1)文法及其分析程序 5.1 自上而下的语法分析 5.2 预测分析程序 递归下降子程序 表驱动的预测分析程序 5.3 LL(1)分析程序的生成 LL(1)文法 FIRST和FOLLOW集 定义和计算 5.4 非LL(1)文法的改造

5.1自上而下的语法分析 1语法分析概念 2自上而下的语法分析的一般过程 3自上而下的语法分析面临的问题

2 5.1自上而下的语法分析 1语法分析概念 2自上而下的语法分析的一般过程 3自上而下的语法分析面临的问题

(上下文无关文法)句型的分析 句型分析就是识别一个符号串是否为某文法 的句型的过程,或者说是某个推导的构造 过程

3 （上下文无关文法）句型的分析 句型分析就是识别一个符号串是否为某文法 的句型的过程，或者说是某个推导的构造 过程

语法树一推导的几何表示 句型 abbas的可能推导序列和语法树 例:GS|: S→aAS a A→SbA A→Ss a b a S→a S→aAS→aAa→ asbaa→ asbbaa→ aabbaa A→baS→aAS→ aSaS→abAS→abaS→ abbas S→aAS→ aSaS→ aSbAa→ gabAa→ aabbaa

4 语法树－推导的几何表示 句型aabbaa的可能推导序列和语法树 例: G[S]: S→aAS A→SbA A→SS S→a A→ba S a A S S b A a a b a SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa

语法分析 在语言的编译实现中,把句子分析的过程称 为语法分析,即完成这个任务的程序称为 语法分析程序或称为识别程序字。外析算法 又称识别算法 从左到右的分析算法,即总是从左到右地识 别输入符号串,首先识别符号串中的最左 符号,进而依次识别右边的一个符号,直 到分析结束

5 语法分析 在语言的编译实现中，把句子分析的过程称 为语法分析，即完成这个任务的程序称为 语法分析程序或称为识别程序。分析算法 又称识别算法。 从左到右的分析算法，即总是从左到右地识 别输入符号串，首先识别符号串中的最左 符号，进而依次识别右边的一个符号，直 到分析结束

分析算法分类 分析算法可分为: 自上而下分析法: 从文法的开始符号出发,寻找与输入符号 串匹配的推导,或者说,为输入串寻找 个最左推导 自下面上分析法: 从输入符号串开始,逐步进行归约,直至 归约到文法的开始符号

6 分析算法分类 分析算法可分为： 自上而下分析法： 从文法的开始符号出发，寻找与输入符号 串匹配的推导，或者说，为输入串寻找一 个最左推导。 自下而上分析法： 从输入符号串开始，逐步进行归约，直至 归约到文法的开始符号

两种方法反映了语法树的两种构 造过程。 自上历下方法是从文法符号开始,将它做为语法 树的根,向下逐步建立语法树,使语法树的结 果正好是输入符号串 自下历上方法则是从输入符号串开始,以它做为 语法树的结果,自底向上的构造语法树

7 两种方法反映了语法树的两种构 造过程。 自上而下方法是从文法符号开始，将它做为语法 树的根，向下逐步建立语法树，使语法树的结 果正好是输入符号串 自下而上方法则是从输入符号串开始，以它做为 语法树的结果，自底向上的构造语法树

自上而下分析 对任何输入串,试图用一切可能的办法, 从文法开始符号着手,自上而下地为输入 串构造一棵语法树,或者说,为输入串寻 找一个最左推导。本质上是一个试探过程, 反复使用不同地产生式谋求匹配输入串的 过程

8 自上而下分析 对任何输入串，试图用一切可能的办法， 从文法开始符号着手，自上而下地为输入 串构造一棵语法树，或者说，为输入串寻 找一个最左推导。本质上是一个试探过程， 反复使用不同地产生式谋求匹配输入串的 过程

自上而下的语法分析的一般过程 例:文法G:S→cAd AA ab a 识别输入串w=cabd是否为该文法的句子 S A 推导过程:S→ cAd cAd→cabd

9 自上而下的语法分析的一般过程 例：文法G： S → cAd A → ab A → a 识别输入串w=cabd是否为该文法的句子 S S S c A d c A d a b 推导过程：S  cAd cAd  cabd

自上而下的语法分析的一般过程 (1)s→cAd(2)A→ab(3)A→a 识别输入串w=cad是否为 该文法的句子 1S→CAd 识别输入串w=caa的过程: 1S→cAd 2后选择(2)扩展A,得到推导S→2选择(2展A,得到推导S→CAd cAd→Cabd 这时 cabd W的第二个符号可以与叶子结点3回溯回到推导S→CAd 得以匹配,但第三个符号d却不能4选择(3)扩展A,得到推导S→cAd 与下一叶子结点b匹配 Ca d 怎么办?-查看A有无另一个选择,5.A没有选择了!回溯到推导S→ 有!回溯,把A为根的子树剪掉, CAd 扫描过的输入串中的a吐出来再6再回溯S有无另一个选择?没有 试探用产生式(3)构造推导S彐 cAd→cad 宣告分析失败。 (请思考若有 (4)S→cB (5)B→a2会怎样?) 10

10 自上而下的语法分析的一般过程 (1)S → cAd (2) A → ab (3) A → a 识别输入串w=cad是否为 该文法的句子 1.S  cAd 2.后选择(2)扩展A，得到推导S  cAd  cabd 这时 w的第二个符号可以与叶子结点a 得以匹配，但第三个符号d却不能 与下一叶子结点b匹配 怎么办？-查看A有无另一个选择， 有！回溯，把A为根的子树剪掉， 扫描过的输入串中的a吐出来,再 试探用产生式（3）构造推导S  cAd  cad 识别输入串w=caa的过程： 1.S  cAd 2.选择(2)扩展A，得到推导S  cAd  cabd 3.回溯回到推导S  cAd 4.选择(3)扩展A，得到推导S  cAd  cad 5. A没有选择了！回溯到推导S  cAd 6.再回溯S有无另一个选择？没有！ 宣告分析失败。 （请思考 若有 (4) S → cB (5) B → aa 会怎样?）