Parser combinator 在C++里的DSL

如果对编译原理稍微有了解, 相信你一定知道语法, 语法分析(Parsing)和语法分析算法, 也见过语法分析器(Parser). 当需要对某个语言进行处理时语法分析是必不可少的阶段, 可是呢, 实现语法却很繁琐, 就算是递归下降算法LL家族在语法较复杂的时候实现也会变得很繁琐单调, 更别说对编码不友好的LR家族算法了. 很多小伙伴会选择使用语法器生成器(Parser generator)来编译产生语法分析器, 输入文法和相关的操作输出一个语法分析器的源码. 这是其中一种很不错的办法, 相信大家都知道, 这里呢介绍另一种比较少被了解的办法: 语法分析器组合子(Parser combinator).

首先我们知道一个语法分析器是一个函数, 输入为需要被分析的字符串或者符号串(Token series)输出为其语法结构或语义, 那么可以定义语法分析器的类型为:

$$Parser(\alpha) := \forall \alpha .\;String\rightarrow [(\alpha, String)]$$

α为我们完成解析之后需要的语法结构或语义值的类型, 比如是一颗抽象语法树(AST), 或者如在之前的文章Packrat Parsing里的四则运算的Parser在分析过程中直接使用文法综合属性计算出对应的语义值(就是表达式的计算结果啦), 返回的是一个数字. 第二个的String为剩余待分析的字符串.

那么我们就可以将这个计算器看作是语法分析器的一个实例(instance), 类型为:

$$Calc:=Parser(int) := String\rightarrow [(int, String)]$$

这样就很好理解了. 大家发现没有, 这里呢我们关注的不是某一个特定的某一个语法分析器和它的实现, 我们关注的是语法分析器的抽象. 我们关心的是如何进行对某个串的结构分析而不是如何计算语义值. 我们这里将两者分离开了.

我们有了语法分析器还不够, 我们需要在其域上定义运算(就像我们有数字是不够的, 我们还需要加法和乘法运算嘛). 对语法分析器的运算就是语法分析器组合子啦, 也是全文的主题. 语法分析器组合子是语法分析器的高阶函数, 简单来理解就是接受语法分析器作为输入返回新的语法分析器, 这里我们需要两种组合子连接组合子(+)与或组合子(|), 连接和或很好理解, 直接对应于语法里的符号连接与或.

给出类型:

\begin{align*} &\left[ + \right] (\alpha ,\beta ):=\forall \alpha ,\beta .\;Parser(\alpha )\times Parser(\beta)\rightarrow Parser(\alpha\times \beta)\\ &\left[ \;|\; \right] (\alpha ,\beta ):=\forall \alpha ,\beta .\;Parser(\alpha )\times Parser(\beta)\rightarrow Parser(\alpha+\beta) \end{align*}

如果小伙伴对这里的对类型的运算加与乘感到疑惑的话可以去参考一下代数数据类型(Algebraic data type)或者我的回答数学中有哪些巧合让人眼前一亮里有粗略的介绍.

构造表示:

\begin{align*} &(p\quad \texttt{<+>}\quad q)\;j\;=\;(p\quad j)\;\cup\;(q\quad j)\\ &(p\quad \texttt{<*>}\quad q)\;j\;=\;\bigcup_{}^{}(map\quad q\quad(p\quad j))\\ \end{align*}

最后我们需要一个语法分析器单位元(Term parser), 这是构成语法最基本的单位, 对应于语法里的终止符. 就是直接识别输入串里的某个符号的单位语法分析器, 可以简单来理解如之前的文章Packrat Parsing里的Number符号与对应的函数, 即是只接受0-9这10个字符并返回数字.

构造表示:

$$term\quad t\quad j\;=\;\begin{cases} \{\}&,j\geq\#input\\ \{j+1\}&,j^{th}\; element\; of\; input=t\\ \{\}&,otherwise \end{cases}$$

(这里的返回忽略了语义值, 返回一个集合, 里面的数字表示剩余需要分析的串的下标index, 这个和我的定义略有不同, 大家能理解意思就好)

最后我们还需要单位元(identity element), 这里的单位元和上面的不同, 这是代数概念上的单位元, 对应与文法里的空符号ε(或是empty啦, 即是对于任意的输入都返回空并且不消耗符号, 类型为:

$$\varepsilon:=Parser(void)\)

