11

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

私が探しているのは、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ライブラリを使用しないことです...：/

4

3 に答える 3

13

これが大まかなスケッチです-文法に直接降りて、各ブランチを順番に試してください。可能な最適化：ブランチ内の単一の非終端記号の末尾再帰。

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
于 2009-10-21T07:56:01.350 に答える
9

さて、あなたが最初にすべきだと思うのは、字句解析器を書くことです。これは、のような「生の」入力を受け取り、["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)"それをトークンリストに変換する、タイプのより現実的な字句解析器を作成できます。

于 2009-10-19T15:32:51.247 に答える
3

派生ツリーが特に必要なのか、それとも構文解析の最初のステップにすぎないのかはわかりません。私は後者を想定しています。

タイプを定義することにより、結果の抽象構文ツリーの構造を定義することから始めることができます。これは次のようなものである可能性があります。

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のドキュメントには算術式に関する小さな例があります。

于 2009-10-18T21:54:53.480 に答える