1.2 ANALYSIS OF THE SOURCE PROGRAM

本节介绍分析、展示在某些文本格式化语言中的应用。

在编译中，分析包括3个阶段：

1. Linear analysis: 组成源程序的字符流从左到右读进来，分组为tokens，具有联合意义的字符串序列
2. Hierarchical analysis 字符或者token被层次型组织为具有联合意义的嵌套集合
3. Semantic analysis 执行一定的检查，确保程序的组成部分能够有意义地配合在一起

Lexical Analysis

在一个编译器中，线性分析叫做lexical analysis 或者 scanning。例如，在词法分析中，赋值语句中的字符

position := initial + rate * 60

会分组为下列token

1. 标识符position
2. 赋值符号 :=
3. 标识符intial
4. 加号+
5. 标识符rate
6. 乘号*
7. 数字60
   

用来分隔这些token的字符通常在词法分析阶段就被排除了

Syntax Analysis

层次型的分析叫做parsing或者syntax analysis。把源程序的token分组为文法词组，编译器可以用来合成输出。通常源程序的文法词组用一棵解析树代表，如下图Fig 1.4


在表达式 initial + rate * 60中，词组rate * 60是一个逻辑单元，因为通常的算术表达式习惯告诉我们乘法应该在加法前计算。因为表达式initial+rate后跟一个* ，所以它们不能组成一个词组。

程序的层次型结构通常用递归规则来表达。例如，我们可以用下面的规则来定义上面的表达式

1. 任何identifier都是一个expression
2. 任何number都是一个expression
3. 如果expression1和expression2都是表达式，那么下面都是表达式
   
• expression1 + expression2
• expression1 * expression2
• ( expression1 )

规则(1)和(2) 是（非递归的）的基本规则，而(3)用对其它表达式进行的操作定义表达式。因此，通过规则(1),initial 和 rate是表达式。通过规则(2), 60是表达式，根据规则(3)，我们可以首先推理rate*60是表达式，最终initial+rate*60是一个表达式。

类似地，许多语言用规则递归定义语句如下：

1. 如果identifier1是一个标识符，而expression2是一个表达式，那么
   identifier1 := expression2
   是一个语句
2. 如果expression1是一个表达式，而statement2是一个语句，那么
   while ( expression1 ) do statement2
   if ( expression1 ) then statement2
   都是语句

词法和语法分析之间的划分有些随意。我们通常选择能够简化整体分析任务的划分方式。决定这种划分的因素因素之一是一种源语言构造是不是具有内在的递归性。词法分析不需要递归，而语法构造需要。上下文无关文法是递归规则的一种形式化，可以用来指导语法分析。

• 例如，识别标识符不需要递归，通常它们是字符串，以一个字母开始，后跟字母和数字。我们通过对输入流的简单扫描就能够识别标识符。一直等到一个既不是字母也不是数字的字符，然后把到这一点位置所有已经发现的字母和数字组合起来成为一个token。组合起来的字符记录在一个表格中，叫做symbol table，从输入中移去，然后开始处理下一个token。
• 另一方面，这种线性扫描在分析表达式或语句的时候不够强大。例如，如果我们不把输入放到某中层次型或嵌套结构中，那么我们就不能正确匹配表达式中的括号，或者匹配语句中的begin和end。

Fig 1.4的解析树parse tree描述了输入的语法结构。该语法结构一种更加通用的内部表现形式是Fig1.5(a)给出的语法树syntax tree。一棵语法树是解析树的压缩表现形式，其中操作符作为中间节点，而一个操作符的操作数成为操作符节点的子节点。构造该树的过程在5.2节讨论。


第2章和第5章详细讨论，syntax-directed translation语法导向翻译，其中编译器使用输入的层次型结构帮助生成输出

Semantic Analysis

语义分析阶段检查源程序是否有语义错误，并且为后继代码生成阶段收集类型信息。它使用语法分析阶段得到的层次型结构确定表达式和语句操作符和操作数

语义分析的一个重要组成部分是类型检查。这里编译器检查每一个操作符，看看它们的操作数类型是否为源语言规格所允许。例如，许多编程语言定义需要一个编译器每次发现把一个real作为数组下标的时候报告错误。但是语言的规格可能允许某些操作数转换，例如，当一个二元算术操作符对一个整数和一个实数操作的时候。此时，编译器可能需要把integer转换成real。

例1在一种机器内，表达一个整数的位模式bit pattern一般来说和表达一个实数的位模式是不同的，就算整数和实数的值一样也是如此。现在假设，所有Fig1.5中的标识符都声明为real，而60自己是一个integer。Fig1.5(a)的类型检查发现*应用于一个实数rate，和一个整数60。一般的做法是把integer转换成real.Fig1.5(b)插入了一个额外的节点，操作符为inttoreal，显式地把整数转换为一个实数。也可以选择两外一种做法，因为inttoreal的操作数是一个常量，编译器可以直接把整数常量替换成相等的实数常量。

Analysis in Text Formatters

可以把一个文本格式化器的输入看作指定boxes的一个层次，box都是矩形区域，被某些位模式所填充，代表浅色和深色像素，然后由输出设备打印。

例如Tex系统用这种方法显示它的输入。每一个不是命令组成部分的字符代表一个包含该字符bit pattern的box，辅以适当的字体和大小。不被“空白”分开的字符组成单词，由一系列横向放置的box组成，Fig1.6图解这一结构。组成单词（或者命令）的字符是文本格式化器分析的线性或者词法方面。

TEX中的Box可能是通过任意横向和纵向组合更小的box生成的。例如：

\hbox{ }

通过横向并列把一个box列表组合起来，而\vbox则实现类似的纵向组合。因此，如果我们在TEX中说：

\hbox{\vbox{ ! 1} \vbox{@ 2}}

那么我们就得到Fig1.7中的box排列。

决定输入所隐含的box的层次安排是TEX中的语法分析部分。

另外一个例子，用于数学的EQN预处理器，或者TEX中的数学处理器，从类似sub下标和sup上标这样的操作符来构造数学表达式。如果EQN碰到下面这种形式的输入文本

BOX sub box

那么它缩小box的大小，把它放到一个BOX的右下角，如Fig 1.8所示。sup类似，只不过是放在右上角。

这些操作符可以递归应用，例如EQN文本

a sub {i sup 2}
产生。把操作符sub和sup分组为token是EQN文本的词法分析部分，但是文本的语法结构需要判断box的大小和放置。