词法分析器

词法分析器,是将输入的字符串解析为符号串的工具;语法分析器,即parser,是将符号串解析为解析树(并将解析树映射为语法树)的工具。

为什么要有词法分析器

一般的编译器教科书,常常是先讲词法分析器,再讲语法分析器,顺带着讲讲生成文法。个人认为这是完全错误的。

我们必须要知道,我们这里提到的Parser解析的全部都是上下文无关文法(CFG),而词法分析器解析的是正则文法,我们还知道,所有的正则文法都是上下文无关文法,那么这就得出一个结论,因为Parser也可以解析正则文法,所以词法分析起是完全不需要的。

为了解释为什么需要词法分析器,我们必须考察一下市面上常见的各种Parser。

Parser从大的方面上分,有三个属性:

  • 定向/非定向
  • 确定型/非确定型
  • 自底向上/自顶向下

其中非定向方法构建的Parser在程序语言中用的不多,这里不表。

如果你认真阅读过关于上一篇正则文法的文章,你会知道“确定型”和“非确定型”的区别在于“确定型”不需要搜索,时间复杂度是线性的;“非确定型”需要搜索,时间复杂度按你搜索的方法不同,从\(O(n^2)\)到\((O(e^n))\)都有可能。如果从这个角度出发,那么这个解析器最好是确定型的。

但凡事有得必有失,确定型的解析器有一个天然劣势–不存在可以解析任何CFG的确定型解析器。这就要求我们必须对文法进行限制,以满足特定的解析器。

这种限制有时候是很不舒服的。而正则文法则不同,只要你的文法是正则文法,不需任何限制即可获得一个确定型解析器

所以我们需要正则文法,来将字符串变为符号串,提前解决一些Parser解析起来很麻烦的东西。

如何构建一个词法分析器

如果你使用的语言有正则表达式支持,那就直接使用正则表达式构建即可;如果没有(常用的语言也就C没有了吧),建议使用flex之类的工具。

这里我们需要注意几个问题:

  • 正则表达式最好写在一起,否则和搜索没有区别。
  • 如果你的正则表达式不支持捕获,那么是无法实现的。
  • 注意错误处理,生成好看的错误。

语法分析器

语法分析器的基本问题

我个人分为三个问题:

  • 如何正确、快速地识别输入符号串
  • 如何构建的解析树
  • 如何把解析树映射成语法树

接下来的讨论,只讨论第一个问题。后面两个问题见下一节。

市面上的常见Parser

现在市面上有很多Parser,大概分为五类:

  • 手写的递归向下解析器
  • 函数式编程语言里的Parser Combinator
  • Parser Generator
  • 手写的算符优先级解析器
  • 一些使用特定算法的其他解析器

递归向下解析器

递归向下指的是一种编程方法。比如说你有这样的文法:

\[A \rightarrow aBc\] \[B \rightarrow dB\]

那么,你写出这种函数:

VALUE handle_A(SYMBOL * stream, int pos){
  if(stream[pos] == a){
    pos++;
    if(SUCCESS(handle_B(stream, pos))){
      if(stream[pos] == c){
        pos++;
        // 变成语法树返回回去
      }
      else{
        // error_handle
      }
    }
    else{
      // error_handle
    }
  }
  else{
    // error_handle
  }
}

VALUE handle_B(SYMBOL * stream, int pos){
  if(stream[pos] == d){
    pos++;
    if(SUCCESS(handle_B(stream, pos))){
      // 变成语法树返回回去
    }
    else{
      // error_handle
    }
  }
  else{
    // error_handle
  }
}

从外形上说,这就是把每一个非终结符写成一个函数,然后在这个函数里处理这个非终结符的内容,并返回成功或失败。

从本质上说,这是一个自顶向下解析器。它是一个下推自动机,具有一个栈,以如下方式运行:

  • 初始化:将初始符号压入栈中(调用handle_S)
  • 从栈顶弹出一个符号
    • 如果是终结符就与当前字符串的第一个符号进行比较,如果成功则继续,失败返回错误
    • 如果是非终结符就将这个非终结符的右手侧压入栈中(调用handle_X)

