PPT《编译原理》

编译原理

第一章 编译程序概述

第二章 PL/0编译程序的实现

第三章 文法和语言

第四章 词法分析

第五章 自顶向下语法分析方法

第六章 自底向上优先分析方法

第七章 LR分析方法

第八章 语法制导翻译和中间代码生成

第九章 符号表

第一章 代码优化第一一章 代码生成 第5章 自顶向下语法分析方法 语法分析是编译程序的核心部分:在词法分析的基础上,识别单词符号序列是否是给定文法的正确句子(程序).

常用方法 自顶向下分析 自底向上分析 确定不确定 算符优先分析 LR分析 自顶向下语法分析方法 自顶向下分析法就是从文法的开始符号出发,试图推导出与输入的单词串完全匹配的句子.如果能够推导出,则该输入串是给定文法的句子;

如果不能推导出,则该输入串不是给定文法的句子. 自顶向下语法分析要解决的关键问题 假定要被代换的最左非终结符号是B,且有n条规则:B→A1|A2|…|An,那么如何确定用哪个右部去替代B? 自顶向下语法分析方法 自顶向下分析法分确定性和不确定性两种.自顶向下的确定性分析法对文法有一定的限制,但实现简单直观,便于手工或自动构造;

自顶向下的不确定性分析法是带有回溯的分析方法,效率低,代价高,极少使用. 第5章 自顶向下语法分析方法

一、确定的自顶向下分析思想

二、LL(1)文法的判别

三、某些非LL(1)文法到LL(1)文法等价变换

四、不确定的自顶向下分析思想

五、确定的自顶向下分析方法 自顶向下语法分析要解决的关键问题 假定要被代换的最左非终结符号是B,且有n条规则:B→A1|A2|…|An,那么如何确定用哪个右部去替代B?

一、确定的自顶向下分析思想

1、方法:从开始符号出发,不断替换非终结符,根据当前的单词符号就可以唯一选定要替换的产生式. 例1:文法G(S):S→pA S→qB A→cAd A→a输入串 W=pccadd 自顶向下的推导过程为: S P A S P A ? c d A ? c d A S P A c d A ? c d A S P A c d A a 相应的语法树: S?pA ? pcAd ? pccAdd ? pccadd 例1:文法G(S):S→pA S→qB A→cAd A→a该文法的特点:(1)每个产生式的右部都由终结符号开始;

(2 )如果两个产生式有相同的左部,则它们的右部由不同的终结符开始.对于这样的文法,其推导过程可以根据当前的输入符号决定选择哪个产生式往下推导,因此,分析过程是唯一确定的. 例2:文法G(S)为: S →Ap S → Bq A →aOcA B→bOdB 该文法的特点:(1)产生式的右部不全是由终结符号开始;

(2 )如果两个产生式有相同的左部,则它们的右部由不同的终结符或非终结符开始.(3)无空产生式.ccap如何根据输入串的第1个符号来确定产生式呢? 例2:文法G(S)为: S →Ap S → Bq A →aOcA B→bOdB 当输入W=ccap推导:自顶向下的推导过程为: 例2:文法G(S)为: S →Ap S → Bq A →aOcA B→bOdB 当输入W=ccap推导:自顶向下的推导过程为: S ?Ap ?cAp ?ccAp ?ccap语法树为: S A P ? S A P c A ? S A P c A c A ? S A P c A c A a 例2:文法G(S)为: S →Ap S → Bq A →aOcA B→bOdB 该文法的特点:(1)产生式的右部不全是由终结符号开始;

(2 )如果两个产生式有相同的左部,则它们的右部由不同的终结符或非终结符开始.(3)无空产生式.ccap如何根据输入串的第1个符号来确定产生式呢?

2、开始符号集合的定义: 设G=(VT,VN, P ,S )是上下文无关文法,开始符号集合为First(?)={ a | ? ?aβ,a∈VT, ? 、β∈V*} 规则右部?的开始符号集包括所有终结符 a,使得规则右部?经过若干推导后得到的字符串以a为起始. 若? ?ε,则规定?∈First(?) . * * 例3:上例中文法是: S?Ap|Bq A ? a | cA B ? b | dB则:FIRST(Ap)=?;