Question

3.3 节展示了如何用非确定性有限自动机实现正则表达式匹配。下推自动机也有一个重要的实际应用：它们能用来解析编程语言。

在2.6 节中，我们已经看到如何使用Treetop 为一部分Simple 语言构建解析器。Treetop 解析器使用解析表达式语法来描述被解析语言的完整语法，但这是一个相当现代的思想。更传统的方式是把解析过程分成两个独立的阶段。

· 词法分析
读取一个原始字符串然后把它转换成一个单词token 序列。每一个单词token 代表程序语法的一个组成部分，例如“变量名”、“左括号”或者“while 关键字”。词法分析器使用称为词法的规则集合来决定什么样的字符应该产生什么样的单词。这个阶段处理杂乱的字符级别的细节，比如变量命名规则、注释和空格，它为下一阶段的处理准备好清楚的单词序列。

· 语法分析
读入一个单词序列并根据正在分析的语言语法判断它们是否代表一个有效的程序。如果程序有效，那么语法解析器会生成一些关于程序结构的附加信息（如一个解析树）。

4.3.1　词法分析

词法分析阶段通常相当直接。这可以通过正则表达式实现（因而也就是通过一台NFA 实现），因为它把字符序列与一些规则简单匹配以判断那些字符是否为关键字、变量名、运算符或者其他什么符号。下面是一些快速但是不整洁的Ruby 代码，可以把一个Simple 程序断成单词：

class LexicalAnalyzer < Struct.new(:string)
  GRAMMAR = [
    { token: 'i', pattern: /if/ }, # if 关键字
    { token: 'e', pattern: /else/ }, # else 关键字
    { token: 'w', pattern: /while/ }, # while 关键字
    { token: 'd', pattern: /do-nothing/ }, # do-nothing 关键字
    { token: '(', pattern: /\(/ }, # 左小括号
    { token: ')', pattern: /\)/ }, # 右小括号
    { token: '{', pattern: /\{/ }, # 左大括号
    { token: '}', pattern: /\}/ }, # 右大括号
    { token: ';', pattern: /;/ }, # 分号
    { token: '=', pattern: /=/ }, # 等号
    { token: '+', pattern: /\+/ }, # 加号
    { token: '*', pattern: /\*/ }, # 乘号
    { token: '<', pattern: /</ }, # 小于号
    { token: 'n', pattern: /[0-9]+/ }, # 数字
    { token: 'b', pattern: /true|false/ }, # 布尔值
    { token: 'v', pattern: /[a-z]+/ } # 变量名
  ]

  def analyze
    [].tap do |tokens|
      while more_tokens?
        tokens.push(next_token)
      end
  end
end

  def more_tokens?
    !string.empty?
  end

  def next_token
    rule, match = rule_matching(string)
    self.string = string_after(match)
    rule[:token]
  end

  def rule_matching(string)
  matches = GRAMMAR.map { |rule| match_at_beginning(rule[:pattern], string) }
rules_with_matches = GRAMMAR.zip(matches).reject { |rule, match| match.nil? }
    rule_with_longest_match(rules_with_matches)
  end

  def match_at_beginning(pattern, string)
    /\A#{pattern}/.match(string)
  end

  def rule_with_longest_match(rules_with_matches)
    rules_with_matches.max_by { |rule, match| match.to_s.length }
  end

  def string_after(match)
    match.post_match.lstrip
  end
end

这个实现使用单个字符作为单词——w 的意思是“while 关键字”，+ 的意思是“加号”，以此类推——因为我们准备把这些单词提供给PDA，而我们Ruby 模拟的PDA 期望以字符作为输入。

单字符的单词足以应付基本的演示需要了，这里我们不需要保留变量名或者字面值。但是在真正的解析器里，我们就需要合适的数据结构表示单词，这样它们才能在传达“某个不知名的变量”或“某个未知的布尔值”之外包含更多的信息。

通过使用Simple 代码组成的字符串创建LexicalAnalyzer 实例，然后调用它的#analyze 方法，我们可以获得一个由单词组成的数组，这个数组说明了如何把代码断成关键字、运算符、标点以及其他语法：

