对于我的应用程序,我正在尝试构建一个SQLite解析器。由于我的应用程序使用的是Objective-C,因此ParseKit似乎是一个不错的选择。我阅读了SQLite的syntax diagrams并基于它们构建了一个语法。但是,当我尝试使用此语法解析某些内容时,解析器将进入无限递归。
我唯一需要的语句是SELECT,INSERT,UPDATE和DELETE(我主要需要SELECT,因为其他人都引用了它)。我的@start旨在处理用分号分隔的多个语句:
@start = statement (';' statement)*;
statement = select_stmt | insert_stmt | update_stmt | delete_stmt ;
语句如下:
select_stmt = select_core ( compound_operator select_core )* order_expr? limit_expr? ;
select_core = 'select' ( 'distinct' | 'all' )? result_column ( ',' result_column )* from_expr where_expr group_expr ;
result_column = '*' | table_name '.' '*' | expr ( 'as'? column_alias )? ;
insert_stmt = 'insert' or_on_failure? 'into' table_name insert_expr ;
insert_expr = insert_expr_cols? (insert_expr_values | select_stmt) ;
insert_expr_cols = '(' column_name ( ',' column_name )* ')' ;
insert_expr_values = 'values' '(' expr ( ',' expr )* ')' ;
insert_expr_defaults = 'default' 'values' ;
update_stmt = 'update' or_on_failure? qualified_table_name update_expr where_expr? limited_expr? ;
update_expr = 'set' update_expr_col ( ',' update_expr_col )* ;
update_expr_col = column_name '=' expr ;
delete_stmt = 'delete' 'from' qualified_table_name where_expr? limited_expr? ;
及其支持的表达方式:
order_expr = 'order' 'by' ordering_term (',' ordering_term)* ;
limit_expr = 'limit' expr ( ( 'offset' | ',' ) expr )? ;
from_expr = 'from' join_source ;
where_expr = 'where' expr ;
group_expr = 'group' 'by' expr ( ',' expr )? ( 'having' expr )? ;
join_source = single_source ( join_operator single_source join_constraint? )* ;
single_source = table_name 'as' table_alias indexed_by? | '(' select_stmt ')' ( 'as'? table_alias )? | '(' join_source ')' ;
or_on_failure = 'or' on_failure ;
on_failure = 'rollback' | 'abort' | 'replace' | 'fail' | 'ignore' ;
limited_expr = order_expr limit_expr ;
名称,别名:
database_name = name ;
table_name = (database_name '.')? name ;
column_name = (table_name '.')? name ;
table_alias = name ;
column_alias = name ;
index_name = name ;
type_name = name+ ( '(' number (',' number)? ')' )? ;
function_name = name ;
collation_name = name ;
qualified_table_name = table_name indexed_by? ;
杂项运算符等:
indexed_by = 'indexed' 'by' index_name | 'not' 'indexed' ;
unary_operator = symbol ;
binary_operator = symbol ;
compound_operator = 'union' 'all'? | 'intersect' | 'except' ;
join_operator = ',' | 'natural'? ( 'left' 'outer'? | 'inner' | 'cross' ) 'join' ;
join_constraint = 'on' expr | 'using' '(' column_name ( ',' column_name )* ')' ;
基本类型:
literal = number
| string
| 'null'
| 'current_time'
| 'current_data'
| 'current_timestamp' ;
number = Number ;
string = Word
| QuotedString ;
name = Word
| QuotedString ;
symbol = Symbol;
和EXPR:
expr = literal
| column_name
| unary_operator expr
| expr binary_operator expr
| function_name '(' ( '*' | 'distinct'? expr ( ',' expr )* )? ')'
| '(' expr ')'
| 'cast' '(' expr 'as' type_name ')'
| expr 'collate' collation_name
| expr 'not'? ( 'like' | 'glob' | 'regexp' | 'match' ) expr ( 'escape' expr )?
| expr ( 'isnull' | 'notnull' | 'not' 'null' )
| expr 'is' 'not'? expr
| expr 'not'? 'between' expr 'and' expr
| expr 'not'? 'in' ( table_name | '(' ( select_stmt | expr ( ',' expr )* )? ')' )
| ( 'not'? 'exists' )? '(' select_stmt ')'
| 'case' expr? ( 'when' expr 'then' expr )+ ( 'else' expr )? 'end' ;
当我单步执行代码时,基本路径是@start->语句-> select_stmt-> select_core-> result_column-> expr-> expr-> expr ...
在PKParser的matchAndAssemble:和PKParser / Subclass的allMatchesFor:之间进行了大约8-9k的调用之后,某些错误消失了,通常是由于EXC_BAD_ACCESS错误(然后LLDB不能执行任何操作)。
附注:如果您要发布一个答案,说:“哦,您应该确实使用/使用它。” A)我喜欢Objective-C。不要告诉我不要使用它。这是我的选择。我的回应可能会很激烈。 B)我尝试挖掘SQLite的源来使用其解析器。我什么都没有。如果您认为我应该使用它,请将其解析器的源发布为没有其他依赖项的单个文件。
最佳答案
ParseKit的开发者在这里。
首先,查看我以前在debugging ParseKit grammars和battling infinite recursion in ParseKit grammars上获得的答案。
我认为第一行可能会有问题(但我不是SQL专家,所以我不确定)。那不应该是:
@start = (statement ';')+;
我强烈建议使用驼峰大小写而不使用下划线,因为下划线会使您的Objective-C回调非常尴尬和丑陋。这就是为什么驼峰大小写是ParseKit语法中的约定的原因。
但是,我看到了主要问题。您的语法包括在ParseKit语法中不允许的Left Recursion。特别是在您的
expr
产品中(我也没有仔细查看它是否也位于其他位置)。ParseKit可以使用递归,但不能保留。最好的解释是在Steven Metsker's "Building Parsers with Java"中。或search the web。
但是基本上左递归是指生产立即引用自身(在表达式的左侧):
e = e '-' Number;
要么
e = Number | e '-' Number;
相反,您必须设计语法以消除左递归,例如:
e = Number ('-' Number)*;
关于objective-c - ParseKit-SQLite解析器进入无限递归,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14597299/