这个时候,读者应该隐隐约约地感到到了一些问题。

第一个问题是,一个非终结符可以生成不同的符号串,比如说:

\[A \rightarrow aBc \tag{0}\] \[A \rightarrow cDf \tag{1}\]

如果现在的栈顶符号是\(A\),你如何判断压入哪个符号串呢?

这就有了递归向下Parser内部的两个实质Parser:

  • 回退解析器。如果遇到这种问题,我们使用搜索广度优先或深度优先搜索算法,将两种路径都尝试一下,如果失败就回退。(非确定型)
  • LL(k)解析器。我们保证文法是LL(k)的,这样一来就可以根据当前输入符号串的前\(k\)个符号判断采取哪条路径。(确定型)

第二个问题是,如果我们遇到的是左递归文法:

\[A \Rightarrow Aa\]

这个规则会使得自动机不停地弹出A和压入A,是一个死循环。所以从本质上来说,执行最左推导的下推自动机极其实现,永远不可能处理原始的左递归文法。

而有时候我们又必须要求左递归,比如四则运算的减号。

有人可能会说,有一个算法可以把左递归强行化成右递归。确实是有,但是如果你把该算法作用于减号上,你会发现,强行化成右递归会导致语义不正确。这个问题是每一个使用递归向下的人不得不解决的。

Parser Combinator

我们知道,所有的生成文法其实都可以写成连接的形式(当然,必须允许重复定义,或者允许选择符号)。而上面的递归向下解析器其实是在用代码定义这些东西:

  • 终结符–是否匹配的if判断语句
  • 非终结符–是否匹配的if判断函数
  • 连接–顺序执行
  • 选择–判断进入哪条路径的if判断语句

很多人会敏锐的认识到,这些东西都可以进行抽象。把代码的运行逻辑留下,作为一个高阶函数;把具体的代码封装成函数作为其参数。而这恰恰就是函数式编程的思想。

如此一来,我们就获得了一个新的工具–Parser Combinator.

我这里举FParsec作为例子,看看它是如何构建解析器的:

FParsec把输入流进行封装。其中最重要的概念就是“position”,即当前要处理的符号串位置。这里需要特别注意,FParsec只支持将字符串作为输入,无法使用词法分析器,这是其美中不足之处。

FParsec将解析器定义为一个函数,原型如下:

  type Parser<'Result, 'UserState> = CharStream<'UserState> -> Reply<'Result>

这里的UserState是我们自己定义的State,一般设为unit(即空类型,没有内容)即可,暂时不去管他;这里的’Result是一个泛型类型,用户可以自己定义结果。

这个函数的意义是,一个输入为CharStream型,输出为Reply的函数。

FParsec提供了一些用来从字符构建非终结符的函数,比如说:

  let internal charReturnE (c: char) result error : Parser<'a,'u> =
    fun stream ->
        if stream.Skip(c) then Reply(result)
        else Reply(Error, error)

我们使用

  let a =  charReturnE "a" "a"

即是定义了非终结符a,对应的字符也是”a”。

FParsec提供了一系列用于连接符号的函数。

  let (.>>) (p: Parser<'a,'u>) (q: Parser<'b,'u>) =
    fun stream ->
        let mutable reply1 = p stream
        if reply1.Status = Ok then
            let stateTag1 = stream.StateTag
            let reply2 = q stream
            let error = if isNull reply1.Error then reply2.Error
                        elif stateTag1 <> stream.StateTag then reply2.Error
                        else mergeErrors reply2.Error reply1.Error
            reply1.Error  <- error
            reply1.Status <- reply2.Status
        reply1

这个符号是将两个非终结符连接起来,形成一个新的非终结符的函数。 比如说:

  let A = charReturnE "a" "a"
  let B = charReturnE "a" "a"
  let C = A .>> B

实际上就是:

\[A \rightarrow a\] \[B \rightarrow b\] \[C \rightarrow AB\]

的实现。