构造表示:

\(!empty\quad j\;=\;\{j\}\)

另外一个是不接受任何符号的语法解析器, 返回空, 类型与ε一样.

\(!void_{parser}:=Parser(void)\)

构造表示:

\(!Void\quad j\;=\;\{\}\)

这个在实践中没有什么用, 也不会出现在文法里. 需要它是因为其代数意义, 这里就提到一下下.这样我们就拥有了对应于文法的所有结构了. 为什么这么定义是可行且有意义的呢, 细心的你可能会发现

\(\left( Parser,\;[\;|\;]\;\right)\) 构成了一个阿贝尔群(Abelian group), 其单位元素[0元素]为\(void_{parser}\)

\(\left( Parser,\;[+]\;\right)\) 构成了一个么半群(Monoid), 其单位元素[1元素]为\(\varepsilon\)

那么类型\(Parser\)构成了一个环(Ring), 其未提到的性质和条件大家有兴趣可以自己去验证一下. 这里并不赘述了. 另外提到的是基于集合论来说注意某些逆元素的存在但不可构造.

这个组合子的结构是不是非常的优雅呢, 笑~

好啦好啦, 可能有些小伙伴对理论并不感兴趣, 我们来说具体的实现吧, 这里我使用的是C++实现:

首先给大家一个例子:

还是之前的文章里的四则运算计算器, 文法为:

\begin{align*} Additive&:=\;Additive\;’+’\;Multitive\;|\;Additive\;’-‘\;Multitive\;|\;Multitive\\ Multitive&:=\;Multitive\;’*’\;Primary\;|\;Multitive\;’/’\;Primary\;|\;Primary\\ Primary&:=\;'(‘\;Additive\;’)’\;|\;Number\\ Number&:=\;Number\;Decimal\;|\;Decimal\\ Decimal&:=\;’0’\;|\;\cdots\;|\;’9′ \end{align*}

使用组合子的实现非常优雅:

ParserCombinator<int> Additive, Multitive, Primary, Number, Decimal;

//Decimal := '0' | ... | '9'
Decimal = ('0'_T | '1'_T | '2'_T | '3'_T | '4'_T | '5'_T | '6'_T | '7'_T | '8'_T | '9'_T) >>
    [](char ch)
    {
        return ch - '0';
    };

//Number := Number Decimal | Decimal
Number = (Number + Decimal >>
    [](int Number, int Decimal)
    {
        return Number * 10 + Decimal;
    }) | Decimal;

//Primary := '(' Additive ')' | Number
Primary = ('('_T + Additive + ')'_T >>
    [](Placeholder, int Additive, Placeholder)
    {
        return Additive;
    }) | Number;

//Multitive := Multitive '*' Primary | Multitive '/' Primary | Primary
Multitive = (Multitive + '*'_T + Primary >>
    [](int Multitive, Placeholder, int Primary)
    {
        return Multitive * Primary;
    }) | (Multitive + '/'_T + Primary >>
        [](int Multitive, Placeholder, int Primary)
    {
        return Multitive / Primary;
    }) | Primary;

//Additive := Additive '+' Multitive | Additive '-' Multitive | Multitive
Additive = (Additive + '+'_T + Multitive >>
    [](int Additive, Placeholder, int Multitive)
    {
        return Additive + Multitive;
    }) | (Additive + '-'_T + Multitive >>
        [](int Additive, Placeholder, int Multitive)
    {
        return Additive - Multitive;
    }) | Multitive;

std::cout << Additive("(1+2)*3") << std::endl;
//Output: 9

简单介绍一下ParserCombinator的食用方式, 笑~

ParserCombinator<int>

模板参数int表示这个语法解析器是一个接受字符串为输入返回其语义为int的语法解析器.

对于文法:

\(Number:=\;Number\;Decimal\;|\;Decimal\)

可以直接在C++代码里写:

Number = Number + Decimal | Decimal;

不过这里还缺少点东西, 就是对于Number + Decimal这个部分我们需要指明在得到Number和Decimal这两个子语法的语义值之后的语义, 就是怎么运算啦. 使用>>指定一个回调函数:

