c - C 中解析器组合器的更好方法？

Question

我正在尝试从头开始引导(C 的一个子集)，而不使用额外的依赖项(解析器生成器、库等)。我也想利用 parser combinators 的想法，这是函数式编程中的一项绝妙技术。我想以简洁实用的方式将函数世界中的这个想法借用到过程 C 中。

我尝试为以下玩具语法实现一些必要的解析器组合器，这也是 Simon Peyton Jones 的书 Implementing Functional Languages - a tutorial 中的示例。

greeting -> hg person "!"
hg       -> "hello"
          | "goodbye"

其中 person 是以字母开头的任何标记。例如 token 列表

["goodbye", "James", "!"]

解析成

[(("goodbye", "James"), ["!"])]

(本书使用 Haskell，很难让它与语言无关，但你明白了 :-)

我用 C 实现了这个，你可以在这里查看代码:https://gist.github.com/4451478

这个实现花费了 200 多行 C 代码，远远超过书中写的约 20 行 Haskell。所以我不确定我是否在正确的轨道上用 C 做解析器组合器，以及是否有任何可能的改进。欢迎任何建议。提前致谢。

Answer 1

我正在研究这个主题，我正在关注 Daniel Holden 的工作，mpc 的作者，这是一个写得很好的 C 语言 parser combinator 库，除其他外，它允许嵌入 EBNF 和 C 代码中的正则表达式:

  mpc_parser_t *Expr  = mpc_new("expression");
  mpc_parser_t *Prod  = mpc_new("product");
  mpc_parser_t *Value = mpc_new("value");
  mpc_parser_t *Maths = mpc_new("maths");

  mpca_lang(MPCA_LANG_PREDICTIVE,
    " expression : <product> (('+' | '-') <product>)*; "
    " product : <value>   (('*' | '/')   <value>)*;    "
    " value : /[0-9]+/ | '(' <expression> ')';         "
    " maths : /^/ <expression> /$/;                    "
    Expr, Prod, Value, Maths, NULL);

Daniel Holden 也写了一篇在线文章 book他在那里展示了使用他的库编写新语言是多么容易。这本书的标题是“构建你自己的 Lisp”。我认为您会发现这对您的项目非常有用。最后但同样重要的是，在库的示例中，有一个现成的程序可以为 C 的子集生成解析器。;-)