上环证明样本（Parser）

上环证明样本：Parsercombinator在C 里的DSL

如果你对编译原理有一点了解，我相信你必须知道语法和语法分析(Parsing)语法分析算法也见过语法分析器(Parser).当需要处理语言时，语法分析是一个必不可少的阶段，但即使是递归下降算法，实现语法也非常繁琐LL当语法复杂时，家庭会变得非常繁琐和单调，更不用说对编码不友好了LR家族算法了.许多朋友会选择使用语法器生成器(Parsergenerator)编译生成语法分析器，输入文法及相关操作输出语法分析器的源代码.这是一个很好的方法，我相信我们都知道，这里介绍另一种很少理解的方法：语法分析器组合子(Parsercombinator).

首先，我们知道语法分析器是函数，输入需要分析的字符串或符号串(Tokenseries)如果输出是语法结构或语义，语法分析器的类型可以定义为：

α语法结构或语义值的类型，如抽象语法树(AST),或者如在之前的文章里的四则运算的Parser在分析过程中，相应的语义值(即表达式计算结果)直接用文法的综合属性计算，数字返回.第二个的String对于剩余需要分析的字符串.

然后我们可以把这个计算器看作是语法分析器的例子(instance),类型为:

这很容易理解.朋友们，我们发现没有喵喵。在这里，我们关注的不是特定语法分析器及其实现，而是语法分析器的抽象.我们关心的是如何进行对某个串的结构分析而不是如何计算语义值.我们在这里分开了两者。.

语法分析器还不够，我们需要在其域定义操作(就像我们有数字是不够的，我们需要加法和乘法操作).语法分析器的操作是语法分析器的组合子，也是全文的主题.语法分析器组合子是语法分析器的高级函数。简单的理解是接受语法分析器作为输入返回新的语法分析器。在这里，我们需要两个组合子连接组合子（ ）和或组合子(|),连接和或易于理解，直接对应于语法中的符号连接.

给出类型:

如果你对这里的类型运算加乘感到困惑，可以参考代数据类型()或者我的回答中有粗略的介绍.

构造表示:

最后，我们需要一个语法分析器单元(Termparser),这是语法中最基本的单位，对应于语法中的终止符.它是一个单位语法分析器，可以直接识别输入串中的符号，可以简单地理解，如前一篇文章Number符号与相应的函数，即是只接受0-9这10个字符返回数字.

构造表示:

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

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

构造表示:

另一种是语法解析器，不接受任何符号，返回空、类型和ε一样.

构造表示:

这在实践中没有用，也不会出现在文法中.因为它的代数意义，这里就提到一下.这样，我们就有了所有与文法相对应的结构.为什么这个定义是可行和有意义的，小心点，你可能会发现

形成阿贝尔群(Abeliangroup),其单位元素[0元素]为

构成一个半群(Monoid),其单元元素[1元素]为

然后类型构成一个环(Ring),如果您感兴趣，的性质和条件感兴趣，及的性质和条件.这里并不赘述了.此外，基于集合论，我们应该注意一些逆元素的存在，但不能构造.

这个组合子的结构很优雅吗？~

嗯，也许有些朋友对理论不感兴趣。让我们具体实现它。我在这里用的是C 实现:

首先给大家举个例子:

或者前一篇文章中的四个计算器，文法是:

组合子的使用非常优雅：

简单介绍一下ParserCombinator吃法，笑~

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

对于文法:

可以直接在C 代码写:

但是这里还是缺少一些东西，那就是Number Decimal我们需要指出这部分正在获得Number和Decimal这两种子语法语义值后的语义是如何计算的？.使用>>指定回调函数：

这是个Lambda表达式表示我们已经分析过了Number后面还有一个数字，那我们就把它拿走Number乘10补这个位数Decimal.然后返回，作为返回值Number Decimal这部分文法的返回值.

最终的完整实现是：

你应该知道如何使用它。

那么这个东西是怎么实现的呢？这个东西太复杂了，我不能面面俱到。我将告诉你所有的细节，我主要关注核心实现和概念.具体分为几个部分：

首先，它分为两部分，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|实现大致如下:

对于单位元(Termparser)的实现大致如下:

这里使用了C 11的userdefinedliteral特性,可直接添加字符_T来生成一个Tokencomponent.

需要递归的实现为(operator 为例):

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

注：这里忽略了语义值，将在下面的第二部分讨论。

调用的ParserCombinator入口如下：

由于C 可以推导模板函数的参数类型，为组合子添加一套类型系统，限制组合子在编译期间的语义类型.

一是推导规则如下：

如果不太了解上面的推导规则也没关系。C 解释方法：

首先要建立代数据类型的基础设施，建立两种基本类型的结构和操作：

ProductTypes对应类型乘积，.AdditionTypes对应类型的和，可以理解为笛卡尔乘积类型或列表类型.

ProductTypes实现大致如下：

例如，我现在必须这么做。int和char相乘，那就是：

AdditionTypes实现大致如下：

举例来说,比如我现在要对int和char加起来就是：

对int和int加起来就是：

利用多重继承和std::is_base_of判断是否已经改变了类型，以确保重复类型不会进入AdditionTypes.

注:AdditionTypes里的数据成员Any类型可以容纳任何类型，完整的实现可以参考我之前的回答

拥有类型和积累后，我们可以很容易地使用模板来推导喵喵的类型，第一部分operator 和operator|模板形式：

简单的直觉理解就是语法

A=B C

A=B|C

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

然后我们在第一部分提到了structInfo加一个成员

用于保存返回的语义值，这里使用Any类型擦除的目的是在不改变的情况下解耦structInfo成员可以容纳任何类型的语义值，structInfo它可以在不复杂的情况下在递归函数之间任意传输cast逻辑.

同时在operator 将获得的值用于内部std::tuple_cat添加到ProductTypes的_Data里就好.

回调函数部分在拥有类型系统后很容易实现：

有了类型系统和推导，我们可以确保我们的调用是正确的类型.

记忆技巧可以参考我之前的文章

朋友们可能已经发现上面四个计算器中有左递归，我们的语法分析组合子显然是递归下降算法，所以我们需要做一些处理来兼容左递归语法.

实现记忆化后，在同一位置再次调用同一语法时，会直接在表中提取出值返回，而不是再次求值，这样，语法分析就可以在线性时间内完成.同时，需要注意的是，记忆化的实现为解决左递归问题提供了工具，并在第一次访问语法非终止符时在记忆表上标记访问次数count=1.如果有左递归，再次进入修改法时会发现标记，说明左递归发生了。如果选择不兼容左递归，可以直接抛出左递归异常.

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

值得注意的是，自底向上分析的结果不一定是唯一的。你可以使用最长的匹配原则来确定分支。当然，你可以引入向前的符号或其他不同的方式来选择决策，甚至继续推迟决策，直到信息足够.或者回溯，回溯实现技术将在下一节说明.

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

这里就不赘述更多细节了。感兴趣的朋友可以阅读
论文:

{n}

如果对CPS不熟悉的小伙伴可以看看我之前的文章和Wiki.这里就不做更多介绍啦.

{n}

由于我们的ParserCombin