Parser

發表於   |   分類於

正文

今次总结Paser相关的一些东西，主要说明Top-Down的LL(1)解析以及Down-Top的LR(1)解析，最后说明抽象语法树（AST）。

LL(1)

LL(1)的缩写表明了该方法的运作方式：左端移进，最左推导，也就是输入串中的字符（或者Token）从左至右逐个扫描，当遇到某一条规约的终结符的时候，从扫描部分的最左端开始进行规约。

例如对于某文法有如下规约（名词）:

r0: S -> Expression

r1: Expression -> Expression + Expression

r2: Expression -> Expression - Expression

r3: Expression -> 1,2…N

可有串： 2+3-4+1

当扫描至+的时候，即为r3的终结符号，于是对已扫描到的2进行归约（动词），得到一个Expression = 2，同时移动到规约r1。

接着扫描3，是为规约r3。

然后是-，得到一个Expression = 3。

此时已经扫描过的部分已有：Expression = 2 + Expression = 3，从而可以按照r1进行归约，得到一个Expression = (Expression = 2) + (Expression = 3)。

剩余部分以此而行，便可以得到整个串了。

LL(1)中的1就是指：每次判定需要使用哪一条规约进行归约的时候，只需要多扫描一个符号即可，例如上面例子中的+和-。

递归子程序法与优先级

优先级一个比较麻烦的地方，上面的例子中+和-是同优先级的，如果哪天有个奇葩规定要求当-和+同时出现时需要优先计算-，则当如何？

先来看看前面两者优先级相同时的“语法图”：

+ == -

再来看看-的优先级比较高的时候的“语法图”：

+ < -

请忽略下面代码对于错误边界的处理，并且一下代码仅为说明过程，递归返回值等的细节也请暂时不要去追究……

首先定义一个过程parseAddExp()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Expression* parseAddExp()
{
  Expression* result = new Expression;
  Expression* left = NULL;
  Expression* right = NULL;
  left = parseMinusExp(left);  
  // 注意这里！！！如果只是一个单独的数字，或者下一个符号不是`+`
  if (NULL == curToken || curToken->m_tkCode != TK_ADD)  
  {
    return left;
  }
  if(curToken->m_tkCode == TK_ADD)
  {
    right = parseMinusExp(right);
  }
  result->m_leftExp = left;
  result->m_rightExp = right;
  return result;
}

再定义一个过程parseMinusExp()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Expression* parseMinusExp()
{
  Expression* left = NULL;
  Expression* right = NULL;
  left = parseNumberExp();
  // 注意这里！！！如果只是一个单独的数字，或者下一个符号不是`-`
  if (NULL == curToken || curToken->m_tkCode != TK_MINUS)  
  {
    return left;
  }
  Expression* result = new Expression;
  if(curToken->m_tkCode == TK_MINUS)
  {
    right = parseNumberExp(right);
  }
  result->m_leftExp = left;
  result->m_rightExp = right;
  return result;
}

最后定义一个过程parseNumberExp()：

1
2
3
4
5
6
7
8
Expression* parseNumberExp()
{
  if (curToken->m_tkCode == TK_INTNUM)
  {
    return new Expression(ToIntNumber(curToken->m_lexeme));
  }
  return NULL;
}

仍旧以串2+3-4+1为例，下面我们将上述过程依次述略述为ADD，MINUS，NUM。

那么对于2，ADD调用MINUS，MINUS解析它，并得知下一个符号是+，于是知道这是仅仅是一个Expression = 2，于是直接返回给Expression Add的左操作数为Expression = 2。

接下来是ADD知晓下一个符号是+，然后将表达式的整个剩余部分送入MINUS中，以期望得到一个右操作数。

串剩余部分是3-4+1。MINUS可以正确捕获到一个Expression Minus = (Expression = 3) - (Expression = 4)，从而将其作为Expression Add的右操作数返回。于是我们得到了一个完整的Expression Add = (Expression = 2) + ( (Expression = 3) - (Expression = 4) )

