Parsing gramatyki przy użyciu OCaml

Question

Mam zadanie napisać parser (zabawka) do gramatyki (zabawki) przy użyciu OCaml i nie wiem, jak rozpocząć (i kontynuować) ten problem.

Oto próbka awk gramatyka:

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

A oto niektóre fragmenty do analizowania:

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

Co szukam jest rulelist który jest wynikiem parsowanie fragment, taki jak ten dla 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"])] 

Ograniczenie jest, aby nie używać żadnych bibliotek SML inne niż lista ...:/

Answer 1

Nie jestem pewien, czy specjalnie wymagają drzewo różniczkowania, lub jeśli jest to to tylko pierwszy krok w analizie. Zakładam to drugie.

Można rozpocząć od zdefiniowania struktury wynikowego drzewa składni abstrakcyjnej poprzez zdefiniowanie typów. Może to być coś takiego:

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 

Potem zaimplementować zejście rekurencyjne parsera. Oczywiście byłoby znacznie ładniejsze jeśli można użyć streams połączeniu z preprocesora camlp4of ...

Nawiasem mówiąc, jest tam mały przykład o wyrażeń arytmetycznych w dokumentacji OCaml here.

Answer 2

Ok, więc najpierw pomyśl, że powinieneś zrobić, to napisać analizator leksykalny. To jest funkcja , która pobiera dane wejściowe "surowe", takie jak ["3"; "-"; "("; "4"; "+"; "2"; ")"], i dzieli je na listę tokenów (czyli reprezentacje symboli terminali).

Można zdefiniować token być

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 

Rodzaj funkcji lexer byłby string list -> token list i ouput

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

byłoby coś

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

ten sprawi, że zadanie pisania parsera będzie łatwiejsze, ponieważ tego nie zrobisz musicie się martwić o rozpoznanie, co jest liczbą całkowitą, czym jest operator itp.

Jest to pierwszy, niezbyt trudny krok, ponieważ tokeny są już rozdzielone. Wszystko, co lexer musi zrobić, to je zidentyfikować.

Po wykonaniu tej czynności można napisać bardziej realistyczny analizator leksykalny typu string -> token list, który pobiera rzeczywistą wejściową wartość nieprzetworzoną, taką jak "3-(4+2)" i zamienia ją na listę znaczników.

Answer 3

Oto przybliżony szkic - bezpośrednio zejdź do gramatyki i wypróbuj każdą gałąź w kolejności. Możliwa optymalizacja: rekursja ogona dla pojedynczej nieterminalnej w gałęzi.

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