logo标签列表

无扫描器解析器生成器

language-agnosticparser-generator
27

前言：尽管解析器（上下文无关语法）识别的语言集比扫描器（正则语法）识别的语言集严格更大，但大多数解析器生成器都需要一个扫描器。

（请不要试图解释背后的原因，我非常清楚）。

我见过一些不需要扫描器的解析器，例如：

不使用扫描器有一些优势：

  • 只需一个概念（上下文无关语法）而不是两个
  • 在一个文件中解析多种语言（如HTML / JavaScript）
  • 解析没有保留关键字的语言（如PL/1）

通常会使用“变通方法”，例如根据解析器请求切换扫描器。

问题：您知道其他无扫描器的解析器生成器吗（任何语言）？这些在使用中是否实用（还是纯学术性质）？除了Tomita/GLR之外，还有其他方法吗？

答案：

  • 由Norman Ramsey编写的解析表达式语法（Lua的LPEG）
  • Yakker由Norman Ramsey开发
  • MBase由SK-logic创建
  • Waxeye由Trevor Robinson设计
    • 这里列出了几个“广义自左向右最右推导分析器”，请参见http://en.wikipedia.org/wiki/Comparison_of_parser_generators#Context-free_languages。 - stacker
    @stacker：维基百科将DParser的词法分析器列为“生成的”；而GLR并不意味着无扫描仪。 - Meinersbur
    我不明白为什么扫描器会对多语言或没有保留关键字的语言构成障碍。扫描器仍然可以用于消耗空格和（至少经常）注释，并将字符连接成数字和单词，因此仍然很有用。 - David Thornley
    1
    尝试使用生成的解析器解析HTML了吗？在<testarea></textarea>中，甚至空格也很重要。当遇到<textarea>时，可以动态地交换扫描器，但我认为这是一种丑陋的hack。（SableCC支持此功能） - Meinersbur
    我问过，为什么你没有将解析器组合归类为无扫描器类别。也许你可以回答这个问题。 - Valentin Tihomirov
    Rekex - 语法作为代数数据类型 - github.com/zhong-j-yu/rekex - ZhongYu
    6个回答
    11

    解析器生成器不需要扫描程序。但如果您不使用扫描程序，那么您就相当疯狂。

    由解析器生成器构建的解析器不关心您输入什么，只要您称其为标记即可。

    如果要在没有扫描程序的情况下使用解析器生成器，请将语法定义到字符级别，并将单个字符作为标记提供给解析器。

    这种做法之所以疯狂，是因为解析比词法分析更复杂。您可以将词法分析程序构建为有限状态机，这些有限状态机基本上会转换成“比较并跳转到下一个状态”的机器代码。就速度而言，这很难被超越。解析器生成器构造的解析器则执行递归下降预测解析（对于大多数LL生成器，例如ANTLR），或通过哈希、二进制或线性搜索等进行表查找。因此，与字符词法分析相比，解析器对标记的处理要花费更多的能量。

    如果将字符作为标记提供给解析器，则解析器会花费与等效词法分析程序相比更多的能量来处理字符。如果您处理大量输入文本，这最终会产生影响，无论是在数百万个小输入流还是在几个非常大的输入流上进行。

    所谓的无扫描GLR解析器相对于设计用于使用标记的GLR解析器而言具有这种性能问题。

    我的公司开发了一款工具，DMS软件重构工具包，它使用GLR分析器（并成功解析了您知道的所有常见语言和许多您不知道的奇怪语言，因为它具有GLR分析器）。我们知道无扫描仪解析器，但由于速度差异，我们选择不实现它们，我们拥有经典风格（但极其强大）的类似LEX子系统来定义词汇标记。在DMS与处理相同输入的基于XT（具有无扫描仪GLR分析器的工具）的工具进行对比的一个案例中，DMS似乎比XT包快10倍。公平地说，所做的实验是临时的而未被重复，但与我的怀疑相匹配，我认为没有理由再次进行测试。YMMV。

    当然，如果我们想进入无扫描仪领域，那么使用字符终端符号编写语法就相当容易了，正如我已经指出的那样。

    GLR无扫描仪解析器确实具有另一个对大多数人无关紧要但非常好的属性。您可以针对无扫描仪解析器编写两个单独的语法，并将它们直接连接起来，仍然可以获得一个解析器（通常具有许多歧义）。当您正在构建嵌入在另一种语言中的语言时，这很重要。如果这不是您正在进行的操作，则这只是一种学术好奇心。

    至于Elkhound是否无扫描仪，据我所知，不是。（编辑：2/10：看起来我错了。这不会是我生命中的第一次错误：）

    1
    感谢您的回答，特别是关于您在行业中的经验报告。 请注意，线性速度差异并不是主要障碍。否则，没有人会用脚本语言编写扫描器。 但是，对于需要无限前瞻（O(n³)）的语法，如标识符令牌，GLR可能导致非线性性能。如果解析器可以处理具有线性复杂度的令牌（并且有相关概念），为什么还要费心编写扫描器呢？ - Meinersbur
    无扫描仪的Elkhound: http://scottmcpeak.com/elkhound/sources/elkhound/examples/scannerless/ - Meinersbur
    @Meinersbur：我不明白你的观点。你似乎是在说扫描器无法处理标识符时会失去线性性；这表明你同意使用无扫描器解析器并不是一个好主意。但接着又说，“为什么费劲写一个扫描器呢？”我错过了什么吗？ - Ira Baxter
    我在某种程度上同意，使用GLR进行无扫描解析并不是最好的选择。但是其他概念（非规范解析、LR-Regular语法、ELR解析等）呢？是否有使用这些概念而具有线性复杂度的实现？ - Meinersbur
    1
    如果语法中存在真正的歧义或局部歧义（需要长距离前瞻来解决），无论是由于终端字符规则还是传统的非终端符号引起的，我认为您不应该期望线性时间的保证。当然，您可能能够编写您的语法以确保没有歧义。在这种情况下，我不知道什么是可能的，但是为了实现这样的属性而打乱您的语法的行为将使得解析技术变得更加无聊。GLR在理论上很昂贵；在实践中，它运作良好。 - Ira Baxter
    11

    另外两个：

    • Bryan Ford的解析表达式文法（PEG）不需要扫描器。高效、惰性的“packrat parser”是可选的。我在使用Lua LPEG版本时一直都有良好的体验，它编译成了一个高效的字节码机器。非常实用。

    • YAKKER看起来非常有趣，尽管它仍然明显处于预发布状态。他们正在使用他们声称的Earley解析算法的有效变体。

    实际上，我非常喜欢无扫描器解析器；它们极大地简化了配置。而典型的扫描器生成器，委婉地说，使用起来并不好玩。从Lex的手册中可以看到：

    消灭这种恐龙的小行星仍在轨道上。

    最后，我没有使用过Elkhound，但我听到的二手报告印象深刻。我会说，毫无疑问，某些无扫描器解析器生成器非常实用。

    3

    boost::spirit::qi是一款不需要词法分析器的解析器，但你可以使用boost::spirit::lex作为前端。根据boost::spirit::lex的介绍:

    实际上，Spirit.Qi允许您直接解析输入字符流，而无需使用词法分析器，这也是Spirit自发明以来一直被使用的方式。

    boost::spirit（最初版本）确实完全符合您的要求，但它已经移动到了boost::spirit::classic中。 spirit::qi，spirit::lex是Spirit的新设计，因此我将古典版本留了出来 :)

    3
    1
    没关系 - 我对每一个答案都感到高兴。 - Meinersbur
    0

    我编写了一个“按需扫描”解析器。

    它是一种介于带有扫描器的解析器和无扫描器解析器之间的折衷方案。

    它允许“没有保留关键字”，并使一种语言嵌入/嵌套在另一种语言中成为可能。

    这种嵌套的一个很好的例子是来自graphviz的Dot语法https://graphviz.gitlab.io/，其中XML / HTML可以嵌入到外部图形语言中。

    您可以在https://info.itemis.com/demo/agl/editor上查看我的解析器和Dot语法的演示

    有关解析器的更多详细信息，请参见https://medium.com/@dr.david.h.akehurst/a-kotlin-multi-platform-parser-usable-from-a-jvm-or-javascript-59e870832a79

    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接