使用OCaml解析语法 [英] Parsing grammars using OCaml

问题描述

我有一个任务是使用OCaml为(玩具)语法编写(玩具)解析器，并且不确定如何启动(并继续)此问题.

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.

以下是Awk语法示例:

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"; "+"];;

我要寻找的是一个规则列表，该规则列表是解析片段的结果，例如，这个片段用于frag1 ["4"; "+"; "3"]:

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, [N Term]);
  (Term, [N Num]);
  (Num, [T "4"])]

限制是不使用List ...以外的任何OCaml库::/

The restriction is to not use any OCaml libraries other than List... :/

推荐答案

这是一个粗略的草图-直接进入语法并按顺序尝试每个分支.可能的优化:分支中单个非终端的尾递归.

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

这篇关于使用OCaml解析语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！