3

文法の字句解析/構文解析のスキルを身に付けようとしています。SQL用に作成した単純なパーサーを振り返っていますが、完全に満足しているわけではありません。パーサーを作成するためのより簡単な方法があったはずです。

SQLにはオプションのトークンと繰り返しがたくさんあるので、私はつまずきました。例えば：

SELECT *
FROM t1
INNER JOIN t2
INNER JOIN t3
WHERE t1.ID = t2.ID and t1.ID = t3.ID

と同等です：

SELECT *
FROM t1
INNER JOIN t2 ON t1.ID = t2.ID
INNER JOIN t3 on t1.ID = t3.ID

ONand句はオプションであり、WHERE複数回発生する可能性があります。私はこれらをパーサーで次のように処理しました。

%{
open AST
%}

// ...    
%token <string> ID   
%token AND OR COMMA
%token EQ LT LE GT GE
%token JOIN INNER LEFT RIGHT ON
// ...

%%

op: EQ { Eq } | LT { Lt } | LE { Le } | GT { Gt } | GE { Ge }

// WHERE clause is optional    
whereClause:
    |                       { None }
    | WHERE whereList       { Some($2) }        

whereList:
    | ID op ID                    { Cond($1, $2, $3) }
    | ID op ID AND whereList      { And(Cond($1, $2, $3), $5) }
    | ID op ID OR whereList       { Or(Cond($1, $2, $3), $5) }


// Join clause is optional    
joinList:
    |                       { [] }
    | joinClause            { [$1] }
    | joinClause joinList   { $1 :: $2 }

joinClause:
    | INNER JOIN ID joinOnClause    { $3, Inner, $4 }
    | LEFT JOIN ID joinOnClause     { $3, Left, $4 }
    | RIGHT JOIN ID joinOnClause    { $3, Right, $4 }

// "On" clause is optional    
joinOnClause:
    |                       { None }
    | ON whereList          { Some($2) }

// ...
%%

つまり、オプションの構文を個別のルールに分割して処理し、再帰を使用して繰り返しを処理しました。これは機能しますが、解析が小さなサブルーチンの束に分割され、文法が実際に何を表しているかを確認するのは非常に困難です。

角かっこ内にオプションの構文を指定し、*または+で繰り返しを指定できれば、はるかに簡単に記述できると思います。これにより、whereClauseとjoinListのルールが次のようになります。

whereClause:
    |                       { None }
//    $1    $2, I envision $2 being return as an (ID * op * ID * cond) list
    | WHERE [ ID op ID { (AND | OR) }]+
        { Some([for name1, op, name2, _ in $1 -> name1, op, name2]) }

joinClause:
    |                       { None }

//    $1, returned as (joinType
//                       * JOIN
//                       * ID
//                       * ((ID * op * ID) list) option) list
    | [ (INNER | LEFT | RIGHT) JOIN ID [ON whereClause] ]*
        { let joinType, _, table, onClause = $1;
          Some(table, joinType, onClause) }

このフォームははるかに読みやすく、キャプチャしようとしている文法をより直感的に表現していると思います。残念ながら、この表記法または同様のものをサポートするOcamlまたはF＃のドキュメントには何も見つかりません。

OcamlYaccまたはFsYaccでオプションまたは反復トークンを使用して文法を表す簡単な方法はありますか？

4

2 に答える 2

3

Menhirを使用すると、非終端記号を別の記号でパラメーター化でき、オプションやリストなどの標準ショートカットのライブラリが提供され、独自のショートカットを作成できます。例：

option(X): x=X { Some x} 
         | { None }

「token?」という構文シュガーもあります。'option(token)'、'token+' は 'nonempty_list(token)' に相当します。

これらすべてが、文法の定義を本当に短縮します。また、ocamlbuild でサポートされており、ocamllyacc のドロップイン代替品として使用できます。強くお勧めします！

おかしい、私もそれを使ってSQLを解析しました:)

于 2009-06-26T09:28:14.307 に答える