递归下降法——处理复杂输入

这篇文章对oolens的推文《OO加油站——递归下降》进行总结。

文法

文法（Grammar）是对语言结构的定义与描述，通过形式化的表述来规定语言结构的规则。

简单来说，文法是语言的规则。

词法

词法（Lex）是指语言中的词汇及其属性和含义的规则，它规定了一个语言中的“词”是如何构成的。

假设有一个语法单元“变量名”，定义其为由大于0个小写字母组成的字符串，也可以表示成这样：

其中：

1. 尖括号内表示一个语法成分；
2. 右箭头表示左侧的部分由右侧的部分组成；
3. 竖线表示右边的规则可以选取竖线两侧的任一种情况。

这样，我们就可以得到变量名的构成规则。换言之，所定义的变量名仅限于一个字母或一个字母后接另一个变量名。

Example

“buaa”是变量名；“buaa_cs”不是变量名，因为它出现了不属于letter中的下划线“_”。

语法

语法（Syntax）是指描述语言中句子结构和组织方式的规则。它规定了一个语言中的”句”是如何构成的。比如说：

在这里，句子是一个主语加上一个谓语连在一起构成的。其中主语可能是i也可能是you；谓语可能是smile，可能是laugh。

文法分析

已知一个字符串，如何判断它是不是我们上面定义的变量名？如何判断它是不是我们定义的句子？

词法分析

可以首先判断一下字符串的长度是否为0 。然后对所有字符依次检查它是否是字母。这是比较基础的应用。

那么考虑下一个问题：

已知有多种词A、B、C、D和他们的构成规则（假设规则间不存在矛盾或重复），给定一个字符串，如果保证字符串完全由这些词组成，依次输出字符串里面的词及其所属的类别。

这个问题不仅涉及到字符串的判断，也同时涉及到字符串的划分。

举一个最简单的例子ismileyoulaughsmile。每一个词的开头都是不重复的。因此可以依次读取所有字母，然后依据该字母是什么而判断读到的是什么单词。

for(int i=0;i<str.size();i++){
  if(str.charAt(i)=='i'){
    System.out.println("i - 主语");
  }
  else if(str.charAt(i)=='y'){
    i=i+2;
    System.out.println("you - 主语");
  }
  else if(str.charAt(i)=='s'){
    i=i+4;
    System.out.println("smile - 谓语");
  }
  else{
    i=i+4;
    System.out.println("laugh - 谓语");
  }
}

Token

在计算机领域，token常常用来表示文本的最小语法单位。这里可以以token来存储字符串经过词法分析得到的一个个单元。

不妨假设我们用一个list来存储分析得到的token，那么每识别出一个token，就可以向这个列表中加上它。这样，经过一遍扫描，我们就可以将一个字符串的信息整合转化成一个token的列表。

for(int i=0;i<str.size();i++){
  if(str.charAt(i)=='i'){
    tokenList.add(new Token("i","主语"));
  }
  else if(str.charAt(i)=='y'){
    i=i+2;
    tokenList.add(new Token("you","主语"));
  }
  else if(str.charAt(i)=='s'){
    i=i+4;
    tokenList.add(new Token("smile","谓语"));
  }
  else{
    i=i+4;
    tokenList.add(new Token("laugh","谓语"));
  }
}

语法分析

现已经将字符串转化为一个一个token了，从现在开始，语法分析的对象从初始的字符串可以转化为这个 “token” 列表。

从代码设计的角度上来看，通过将字符串经过词法分析转化为 “token” 列表，词法分析这一道工序将半成品tokenList传入到下一道工序：语法分析，而不是直接在语法分析阶段调用词法的解析，能够很好的减少这两个不同级别处理之间的耦合。

为了说明如何进行语法分析，这里引入一个稍显复杂的规则：

在这个结构中，表达式 = 项 + 项 + …… + 项，项 = 因子 * 因子 * …… * 因子；因子用一个字母i表示且不可再分。

