编程语言语法的每种方法有哪些特定的优点和缺点?为什么/何时应该使用发电机?

评论

试一试Boost.Spirit Qi。

#1 楼

确实有三个选项,这三个选项在不同情况下更可取。
选项1:解析器生成器,或者“您需要解析某种语言,而只是想让它正常工作,该死”
说,现在要求您为某些古老的数据格式构建一个解析器。或者您需要解析器要快。或者您需要解析器易于维护。
在这种情况下,最好使用解析器生成器。您不必摆弄细节,也不必获取大量复杂的代码即可正常工作,您只需写出输入所要遵循的语法,编写一些处理代码并预先保存:即时解析器。 br />优点很明显:

(通常)编写规范非常容易,尤其是在输入格式不太奇怪的情况下(如果选择2,则更好)。 br />最终您将获得易于维护的易于理解的工作:语法定义的流程通常比代码自然得多。书面代码。手写代码可以更快,但是只有在您了解您的知识之后,这就是为什么最广泛使用的编译器使用手写递归下降解析器的原因。
您需要注意一件事使用解析器生成器:有时可以拒绝您的语法。有关各种类型的解析器以及它们如何咬您的概述,您可能要从这里开始。在这里,您可以找到许多实现的概述以及它们接受的语法类型。
选项2:手写解析器,或者“您想构建自己的解析器,并且关心对用户友好”
解析器生成器很好,但是它们对用户(最终用户而不是您)不是很友好。通常,您无法提供良好的错误消息,也无法提供错误恢复功能。也许您的语言很奇怪,并且解析器拒绝了您的语法,或者您需要的控制权超出了生成器的能力。
在这些情况下,最好使用手写递归下降解析器。尽管正确处理可能很复杂,但是您可以完全控制解析器,因此您可以执行解析器生成器无法完成的各种出色工作,例如错误消息甚至错误恢复(尝试从C#文件中删除所有分号:C#编译器会抱怨,但无论分号是否存在,无论如何都会检测到大多数其他错误。
假设解析器的质量足够高,手写解析器通常也比生成的解析器性能更好。另一方面,如果您通常由于缺乏经验,知识或设计而导致编写解析器失败(通常是由于这些因素的结合),那么性能通常会变慢。但是对于词法分析器而言,情况恰恰相反:通常生成的词法分析器使用表查找,从而使它们比(大多数)手写查找器更快。毕竟,您必须编写越来越复杂的代码,此外,您还必须确切地了解如何解析语言。另一方面,如果您想学习如何创建自己的语言(因此,要获得语言设计经验),则最好选择选项1或选项3:如果要开发一种语言,它可能会发生很大变化,选项1和3给您带来更轻松的时间。
选项3:手写的解析器生成器,或者'您正在尝试从该项目中学到很多东西,并且您不介意以一个漂亮的作品结尾您可以重用很多代码”
这是我目前要走的路:您编写自己的解析器生成器。虽然非常简单,但这样做可能会教给您最多的知识。我首先创建了自己的词法生成器。我通常从开始使用代码开始设计软件,因此我考虑了如何使用我的代码并编写了这段代码(在C#中):
Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    { // This is just like a lex specification:
      //                    regex   token
        new StringTokenPair("\+",  CalculatorToken.Plus),
        new StringTokenPair("\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\d+", CalculatorToken.Number),
    });

foreach (CalculatorToken token in
             calculatorLexer.GetLexer(new StringReader("15+4*10")))
{ // This will iterate over all tokens in the string.
    Console.WriteLine(token.Value);
}

// Prints:
// 15
// +
// 4
// *
// 10

输入字符串标记对使用算术堆栈的思想转换为相应的递归结构,以描述它们表示的正则表达式。然后将其转换为NFA(不确定性有限自动机),然后将其转换为DFA(确定性有限自动机)。然后,您可以将字符串与DFA进行匹配。
这样,您可以很好地了解词法分析器的工作原理。另外,如果您以正确的方式进行操作,则词法分析器生成器的结果可以与专业实现大致一样快。与选项2相比,您也不会失去任何表现力,而与选项1相比,您不会失去太多表现力。
我在1600多行代码中实现了lexer生成器。这段代码可以完成上述工作,但是每次启动程序时它仍会即时生成词法分析器:我将添加代码以将其写入磁盘。
如果您想知道编写自己的词法分析器,这是一个很好的起点。
解析器生成器
然后编写解析器生成器。我再次在这里参考有关各种解析器的概述-根据经验,解析器解析的越多,速度就越慢。
速度对我而言不是问题,我选择实现Earley解析器。事实证明,Earley解析器的高级实现速度是其他解析器类型的两倍。
作为快速打击的回报,您可以解析任何语法,甚至是模棱两可的语法。这意味着您不必担心解析器中是否存在任何左递归,或者移位-减少冲突是什么。如果结果的语法树无关紧要,也可以使用歧义语法更轻松地定义语法,例如,将1 + 2 + 3解析为(1 + 2)+3还是1都无关紧要+(2 + 3)。
这是使用我的解析器生成器的一段代码的样子:
Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    {
        new StringTokenPair("\+",  CalculatorToken.Plus),
        new StringTokenPair("\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\d+", CalculatorToken.Number),
    });

