Phân tích cú pháp ngữ pháp bằng OCaml

Question

Tôi có nhiệm vụ viết một trình phân tích cú pháp (đồ chơi) cho ngữ pháp (đồ chơi) bằng OCaml và không chắc chắn cách bắt đầu (và tiếp tục) vấn đề này.

Dưới đây là một AWK ngữ pháp mẫu:

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

Và đây là một số mảnh vỡ để phân tích:

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

Những gì tôi đang tìm kiếm là một rulelist đó là kết quả của sự phân tích một đoạn, chẳng hạn như cái này cho 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"])] 

Hạn chế là không sử dụng bất kỳ thư viện OCaml khác ngoài Danh sách ...:/

Answer 1

Tôi không chắc chắn nếu bạn đặc biệt yêu cầu các cây nguồn gốc, hoặc nếu điều này là chỉ là một bước đầu tiên trong phân tích cú pháp. Tôi giả định sau.

Bạn có thể bắt đầu bằng cách xác định cấu trúc của cây cú pháp trừu tượng kết quả bằng cách xác định các loại. Có thể giống như sau:

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 

Sau đó, tôi sẽ triển khai trình phân tích cú pháp gốc đệ quy. Tất nhiên nó sẽ đẹp hơn nhiều nếu bạn có thể sử dụng streams kết hợp với tiền xử lý camlp4of ...

Nhân tiện, có một ví dụ nhỏ về biểu thức số học trong tài liệu OCaml here.

Answer 2

Ok, do đó, điều đầu tiên bạn nên làm là viết một máy phân tích từ vựng. Đó là hàm lấy đầu vào ‘thô’, như ["3"; "-"; "("; "4"; "+"; "2"; ")"], và tách nó thành danh sách mã thông báo (có nghĩa là, biểu thị các ký hiệu đầu cuối).

Bạn có thể xác định một mã thông báo được

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 

Các loại lexer chức năng sẽ string list -> token list và ouput của

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

sẽ là một cái gì đó giống như

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

này sẽ làm cho công việc viết trình phân tích cú pháp dễ dàng hơn, bởi vì bạn sẽ không phải lo lắng về việc nhận biết số nguyên là gì, toán tử là gì, v.v.

Đây là bước đầu tiên, không quá khó vì mã thông báo đã được tách riêng. Tất cả các lexer phải làm là xác định chúng.

Khi thực hiện xong, bạn có thể viết một bộ phân tích từ vựng thực tế hơn, loại string -> token list, thực hiện nhập liệu thô thực tế, chẳng hạn như "3-(4+2)" và biến nó thành danh sách mã thông báo.

Answer 3

Đây là một bản phác thảo sơ sài - thẳng thắn đi sâu vào ngữ pháp và thử từng chi nhánh theo thứ tự. Tối ưu hóa có thể có: đệ quy đuôi cho một thiết bị đầu cuối không trong một chi nhánh.

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