最外层是表达式，表达式可以被看作是几个项的和，项可以被看作是几个因子的乘积，这样，一个表达式的结构很明显的分成了三层，此时进行词法分析是个很简单的过程，我们只需要对i，*，+分别识别即可。

在思考如何做语法分析的问题前，不妨考虑一下，什么样的结构能够最好的表达各个语法结构之间的关系呢？

回答这个问题，不妨先回头看看前面已经建立的对该规则的认识：表达式的“三层”，用图像来表示的话应当是下面的样子。

语法分析的目的，就是生成一个这样的树，它用节点之间的联系来表达原本表达式的语法结构。这种树一般被称为语法树（Syntax Tree）或抽象语法树（Abstract Syntax Tree，AST）。

可以构建语法树的几个节点类，其中表达式用Expr表示，项用Term表示，因子用Factor表示：

public class Expr{
  private ArrayList<Term>terms;
}

public class Term{
  private ArrayList<Factor>factors;
}

public class Factor{
}

语法分析就是建立由这几个类构成的节点的语法树的过程。

自顶向下建树

对字符串进行分析时，默认这个字符串代表一个表达式。因此，无论这个字符串的内容是什么，它转化成的语法树的树根都是表达式。

做法步骤如下：

1. 对表达式按照规则进行拆分；
2. 识别出构成表达式的一个一个项；
3. 对项按照规则进行拆分；
4. 识别出构成项的一个一个因子；
5. 构建一颗自顶向下的逻辑树。

下降

对于规则

可以对其进行一定的变化，假设将其翻译为

那么，对于这一条翻译过的规则，它的视角从表达式层到了顶层。也就是说，每一条语法规则，事实上都说明了一个语法单元作为树节点时，它的子节点是如何构成的。而分析这个构成的过程，我们就在语法树上下降了一层。

从全局到局部

如果从全局的视角来看，综合考虑所有的规则，就会得到上面图中的语法树。它的大小，宽度和深度随着规则的扩张而不断增加，规则条数越多，树越复杂，我们要从全局的视角来处理也就越困难，可以想象一下添加若干将因子再拆成更低层的组成部分的情况：

那么从全局来看，我们的语法树将会变得十分的庞大和复杂，解析它的程序也会变得复杂起来。

但是实际上，一个节点有关的语法结构，是不随其所在的位置变化的：某个Term无论是Expr的第几个Term，它的构成规则也不会改变，都是由若干个因子和若干个”*”按次序排布构成。这个局部的性质，不随其在全局的位置和周围的状态改变。所以，不妨把全局的视角，”短视地”移动到局部：

那么就能从语法树中提取出这样的的一个结构。它揭示了这样一个事实：不用管项从哪里来，只需要知道项往哪里去，就能够处理好项的解析。如果仅仅将这一部分的逻辑抽象出来写一段程序，想必比之前写整个树的程序轻松不少。再往上的另一条规则，也可以被单独抽象出来：

一个表达式，就是几个项而已。如果我们能够在这里屏蔽项的解析过程，而直接返回项的解析结果，那么就可以将表达式的解析过程化简为一次简单的下降。

Notice

以往的代码编写中，可能习惯将解决一个局部问题的具体过程嵌入到更高层次代码的编写中（例如在这俩将解析项的具体过程直接写到解析表达式的过程中）。但事实上，让逻辑变简单的一个方法是，在高层次的代码编写中忽视局部问题的解决过程，假设其已经被某个方法解决，从而直接调用该方法即可。

选择合适的局部视角，合理的屏蔽细节，将具体的实现封装，是让代码高效且清晰的重要手段。

如果parseExpr()，parseTerm()分别用来表示解析表达式和项的过程，可以得到下面这种实现：

parserExpr:
  新建一个Term的容器T
  调用parserTerm获得一个项t
  T中加上parserTerm返回的项t
  while 当前token是+:
    跳过当前token(+)
    调用parserTerm获得一个项t
    T中加上parserTerm返回的项t
  利用T生成一个新的Expr e
  返回e