[](int Number, int Decimal)
{
    return Number * 10 + Decimal;
})

这是个Lambda表达式, 表示我们已经分析好的Number后面还跟着一个数字, 那么我们就把Number乘10再补上这个个位数Decimal. 然后返回, 这个返回值就作为Number + Decimal这部分文法的返回值.

最后的完整的实现就是:

//Number := Number Decimal | Decimal
Number = (Number + Decimal >>
    [](int Number, int Decimal)
    {
        return Number * 10 + Decimal;
    }) | Decimal;

大家应该明白怎么使用了吧

那么这个东西是怎么实现的呢, 这东西太复杂了, 篇幅限制我不能面面俱到, 将给大家所有细节, 我主要讲讲核心实现和理念. 具体分成几个部分:

1. 基本实现思想

首先分成两个部分组成, ParserCombinator和ParserCombinatorComponent, 如名字所示, ParserCombinator是一个语法分析器而ParserCombinatorComponent是构成语法分析器的组成部分, 例如A = B + C这个表达式中, A, B, C是一个ParserCombinator而B+C是一个ParserCombinatorComponent, 用以表示语法的中间构成. 这么区分是为了能够进行递归, 使用ParserCombinator类型识别出表达式中那些符号需要被引用.

ParserCombinator里面不包含具体的实现而是保存了一个指向具体实现的ParserCombinatorComponent的指针, 在构造使用+与|表达式时遇到ParserCombinator将会把指针保存下来用以递归调用.

大家看到上面的表达式肯定知道这个是使用操作符重载完成的, 这里重载了+和|这两个操作符.

+与|的两个参数可以是ParserCombinator或ParserCombinatorComponent返回一个新的ParserCombinatorComponent.

具体来说大致的实现如下:

ParserCombinatorComponent里保存了一个具体实现的函数对象(std::function)为func, 完成具体的分析与调用. operator +与operator | 实现大致为:

typedef ParserCombinatorComponent Component;

struct Info
{
    const std::string& str,
    size_t index,
    bool success
};

Component operator + (Component lhs, Component rhs)
{
    Component ret();
    ret.func = [lhs_func = lhs.func, rhs_func = rhs.func]
    (Info in)->Info
    {
        Info lhs_ret(lhs_func(in));
        if(lhs_ret.success)
        {
            return rhs_func(lhs_ret);
        }
        return lhs_ret;
    };
    return ret;
}

Component operator | (Component lhs, Component rhs)
{
    Component ret();
    ret.func = [lhs_func = lhs.func, rhs_func = rhs.func]
    (Info in)->Info
    {
        Info lhs_ret(lhs_func(in));
        if(lhs_ret.success)
        {
            return lhs_ret;
        }
        return rhs_func(in);
    };
    return ret;
}

对于单位元(Term parser)的实现大致为:

Component Token(char ch)
{
    Component ret();
    ret.func = [=](Info in)->Info
    {
        bool success(in.str[in.index]==ch); 
        return Info
        {
            in.str,
            in.index+success,
            success
        };
    };
    return ret;
}

Component operator"" _T(char ch)
{
    return Token(ch);
}

这里使用了C++11的user defined literal特性, 可以在字面字符上直接加_T来生成一个Token component.

对于需要递归的实现为(以operator +为例):

Component operator + (ParserCombinator lhs, Component rhs)
{
    Component ret();
    ret.func = [lhs_ref = lhs.ptr, rhs_func = rhs.func]
    (Info in)->Info
    {
        Info lhs_ret(ptr->func(in));
        if(lhs_ret.success)
        {
            return rhs_func(lhs_ret);
        }
        return lhs_ret;
    };
    return ret;
}

注意这里捕获的是ParserCombinator里指向具体实现的指针lhs.ptr.

注: 这里忽略了语义值, 将在接下来的第二部分讲到。

2. 类型系统

由于C++可以针对模板函数的参数进行类型推导这样我们就可以为我们的组合子添加上一套类型系统, 在编译期进行约束保证组合子的语义的类型正确.

首先推导规则如下:

