在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仍然采用单元类型.

Answer 1

据我所知,你的AST与你的语法不符.

您可以通过在AST类型中使用特定空节点来表示语法中的Epsilon来解决问题.

或者,您可以更改语法以分解Epsilon.

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

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