Grammar<IntWrapper, CalculatorToken> calculator
    = new Grammar<IntWrapper, CalculatorToken>(calculatorLexer);

// Declaring the nonterminals.
INonTerminal<IntWrapper> expr = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> term = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> factor = calculator.AddNonTerminal<IntWrapper>();

// expr will be our head nonterminal.
calculator.SetAsMainNonTerminal(expr);

// expr: term | expr Plus term;
calculator.AddProduction(expr, term.GetDefault());
calculator.AddProduction(expr,
                         expr.GetDefault(),
                         CalculatorToken.Plus.GetDefault(),
                         term.AddCode(
                         (x, r) => { x.Result.Value += r.Value; return x; }
                         ));

// term: factor | term Times factor;
calculator.AddProduction(term, factor.GetDefault());
calculator.AddProduction(term,
                         term.GetDefault(),
                         CalculatorToken.Times.GetDefault(),
                         factor.AddCode
                         (
                         (x, r) => { x.Result.Value *= r.Value; return x; }
                         ));

// factor: LeftParenthesis expr RightParenthesis
//         | Number;
calculator.AddProduction(factor,
                         CalculatorToken.LeftParenthesis.GetDefault(),
                         expr.GetDefault(),
                         CalculatorToken.RightParenthesis.GetDefault());
calculator.AddProduction(factor,
                         CalculatorToken.Number.AddCode
                         (
                         (x, s) => { x.Result = new IntWrapper(int.Parse(s));
                                     return x; }
                         ));

IntWrapper result = calculator.Parse("15+4*10");
// result == 55