等等，解析怎么就停止了？后面还有一个+1呢？实际上，只需要对过程ADD进行一些修改，使它支持对连续的N个+进行解析就可以了，对于连续个-，同样可这么干。

那么我们的最终解析过程就极有可能是这样的（视编码而定，但是优先级是肯定对的）：

AST

结果是一个二叉树是因为+和-都是二元运算符的原因；如果全是是一元运算符则是一个单链表，例如成员运算符；全是三元运算符，例如Exp?Exp:Exp，则是一个三叉树；混起来就看起来像是一个普通的树了。

回顾一下前面的解析过程，发现在建立这棵树的时候，每次都是从一颗子树的根节点开始创建，然后递归进行创建它的子节点，所谓的Top-Bottom就是由此而来。

抽象语法树(AST)

前面既然提到了树，那么就顺势说一下吧，很容易理解了。

抽象语法树实际上就是语言无关的，代码的抽象表示，可以认为是代码的一种中间表示形式：单单从上面的那个串：2+3-4+1，根本无法断定它是用哪个语言的来写的。当然设计思想不同的语言，其对应的抽象语法树还是有差别的——比如函数式编程语言与C。

抽象语法树带来的最大好处就是语法制导的翻译和中间代码生成，这个留待以后说明。

顺带一提：上面的树想要恢复原有的表达式，只需要对其进行后序遍历即可（当然需要控制一下左右子节点先后顺序），不妨尝试把原来的数学表达式翻译为三地址码序列：

1
2
3
4
OP  dest  op1  op2
SUB r1    3    4,
ADD r1    2    r1,
ADD r1    r1   1,

LR(1)

实际上，LR分析在《数据结构》课程上已经是接触过的，只不过那时的说法并非如此而已：基本上在学习Stack之后都会有一个处理四则混合运算的“计算器”作业，这个作业实际上就是LR分析的应用。

这里就从四则混合运算入手来说明一下LR(1)解析。

这里举例要用到的串：4+2*3-6/3。暂且不去考虑括号对运算的影响。

r0: S -> Expression

r1: Expression -> Expression + Expression

r2: Expression -> Expression - Expression

r3: Expression -> Expression * Expression

r4: Expression -> Expression / Expression

r5: Expression -> 1,2…N

先对解析过程有个印象：

LR

下面LR(1)的Parser伪码来自《Engineering a Compiler, 2nd》，Figure 3.15：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
push $;
push start state, s0;
word ← NextWord( );
while (true) do;
  state ← top of stack;
  if Action[state,word] = ‘‘reduceA→ β’’ then begin;
    pop 2 × | β | symbols;
    state ← top of stack;
    push A;
    push Goto[state, A];
  end;
  else if Action[state,word] = ‘‘shift si’’ then begin;
    push word;
    push si ;
    word ← NextWord( );
  end;
  else if Action[state,word] = ‘‘accept’’
    then break;
  else
    Fail( );
end;
report success; /* executed break on ‘‘accept’’ case */

大致回忆一下“计算器”作业的过程：使用两个Stack，一个是装载运算符，一个装载读取到的数字；从左到右逐个读取字符，遇到数字就把数字放进数字栈，遇到运算符就把运算符放进运算符栈；如果将要入栈的运算符是*或者\，就从数字栈弹出两个数字，用将要入栈的运算符计算结果，并将结果入数字栈；如果将要入栈的运算符是+或者-，那么就从运算符栈中弹出一个运算符，数字栈中弹出两个数字，计算并将结果压入数字栈；迭代这一过程，直到运算符栈为空，此时数字栈中应该只剩下一个数字，便是最后结果。

再看上面的伪代码：注意到if块中有一个“pop 2 × | β | symbols”。

再注意：四则运算文法中的规约，对于r1~r4都能找出一个代表性的符号，而这个符号，恰好就是运算符。

