Building AST in OCaml

Question

Sto usando OCaml per creare un parser di discesa ricorsivo per un sottoinsieme di Scheme. Ecco la grammatica:

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

Quindi dire che ho:

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

Pseudocodice

Queste funzioni devono tornare espr tipo di costruire l'AST

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

Utilizzando First Set di S che sono token e '(':

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

La mia domanda è "Come ritorno per la parte Epsilon poiché non riesco a tornare()?". Una funzione OCaml richiede lo stesso tipo di restituzione e anche se per la parte Epsilon viene lasciato vuoto, OCaml assume ancora il tipo di unità.

Answer 1

Per quanto posso vedere, il tuo AST non corrisponde alla grammatica.

È possibile risolvere il problema avendo un nodo specificamente vuoto nel tipo AST per rappresentare Epsilon nella grammatica.

Oppure, è possibile modificare la grammatica per calcolare Epsilon.

Ecco una grammatica equivalente senza Epsilon:

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

Answer 2

Forse invece di creare manualmente le funzioni del parser è meglio utilizzare gli approcci esistenti: ad esempio LALR (1) ocamlyacc o LLL basato su camlp4 (k) parsers?