本节介绍一种解析方法，可以应用来构造语法导向翻译器。一个完整的C程序，实现Fig 2.13的translation scheme，出现在下一节中。一种可选的方式是使用一种软件工具直接从一个translation scheme产生一个翻译器。参见4.9描述这样一种工具。他可以不加修改实现Fig 2.13的translation scheme.
可以为任何文法构造一棵解析树。但是实际中使用的文法，有一种特殊的形式。对任何上下文无关的文法，有一个解析器取最多O(n^3)时间来解析一个n个token的字符串。但是3次方的时间太昂贵了。给定一个编程语言，我们一般能够构造一个快速解析的文法。实际中，线性算法基本上足以解析所有的语言。编程语言解析器基本上总是在输入上进行一次从左到右的扫描，每次只看一个token.
最大多数解析方法属于两种类别之一，叫做top-down自顶向下和bottom-up自底至上.这些术语指解析树的节点被构造的顺序。前者，构造从根节点开始，朝着叶节点进发，而后者，构造开始于叶节点，朝着根前进。top-down解析器的流行归功于采用top-down方法能够用手工比较简单地构造高校的解析器。但是Bottom-up解析，能够处理更多类别的文法和translation schemes，因此直接用来从文法产生解析器的软件工具趋向于采用bottom-up方法。
Top-Down Parsing
我们用适合这种方法的一种文法介绍top-down解析。本节后面，我们讨论一般性的top-down解析器构造。下面的文法生成Pascal的一个子集。我们使用dotdot代表".."，重点突出字符序列当作一个单元。
type → simple
| ↑id
| array [simple] of type
simple →integer
| char
| num dotdot num
一棵解析树的top-down构造，从root开始，标以开始非终结符，然后重复下面的两步(Fig 2.15为例).
- 在节点n，标以非终结符A，选择A的其中一个产生式，用产生式右边的符号构造n的子节点
- 寻找将被构造子树的下一个节点
对某些文法而言，上面各步可以在对输入字符串进行一次从左到右的扫描即可实现。输入中当前被扫描的token经常被引用为lookahead符号。开始，lookahead 符号是第一个，也就是最左边，输入字符串的token。Figure 2.16演示了解析下面字符串的过程：
array [ num dotdot num] of integer
最初，array这个token是lookahead symbol, 解析树的已知部分由root组成，标签是Fig. 1.16(a)的开始非终结符type。目标是构造解析树的剩余部分，以便让这个解析树生成的字符串和输入字符串匹配。
当一个匹配发生的时候，Fig. 2.16(a)的非终结符type必须派生一个字符串，从lookahead symbol array开始。在文法(2.8)中，只有一个type的产生式可以派生这样的字符串，我们选择它，用它右边构造root的子节点。
Fig2.16三个快照的每一个都有一个箭头标记输入字符串中的lookahead symbol，以及当前被考虑的解析树中的节点。当某一个节点的子节点被构造时，我们接下去考虑最左边的子。在Fig2.16(b)中，root的子刚刚被构造出来，最左边的子array正被考虑。
当解析树中被考虑的节点是一个终结符，并且终结符匹配lookahead symbol的时候，我们同时前进解析树和输入。输入中的下一个token变成新的lookahead symbol，解析树的下一个子节点被考虑。在Fig. 2.16(c)中，解析树的箭头前进到root的下一个子节点，输入中的箭头也前进到下一个token [。在下一次前进以后，解析树中的箭头将指向非终结符simple这个子节点。当一个非终结符的节点被考虑时，我们将重复为非终结符选择一个产生式的过程。
一般来说，非终结符产生式的选择可能回引起trail-and-error;也就是，我们可能必须尝试一个产生式，如果发现不合适的时候回退并尝试另外一个产生式。如果使用了一个产生式，我们不能完成匹配输入字符串的一棵树，那么这个产生式是不合适的。但是，这里有一种重要的特殊情况，叫做predictive parsing，不会发生回退。
Predictive Parsing
Recursive-descent parsing递归下降解析是一种top-down的语法分析方法，其中我们执行一系列递归过程去处理输入。一个过程和文法的每一个非终结符关联。这里我们考虑递归下降解析的一种特殊情况，叫做predictive parsing，其中lookahead symbol无二义性地确定了每一个非终结符选择的过程。处理输入时过程的被调用序列隐式地定义了输入的一棵解析树。
procedure match(t:token);
begin
if lookahead = t then
lookahead := nexttoken
else error
end;
procedure type
begin
if lookahead is in {integer, char, num} then
simple
else if lookahead = '↑' then begin
match('↑');match(id)
end
else if lookahead = array then begin
match(array);match('[');simple;match(']');match(of);type
end
else error
end;
procedure simple
begin
if lookahead = integer then
match(integer)
else if lookahead = char then
match(char)
else if lookahead = num then begin
match(num);match(dotdot);match(num);
end
else error
end;
Fig. 2.17. Pseudo-code for a predictive parser
Fig. 2.17的predictive解析器由文法(2.8)中的非终结符type和simple对应的过程组成，另外还有一个附加的过程match.我们使用match来简化type和simple的代码。它前进到下一个输入token，如果它的参数t匹配lookahead symbol。于是match改变变量lookahead，它是当前被扫描的输入token.
解析从我们文法中的开始非终结符type对应的过程开始。和Fig. 2.16一样的输入，lookahead开始是第一个token array。过程type 执行代码
match(array);match('[');simple;match(']');match(of);type对应产生式的右边
type → array [simple] of type
注意右边的每一个终结符被lookahead symbol匹配，而每一个非终结符导致对它相应过程的调用。
使用Fig. 2.16的输入，在array后面，[被匹配之后，lookahead符号是num。在这一点过程simple被调用，执行代码：
match(num);match(dotdot);match(num);
lookahead符号引导对产生式的选择。如果产生式的右边开始于一个token，那么在lookahead symbol匹配这个token的时候，这个产生式就能够使用。现在考虑一个右边开始于一个非终结符，例如：
type → simple (2.10)
这个产生式在lookahead symbol 能够从simple生成出来的时候使用。例如，在执行代码片断(2.9)的过程中，假设lookahead symbol是integer，当控制到达过程调用type的时候。没有任何type的产生式开始于token integer。但是，simple的一个产生式确实开始于integer，因此产生式(2.10)被使用，在lookahead是integer的时候，type调用simple过程。
Predictive parsing依赖于一个信息，就是一个产生式的右边能够产生什么样的第一个symbol。更加精确地说，让α非终结符A的右边。我们定义FIRST(α)为由α生成的字符串中，可能出现为第一个symbol的token集合。如果α是ε，或者能够生成ε,那么ε也在FIRST(α)之内。例如：
FIRST(simple) = {integer, char, num}
FIRST(↑id) = {↑}
FIRST(array [ simple ] of type) = {array}
实践中，很多产生式右边以token开始，从而简化了FIRST集合的构造。计算FIRST的一个算法在4.4中。
如果有两个产生式A →α和A →β,那么必须考虑FIRST集合。没有回退的递归下降解析需要FIRST(α)和FIRST(β)是分离的。这样lookahead符号能够用来决定使用哪一个产生式。如果lookahead符号在FIRST(α)中，那么采用α。不然，如果lookahead 符号在FIRST(β)中，那么使用β。
When to Use ε-Productions
右边带有 ε的产生式需要特别的对待。递归下降解析器将使用ε-Production作为缺省，如果没有其他的产生式可用。例如，考虑
stmt → begin opt_stmts end
opt_stmts → stmt_list | ε
在解析opt_stmts的时候，如果lookahead符号不在FIRST(stmt_list)中，那么将使用ε-Production。这个选择非常正确,如果lookahead符号是end.任何不是end的lookahead符号将导致错误，在解析stmt的过程中。
Designing a Predictive Parser
一个predictive parser 是一个程序，其中每一个非终结符都有一个过程。每一个过程做两件事情：
- 它通过察看lookahead符号决定采用哪个产生式。如果产生式的右边为α，lookahead符号在FIRST(α)，那么将采用这个产生式。如果对任何lookahead 符号，两个右边存在着一个冲突，那么我们就不能在这种文法上使用这种解析方法。一个右边具有ε的产生式将被使用，如果lookahead符号不再任何其它右边的FIRST集合中。
- 过程通过模拟右边使用一个产生式。一个非终结符导致对应过程的调用，一个匹配lookahead符号的token导致下一个token被读入。如果在某些点，产生式中的token和lookahead符号不匹配，那么就会报告错误。Fig 2.17是把这些规则应用到文法2.8的结果。
- 构造一个predictive parser, 忽略产生式中的动作。
- 把translation scheme中的动作复制到解析器。如果动作出现在产生式p中的文法符号X之后，那么他就被复制到实现X的代码之后。如果它出现在产生式的开始，那么他就被复制到实现该产生式的代码之前。
我们将在下一节构造这样一个翻译器。
Left Recursion
一个递归下降解析器可能无穷循环。例如
expr → expr + term
其中右边最左边的符号和产生式左边的非终结符一样。假设expr的过程决定应用此产生式。右边以expr开始，因此对expr将被递归调用。于是解析器就陷入了无穷循环。注意,lookahead符号仅在右边的一个终结符被匹配的时候才会发生变化。因此产生式以非终结符expr开始，那么就不会对输入发生任何改变，导致无穷循环。
一个左递归产生式可以通过重写产生式排除。考虑一个非终结符A具有两个产生式：
A → Aα | β
其中α和β是不以A开始的终结符和非终结符。例如，表达式：
expr → expr + term | term
中，A = expr, α = + term, β = term.
非终结符A是left recursive左递归的，因为产生式A → Aα的右边还是以A开始。重复此产生式在A的右边构造起一序列的α，例如图2.18(a)。当A最终被β替换的时候，我们有一个β后面跟着一系列的0或者多个α.
相同的效果，可以通过Fig 2.18(1)实现，通过用下面的方式重写A的产生式：
A → βR
R → αR | ε (2.11)
这里R是一个新的非终结符。
产生式R → αR 是右递归的，因为R的产生式右边，R是最后一个符号。右递归的产生式导致树朝右下方增长，如Fig. 2.18(b)所示。朝右下方增长的数使得它难以翻译包含左结合操作符的表达式，例如减。但是，在下一节中，我们可以看到表达式正确翻译成后缀记法，如果在一个右递归文法上仔细定义translation scheme。
在第4章中，我们会讨论左递归更加通用的形式，显示可以从一种文法中排除所有的左递归。
没有评论:
发表评论