在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

我的问题是，“既然我回不来()，那我该怎么回去呢？”OCaml函数需要相同的返回类型，即使对Epsilon部件保留空白，OCaml仍然采用单元类型。

Answer 1

据我所见，你的AST与你的语法不匹配。

您可以通过在AST类型中有一个特定的空节点来表示语法中的Epsilon来解决这个问题。

或者，你也可以改变你的语法，把Epsilon分解出来。

这里有一个没有Epsilon的等价语法：

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

Answer 2

与其手工创建解析器函数，不如使用现有的方法:例如，LALR(1) 八聚氰或基于camlp4的LL(k) 解析器？