\begin{align*} &[+]\;:\quad\frac{\Gamma\vdash_s L:Parser(e_0)\quad\Gamma\vdash_s R:Parser(e_1) } {\Gamma\vdash_s L+R: Parser(e_0\times e_1)} \\ &[\;|\;]\;:\quad\frac{\Gamma\vdash_s L:Parser(e_0)\quad\Gamma\vdash_s R:Parser(e_1) } {\Gamma\vdash_s L\;|\;R: Parser(e_0+e_1)} \\ &[\;>\!>\;]\;:\quad\frac{\Gamma\vdash_s L:Parser(e_0)\quad\Gamma\vdash_s F:e_0\rightarrow e_1 } {\Gamma\vdash_s L\;>\!>\;F: Parser(e_1)} \end{align*}

如果不是很明白上面的推导规则也没关系, 下面我用C++的方式来解释:

首先需要搭建一个代数数据类型的基础设施, 构建两个基本类型构造子和运算:

ProductTypes
PushProductTypes

AdditionTypes
PushAdditionTypes

ProductTypes对应于类型的乘积, . AdditionTypes对应于类型的和, 可理解为类型的笛卡尔乘积或者是类型的列表.

ProductTypes的实现大致如下:

template<class... _Types>
struct ProductTypes
{
    typedef std::tuple<_Types...> Tuple_type;
    Tuple_type _Data;
}

template<class _Type, class... _Types>
struct PushProductTypes;

template<class... _Tys, 
    class... _Types>
struct PushProductTypes<ProductTypes<_Tys...>, _Types...>
{
    typedef ProductTypes<_Tys..., std::decay_t<_Types>...> type;
};

template<class _Type,
    class... _Types>
struct PushProductTypes
{
    typedef ProductTypes<std::decay_t<_Ty>, std::decay_t<_Types>...> type;
};

举例来说, 比如我现在要对int和char进行相乘, 那么就是:

PushProductTypes<int, char>::type;    //ProductTypes<int, char>

对ProductTypes<int, char>和long进行相乘, 那么就是:

PushProductTypes<ProductTypes<int, char>, char>::type;
//ProductTypes<int, char, long>

AdditionTypes的实现大致如下:

template<class _Type>
struct AdditionTypesBase
{
};

template<class... _Types>
struct AdditionTypes
    :AdditionTypesBase<_Types>...
{
    Any _Data;
}

template<class _Type, class _SubType>
struct PushAdditionTypes;

template<class _Type, class _SubType>
struct PushAdditionTypes
{
    typedef std::decay_t<_Type> _dType;
    typedef std::decay_t<_SubType> _dSubType;
    typedef typedef typename std::conditional<std::is_same<_Type, _dSubType>::value,
        _dType
        AdditionTypes<_dType, _dSubType>> type;
};

template<class... _Tys, 
    class _SubType>
struct PushAdditionTypes<AdditionTypes<_Tys...>, _SubType>
{
    typedef std::decay_t<_SubType> _dSubType;
    typedef AdditionTypes<_Tys...> _Type;
    typedef typename std::conditional<std::is_base_of<AdditionTypesBase<_dSubType>, _Type>::value,
        _Type,
        AdditionTypes<_Tys..., _dSubType>
    >::type type;
};

举例来说, 比如我现在要对int和char进行相加, 那么就是:

PushAdditionTypes<int, char>::type;    //AdditionTypes<int, char>

对int和int进行相加, 那么就是:

PushAdditionTypes<int, int>::type;    //int

对AdditionTypes<int, char>和int进行相加, 那么就是:

PushAdditionTypes<AdditionTypes<int, char>, int>::type;
//AdditionTypes<int, char>

利用多重继承和std::is_base_of来判断是否已经存在改类型, 以此保证重复的类型将不会进入AdditionTypes.

注: AdditionTypes里的数据成员Any类型是可以容纳任何类型的类型.

拥有了类型的和与积之后我们就可以很方便使用模板进行类型推导了, 将第一部分的operator + 和operator | 写成模板的形式:

template<class e_0, class e_1,
    class _Return_type = typename Component<PushProductTypes<e_0, e_1>::type>>
_Return_type operator + (Component<e_0> lhs, Component<e_1> rhs);

template<class e_0, class e_1,
    class _Return_type = typename Component<PushAdditionTypes<e_0, e_1>::type>>
_Return_type operator | (Component<e_0> lhs, Component<e_1> rhs);

简单的直觉理解就是比如语法