(请注意,IntWrapper只是一个Int32,只是C#要求它是一个类,因此我不得不介绍一个包装器类)
我希望您看到上面的代码非常强大:可以解析出您能想到的任何语法。您可以在语法中添加任意代码位以执行许多任务。如果您设法使所有这些工作正常进行,则可以非常轻松地重用生成的代码来完成许多任务:想象一下使用这段代码来构建命令行解释器。

评论


我认为您低估了创建高性能解析器和词法分析器所需的工作量。

–user1249
2010-12-23 17:01

我已经完成了自己的词法生成器的构建,而当我决定实现另一种算法时,我与构建自己的解析器生成器相距甚远。我花了很长时间才能使所有功能正常工作,但是我再一次也没有追求“高性能”,只是“良好的性能”和“出色的渐进性能”-Unicode是获得良好运行时间的一个bit子。并且使用C#已经增加了性能开销。

–亚历克斯十Brink
2010-12-23 18:13

很好的答案。我会同意您的选择。 3由于您上述所有原因。但是我可能要补充一点,如果像我的情况那样,您也非常认真地设计一种语言,或者您还应该在尝试创建自己的语言的同时使用解析器生成器。这样您就可以在语言问题上抢先一步,并能够更快地了解自己的语言

–Lefteris
2012年12月16日下午4:41

还有第四个选择:解析器组合器。

–尤里·阿尔伯克基
2014-09-24 15:44

@AlextenBrink您碰巧有一个github帐户吗?我真的很想得到这个词法分析器/解析器。您所做的令人印象深刻的事情。

–贝鲁兹
2015年7月3日15:25



#2 楼

如果您从未写过解析器,我建议您这样做。这很有趣,您可以了解事物的工作方式,还可以欣赏解析器和词法分析器生成器在下次需要解析器时为您节省的精力。

我还建议您尝试阅读http://compilers.iecc.com/crenshaw/,因为它对操作方法具有扎实的态度。

评论


好的建议和非常有用的链接。

–马涅罗
2010年11月9日,18:50

#3 楼

编写自己的递归下降解析器的优点是,您可以针对语法错误生成高质量的错误消息。使用解析器生成器,可以产生错误并在某些点添加自定义错误消息,但是解析器生成器完全无法完全控制解析。

编写自己的解析器的另一个好处是是因为它更易于解析为与语法没有一对一对应关系的更简单表示形式。

如果语法是固定的,并且错误消息很重要,请考虑自己滚动,或至少使用解析器生成器为您提供所需的错误消息。如果语法在不断变化,则应考虑改用解析器生成器。在第一种情况下,他希望自己编写自己的递归下降解析器!

评论


我几乎不相信第一个实验应该使用解析器生成器。您给了我一些好处,可以切换到自定义解决方案。我尚未决定什么,但这是对我有帮助的有用答案。

–马涅罗
2010年11月9日,18:40



++这个答案正是我要说的。我已经建立了许多语言,并且几乎总是使用递归。我只会补充说,有时候我最需要的语言是通过在C或C ++(或Lisp)之上分层一些宏来构建的。

–迈克·邓拉维(Mike Dunlavey)
2010年11月9日在21:40



JavaCC被认为具有最好的错误消息。另外,请注意V8和Firefox上的JavaScript错误和警告消息,我认为它们没有使用任何解析器生成器。

–唐明
2010年11月13日在1:01

@SHiNKiROU:确实,JavaCC也使用递归下降解析并不是偶然的。

– Macneil
10 Nov 13'2:01

#4 楼

选项3:都不使用(滚动您自己的解析器生成器)
只是因为有理由不使用ANTLR,野牛,Coco / R,Grammatica,JavaCC,Lemon,Parboiled,SableCC,Quex等-这并不意味着您应该立即使用自己的解析器+词法分析器。
弄清楚为什么所有这些工具都不够好-为什么它们不能让您实现目标?
除非您确定语法中的古怪之处您要处理的是唯一的,不应该只为其创建一个自定义解析器+词法分析器。相反,创建一个可以创建所需内容的工具,但该工具也可以用于满足将来的需求,然后将其作为免费软件发布,以防止其他人遇到与您相同的问题。

评论


我同意先尝试解析器生成器,然后再尝试自定义解决方案,但是有哪些特定(缺点)优势?这几乎是一个一般性建议。

–马涅罗
2010年11月9日,18:34

这是一般性建议-但随后您问了一个一般性问题。 :P我将在明天对利弊进行一些更具体的介绍。

– Peter Boughton
2010年11月9日23:25

我认为您低估了创建自定义解析器和词法分析器所需的工作量。尤其是可重用的。

–user1249
2010-12-23 17:01

#5 楼

滚动自己的解析器会迫使您直接考虑语言的复杂性。如果该语言难以解析,则可能很难理解。

早期,由于高度复杂(有些人会说“遭受酷刑”)语言语法。 JOVIAL是一个特别糟糕的示例:它需要提前两个符号,而其他所有内容最多都需要一个符号。这使得为​​JOVIAL编译器生成解析器比预期的要困难得多(因为通用动力公司/ Fort Worth Division在为F-16程序购买JOVIAL编译器时学到了困难的方法。)如今,递归下降。通常是首选方法,因为它对于编译器编写者来说更容易。递归下降编译器极大地奖励了简单,简洁的语言设计,因为编写一种简单,干净的语言的递归下降解析器要比使用复杂的,混乱的语言要容易得多。

最后:您考虑过将语言嵌入LISP,并让LISP解释器为您完成繁重的工作? AutoCAD做到了这一点,发现这使他们的生活变得更加轻松。有很多轻量级的LISP解释器,有些是可嵌入的。

评论


推出自定义解决方案是一个有趣的论点。

–马涅罗
2010年11月9日18:46

非常好。作为补充,我将在Fortran之前添加Fortran要求几乎任意(整行)先行以解析事物的信息。但是当时,他们没有其他想法如何制作(或实现)一种语言。

– Macneil
2010年11月15日,0:14

步行是最好的交通工具,因为它使您有时间思考是否真正值得一去。也很健康。

–babou
2014年10月13日在12:20

#6 楼

我曾经为商业应用编写过一个解析器,并且我使用了yacc。有一个竞争性的原型,其中开发人员使用C ++手工编写了整个程序,而它的工作速度慢了大约五倍。抱歉-差不多是10年前了,所以我记不清了-用C语言编写了大约1000行。

我之所以手动编写词法分析器是解析器的输入语法。这是我的解析器实现必须遵守的要求,而不是我设计的要求。 (当然,我会对其进行不同的设计。更好!!)语法在很大程度上依赖于上下文,甚至词法依赖于某些地方的语义。例如,分号可以在一处成为令牌的一部分,而在另一处成为分隔符-基于对以前解析出的某些元素的语义解释。因此,我在手写词法分析器中“掩埋”了这种语义依赖性,这给了我一个相当简单的BNF,它很容易在yacc中实现。强大的抽象功能,使程序员可以根据终端,非终端,产品和类似内容进行思考。另外,在实现yylex()函数时,它帮助我专注于返回当前令牌,而不必担心它之前或之后的内容。 C ++程序员在字符级别上工作,没有这种抽象的好处,最终创建了一个更复杂,效率更低的算法。我们得出的结论是,较慢的速度与C ++本身或任何库无关。我们使用加载到内存中的文件来测量纯解析速度;如果我们遇到文件缓冲问题,则yacc并不是解决该问题的首选工具。它在一种特定情况下有效。

评论


我对手工实现C ++的速度慢了五倍感到好奇:也许这是不良的文件缓冲?它可以带来很大的不同。

– Macneil
2010年11月9日15:22

@Macneil:我要在答案中添加一个内容;评论太长。

– azheglov
2010年11月9日19:36



++好的经验。我不会过多地关注性能。好的程序很容易因无聊而不必要的事情而变慢。我已经写了足够多的递归下降解析器,知道不应该做什么,所以我怀疑是否有更快的方法。毕竟,需要阅读字符。我怀疑运行于表的解析器会慢一些,但可能不足以引起注意。

–迈克·邓拉维(Mike Dunlavey)
2010年11月9日在21:49



#7 楼

这完全取决于您需要解析的内容。您能否以自己的速度超过词法学习器的学习曲线?解析的内容是否足够静态以至于您以后不会后悔该决定?您是否发现现有的实施方案过于复杂?如果是这样,请尽情滚动自己的乐趣,但前提是您不要回避学习曲线。

最近,我真的很喜欢柠檬解析器,它可以说是最简单,最简单的。我曾经用过。为了使事情易于维护,我只将其用于大多数需求。 SQLite以及其他一些著名的项目都使用它。您可能会,如果是这样,为什么不做一个?我有一种感觉,您会回到使用现有的那种方法,但是如果必须的话,请挠痒痒:)

