AST construction in OCaml

Question

I use OCaml to create a recursive descent parser for a subset of the Schema. Here's the grammar:

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

So to speak, I have:

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

pseudo code

These functions must return an expr type for the AST assembly.

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

Using the first set of S, which are tokens and '(':

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

My question is: "How do I get back for the Epsilon part, since I just can't go back ()?". The OCaml function requires the same return type, and even if I leave it empty for the Epsilon part, OCaml still accepts the device type.

Answer 1

As far as I understand, your AST does not match your grammar.

You can solve this problem by specifying a special empty node in your AST type to represent Epsilon in your grammar.

Or, you can change your grammar to split Epsilon.

Here's the equivalent grammar without Epsilon:

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

Answer 2

Perhaps, instead of creating parser functions manually, it is better to use existing approaches: for example, LALR (1) ocamlyacc or camlp4 based on LL (k) parsers ?