0

非常に単純なSQLパーサーを作成しましたが、ファズテスト中にこの状況に遭遇しました。

SELECT   123     +      ,
K_SELECT INTEGER T_PLUS T_COMMA

もちろん、これは構文エラーですが、「キャッチ」する方法がわかりません。

「next_column_expressionが早すぎた」と「binary_expressionが終了しなかった」のどちらを判断するのですか。私はJavaプロジェクトでANTLR3とかなり協力してきました。しかし、これはまったく異なります。

スケルトンパーサーのルールは次のとおりです。

/* be more versbose about error messages */
%error-verbose

/* keywords */
%token K_CREATE
%token K_FROM
%token K_INTEGER
%token K_SELECT
%token K_TABLE
%token K_TEXT
%token K_WHERE
%token K_VALUES
%token K_INSERT
%token K_INTO

/* variable tokens */
%token IDENTIFIER
%token INTEGER

/* fixed tokens */
%token T_ASTERISK
%token T_PLUS
%token T_EQUALS
%token T_END ";"
%token T_COMMA
%token T_BRACKET_OPEN
%token T_BRACKET_CLOSE

%token END 0 "end of file"

%%

input:
    statement {
    }
    END
;

statement:
    select_statement {
    }
    |
    create_table_statement {
    }
    |
    insert_statement {
    }
;

keyword:
    K_CREATE | K_FROM | K_INTEGER | K_SELECT | K_TABLE | K_TEXT | K_WHERE | K_VALUES | K_INSERT | K_INTO
;

table_name:
    error {
        // "Expected table name"
    }
    |
    keyword {
        // "You cannot use a keyword for a table name."
    }
    |
    IDENTIFIER {
    }
;

select_statement:
    K_SELECT column_expression_list {
        // "Expected FROM after column list."
    }
    error
    |
    K_SELECT error {
        // "Expected column list after SELECT."
    }
    |
    K_SELECT column_expression_list {
    }
    K_FROM table_name {
    }
;

column_expression_list:
    column_expression {
    }
    next_column_expression
;

column_expression:
    T_ASTERISK {
    }
    |
    expression {
    }
;

next_column_expression:
    |
    T_COMMA column_expression {
    }
    next_column_expression
;

binary_expression:
    value {
    }
    operator {
    }
    value {
    }
;

expression:
    value
    |
    binary_expression
;

operator:
    T_PLUS {
    }
    |
    T_EQUALS {
    }
;

value:
    INTEGER {
    }
    |
    IDENTIFIER {
    }
;

%%
4

1 に答える 1

3

LR (shift-reduce) 構文解析を理解する必要があり、文法のエラー規則を使用して yacc がエラーから回復する方法を理解する必要があります。前者は大きな問題であり、PDA の理論と実践、およびシフト削減構文解析をカバーする書籍が多数あります (クラシックであるHopcroft & UllmanとAho, Sethi & Ullmanは、かなり内容が濃くても完全です)。

shift-reduce 構文解析を理解すれば、yacc エラー回復はかなり簡単です。基本的に、現在のトークンをシフトまたは削減できない状態になると、簡単な一連の手順を実行して回復を試みます。

  1. error特殊なトークンをシフトできる状態になるまで状態をポップします。現在の状態が変化する可能性がある場合、これはゼロ ポップである可能性がありますerror。

  2. エラートークンをシフトし、ターゲット状態でデフォルトの削減を行います。

  3. 現在の状態で処理できるトークンが見つかるまで、入力トークンを破棄します。error状態のドロップと同様に、シフト後の状態が次のトークンを処理できる場合、破棄はゼロになる可能性があります。

以上です。

したがって、現在の文法と間違った入力の例で何が起こるかを見ると、次のことがわかります。

  1. SELECT状態に入るトークンをシフトしますselect_statement: K_SELECT ...
  2. 123トークンをシフトし、それを a に減らし、value状態にシフトします*expr: value ...
  3. +トークンをシフトし、それを an に減らし、operator状態にシフトしますbinary_expression: value operator ...
  4. トークン,を見て、現在の状態でシフトまたは削減できないため、構文エラーを発行します。
  5. を処理できるものを探している状態をポップしますerror。上位 2 つの状態 (上記の 3 と 2 から) は破棄できないため、破棄されます。次の状態はできるので、最終的には状態になりますselect_statement: K_SELECT error
  6. それがデフォルトの削減状態なので、削減されてからselect_statement削減されstatementて、状態に移行しますinput: statement END
  7. 現在の状態で処理できるトークンが見つかるまで、入力トークンの破棄を開始しますEND。ENDそのため、eof または eofになるまですべてを破棄します。

今、あなたの質問は「どうすれば違うことをすることができますか?」のようです。

「バイナリ表現が完全ではない」リカバリが必要な場合は、次のようなルールを追加できます。

binary_expression: value error

これは*expr: value上記の状態の一部になるため、エラー回復はそこでポップを停止し、エラー トークンをシフトして、,トークンをシフトできる状態になります。

大規模な文法で状態を解きほぐし、エラー回復が何をするかを理解しようとするときはいつでも、-v フラグを指定して yacc/bison を実行し.output、すべての状態を含むファイルを生成すると非常に役立ちます。

于 2013-02-02T19:41:43.677 に答える