A = B + C

B返回类型int, C返回类型char, 那么A的类型应该是一个tuple<int, char>, 即是ProductTypes<int, char>.

A = B | C

B返回类型int, C返回类型char, 那么A的类型应该是包含的是int或者是char, 即是AdditionTypes<int, char>.

如果B和C类型一致那么A即是B与C的类型.

之后我们给第一部分里提到的struct Info添加上一个成员

Any value;

用以保存返回的语义值, 这里使用Any进行类型擦除目的是解耦, 在不改变struct Info成员情况能够容纳任意类型的语义值, struct Info可以在递归函数间任意传递而不需要复杂的cast逻辑.

同时在operator +里面把获取到的值用std::tuple_cat添加到ProductTypes的_Data里就好.

在有了类型系统之后就能很容易实现回调函数部分了:

template<class e_0, 
    class Func,
    class _Return_type = typename std::result_of<Func>::type>
_Return_type operator >> (Component<e_0> lhs, Func f)
{
    _Return_type ret();
    ret.func = [lhs_func = lhs.func, f]
    (Info in)->Info
    {
        Info lhs_ret(lhs_func(in));
        if(lhs_ret.success)
        {
            if constexpr(is_ProductTypes<e_0>::value)
                lhs_ret.value=std::apply(f, lhs_ret.value._Data);
            else
                lhs_ret.value=f(lhs_ret);
        }
        return lhs_ret;
    };
    return ret;
}

使用std::apply可以将tuple的每个成员map到被调用函数的参数上.

在有了类型系统以及推导的情况下就能保证我们的调用都是类型正确的啦.

3. 记忆化与左递归兼容

有关记忆化的技巧可以参考我之前的一篇文章Packrat Parsing 回溯式线性时间语法分析

小伙伴们可能已经发现了上面的四则运算计算器里是存在左递归的, 我们的语法分析组合子很明显是递归下降算法实现, 那么我们需要对左递归做一些处理以兼容左递归语法.

在实现了记忆化之后, 再次在同样位置调用同一个语法时会直接在表里提取出值返回而不是再次求值, 这样保证了能在线性时间内完成语法分析. 同时注意到记忆化的实现为解决左递归问题提供了工具, 在第一次访问该语法非终止符时在记忆化表上标记访问次数count=1. 如果存在左递归那么在再次进入改文法时会发现标记, 表示发生了左递归, 如果选择不兼容左递归的话可以直接抛出左递归异常.

兼容左递归的核心思想为, 在对左递归进行递归调用时递归深度并不是无限的, 因为我们需要分析的串长度是有限的, 而该左递归语法非终止符若成功完成分析那么必须消耗至少一个符号(否则将会出现空循环, 这种病态(ill-formed)语法并不能完成分析, 小伙伴们思考一下为什么). 于是在再次进入该左递归语法非终止符的时候对访问次数count加一, 如果count超过了剩余待分析串的长度+1那么可以直接返回分析失败, 这时候将不可能完成分析. 然后返回递归, 进行自底向上进行语法分析, 选取最长分析作为返回, 这个时候相当于做了一次延时决策, 类似与LR分析算法.

值得留意一下的是自底向上分析时结果不一定是唯一的, 这里我使用的是最长匹配原则, 当然你在实现时可以引入向前看符号或者别的不同方式进行选取决策, 甚至继续延迟决策直到信息足够时.

具体实现并不复杂, 只需要对记忆化表添加上访问计数和相关结构就好了.

更多的细节这里我不赘述了, 有兴趣的小伙伴可以去阅读论文:

Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars [.PDF]

4. Continuation-passing style(CPS)

如果对CPS不熟悉的小伙伴可以看看Wiki Continuation-passing style. 这里就不做更多介绍了.

由于我们的ParserCombinator是由ParserCombinatorComponent自底向上构建的, 每一个Component能得到的仅仅是其Sub-component的综合属性, 并不知道后续的分析流程, 无法进行回溯决策(当然一种办法是把所有分支使用一个set装起来返回, 但这样内存效率将很有可能无法接受).

将匹配流程全体进行CPS变换之后, 在每一个Component下我们将可以得到其Sub-component的综合属性以及将来的匹配分析流程信息(即是Continuation啦). 这时分支与左递归便可以进行回溯匹配.

