6 编译原理及实线 China-pub.C 下载 语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析 (syntax analysis),这与自然语中句子的语法分析类以。语法分析定义了程序的结构元素及 其关系。通常将语法分析的结果表示为分析树(parse tree)或语法树(syntax tree)。 例如，还是那行C代码，它表示一个称为表达式的结构元素，该表达式是一个由左边为 下标表达式、右边为整型表达式的赋值表达式组成。这个结构可按下面的形式表示为一个分 析树： expression sign-expression subscript-expression 请注意，分析树的内部节点均由其表示的结构名标示出，而分析树的叶子则表示输入中的 记号序列（结构名以不同字体表示以示与记号的区别）。 分析树对于显示程序的语法或程序元素很有帮助，但是对干表示该结构却显得力不从心了 分析程序更趋向于生成语法树，语法树是分析树中所含信息的浓缩（有时因为语法树表示从分 析树中的进一步抽取，所以也被称为抽象的语法树(abstract syntax tree)。下面是一个C赋值 语句的抽象语法树的例子： assign-expression subscripi-expression 请注意，在语法树中，许多节点（包括记号节点在内）已经消失。例如，如果知道表达式 是一个下标运算，则不再需要用括号“【”和“1”来表示该操作是在原始输入中。 (③)语义分析程序(semantic analyzer) 程序的语义就是它的“意思”，它与语法或结构不同。程序的语义确定程序的运行，但是 大多数的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。 这些特征被称作静态语义(static semantic),而语义分析程序的任务就是分析这样的语义（程 序的“动态”语义具有只有在程序执行时才能确定的特性，由于编译器不能执行程序，所以它 不能由编译器来确定)。一般的程序设计语言的典型静态语义包括声明和类型检查。由语义分 析程序计算的额外信息（诸如数据类型）被称为属性(attribute),它们通常是作为注释或“装 饰”增加到树中（还可将属性添加到符号表中）。 在正运行的C表达式
语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析 （syntax analysis），这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及 其关系。通常将语法分析的结果表示为分析树（ parse tree）或语法树（syntax tree）。 例如，还是那行 C代码，它表示一个称为表达式的结构元素，该表达式是一个由左边为 下标表达式、右边为整型表达式的赋值表达式组成。这个结构可按下面的形式表示为一个分 析树： 请注意，分析树的内部节点均由其表示的结构名标示出，而分析树的叶子则表示输入中的 记号序列（结构名以不同字体表示以示与记号的区别）。 分析树对于显示程序的语法或程序元素很有帮助，但是对于表示该结构却显得力不从心了。 分析程序更趋向于生成语法树，语法树是分析树中所含信息的浓缩（有时因为语法树表示从分 析树中的进一步抽取，所以也被称为抽象的语法树（ abstract syntax tree））。下面是一个C赋值 语句的抽象语法树的例子： 请注意，在语法树中，许多节点（包括记号节点在内）已经消失。例如，如果知道表达式 是一个下标运算，则不再需要用括号“[”和“]”来表示该操作是在原始输入中。 (3) 语义分析程序（semantic analyzer） 程序的语义就是它的“意思”，它与语法或结构不同。程序的语义确定程序的运行，但是 大多数的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。 这些特征被称作静态语义（ static semantic），而语义分析程序的任务就是分析这样的语义（程 序的“动态”语义具有只有在程序执行时才能确定的特性，由于编译器不能执行程序，所以它 不能由编译器来确定）。一般的程序设计语言的典型静态语义包括声明和类型检查。由语义分 析程序计算的额外信息（诸如数据类型）被称为属性（ a t t r i b u t e），它们通常是作为注释或“装 饰”增加到树中（还可将属性添加到符号表中）。 在正运行的C表达式 6 编译原理及实践 下载
China-pub.com 下载 第1京樱论7 a【index】=4+2 中，该行分析之前收集的典型类型信息可能是：a是一个整型值的数组，它带有来自整型子范 围的下标：1ndx则是一个整型变量。接着，语义分析程序将用所有的子表达式类型来标注语 法树，并检查赋值是否使这些类型有意义了，如若没有，则声明一个类型匹配错误。在上例中， 所有的类型均有意义，有关语法树的语义分析结果可用以下注释了的树来表示： assign-statement additive. identifier identifier number array of intege index intege intege intege (4)源代码优化程序(source code optimizer) 编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完 成的，而此时代码改进可能只依赖于源代码。这种可能性是通过将这一操作提供为编译过程中 的单独阶段指出的。每个编译器不论在已完成的优化种类方面还是在优化阶段的定位中都有很 大的差异。 在上例中，我们包括了一个源代码层次的优化机会，也就是：表达式4+2可由编译器计算 先得到结果6（这种优化称为常量合并(onstant foin)。当然，还会有更复杂的情况（有 些将在第8章中提到)。还是在上例中，通过将根节点右面的子树合并为它的常量值，这个优化 就可以直接在（注释）语法树上完成： assign-statement bnegnan integer idontifier identifior aray of integer 尽管许多优化可以直接在树上完成，但是在很多情况下，优化接近于汇编代码线性化形式 的树更为简便。这样节点的变形有许多，但是三元式代码(three-address code)(之所以这样称 呼是因为它在存储器中包含了3个（或3个以上）位置的地址)却是标准选择。另一个常见的选 择是P.代码(P-code),它常用于Pascal编译器中。 在前面的例子中，原先的C表达式的三元式代码应是： t=4+2 a【index】=t (请注意，这里利用了一个额外的临时变量t存放加法的中间值)。这样，优化程序就将这个代 码改进为两步。首先计算加法的结果： t=6 a【1ndex】=t
a [index] = 4 + 2 中，该行分析之前收集的典型类型信息可能是： a是一个整型值的数组，它带有来自整型子范 围的下标；i n d e x则是一个整型变量。接着，语义分析程序将用所有的子表达式类型来标注语 法树，并检查赋值是否使这些类型有意义了，如若没有，则声明一个类型匹配错误。在上例中， 所有的类型均有意义，有关语法树的语义分析结果可用以下注释了的树来表示： (4) 源代码优化程序（s o u rce code optimizer） 编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完 成的，而此时代码改进可能只依赖于源代码。这种可能性是通过将这一操作提供为编译过程中 的单独阶段指出的。每个编译器不论在已完成的优化种类方面还是在优化阶段的定位中都有很 大的差异。 在上例中，我们包括了一个源代码层次的优化机会，也就是：表达式 4 + 2可由编译器计算 先得到结果6（这种优化称为常量合并（ constant folding））。当然，还会有更复杂的情况（有 些将在第8章中提到）。还是在上例中，通过将根节点右面的子树合并为它的常量值，这个优化 就可以直接在（注释）语法树上完成： 尽管许多优化可以直接在树上完成，但是在很多情况下，优化接近于汇编代码线性化形式 的树更为简便。这样节点的变形有许多，但是三元式代码（ three-address code）（之所以这样称 呼是因为它在存储器中包含了3个（或3个以上）位置的地址）却是标准选择。另一个常见的选 择是P -代码（P - c o d e），它常用于P a s c a l编译器中。 在前面的例子中，原先的C表达式的三元式代码应是： t = 4 + 2 a [ index] = t （请注意，这里利用了一个额外的临时变量 t 存放加法的中间值）。这样，优化程序就将这个代 码改进为两步。首先计算加法的结果： t = 6 a [index] = t 第 1章 概 论 7 下载