另外，在之前的表驱动编程和基于状态编程中，曾经提到过：对于由于if-else分支过多而冗长的程序，可以使用状态与表来解决，而在计算器的程序中，需要经常判定读取到的符号的意义。回看上面的伪代码：state，Action[ ]，Goto[ ]。

再有：LR的分析栈包含两个：状态栈以及文法符号栈，而“计算器”也有两个栈。

先把四则运算文法的Action与Goto表填出来。GoTo表实际上就是一个状态转移表。

补充：Action表中有些许错误：单一的number直接accept了，严格来讲应该reduce r5

1
2
3
4
5
6
7
8
9
10
11
Action Table: 空白表项说明是遇到了错误。

     |   number  |    +      |     -     |    *      |     /     |   EOF   |
s0   |  shift s5 |           |           |           |           |  Accept | 初始状态
s1   |  shift s6 |           |           |           |           |         | number +
s2   |  shift s7 |           |           |           |           |         | number -
s3   | reduce r3 |           |           |           |           |         | number * 或者 number + number * 或者 number - number *
s4   | reduce r4 |           |           |           |           |         | number * 或者 number + number * 或者 number - number *
s5   |           |  shift s1 |  shift s2 |  shift s3 |  shift s4 |  Accept | 在已经有了一个数字 number 之后读取到了运算符/EOF
s6   |           | reduce r1 | reduce r1 |  shift r3 |  shift r4 |         | s6是指当前已经分析到 number+number的情况了
s7   |           | reduce r2 | reduce r2 |  shift r3 |  shift r4 |         | s7是指当前已经分析到 number-number的情况了

之所以先填写Action表，是为了说明为何需要一个GoTo表：注意Action表中的reduce ri，如果只有一个Action表的话，一旦归约之后，就有可能会出现无法进行接下来的分析的情况——因为无法得知当前的状态了！

例如：number + number * number，规约之后应当是 number + number，此时的状态应当为s6，但是在只有一个Action表的情况下无法获取。因此需要一个Goto表来协助。

1
2
3
4
5
6
7
8
9
10
Goto Table:
     |   number  |    +      |     -     |    *      |     /     |   EOF   |
s0   |           |           |           |           |           |         |
s1   |           |           |           |           |           |         |
s2   |           |           |           |           |           |         |
s3   |    s5     |    s6     |    s7     |           |           |         | number * 或者 number + number * 或者 number - number *
s4   |    s5     |    s6     |    s7     |           |           |         | number * 或者 number + number * 或者 number - number *
s5   |           |           |           |           |           |         | 在已经有了一个数字 number 之后读取到了运算符/EOF
s6   |           |    s5     |    s5     |           |           |         | s6是指当前已经分析到 number+number的情况了，一旦规约则只剩单个number
s7   |           |    s5     |    s5     |           |           |         | s7是指当前已经分析到 number-number的情况了，一旦规约则只剩单个number

表填完了，接下来使用上面的伪码与这两张表对例串4+2*3-6/3进行分析：

Table

最后一步可以根据需要来组成最后的语法树——C语言中，运算的结合方向为从右向左，应该与此有关。

LR分析中的每一个reduce过程实际上都可以看作是一个语法树的结点的生成过程（如果对每一个number也加入一个reduce的话，这一事实将更加明显），很显然，整个过程自子节点开始，逐步生成整个语句的语法树，这即是Down-Top。

结束

需要注意的是，这里对于LR(1)分析的说明中，由于每个人对具体细节的不同，两个表的内容可能有一些出入；又，由于对LR分析的理解不是足够深刻，文中关于LR(1)的分析可能有错误的地方，还请诸位看官邮件至solaxu@outllook.com不吝指出。

然而LR分析最重要的部分并非分析过程，而是Action表和Goto表的构建。例子因为比较简单，所以可以手工填写，但是对于一门实际语言这显然是不可能的。于此部分本人仅略知皮毛，不敢妄言，还请众位见谅则个。