parsing - 在 OCaml 中构建 AST

Question

我正在使用 OCaml 为 Scheme 的子集构建递归下降解析器。这是语法：

    S -> a|b|c|(T)
    T -> ST | Epsilon

所以说我有：

   type expr = 
       Num of int | String of string | Tuple of expr * expr

伪代码

这些函数必须返回 expr 类型来构建 AST

parseS  lr =
   if head matches '(' then
     parseL lr
   else
     match tokens a, b, or c

使用第一组 S，它们是令牌和 '('：

parseL lr = 
   if head matches '(' or the tokens then
       Tuple (parseS lr, parseL lr)
  else
       match Epsilon

我的问题是“我如何返回 Epsilon 部分，因为我无法返回 ()？”。OCaml 函数需要相同的返回类型，即使我将 Epsilon 部分留空，OCaml 仍然采用单位类型。

score 6 · Accepted Answer

据我所知，您的 AST 与您的语法不符。

您可以通过在 AST 类型中使用一个专门的空节点来表示语法中的 Epsilon 来解决问题。

或者，您可以更改语法以排除 Epsilon。

这是一个没有 Epsilon 的等效语法：

S -> a|b|c|()|(T)
T -> S | S T

score 4 · Accepted Answer

也许与其手动创建解析器函数，不如使用现有的方法：例如，基于 LALR(1) ocamlyacc或 camlp4 的 LL(k)解析器？

2 回答 2