FParsec本质上是一个回退解析器,但它的性能却相当不错。这是因为它对选择符号(<|>)的实现:

  let (<|>) (p1: Parser<'a,'u>) (p2: Parser<'a,'u>) : Parser<'a,'u> =
    fun stream ->
        let mutable stateTag = stream.StateTag
        let mutable reply = p1 stream
        if reply.Status = Error && stateTag = stream.StateTag then
            let error = reply.Error
            reply <- p2 stream
            if stateTag = stream.StateTag then
                reply.Error <- mergeErrors reply.Error error
        reply

我们看到,如果第一个Parser失败,当且仅当在stateTag没有改变时,才会进行用第二个Parser进行解析。

这个stateTag,实际上就是position,也就是是当前解析到的位置。如此设计,保证了这个Parser仅仅会回退一个字符,因为如果第一个字符是匹配的,position就发生了变化。如此设计,使得它在某种意义上具有了\(LL(1)\)的特性。

当然,我们也可以使用attempt强行使它回退。

针对下推自动机无法识别左递归的问题,FParsec引入了一个算符优先级解析器,帮助我们识别(1 + 1 - 2)一类的式子。

个人认为FParsec是一个不错的东西。但是F#和Haskell一样,本身语言设计有诸多麻烦之处,实际开发体验并没有特别舒服。

Parser Generator

这个东西应该是最为正统的方式了。Parser Generator可以做到由文法直接生成代码,我们不太需要关系内部是如何实现的。这个东西的集大成者是yacc,我们没什么好说的。

算符优先级解析器

我们并不陌生,大名鼎鼎的调度场算法即是这类解析器的一种,这里也不耗费笔墨了。

从解析树到语法树

解析树,顾名思义,就是解析器生成的树。这里有两个问题:

  • 逻辑上的解析树是唯一的,也就是生成文法生成句子的那棵生成树。
  • 一个可以正确识别出输出符号串的解析器,一定是正确地构建出解析树了的,但是这颗解析树是逻辑上的,而非实现上的。实现上的解析树是什么样的,需要一一讨论。

语法树则不同,语法树和解析树的关系是若即若离的:

  • 语法树的节点并不是解析器自动生成的,而是人为设计的。
  • 即使没有Parser,我们也可以直接根据想法(而不是根据生成文法),构建出语法树。
  • 一般来说,我们的Parser会在解析的同时,将解析时映射为语法树。

我们考察两个有代表性的解析器–递归向下解析器与Yacc生成的解析器–是如何构建出解析树,并将其映射为语法树的。

递归向下解析器的情况

以如下文法为例:

\[S \rightarrow A\] \[A \rightarrow M\] \[A \rightarrow M + A\] \[M \rightarrow D * M\] \[M \rightarrow D\] \[D \rightarrow int | (A)\]

这文法定义了一个支持加乘两种运算的式子。

我们用C#实现一下;


namespace RecursiveDesentParser
{
    class Parser
    {
        public string Target { get; set; }
        private int pointer = 0;
        private Node head = new Node("S");
        public Parser(string s)
        {
            Target = s;
        }
        public bool Parse()
        {
            var success = (head = ParseA()) != null;
            return ParseEpsilon() && success;
        }
        private Node ParseA()
        {
            Node now = ParseM();
            if (now != null)
            {
                if (ParseChar('+'))
                {
                    List<Node> nodes = new List<Node>();
                    nodes.Add(now);
                    var tail = ParseA();
                    nodes.Add(tail);
                    return new Node("+", nodes);
                }
                else { return now; }
            }
            else { return null; }
        }
        private Node ParseM()
        {
            Node now = ParseD();
            if(now != null)
            {
                if (ParseChar('*'))
                {
                    List<Node> nodes = new List<Node>();
                    nodes.Add(now);
                    var tail = ParseM();
                    nodes.Add(tail);
                    return new Node("*", nodes);
                }
                else { return now; }
            }
            else { return null; }
        }
        // 以下代码略
    }
}

现在来解析这样的式子:

\[1 + 2 * 3\]

为了更好地展示解析的过程,我们需要把整个解析的所有调用都画出来:

ParseA
  ParseM
    ParseD : 1
  ParseChar : +
  ParseA
    ParseM
      ParseD : 2
      ParseChar : *
      ParseM
        ParseD : 3