>> LexicalAnalyzer.new('y = x * 7').analyze
=> ["v", "=", "v", "*", "n"]
>> LexicalAnalyzer.new('while (x < 5) { x = x * 3 }').analyze
=> ["w", "(", "v", "<", "n", ")", "{", "v", "=", "v", "*", "n", "}"]
>> LexicalAnalyzer.new('if (x < 10) { y = true; x = 0 } else { do-nothing }').analyze
=> ["i", "(", "v", "<", "n", ")", "{", "v", "=", "b", ";", "v", "=", "n", "}", "e",
"{", "d", "}"]

词法分析要按照最长匹配选择规则进行，否则会造成变量名被错误地识别为关键字：

> LexicalAnalyzer.new('x = false').analyze
=> ["v", "=", "b"]
> LexicalAnalyzer.new('x = falsehood').analyze
=> ["v", "=", "v"]

解决这个问题还有其他的方法。一种就是在规则中使用限制性更强的正则表达式：如果布尔值的规则使用模式/(true|false)(?![a-z])/，那它就不会首先匹配字符串'falsehood' 了。

4.3.2　语法分析

把字符串转成单词之后，难一些的问题就是确定这些单词是否表示一个语法有效的Simple程序了。我们不能使用正则表达式或者NFA——Simple 的语法允许任意的括号嵌套，而我们已经知道有限自动机的能力不足以识别这样的语言。但是使用下推自动机是可以识别单词的有效序列的，所以下面来看看如何构造一台下推自动机。

首先，我们需要一个语法描述单词如何组合形成程序。下面是基于2.6 节中Treetop 语法结构的一部分Simple 语法：

< 语句> ::= <while> | < 赋值>
<while> ::= 'w' '(' < 表达式> ')' '{' < 语句> '}'
< 赋值> ::= 'v' '=' < 表达式>
< 表达式> ::= < 小于表达式>
< 小于表达式> ::= < 乘> '<' < 小于表达式> | < 乘>
< 乘> ::= < 名词> '*' < 乘> | < 名词>
< 名词> ::= 'n' | 'v'

这叫作上下文无关文法（Context-Free Grammar，CFG）。7 每一条规则的左边是一个符号，右边是一个或多个符号序列和单词。例如，规则< 语句>::= <while> | < 赋值> 的意思是一个Simple 语句要么是while 循环要么是一个赋值，而< 赋值> ::= 'v' '=' < 表达式> 的 意思是一个赋值语句由一个变量名后面跟上一个等号和一个表达式组成。

7文法是“上下文无关的”指它的规则没有提到文法可能出现的上下文；一个赋值语句不管周围是什么单词，它总是包含一个变量名、赋值符号和表达式。不是所有的语言都可以用这种文法描述，但几乎所有的编程语言都可以。

CFG 是一个Simple 结构的静态描述，但我们把它看成一个生成Simple 程序的规则集合。从“< 语句>”开始，我们应用文法规则递归展开符号直到只剩下单词为止。下面是根据规则完全展开“< 语句>”的方式之一：

< 语句> → < 赋值>
→ 'v' '=' < 表达式>
→ 'v' '=' < 小于表达式>
→ 'v' '=' < 乘>
→ 'v' '=' < 名词> '*' < 乘>
→ 'v' '=' 'v' '*' < 乘>
→ 'v' '=' 'v' '*' < 名词>
→ 'v' '=' 'v' '*' 'n'

这表明'v' '=' 'v' '*' 'n'在语法上有效，但我们要的是相反方向的能力：能识别有效的程序，而不是生成它们。在由词法分析得到一串单词的时候，我们想要知道是否可以按照某种顺序应用文法规则把“< 语句>”扩展成这些单词。幸好，有办法把上下文无关文法转换成能做出这种判断的非确定性下推自动机。

把一个CFG 转换成PDA 的方法如下。

1.选取一个字符表示文法中的每个符号。在这种情况下，我们使用每个符号的大写首字母——S 表示“< 语句>”，W 表示<while>，以此类推——这是为了与我们已经用来作为单词的小写字符区分开。