若是熟悉CPS变换的话, 实现并不是很复杂.

Continuation的定义:

typedef std::function<bool(const Info&)> Continuation;

进行CPS变换后Continuation和每个Component的实现函数func返回值为bool, 表示后续的分析成功与否.

连接(+)与分支(|)两个Component的变换如下:

Component operator + (Component lhs, Component rhs)
{
  Component ret();
  ret.func = [lhs_func = lhs.func, rhs_func = rhs.func]
  (Info in, Continuation cont)->bool
  {
    return lhs_func(in, [&cont](auto lhs_ret)->bool
    {
      if(lhs_ret.success)
      {
        return rhs_func(lhs_ret, cont);
      }
      return false;
    });
  };
  return ret;
}

Component operator | (Component lhs, Component rhs)
{
  Component ret();
  ret.func = [lhs_func = lhs.func, rhs_func = rhs.func]
  (Info in, Continuation cont)->bool
  {
    return lhs_func(in, [&cont](auto lhs_ret)->bool
    {
      if(lhs_ret.success && cont(lhs_ret))
      {
        return true;
      } else {
        return rhs_func(in, cont);
      }
    });
  };
  return ret;
}

留意分支(|)中, 选择左分支进行后续分析失败(cont(lhs_ret)为false)后回溯至右分支.

单位元(Term parser)的变换为:

Component Token(char ch)
{
  Component ret();
  ret.func = [=](Info in, Continuation cont)->bool
  {
    bool success(in.str[in.index]==ch);	
    return cont(Info
    {
      in.str,
      in.index+success,
      success
    });
  };
  return ret;
}

进行CPS变换后入口函数要稍微改动一下:

Info operator ()(const std::string& str) const
{
  Info in
  {
    str, 0, false
  };
  Info ret;
  ptr->func(in, [&ret](auto result)
  {
    ret = result;
    return ret.success;
  });  //ptr, the pointer of the component
  return ret;
}

这里的代码为了简洁省略了第二部分介绍的类型系统相关内容.

对于左递归, 每一次递归在对访问计数count加一的同时保存下当前的分析结果, 在递归结束后依次调用Continuation, 直到分析成功便退出.

5. 垃圾回收

细心的小伙伴可能还会对内存管理的细节表示有疑问, 注意到所有的递归实现都是使用引用实现的, 如下的:

ParserCombinator<int> Number, Decimal;

Decimal = ('0'_T | '1'_T | '2'_T | '3'_T | '4'_T | '5'_T | '6'_T | '7'_T | '8'_T | '9'_T);
Number = Number + Decimal | Decimal;

如果Number和Decimal是定义在函数里的, 并且返回了Number, 这时Decimal将会被销毁, 那么引用将会失效, 将会产生运行时错误, 虽然我们可以手动返回一个结构把所有将会被调用到的语法分析器保存起来一起返回, 但这不优雅(笑~).

这个问题可以使用C++里的智能指针std::shared_ptr完成, 可以将所有的ParserCombinator和ParserCombinatorComponent的连接改成std::shared_ptr, 在进行构造ParserCombinatorComponent时遇到了ParserCombinator的话直接捕获ParserCombinator结构内保存的指向实现component的shared_ptr. 这样虽然不会出现空指针的问题, 但同时引入了另一个问题, 循环引用内存泄漏.

比如:

A = '1'_T + B
B = '2'_T + A | '3'_T

引用关系为:

注意环\((+_A)\rightarrow (B)\rightarrow (\;|\;)\rightarrow (+_B)\rightarrow (A)\rightarrow (+_A)\)

shared_ptr实现使用的引用计数在引用关系为有向带环图上将会失效, 环的出现将会造成内存泄漏, 解决方法为将该带环图转换为无环图, 思路并不复杂.

把A与B单独分开来看, 去除所有的递归引用关系, 只保留直接调用:

子图A与B是两颗有向树, 显然所有的节点的入度都是1, 意味着所有节点的存在性只依赖与父节点, 那么我们可以将递归引用控制权上移(如果该节点需要递归引用别的符号当且仅当该节点的父节点存在, 小伙伴可以思考一下为什么), 将递归控制权上移至树根:

这个时候转变成了无环图, 证明无环很容易:

考虑子图L和R, R中所有节点为所接节点的树根, 树是无环的, 再考虑子图S=L∪R, S为有向二分图, 所有边方向为由L至R, 假设存在环, 则必定存在一条由R至L的边, 矛盾. 证明完毕.

注: 若在上移过程中出现自我引用则删去该引用. 重复的相同引用则保留一个向上传递.

具体的C++实现并不困难, 只需要使用weak_ptr保存递归引用, 然后在构造组合子过程中把两个子组合子中的weak_ptr保存在一起, 检查一下是否有自我引用和重复引用, 我使用unordered_map来实现的. 在到达树根后在ParserCombinator中lock所有weak_ptr并保存在一个vector里.

结语

花了几天写了这个实验性的Parser combinator, 这个Parser combinator可以看作是一个嵌入到C++里的微型的函数式DSL, 专门用于进行语法分析.

当初选在C++里写时因为C++提供了不错的工具, 操作符重载可以使得表达更优雅, 同时是静态类型的, 有模板作为工具来操作类型, C++11带来的Lambda也让构造更加直观. 但是开始写了之后我就后悔了, 现在看到模板都想吐了QAQ. 右值引用更是编码地狱, 直接让所有重载函数数目翻倍. 然后还有各种C++特性纠缠在一起带来的一些奇奇怪怪的问题. 这个Parser combinator的实现我尽可能的隐藏了内部的细节, 只将最简单的调用接口暴露了出来, 为了表达的优雅. 所以嘛, 最后就变成了调试地狱, 不说了让我一个人静静. (其实想想应该用Haskell写才对)

需要源码的小伙伴可以在这里下载: Parser Combinator [.zip]

代码是用C++17编写的, 大量运用了模板元编程和SFINAE等的现代C++技术. 无法在VS 2015里编译, 因为15版VS有奇怪的编译BUG, 我也不知道怎么才能绕过去. 最好使用Clang++编译, G++最好使用6以后的版本.

因为编码和调试难度过高, 我很难保证不会出些奇奇怪怪的BUG. 虽然我用起来好像没什么问题.

最后文章很长, 感谢各位小伙伴的耐心阅读. 文章里只讲了关键的实现思路, 省略了很多细节, 如果有什么疑问欢迎来找我哦.

谢谢啦~

附录. 其他功能:

还有一些其他前面没有介绍到的功能, 这里做个简单介绍:

以函数作为Token, 除了之前提到的用’c’_T或者”str”_T作为token来构造term以外还可以使用函数更加灵活地识别Token, 如下Decimal中识别数字字符就可以简单用一个isdigit代替:

Decimal = Token([](char ch) { return isdigit(ch); }) >>
    [](char ch)
{
    return ch - '0';
};

甚至写成更简单的形式:

Decimal = Token(isdigit) >>
    [](char ch)
{
    return ch - '0';
};

直接返回:

比如对于某些语法节点我们并不关系其值, 我们只需要其能完成分析就好了, 那么这时可以使用Return(val)直接返回一个值, 比如:

ParserCombinator<int> A;
A = '1'_T >> Return(1) | '2'_T >> Return(2);

在匹配到字符1时返回1, 匹配到字符1时返回2.

求值函数Val(ParserCombinator):

比如我们需要对现有的ParserCombinator添加成分的话使用函数Val, 接上面的代码:

A = A + '3'_T;
//A := A '3'

A = Val(A) + '3'_T;
//A := ('1' | '2') '3'

对比一下就知道Val的意思啦.

最后还有一个错误恢复:

A[([](std::string str, size_t index) 
{ 
    if (index == str.length()) 
        return Recovery(0, 0); 
    std::cout << "Fail: " << str[index] << std::endl; 
    return Recovery(1, 1); 
})];

使用中括号[]包围一个回調函数, 在该节点语法分析失败后会被调用, 两个参数, 第一个参数为当前分析的字符串, 第二个参数为当前分析失败的位置. 返回一个Recovery, 第一个参数为继续分析跳过的符号数目, 0则表示不恢复该错误, 第二个参数为错误恢复后的返回值.

还有更多的细节想了解的话也欢迎随时来找我.

Leave a Reply

Your email address will not be published. Required fields are marked *