8

PS.在哪里阅读解析理论？

4

11 回答 11

12

总结：最短的大概是Antlr。

去龙书学习解析理论很诱人。但我不认为龙书和你对“理论”的含义有相同的想法。Dragon Book 描述了如何构建手写解析器、解析器生成器等，但您几乎可以肯定想要使用解析器生成工具。

一些人建议使用 Bison 和 Flex（或者他们的旧版本 Yacc 和 Lex）。这些都是老顽固，但它们不是非常有用的工具。他们的文档本身并不差，只是它对处理使用它们的意外复杂性并没有太大帮助。他们的内部数据没有很好地封装，很难用他们做任何高级的事情。例如，在phc中我们仍然没有正确的行号，因为这非常困难。当我们修改语法以包含 No-op 语句时，它们变得更好了，但这是一个令人难以置信的 hack，不应该是必要的。

从表面上看，Bison 和 Flex 可以一起工作，但界面很尴尬。更糟糕的是，每个版本都有很多版本，只能与其他的某些特定版本很好地配合。而且，最后我至少检查了哪些版本的文档非常差。

编写递归下降解析器很简单，但可能很乏味。Antlr 可以为您做到这一点，它似乎是一个非常好的工具集，其好处是您在这个项目中学到的东西可以应用于许多其他语言和平台（Antlr 非常便携）。还有很多现有的语法可供学习。

目前尚不清楚您正在使用哪种语言，但有些语言具有出色的解析框架。特别是，Haskell Parsec Library看起来非常优雅。如果您使用 C++，您可能会想使用Spirit。我发现它很容易上手，但很难——但仍然可能——用它来做一些高级的事情。这符合我对 C++ 的总体经验。我说我发现它很容易开始，但是我已经写了几个解析器，并在编译器类中研究了解析。

长话短说：Antlr，除非你有很好的理由。

于 2009-10-10T00:00:31.953 回答
11

阅读《龙书》总是一个好主意。但是请注意，如果您的语言不是微不足道的，那么就没有真正的“短”方法来做到这一点。

于 2009-10-04T13:35:18.390 回答
5

这取决于您的语言。一些非常简单的语言只需要很少的解析，因此可以手动编码；其他语言使用 PEG 生成器，例如Rats！（PEG 是解析器表达式语法，它位于 Regex 和 LR 解析器之间）或传统的解析器生成器，例如 Antlr 和 Yacc。不太正式的语言需要概率技术，例如链接语法。

于 2009-10-04T13:38:41.953 回答
4

编写递归下降解析器。这有时比 YACC/BISON 更容易，而且通常更直观。

于 2009-10-04T13:52:35.057 回答
3

Douglas Crockford 有一个用 JavaScript 编写的解析器的平易近人的例子。

于 2009-10-10T00:19:18.677 回答
2

YACC，对于不同的语言有不同的实现。

祝你的语言好运 ;-)

于 2009-10-04T13:28:27.953 回答
2

我使用了GOLD Parsing System，因为对于像我这样的新手来说，它似乎比 ANTLR 更容易使用，同时仍然具有足够的功能来满足我的需求。该网站包括文档（包括关于写作语法的说明，这是工作的一半）以及软件。

于 2009-10-04T13:44:03.443 回答
2

尝试使用Bison进行解析，使用Flex进行词法分析

您的语言的野牛定义采用上下文无关语法的形式。关于这个主题的维基百科文章非常好，可能是一个很好的起点。

于 2009-10-04T13:46:00.073 回答
1

为您的宿主语言使用解析器生成器是最快的方法，结合诸如Dragon Book或 {C,ML} 系列中的 Modern Compiler Construction 等书籍的解析理论。

如果您使用 C，yacc并且 GNU 版本bison是标准生成器。Antlr 广泛用于多种语言，据我所知支持 Java、C# 和 C++。几乎所有语言中还有许多其他语言。

目前我个人最喜欢的是Menhir，一个优秀的 OCaml 解析器生成器。ML 风格的语言（Ocaml、Standard ML 等）方言通常非常适合构建编译器和解释器。

于 2009-10-10T00:32:43.007 回答
1

对于没有编译器理论背景的人来说，ANTLR 是最简单的，因为：

  • ANTLRWORKS（可视化解析和 AST 调试）

  • ANTLR 书（无需编译器理论背景）

  • 词法分析器和解析器只有 1 种语法。

于 2009-10-10T08:24:27.307 回答
1

如果您对解析表达式语法感到满意，那么编写自己的解析器可能会非常短。这是一个简单的 Packrat 解析器，它采用合理的 PEG 子集：

import functools

class peg_parse:
    def __init__(self, grammar):
        self.grammar = {k:[tuple(l) for l in rules] for k,rules in grammar.items()}

    @functools.lru_cache(maxsize=None)
    def unify_key(self, key, text, at=0):
        if key not in self.grammar:
            return (at + len(key), (key, [])) if text[at:].startswith(key) \
                else (at, None)
        rules = self.grammar[key]
        for rule in rules:
            l, res = self.unify_rule(rule, text, at)
            if res is not None: return l, (key, res)
        return (0, None)


    def unify_line(self, parts, text, tfrom):
        results = []
        for part in parts:
            tfrom, res = self.unify_key(part, text, tfrom)
            if res is None: return tfrom, None
            results.append(res)
        return tfrom, results

它接受 python 字典形式的语法，以非终结符作为键，替代作为数组的元素，每个替代都是一个表达式序列。下面是一个示例语法。

term_grammar = {
    'expr': [
        ['term', 'add_op', 'expr'],
        ['term']],
    'term': [
        ['fact', 'mul_op', 'term'],
        ['fact']],
    'fact': [
        ['digits'],
        ['(','expr',')']],
    'digits': [
        ['digit','digits'],
        ['digit']],
    'digit': [[str(i)] for i in list(range(10))],
    'add_op': [['+'], ['-']],
    'mul_op': [['*'], ['/']]
}

这是驱动程序：

import sys
def main(to_parse):
    result = peg_parse(term_grammar).unify_key('expr', to_parse)
    assert (len(to_parse) - result[0]) == 0
    print(result[1])

if __name__ == '__main__': main(sys.argv[1])

可以这样调用：

python3 parser.py '1+2'
('expr', 
    [('term', 
       [('fact', 
           [('digits', [('digit', [('1', [])])])])]), 
     ('add_op', [('+', [])]), 
     ('expr', 
       [('term', [('fact', [('digits', [('digit', [('2', [])])])])])])])

Parsing Expression Grammars 需要注意编写：备选方案的顺序很重要（与上下文无关语法不同，备选方案是有序的选择，首先尝试第一个选择，只有在第一个不匹配时才尝试第二个选择）。但是，它们可以表示所有已知的上下文无关文法。

另一方面，如果您决定使用上下文无关语法，Earley Parser是最简单的语法之一。

于 2018-12-07T10:38:01.257 回答