China-pub.Com 第4章自顶向下的分析 113 下载 4.2LL(1)分析 4.2.1LL(1)分析的基本方法 LL()分析使用显式栈而不是递归调用来完成分析。以标准方式表示这个栈非常有用，这 样LL()分析程序的动作就可以快捷地显现出来。在这个介绍性的讨论中，我们使用了生成成 对括号的串的简单文法： S-(S)SE (参见第3章的例3.5)。 假设有这个文法和串()，则表4-1给出了自顶向下的分析程序的动作。此表共有4列。第1 列为便于以后参考给每个步骤标上了号码。第2列显示了分析栈的内容，栈的底部向左，栈的 顶部向右。栈的底部标注了一个美元符号，这样一个在顶部包含了非终结符S的栈就是： SS 且将额外的栈项推向右边。表的第3列显示了输入。输入符号由左列向右。美元符号标出了输 入的结束（它与由扫描程序生成的EOF记号相对应）。表的第4列给出了由分析程序执行的动作 的简短描述，它将改变栈和（有可能）输入，如在表的下一行中所示一样。 表41自顶向下的分析程序的分析动作 分析栈 输入 动作 1$S ()s S-(S)5 2SS)St ()s 匹配 3$S)s S s 匹配 55 S- 65 接受 自顶向下的分析程序是从将开始符号放在栈中开始的。在一系列动作之后，它接受一个输 入串，此时栈和输入都空了。因此，成功的自顶向下的分析的一般示意法应是： StartSymbol InputString accept 在上面的例子中，开始符号是S,输入串是)。 自顶向下的分析程序通过将栈顶部的非终结符替换成文法规则中(BNF中)该非终结符的 一个选择来作出分析。其方法是在分析栈的项部生成当前输入记号，在项部它己匹配了输入记 号并将它从找和输入中舍弃掉。这两个动作 1)利用文法选择A→α将栈顶部的非终结符A替换成串α。 2)将栈顶部的记号与下一个输入记号匹配。 是自顶向下的分析程序中的两个基本动作。第1个动作称为生成(generate):通过写出在替换 中使用的BNF选择（它的左边在当前必须是栈顶部的非终结符）来指出这个动作。第2个动作 将栈顶部的一个记号与输入中的下一个记号匹配（并通过取出栈和将输入向前推进而将二者全 4.2 LL(1)分析 4.2.1 LL(1)分析的基本方法 L L ( 1 )分析使用显式栈而不是递归调用来完成分析。以标准方式表示这个栈非常有用，这 样L L ( 1 )分析程序的动作就可以快捷地显现出来。在这个介绍性的讨论中，我们使用了生成成 对括号的串的简单文法： S→(S) S | （参见第3章的例3 . 5 )。 假设有这个文法和串 ( )，则表4 - 1给出了自顶向下的分析程序的动作。此表共有 4列。第1 列为便于以后参考给每个步骤标上了号码。第 2列显示了分析栈的内容，栈的底部向左，栈的 顶部向右。栈的底部标注了一个美元符号，这样一个在顶部包含了非终结符 S的栈就是： $ S 且将额外的栈项推向右边。表的第 3列显示了输入。输入符号由左列向右。美元符号标出了输 入的结束（它与由扫描程序生成的 E O F记号相对应）。表的第4列给出了由分析程序执行的动作 的简短描述，它将改变栈和（有可能）输入，如在表的下一行中所示一样。 表4-1 自顶向下的分析程序的分析动作 分 析 栈 输 入 动 作 1 $ S ( ) $ S → ( S ) S 2 $ S ) S ( ( ) $ 匹配 3 $ S ) S ) $ S → 4 $ S ) ) $ 匹配 5 $ S $ S → 6 $ $ 接受 自顶向下的分析程序是从将开始符号放在栈中开始的。在一系列动作之后，它接受一个输 入串，此时栈和输入都空了。因此，成功的自顶向下的分析的一般示意法应是： $ S t a rt S y m b o l InputString $ . . . . . . . . . . . . $ $ accept 在上面的例子中，开始符号是S，输入串是( )。 自顶向下的分析程序通过将栈顶部的非终结符替换成文法规则中（ B N F中）该非终结符的 一个选择来作出分析。其方法是在分析栈的顶部生成当前输入记号，在顶部它已匹配了输入记 号并将它从栈和输入中舍弃掉。这两个动作 1) 利用文法选择A→a将栈顶部的非终结符A替换成串a。 2) 将栈顶部的记号与下一个输入记号匹配。 是自顶向下的分析程序中的两个基本动作。第 1个动作称为生成（g e n e r a t e）：通过写出在替换 中使用的B N F选择（它的左边在当前必须是栈顶部的非终结符）来指出这个动作。第 2个动作 将栈顶部的一个记号与输入中的下一个记号匹配（并通过取出栈和将输入向前推进而将二者全 第 4章 自顶向下的分析 1 1 3 下载