编译原理实用教程 -杨德芳 第4章 自顶向下的语法分析技术.pptVIP

第4章 自顶向下的语法分析技术 本章学习目标 语法分析是继词法分析之后，编译过程的第二个阶段。它的主要任务是对词法分析的输出结果—单词序列进行分析，识别出合适的语法单位。语法分析分为自顶向下和自底向上的两类方法。自顶向下的语法分析又分为确定的自顶向下分析（无回溯）和不确定的（带回溯的）的自顶向下语法分析两种。本章主要内容有： 。 自顶向下的语法分析的基本思想。 LL(1)语法分析方法。 确定的自顶向下分析技术，包括递归子程序法和预测分析技术 4.1确定的自顶向下分析方法 自顶向下分析就是从文法的开始符号出发并寻找出这样一个推导序列：推导出的句子恰好是输入符号串；或者说，能否从根结点出发向下生长出一棵语法树，其叶结点组成的句子恰好为输入符号串。显然，语法树的每一步生长（每一步推导）都以能否与输入符号串匹配为准。 如果最终句子得到识别，则证明输入符号串为该文法的一个句子；否则，输入符号串不是该文法的句子。自顶向下分析分为确定的自顶向下分析和不确定的自顶向下分析法两种。 具体分析方法归纳如下： （1）自顶向下建树，试图生成一个和所给符号串（输入符号串）相一致的终结符号串。 （2）在建树过程中，按照一定的规律选择生成规则，展开为向下生长的树。每一步都试图将生成的尚未消除的最左叶片与输入符号匹配。 （3）匹配失败后，必须退回到出错点，选择其他可能的规则，直到生长出与读入符号串完全一致的树型结构，这种方法称为回溯。 （4）如果按上述方法构造成功，说明读入的符号串是文法的一个句子；反之，如果穷尽所有的途径都没有办法成功，则说明读入的符号串不是文法的一个句子。 4.1.1确定的自顶向下分析思想 确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号（单词符号）惟一地确定选用哪个产生式替换非终结符往下推导，或者构造一棵相应的语法树。 例题4.1设有文法G[S] ： S?pA | qB A?cAd |a B?dB |b 若输入串W=pccadd。自顶向下的推导过程为：S?pA?pcAd?pccAdd ?pccadd 确定的自顶向下分析的语法树如图4-1所示。 例4.2 设有文法G[S] 为： S?Ap | Bq A?a |cA B?b |dB 当输入串W=ccap时，那么试图推出输入串的推导过程为：S?Ap?cAp?ccAp?ccap，构造出确定的自顶向下分析的语法树如图4-2所示。 该文法的产生式的右部不全是终结符开始，也有非终结符A和B。在推导过程中选用哪个产生式就不直观。比如在第一步推导中，是选择以A开始还是以B开始的产生式，我们必须向下再找一步，看看A和B的产生式哪个是有c开始。先看A，A的产生式规则是有a和c开始，而B的产生式规则是有b 和d 开始，很显然是用以A开始的产生式规则。 所以就产生了推导：S?Ap，此时，A有两个产生式规则，很容易判断出用哪个。通过此例子，能看出在语法推导过程中，有一点很重要，那就是文法中产生式规则的开始符号。下面就产生式规则的首符号集进行定义。 定义4.1 设G=(VN, VT,S,P)是上下文无关文法 FIRST( ? )={a|?a?,a? VT , ?,? ? V* } 如果??，则规定?? FIRST( ? ),，FIRST( ? )为?的开始符号集或首符号集。 定义4.1 设G=(VN, VT,S,P)是上下文无关文法 FIRST( ? )={a|?a?,a? VT , ?,? ? V* } 如果??，则规定?? FIRST( ? ),，FIRST( ? )为?的开始符号集或首符号集。 例如，FIRST(Ap)={a,c} FIRST(Bq)={b,d} 这样，在推导时，只要这两个产生式右部的首符号集没有交集，就可以惟一的选择产生式的规则。 例4.3 若有文法G[S]： S?aA | d A?bAS| ? 若输入串W=abd，则试图推导出abd 串的推导过程为：S? aA ? abAS ? abS? abd 该输入串确定的语法树如下图4-3所示。 定义4.2 设G=（VT,VN,S,P）是上下文无关文法，A? VN ，S是开始符号 FOLLOW（A）={a| S?A?，且a? VT，a?FIRST(?)，?? VT*，??V+} 若S=?A?，且 ?=*?，且#? FOLLOW(A)。 也可以定义为FOLLOW（A）={a|S…Aa…，a? VT} 若有S=…A，则规定#?FOLLOW（A） 一般来讲，我们用“#”作为输入串的结束符，或称为句子的括号，如#输入串#。 4.1.2 LL(1)文法的定义 根据上面的分析我们重新定义一个产生式被选择时的集合SELECT如下。 定义4.3 给定上下文无关文法的产生式A??，A?VN，??V*，