2

我正在开发一个编译器（接近 C 的语言），我必须在 C 中实现它。我的主要问题是如何选择正确的解析方法以便在编写编译器时高效。

这是我目前的语法：http: //img11.hostingpics.net/pics/273965Capturdcran20130417192526.png

我正在考虑制作一个自上而下的解析器 LL(1)，如下所述：http: //dragonbook.stanford.edu/lecture-notes/Stanford-CS143/07-Top-Down-Parsing.pdf

考虑到这种语法，它是否是一个有效的选择，因为我知道我首先必须删除左递归规则。您还有其他建议吗？

谢谢你，门蒂内特

4

4 回答 4

2

构建解析器的最有效方法是使用特定工具，其存在的目的是构建解析器。它们曾经被称为编译器编译器，但现在焦点已转移（扩大）到语言工作台，它为您提供更多帮助来构建自己的语言。例如，几乎任何语言工作台都会立即为您的语言提供 IDE 支持和语法突出显示，只需查看语法即可。它们还极大地帮助调试您的语法和语言（您没想到左递归是您最大的问题，是吗？）。

在目前最好的支持和开发的语言工作台中，可以命名：

如果你真的这么想，或者如果你考虑自己编写一个解析器只是为了娱乐和体验，最好的现代算法是SGLR、GLL和Packrat。每一个都是持续半个世纪的算法研究的精髓，所以不要指望在一瞬间完全理解它们，也不要指望你会出现的前几个“修复”会带来任何好处和。但是，如果您确实提出了不错的改进，请不要犹豫与作者分享您的发现或以其他方式发表！

于 2013-04-19T08:24:53.527 回答
2

这里有很多答案，但他们把事情弄糊涂了。是的，有 LL 和 LR 解析器，但这不是你的选择。

你有语法。有一些工具可以在给定语法的情况下自动为您创建解析器。可敬的Yacc和Bison就是这样做的。他们创建了一个 LR 解析器（实际上是 LALR）。还有一些工具可以为您创建 LL 解析器，例如ANTLR。像这样的工具的缺点是它们不灵活。他们自动生成的语法错误消息很糟糕，错误恢复很困难，而且旧的鼓励你以一种方式分解你的代码——这恰好是错误的方式。正确的方法是让你的解析器吐出一个抽象语法树，然后让编译器从中生成代码。这些工具希望您混合解析器和编译器代码。

当您使用这样的自动化工具时，LL、LR 和 LALR 之间的功率差异确实很重要。你不能“欺骗”来扩大他们的权力。（在这种情况下，强大意味着能够为有效的上下文无关文法生成解析器。有效的上下文无关文法是为每个输入生成唯一的、正确的解析树，或者正确地说它与文法不匹配。）我们目前没有可以为每个有效语法创建解析器的解析器生成器。然而，LR 可以处理比任何其他类型更多的语法。无法处理语法并不是一场灾难，因为您可以以解析器生成器可以接受的形式重写语法。然而，如何做到这一点并不总是很明显，

存在 LL、LALR 和 LR 解析器的原因是很久以前，生成 LR 解析器的工作在时间和内存方面对现代计算机来说都是一项繁重的工作。（注意这是它需要生成解析器，这仅在您编写它时发生。生成的解析器运行得非常快。）但那是很久以前的事了。对于中等复杂的语言，生成 LR(1) 解析器所需的 RAM 远少于 1GB，而在现代计算机上则需要不到一秒钟的时间。出于这个原因，您最好使用 LR 自动解析器生成器，例如Hyacc。

另一种选择是您编写自己的解析器。在这种情况下，只有一个选择：LL 解析器。当这里的人说写 LR 很难时，他们低估了情况。人类几乎不可能手动创建 LR 解析器。您可能认为这意味着如果您编写自己的解析器，您将被限制使用 LL(1) 语法。但这并不完全正确。由于您正在编写代码，因此您可以作弊。您可以前瞻任意数量的符号，并且因为在您准备好并准备好之前您不必输出任何内容，因此抽象语法树不必匹配您正在使用的语法。这种作弊的能力弥补了 LL 和 LR(1) 之间失去的所有权力，而且通常还有一些。

手写解析器当然有其缺点。无法保证您的解析器实际上匹配您的语法，或者就此而言不检查您的语法是否有效（即识别您认为的语言）。它们更长，而且更不鼓励您将解析代码与编译代码混合使用。它们显然也只用一种语言实现，而解析器生成器经常用几种不同的语言输出它们的结果。即使他们不这样做，LR 解析表也可以用只包含常量的数据结构（比如 JSON）来表示，而实际的解析器只有 100 行代码左右。但是手写解析器也有好处。因为您编写了代码，所以您知道发生了什么，因此更容易进行错误恢复并生成合理的错误消息。