评论


+1表示“您能以比词法学习器更快的速度滚动自己的书吗?”

– bobah
2010年11月9日,9:31

是的,很好。

–马涅罗
2010年11月9日18:47

#8 楼

您是否考虑过Martin Fowlers语言工作台方法?引用文章


语言工作台对
等式所做的最明显改变是易于创建外部DSL。您不再需要
编写解析器。您必须定义
抽象语法-但这实际上是一个非常简单的数据建模步骤。另外,您的DSL获得了一个功能强大的IDE-尽管您确实必须花费一些时间来定义该编辑器。
生成器仍然是您必须要做的事,我的理解是是它
并没有比以往任何时候都容易。
但是,为
构建一个好而简单的DSL生成器是该练习中最简单的部分之一。


读到那句话,我想写自己的解析器的日子已经过去了,最好使用可用的一种库。掌握了库之后,将来创建的所有DSL都将从该知识中受益。另外,其他人也不必学习您的解析方法。

进行编辑以涵盖注释(和修订后的问题)

滚动自己的优势


您将拥有解析器,并通过一系列复杂的问题获得所有可爱的思考经验
您可能会想到其他人没有想到的特殊内容(不太可能,但您似乎就像一个聪明的家伙)
会让您陷入一个有趣的问题中

所以总之,当您想真正深入到严重困难的人的肠子中时,应该自己动手您强烈渴望掌握的问题。