可以看到，有了parseTerm()的封装，我们解析Expr的过程(parseExpr)，就变成了对语法规则的简单叙述。parseTerm的过程也如法炮制。

当然，factor在当前的题目背景下仅是一个i ，因此我们解析factor的过程就是读入一个i ，然后包装成一个factor对象再返回，它不需要调用其他的子过程。

parserTerm:
  新建一个Factor的容器F
  调用parserFactor获得一个因子f
  F中加上parserFactor返回的因子f
  while 当前token是*:
    跳过当前token(*)
    调用parserFactor获得一个因子f
    F中加上parserFactor返回的因子f
  利用F生成一个新的Term t
  返回t

parserFactor:
  检查当前的token是否是i
  跳过当前的token(i)
  利用i生成一个新的Factor f
  返回f

这样就按每一条规则，生成了解析表达式语法结构的代码。

递归

必须指出的是，如果我们不曾听说过或者学习过类似的观点，也可以用一个多层的循环来简单地解决这个问题。这是因为我们上面题面给出的语法结构所形成的树，具有固定的层数，我们可以清楚的知道这个树的终结就在子节点的factor处。

为了更好地说明递归下降法的意义，我们来修改一下上述因子的语法规则:

这么做的话，我们的语法树就不是简单的三层了。甚至说我们并不知道它的层数，因为任何一个因子都可以通过解析为表达式的方式来不断的向下扩张，这无疑给了我们很大的复杂性。我们的解析流程，可能会呈现<表达式>-<项>-<因子>-<表达式>\的递归调用过程。如果再从全局的视角来看，这个语法树的宽度和深度等性质不再可知，它已经变得不可捉摸了。

但是我们从局部的视角来看，会发现表达式的语法规则没有变，项的也没有变，唯一变的是因子，所以我们只需要修改上面的parseFactor过程就好。

parserFactor:
  检查当前的token是否是i
  if 真:
    跳过当前的token(i)
    利用i生成一个新的Factor f
    返回f
  if 假，说明是(表达式):
    跳过当前token(()
    调用parserExpr()获得一个表达式e
    利用e生成因子f
    跳过当前token())
    返回f

具体实现

这里我们需要总结一下：

1. 递归下降分析方法的主要做法是，对文法每条规则的左部符号（ ‘→’ 左侧的符号），建立一个解析子程序，用以完成该符号所代表成分的分析和识别。
2. 对于每个符号的分析子程序的功能则是，用该符号对应文法中的规则来匹配输入的token流。

根据我们上面的例子可以看到，递归下降算法的思想严格依照文法来编写，甚至可以理解为文法的一种“翻译”，递归下降正是依托于文法保证了该算法的正确性。

递归下降分析法作为自顶向下的分析过程，其一级一级的向下分配任务，通过检测当前符号和预期符号 （文法中的规则） 的相符性来选择”分支”进行解析，进而建立结构。

下面我们进一步真正实现该算法：

题目背景

为了方便举例，我们仍然使用表达式解析作为背景，不过对其中的一些规则进行修改。给一个表达式，解析它的结构，并用输出来检验解析的正确性。表达式规则如下：

解法步骤

建类

观察上面在→左面的部分，他们都是我们需要进行分析的语法成分，因此我们需要对他们进行建类，并且构造解析方法。

1. 表达式类 → Expr

2. 项类 → Term

3. 因子类 → Factor ← Number & Expr

这里考虑到有两种因子，我们应当分开来处理。

表达式因子实质就是表达式加括号，而括号本质上是为了区分优先级，但优先级可以由我们的语法树结构来体现，因此为了减少类，可以将这二者统一，都使用表达式Expr来存储信息。

常数因子则可以单独用Number来存。

Expr和Number都属于因子，因此我们可以利用面向对象的知识，创造一个Factor接口(Interface)，然后让Expr和Number实现这个接口。

实现Lexer

我们通常将词法分析部分所用的类叫做Lexer，它实现了词法分析功能，并且将分析得到的信息存储到token流中。