最后，权衡通常是这样的：

  • 对于一次性工作，使用 LR(1) 解析器生成器要好得多。生成器会检查你的语法，节省你的工作量，现代的会直接拆分抽象语法树，这正是你想要的。
  • 对于像 mcc 或 gcc 这样高度完善的工具，请使用手写的 LL 解析器。无论如何，您将编写大量单元测试来保护自己，错误恢复和错误消息更容易正确处理，并且它们可以识别更大类别的语言。

我唯一的另一个问题是：为什么是 C？编译器通常不是时间关键代码。如果你愿意让你的编译器运行得慢一点——例如我自己的Lrparsing ，有非常好的解析包可以让你在 1/2 的代码中完成工作。请记住，这里的“相当慢”的意思是“人类几乎察觉不到”。我想答案是“我正在处理的作业指定 C”。为了给你一个想法，当你放宽要求时，从你的语法到解析树变得多么简单。这个程序：

#!/usr/bin/python

from lrparsing import *

class G(Grammar):
  Exp = Ref("Exp")
  int = Token(re='[0-9]+')
  id = Token(re='[a-zA-Z][a-zA-Z0-9_]*')
  ActArgs = List(Exp, ',', 1)
  FunCall = id + '(' + Opt(ActArgs) + ')'
  Exp = Prio(
      id | int | Tokens("[]", "False True") | Token('(') + List(THIS, ',', 1, 2) + ')' |
      Token("! -") + THIS,
      THIS << Tokens("* / %") << THIS,
      THIS << Tokens("+ -") << THIS,
      THIS << Tokens("== < > <= >= !=") << THIS,
      THIS << Tokens("&&") << THIS,
      THIS << Tokens("||") << THIS,
      THIS << Tokens(":") << THIS)
  Type = (
      Tokens("", "Int Bool") |
      Token('(') + THIS + ',' + THIS + ')' |
      Token('[') + THIS + ']')
  Stmt = (
      Token('{') + THIS * Many + '}' |
      Keyword("if") + '(' + Exp + ')' << THIS + Opt(Keyword('else') + THIS) |
      Keyword("while") + '(' + Exp + ')' + THIS |
      id + '=' + Exp + ';' |
      FunCall + ';' |
      Keyword('return') + Opt(Exp) + ';')
  FArgs = List(Type + id, ',', 1)
  RetType = Type | Keyword('void')
  VarDecl = Type + id + '=' + Exp + ';'
  FunDecl = (
      RetType + id + '(' + Opt(FArgs) + ')' +
      '{' + VarDecl * Many + Stmt * Some + '}')
  Decl = VarDecl | FunDecl
  Prog = Decl * Some
  COMMENTS = Token(re="/[*](?:[^*]|[*][^/])*[*]/") | Token(re="//[^\n\r]*")
  START = Prog

EXAMPLE = """\
Int factorial(Int n) {
  Int result = 1;
  while (n > 1) {
    result = result * n;
    n = n - 1;
  }
  return result;
}
"""

parse_tree = G.parse(EXAMPLE)
print G.repr_parse_tree(parse_tree)

产生这个输出：

(START (Prog (Decl (FunDecl
  (RetType (Type 'Int'))
  (id 'factorial') '('
  (FArgs
    (Type 'Int')
    (id 'n')) ')' '{'
  (VarDecl
    (Type 'Int')
    (id 'result') '='
    (Exp (int '1')) ';')
  (Stmt 'while' '('
    (Exp
      (Exp (id 'n')) '>'
      (Exp (int '1'))) ')'
    (Stmt '{'
      (Stmt
        (id 'result') '='
        (Exp
          (Exp (id 'result')) '*'
          (Exp (id 'n'))) ';')
      (Stmt
        (id 'n') '='
        (Exp
          (Exp (id 'n')) '-'
          (Exp (int '1'))) ';') '}'))
  (Stmt 'return'
    (Exp (id 'result')) ';') '}'))))
于 2013-05-04T03:34:59.020 回答
1

感谢您提供所有这些建议，但我们最终决定使用与此处完全相同的方法来构建自己的递归下降解析器：http ://www.cs.binghamton.edu/~zdu/parsdemo/recintro.html

实际上，我们更改了语法以删除左递归规则，并且因为我在第一条消息中显示的语法不是 LL(1)，我们使用我们的令牌列表（由我们的扫描仪制作）进行前瞻更远。看起来它工作得很好。

现在我们在这些递归函数中构建了一个 AST。你有什么建议吗？提示？非常感谢。

于 2013-04-25T07:41:49.373 回答
0

最有效的解析器是 LR 解析器，而 LR 解析器有点难以实现。您可以使用递归下降解析技术，因为它更容易在 C 中实现。

于 2013-04-17T17:43:13.070 回答