使用他人库的优点


您将避免重新发明轮子(编程中的常见问题)您会同意的)
您可以专注于最终结果(闪亮的新语言),而不必太担心它的解析方式等
您会看到自己的语言运行得更快(但是您得到的回报将不是,因为不是您所有的人)

因此,如果您想获得快速的最终结果,请使用别人的图书馆。 />
总的来说,这取决于您要承担多少问题和解决方案。如果需要全部内容,请自己滚动。

评论


这是思考的绝佳选择。

–马涅罗
2010年11月9日18:49

@bigown编辑以更好地回答您的问题

–加里·罗(Gary Rowe)
2010年11月9日在21:29

#9 楼

这取决于您的目标。
您是否要学习解析器/编译器的工作方式?然后从头开始写自己的。这是您真正学会欣赏他们正在做的所有事情的唯一方法。我过去几个月一直在写一篇文章,这是一次有趣而宝贵的经历,尤其是“啊,所以这就是X语言做到这一点的原因……”片刻。
您需要快速整理一些内容吗?在截止日期前申请?然后也许使用解析器工具。
您是否需要在未来10年,20年甚至30年中扩展的东西?自己写,慢慢来。绝对值得。

评论


这是我在编译器上的第一篇工作,我在学习/实验,并且打算长期保持它。

–马涅罗
2010年11月9日20:19

#10 楼

编写自己的书的最大好处是,您将知道如何编写自己的书。使用yacc之类的工具的最大好处是,您将知道如何使用该工具。我是树梢小游戏的爱好者。

评论


没有特别的帮助。您可能还说过:“学习驾驶的优势在于可以驾驶。学习骑自行车的优点是您可以骑自行车。”

–泽林
2015年11月11日17:19

#11 楼

为什么不分叉一个开放源代码的解析器生成器并使其成为自己的呢?
如果不使用解析器生成器,那么如果对语言的语法进行了较大的更改,则代码将很难维护。
/>
在解析器中,我使用正则表达式(我的意思是Perl风格)来标记化,并使用一些便捷函数来提高代码的可读性。但是,解析器生成的代码可以通过制作状态表和较长的switch-case来加快速度,这可能会增加源代码的大小,除非您对它们进行编码。这是我的自定义解析器的两个示例:

https://github.com/SHiNKiROU/DesignScript-一种BASIC方言,因为我太懒了,无法以数组符号编写先行方式,所以我牺牲了错误消息的质量
https:// github.com/SHiNKiROU/ExprParser-一个公式计算器。注意奇怪的元编程技巧

#12 楼

“我应该使用这个久经考验的'轮子'还是重新发明它?”

评论


您说的这个“轮子”是什么? ;-)

–Jason Whitehorn
2010年11月9日,11:03

IMO对这个问题不是很好的意见。这只是不适合特定情况的一般建议。我开始怀疑area51.stackexchange.com/proposals/7848提案过早关闭。

–马涅罗
2010年11月9日,18:31



如果车轮从未被重新发明过,我们将不会每天以超过100kmph的速度行驶-除非您要建议在木轴上旋转的大块重石块比在轮胎中使用的现代轮胎的许多变体都要好这么多车?

– Peter Boughton
2010年11月9日23:25

这是一个正确的意见,这是正确的直觉。我认为,如果您可以列出特定的优点或缺点,那么这个答案可能会更有帮助,因为这种情况完全取决于具体情况。

– Macneil
2010年11月15日,0:12

@Peter:重新发明某些东西(意味着完全不同)是一回事,但是完善现有解决方案以满足其他要求则更好。我全力支持“改进”,但是回到图纸板上解决已经解决的问题似乎是错误的。

– JBR威尔金森
2010-11-15 23:55