2.使用PDA 的栈存储表示文法符号的字符（S、W、A、E……） 和单词（w、v、=、*、……）。PDA 启动的时候，立即把一个符号推入栈中，这个符号表示它正在试图识别的结构。我们想要识别Simple 语句，所以PDA 开始时要把S 推入栈中：

>> start_rule = PDARule.new(1, nil, 2, '$', ['S', '$'])
=> #<struct PDARule ...>

把文法规则转换成无需任何输入就能扩展栈顶符号的PDA 规则。每一个文法规则描述了如何把一个符号扩展成由其他符号和单词组成的序列，而我们可以把这个描述转换成一个PDA 规则，它把一个代表特定符号的字符弹出栈并把其他字符推入栈中：

>> symbol_rules = [
  # <statement> ::= <while> | <assign>
  PDARule.new(2, nil, 2, 'S', ['W']),
  PDARule.new(2, nil, 2, 'S', ['A']),

  # <while> ::= 'w' '(' <expression> ')' '{' <statement> '}'
  PDARule.new(2, nil, 2, 'W', ['w', '(', 'E', ')', '{', 'S', '}']),

  # <assign> ::= 'v' '=' <expression>
  PDARule.new(2, nil, 2, 'A', ['v', '=', 'E']),

  # <expression> ::= <less-than>
  PDARule.new(2, nil, 2, 'E', ['L']),

  # <less-than> ::= <multiply> '<' <less-than> | <multiply>
  PDARule.new(2, nil, 2, 'L', ['M', '<', 'L']),
  PDARule.new(2, nil, 2, 'L', ['M']),

  # <multiply> ::= <term> '*' <multiply> | <term>
  PDARule.new(2, nil, 2, 'M', ['T', '*', 'M']),
  PDARule.new(2, nil, 2, 'M', ['T']),

  # <term> ::= 'n' | 'v'
  PDARule.new(2, nil, 2, 'T', ['n']),
  PDARule.new(2, nil, 2, 'T', ['v'])
  ]
