Parsing grammars using OCaml

Question

I have a task to write a (toy) parser for a (toy) grammar using OCaml and not sure how to start (and proceed with) this problem. Here's a sample Awk grammar: ``` type ('nonterm, 'term) symbol = N of 'nonterm | T of 'term;; type awksub_nonterminals = Expr | Term | Lvalue | Incrop | Binop | Num;; let awksub_grammar = (Expr, function | Expr -> [[N Term; N Binop; N Expr]; [N Term]] | Term -> [[N Num]; [N Lvalue]; [N Incrop; N Lvalue]; [N Lvalue; N Incrop]; [T"("; N Expr; T")"]] | Lvalue -> [[T"$"; N Expr]] | Incrop -> [[T"++"]; [T"--"]] | Binop -> [[T"+"]; [T"-"]] | Num -> [[T"0"]; [T"1"]; [T"2"]; [T"3"]; [T"4"]; [T"5"]; [T"6"]; [T"7"]; [T"8"]; [T"9"]]);; ``` And here's some fragments to parse: ``` let frag1 = ["4"; "+"; "3"];; let frag2 = ["9"; "+"; "$"; "1"; "+"];; ``` What I'm looking for is a rulelist that is the result of the parsing a fragment, such as this one for frag1 ["4"; "+"; "3"]: ``` [(Expr, [N Term; N Binop; N Expr]); (Term, [N Num]); (Num, [T "3"]); (Binop, [T "+"]); (Expr…

Accepted Answer

Here is a rough sketch - straightforwardly descend into the grammar and try each branch in order. Possible optimization : tail recursion for single non-terminal in a branch.

```
exception Backtrack

let parse l =
  let rules = snd awksub_grammar in
  let rec descend gram l =
    let rec loop = function 
      | [] -> raise Backtrack
      | x::xs -> try attempt x l with Backtrack -> loop xs
    in
    loop (rules gram)
  and attempt branch (path,tokens) =
    match branch, tokens with
    | T x :: branch' , h::tokens' when h = x -> 
        attempt branch' ((T x :: path),tokens')
    | N n :: branch' , _ -> 
        let (path',tokens) = descend n ((N n :: path),tokens) in 
        attempt branch' (path', tokens)
    | [], _ -> path,tokens
    | _, _ -> raise Backtrack
  in
  let (path,tail) = descend (fst awksub_grammar) ([],l) in
  tail, List.rev path
```

Parsing grammars using OCaml

Solution

Problem