我们发现:调用函数的过程,自然地形成了一颗解析树!,这也正是递归向下解析器的一大特性。

调用函数的过程本身就是解析树,将解析树映射为语法树的做法就呼之欲出了:将返回值作为语法树的节点,在每个函数内部实现解析树到语法树的节点的映射:

private Node ParseA()
{
    Node now = ParseM();
    if (now != null)
    {
        if (ParseChar('+'))
        {
            List<Node> nodes = new List<Node>();
            nodes.Add(now);
            var tail = ParseA();
            nodes.Add(tail);
            return new Node("+", nodes);
        }
        else { return now; }
    }
    else { return null; }
}

在这个函数里,我们把自然形成的这个解析树:

A
  M
  +
  A

映射成了这样的语法树:

+
  M
  A

Yacc的情况

yacc是一个LALR(1)文法的Parser Generator. 它产生的分析器是一个自底向上的确定型分析器。

自底向上的意思是,它对应一个这样的自动机:

(在下面的示意中, .表示在.之前的位置已经被分析完了)

这个自动机的输入是一个字符串,它开始的状态是当然是:

\[.a_{0}a_{1}a_{2}a_{3}\]

这个自动机还具有一个栈,在开始状态,栈中没有元素。

\[S\]

这个自动机有两种操作:

  • 读入一个字符,把字符放到栈里。
  • 把栈里的字符进行规约,化成别的符号。

它不断地进行这两个操作,直至栈中得到开始符号为止。

以下面的语法和输入字符为例:

\[S \Rightarrow A\] \[A \rightarrow Aa | a\] \[aaaa\]

首先,开始的状态是:

\[栈:\] \[.aaaa\]

移进一个a:

\[栈:a\] \[a.aaa\]

进行规约:

\[栈:A\] \[a.aaa\]

再移入一个a:

\[栈:Aa\] \[aa.aa\]

下面的操作就无需多言了。

这里我们会发现,自底向上的解析器的解析树,实际上体现在“规约”中,每一次的规约,实际上是以解析树的叶子节点替换解析树的根节点

但这样一来,真正的解析树其实没有被留下,也就无法把解析树映射为语法树了。

为了解决这个问题,yacc引入了一个“内容栈”和“符号栈”的概念。

  • 内容栈:栈里是类型为YYSTYPE的值,它是保存结果用的栈。
  • 符号栈:我们刚才说得用来分析的栈。

这两个栈到底是怎么一回事呢?我们来看一个例子:


%{
#include <stdio.h>
 typedef struct node
 {
 struct node *left;
 struct node *right;
 char *token;
 } node;
 node *mknode(node *left, node *right, char *token);
 void printtree(node *tree);
#define YYSTYPE struct node *
%} 

exp : term {$$ = $1;}
 | exp PLUS term {$$ = mknode($1, $3, "+");}
 | exp MINUS term {$$ = mknode($1, $3, "-");} 

不难看出,node是语法树的节点类型,而那句


#define YYSTYPE struct node *

就是将内容栈的元素类型定义为node*指针类型。

下面的那句


exp : term {$$ = $1;}
 | exp PLUS term {$$ = mknode($1, $3, "+");}
 | exp MINUS term {$$ = mknode($1, $3, "-");} 

如果除去大括号,就是生成文法;而大括号里面的内容,则是对每条文法在内容栈上的操作,这个写法表示,在运用这条文法进行规约时,将内容栈上的对应元素拿出,并压入新构造的node*指针。

这样一来,我们又实现了从解析树映射到语法树的操作。

需要注意的几个问题

不要给Parser增加太多负担

有些人想要在解析阶段就识别出来这种语法错误:

char a = 0;
a();

如果真的想做,这需要CSG解析。而CSG解析并没有一个很好的算法,所以,应该放弃这种不切实际的想法,在后面的阶段再检查这种错误。

最好不要实现Parser

通过上面的描述,可以看到Parser是一个苦大仇深的行业。如果你实现一个复杂的语法,它的Parser会非常复杂,这会耗尽你对程序语言的热情。所以,让我们一起来实现Lisp吧!