=> [#<struct PDARule ...>, #<struct PDARule ...>, ...]

例如，赋值语句的规则说的是“< 赋值>”符号可以扩展成单词v、= 以及后面的“< 表达式>”符号，因此我们有一个对应的PDA 规则，它可以自发地从栈中弹出A 并推入字符v=E。“< 语句>”规则说的是我们可以把“< 语句>”符号用一个<while> 或者“< 赋值>”替换；我们已经把它转换成了一个PDA 规则，它把一个S 从栈中弹出，然后用一个W替换，而另一条规则是把S 从弹出然后推入A。

4.为每一个单词符号赋予一个PDA 规则，这个规则从输入读取字符然后把它从栈中弹出：

>> token_rules = LexicalAnalyzer::GRAMMAR.map do |rule|
    PDARule.new(2, rule[:token], 2, rule[:token], [])
  end
=> [#<struct PDARule ...>, #<struct PDARule ...>, ...]

这些单词规则与符号规则的工作方式相反。符号规则试图让栈变大，有时候会推入一些字符以替换已经弹出的；单词规则总是让栈更小，随着栈的变小处理输入。

5.最后，生成一个PDA 规则，在栈变成空时它允许机器进入接收状态：

>> stop_rule = PDARule.new(2, nil, 3, '$', ['$'])
=> #<struct PDARule ...>

现在我们可以使用这些规则构建一台PDA，输入一个由单词组成的字符串看它是否能够识别。由Simple 语法生成的规则是非确定性的（每当字符S、L、M 或者T 处于栈顶的时候，就会有多个可用的规则），因此它只能是一台NPDA。

>> rulebook = NPDARulebook.new([start_rule, stop_rule] + symbol_rules + token_rules)
=> #<struct NPDARulebook rules=[...]>
>> npda_design = NPDADesign.new(1, '$', [3], rulebook)
=> #<struct NPDADesign ...>
>> token_string = LexicalAnalyzer.new('while (x < 5) { x = x * 3 }').analyze.join
=> "w(v<n){v=v*n}"
>> npda_design.accepts?(token_string)
=> true
>> npda_design.accepts?(LexicalAnalyzer.new('while (x < 5 x = x * }').analyze.join)
=> false

为了准确地表示整个过程，下面是向这台NPDA 输入字符串'w(v<n){v=v*n}' 后的一个可能执行：

状态	是否接受	栈的内容	剩余输入	动作
1	否	$	w(v<n){v=v*n}	推入S，转移到状态2
2	否	S$	w(v<n){v=v*n}	弹出S，推入W
2	否	W$	w(v<n){v=v*n}	弹出W，推入w(E){S}
2	否	w(E){S}$	w(v<n){v=v*n}	读取w，弹出w
2	否	(E){S}$	(v<n){v=v*n}	读取(，弹出(
2	否	E){S}$	v<n){v=v*n}	弹出E，推入L
2	否	L){S}$	v<n){v=v*n}	弹出L，推入M<L
2	否	M<L){S}$	v<n){v=v*n}	弹出M，推入T
2	否	T<L){S}$	v<n){v=v*n}	弹出T，推入v
2	否	v<L){S}$	v<n){v=v*n}	读取v，弹出v
2	否	<L){S}$	<n){v=v*n}	读取<，弹出<
2	否	L){S}$	n){v=v*n}	弹出L，推入M
2	否	M){S}$	n){v=v*n}	弹出M，推入T
2	否	T){S}$	n){v=v*n}	弹出T，推入n
2	否	n){S}$	n){v=v*n}	读取n，弹出n
2	否	){S}$	){v=v*n}	读取)，弹出)
2	否	{S}$	{v=v*n}	读取{，弹出{
2	否	S}$	v=v*n}	弹出S，推入A
2	否	A}$	v=v*n}	弹出A，推入v=E
2	否	v=E}$	v=v*n}	读取v，弹出v
2	否	=E}$	=v*n}	读取=，弹出=
2	否	E}$	v*n}	弹出E，推入L
2	否	L}$	v*n}	弹出L，推入M
2	否	M}$	v*n}	弹出M，推入T*M
2	否	T*M}$	v*n}	弹出T，推入V
2	否	v*M}$	v*n}	读取v，弹出v
2	否	*M}$	*n}	读取*，弹出*
2	否	M}$	n}	弹出M，推入T
2	否	T}$	n}	弹出T，推入n
2	否	n}$	n}	读取n，弹出n
2	否	}$	}	读取}，弹出}
2	否	$		转移到3
3	是	$		—

这个执行过程的跟踪向我们展示了机器在符号和单词规则之间的摇摆：符号规则不断地扩展栈顶符号，直到此符号被一个单词取代，然后单词规则再对栈（和输入）进行处理，直到遇到一个符号为止。只要输入字符串能够由文法规则生成，这样的反复就能得到一个空栈。8

8这个算法叫作LL 分析。第一个L 代表“从左到右”，因为输入字符串是按这个方向读取的；第二个L 代表“左侧优先推导”，因为总是栈中最左边的（也就是最上面的）符号得到扩展。

在每一步执行中PDA 是怎么知道选择哪个规则的呢？这是非确定性的力量：我们模拟的NPDA 对所有可能的规则进行尝试，因此只要存在某种方式能得到空栈，我们就能找到它。

4.3.3　实践性

这个分析的过程依赖于非确定性，但在实际程序中，最好能避免非确定性，因为一个确定性的PDA 模拟起来要比非确定性的快得多而且容易得多。幸运的是，在每个阶段几乎都可以使用输入单词本身决定该应用哪个符号规则，这样就可能把非确定性去掉——这个技术叫作递推（lookahead）——但这让从CFG 到PDA 的转换更为复杂。

只能识别有效程序也不够好。就像我们在2.6 节看到的那样，解析一个程序的要领就是把程序转成一个能用来做一些有用事情的结构化表示。在实践中，我们可以让PDA 模拟记录它到达接受状态过程中的规则序列，以此来创建结构化表示，这个规则序列提供了构建一个分析树所需的足够信息。例如，上面的执行序列展示了为了形成需要的单词序列如何展开栈顶的符号，并且告诉了我们字符串'w(v<n){v=v*n}' 的解析树形状：