清华大学：《编译原理》课程教学资源_第五章 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 语法分析 在语言的编译实现中，把句子分析的过程称 为语法分析，即完成这个任务的程序称为 语法分析程序或称为识别程序。分析算法 又称识别算法。 从左到右的分析算法，即总是从左到右地识 别输入符号串，首先识别符号串中的最左 符号，进而依次识别右边的一个符号，直 到分析结束