使用OCaml解析语法

Question

我有一个任务，使用OCaml为（玩具）语法编写（玩具）解析器，并且不知道如何开始（并继续）这个问题。

这里有一个样品在awk语法：

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

和这里的一些片断解析：

let frag1 = ["4"; "+"; "3"];; 
let frag2 = ["9"; "+"; "$"; "1"; "+"];; 

我正在寻找的是一个rulelist那就是解析片段的结果，比如这个用于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"])] 

的限制是不使用比列表中的其他任何OCaml的库...：/

Answer 1

我不知道，如果你明确要求派生树，或者如果这是这只是解析的第一步。我假设后者。

您可以通过定义类型来定义生成的抽象语法树的结构。它可能是这样的：

type expr = 
    | Operation of term * binop * term 
    | Term of term 
and term = 
    | Num of num 
    | Lvalue of expr 
    | Incrop of incrop * expression 
and incrop = Incr | Decr 
and binop = Plus | Minus 
and num = int 

然后，我会实现一个递归下降解析器。当然，它会好得多，如果你可以使用streams与预处理camlp4of结合...

顺便说一句，有大约OCaml的文档here在算术表达式中的一个小例子。

Answer 2

好吧，所以第一个想你应该做的就是编写一个词法分析器。这是 函数采用'原始'输入，如["3"; "-"; "("; "4"; "+"; "2"; ")"], ，并将其拆分为令牌列表（即终端符号的表示形式）。

可以定义一个令牌是

type token = 
    | TokInt of int   (* an integer *) 
    | TokBinOp of binop  (* a binary operator *) 
    | TokOParen    (* an opening parenthesis *) 
    | TokCParen    (* a closing parenthesis *)  
and binop = Plus | Minus 

的类型lexer功能将string list -> token list和

lexer ["3"; "-"; "("; "4"; "+"; "2"; ")"] 

的输出中会像

[ TokInt 3; TokBinOp Minus; TokOParen; TokInt 4; 
    TBinOp Plus; TokInt 2; TokCParen ] 

这将使解析器的编写工作变得更容易，因为你不会必须 担心识别什么是整数，什么是运营商等。

这是第一个，不是太困难的步骤，因为令牌已经分开。 词法分析器所要做的就是识别它们。

完成此操作后，您可以编写一个类型为string -> token list的更现实的词法分析器，它需要实际的原始输入（例如"3-(4+2)"）并将其转换为令牌列表。

Answer 3

这是一个粗略的草图 - 直接下降到语法并尝试每个分支的顺序。可能的优化：分支中单个非终端的尾递归。

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