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 和 shift-reduce 解析（经典，Hopcroft & Ullman和Aho，Sethi & Ullman是完整的，如果相当密集）。

一旦你理解了 shift-reduce 解析，yacc 错误恢复就相当简单了。基本上，每当它进入不能移动或减少当前令牌的状态时，它需要一系列简单的步骤来尝试恢复：

  1. 它会弹出状态，直到达到可以转移特殊error标记的状态。如果当前状态可以转变，这可能是零弹出error。

  2. 它移动错误标记，然后在目标状态中进行任何默认缩减。

  3. 它会丢弃输入标记，直到找到可以在当前状态下处理的标记。error与状态丢弃一样，如果转移后的状态可以处理下一个令牌，则丢弃可能为零。

就是这样。

因此，如果我们查看您当前的语法和示例错误输入会发生什么，我们会发现：

  1. 将SELECT令牌转换为状态select_statement: K_SELECT ...
  2. 转移123令牌，将其简化为 avalue并转移到状态*expr: value ...
  3. 转移+令牌，将其简化为一个operator并转移到一个状态binary_expression: value operator ...
  4. 看到令牌,并且在当前状态下不能移位或减少，因此发出语法错误。
  5. 流行音乐国家正在寻找一个可以处理error. 前两个状态（来自上面的 3 和 2）不能这样被丢弃。下一个状态可以，所以我们最终处于一个状态select_statement: K_SELECT error
  6. 那是一个默认的归约状态，所以它被归约到select_statement哪个被归约到statement哪个转移到一个状态input: statement END
  7. 它开始丢弃输入标记，直到找到当前状态可以处理的标记，即只有END. 所以它会丢弃所有东西，直到它到达END或 eof。

现在你的问题似乎是，“我该如何做一些不同的事情？”

如果您想要“二进制表达式未完成”恢复，您可以添加如下规则：

binary_expression: value error

这最终会成为上述*expr: value状态的一部分，因此错误恢复将停止在那里弹出并移动错误令牌，最终进入可以移动,令牌的状态。

每当您试图解开大型语法中的状态并了解错误恢复将做什么时，使用 -v 标志运行 yacc/bison 以生成.output包含所有状态的文件会非常有帮助。

于 2013-02-02T19:41:43.677 回答