首先梳理一下我们需要的token类型：**+ - * ( ) 数**。

可以分别对这几个类型的词法单元建立token的标识符，可以建立一个token类来实现这个操作：

public class Token {
  public enum Type {
  ADD, SUB, MUL, LPAREN, RPAREN, NUM
  }
  private final Type type;
  private final String content;
  //....
}

同时，在词法分析部分，lexer需要识别不同的token，注意到，这几个类型的词法单元的开头字符必然不同，因此我们利用这一点来实现词法分析。

public Lexer(String input) {
    int pos = 0;
    while (pos < input.length()) {
        if (input.charAt(pos) == '(') {
            tokens.add(new Token(Token.Type.LPAREN, "("));
            pos++;
        } else if (input.charAt(pos) == ')') {
            tokens.add(new Token(Token.Type.RPAREN, ")"));
            pos++;
        } else if (input.charAt(pos) == '+') {
            tokens.add(new Token(Token.Type.ADD, "+"));
            pos++;
        } else if (input.charAt(pos) == '-') {
            tokens.add(new Token(Token.Type.SUB, "-"));
            pos++;
        } else if (input.charAt(pos) == '*') {
            tokens.add(new Token(Token.Type.MUL, "*"));
            pos++;
        } else {
            char now = input.charAt(pos);
            StringBuilder sb = new StringBuilder();
            while (now >= '0' && now <= '9') {
                sb.append(now);
                pos++;
                if (pos >= input.length()) {
                    break;
                }
                now = input.charAt(pos);
            }
            tokens.add(new Token(Token.Type.NUM, sb.toString()));
        }
    }
}

这样，我们就获得了一个经过了词法分析的token流，便可以从中逐一地拿出token方便我们进行语法分析了。

实现Parser

这一步我需要进入到递归下降法的真正实现了。但是首先我们需要先看看题目中的文法，它并不能直接的使用递归下降法：

怎么判断箭头右边走哪一个路线呢？甚至说，就算去掉一个路线：

难道是要在表达式的解析开始就再次调用表达式的解析吗？具体的情况就是：

parserExpr() {
  parserExpr();
  //.....
  }

这样的代码会陷入无限的递归中，不是我们想要的结果。事实上，在编译原理中，有类似规则的文法叫做左递归文法，它是不能用递归下降法解决的。幸运的是，我们可以通过改写文法来消除左递归：

这里，花括号代表可以有0个或多个该部分，这样的改写与我们对原本规则的理解一致，因此是等价的。类似的，我们对其他的规则也进行改写。

parser部分的关键则是如何用获得的token判断应当如何调用解析的方法：

public Expr parserExpr() {
  ArrayList<Term> terms = new ArrayList<>();
  ArrayList<Token> ops = new ArrayList<>();
  terms.add(parserTerm());
  while (lexer.notEnd()&&(lexer.now().getType() ==
  Token.Type.ADD
  || lexer.now().getType() == Token.Type.SUB)) {
    ops.add(lexer.now());
    lexer.move();
    terms.add(parserTerm());
  }
  return new Expr(terms, ops);
}

public Term parserTerm() {
  ArrayList<Factor> factors = new ArrayList<>();
  factors.add(parserFactor());
  while (lexer.notEnd()&&lexer.now().getType() ==
        Token.Type.MUL) {
    lexer.move();
    factors.add(parserFactor());
  }
  return new Term(factors);
}

public Factor parserFactor() {
  if (lexer.now().getType() == Token.Type.NUM) {
    Num num = new Num(lexer.now().getContent());
    lexer.move();
    return num;
  } else {
   // 这里调用move之前lexer.now()是(    
   lexer.move();    
   Expr expr = parserExpr();   
   // 这里调用move之前lexer.now()是)    
   lexer.move();   
   // 调用上面的move之后刚好保证表达式因子的全部成分被跳过。    
   return expr;  
  }
}

其中，lexer.now()获取当前分析的token，lexer.move()则可以移动到下一个token。