¿Tengo un error en mi gramática o en la herramienta de generación de analizador?

La siguiente es una gramática del formato EBNF (en su mayoría, la syntax real se documenta aquí ) para la que estoy intentando generar un analizador:

expr = lambda_expr_list $; lambda_expr_list = [ lambda_expr_list "," ] lambda_expr; lambda_expr = conditional_expr [ "->" lambda_expr ]; conditional_expr = boolean_or_expr [ "if" conditional_expr "else" conditional_expr ]; boolean_or_expr = [ boolean_or_expr "or" ] boolean_xor_expr; boolean_xor_expr = [ boolean_xor_expr "xor" ] boolean_and_expr; boolean_and_expr = [ boolean_and_expr "and" ] boolean_not_expr; boolean_not_expr = [ "not" ] relation; relation = [ relation ( "==" | "!=" | ">" | "<=" | "=" | [ "not" ] "in" | "is" [ "not" ] ) ] bitwise_or_expr; bitwise_or_expr = [ bitwise_or_expr "|" ] bitwise_xor_expr; bitwise_xor_expr = [ bitwise_xor_expr "^" ] bitwise_and_expr; bitwise_and_expr = [ bitwise_and_expr "&" ] bitwise_shift_expr; bitwise_shift_expr = [ bitwise_shift_expr ( "<>" ) ] subtraction_expr; subtraction_expr = [ subtraction_expr "-" ] addition_expr; addition_expr = [ addition_expr "+" ] division_expr; division_expr = [ division_expr ( "/" | "\\" ) ] multiplication_expr; multiplication_expr = [ multiplication_expr ( "*" | "%" ) ] negative_expr; negative_expr = [ "-" ] positive_expr; positive_expr = [ "+" ] bitwise_not_expr; bitwise_not_expr = [ "~" ] power_expr; power_expr = slice_expr [ "**" power_expr ]; slice_expr = member_access_expr { subscript }; subscript = "[" slice_defn_list "]"; slice_defn_list = [ slice_defn_list "," ] slice_defn; slice_defn = lambda_expr | [ lambda_expr ] ":" [ [ lambda_expr ] ":" [ lambda_expr ] ]; member_access_expr = [ member_access_expr "." ] function_call_expr; function_call_expr = atom { parameter_list }; parameter_list = "(" [ lambda_expr_list ] ")"; atom = identifier | scalar_literal | nary_literal; identifier = /[_A-Za-z][_A-Za-z0-9]*/; scalar_literal = float_literal | integer_literal | boolean_literal; float_literal = point_float_literal | exponent_float_literal; point_float_literal = /[0-9]+?\.[0-9]+|[0-9]+\./; exponent_float_literal = /([0-9]+|[0-9]+?\.[0-9]+|[0-9]+\.)[eE][+-]?[0-9]+/; integer_literal = dec_integer_literal | oct_integer_literal | hex_integer_literal | bin_integer_literal; dec_integer_literal = /[1-9][0-9]*|0+/; oct_integer_literal = /0[oO][0-7]+/; hex_integer_literal = /0[xX][0-9a-fA-F]+/; bin_integer_literal = /0[bB][01]+/; boolean_literal = "true" | "false"; nary_literal = tuple_literal | list_literal | dict_literal | string_literal | byte_string_literal; tuple_literal = "(" [ lambda_expr_list ] ")"; list_literal = "[" [ ( lambda_expr_list | list_comprehension ) ] "]"; list_comprehension = lambda_expr "for" lambda_expr_list "in" lambda_expr [ "if" lambda_expr ]; dict_literal = "{" [ ( dict_element_list | dict_comprehension ) ] "}"; dict_element_list = [ dict_element_list "," ] dict_element; dict_element = lambda_expr ":" lambda_expr; dict_comprehension = dict_element "for" lambda_expr_list "in" lambda_expr [ "if" lambda_expr ]; string_literal = /[uU]?[rR]?(\u0027(\\.|[^\\\r\n\u0027])*\u0027|\u0022(\\.|[^\\\r\n\u0022])*\u0022)/; byte_string_literal = /[bB][rR]?(\u0027(\\[\u0000-\u007F]|[\u0000-\u0009\u000B-\u000C\u000E-\u0026\u0028-\u005B\u005D-\u007F])*\u0027|\u0022(\\[\u0000-\u007F]|[\u0000-\u0009\u000B-\u000C\u000E-\u0021\u0023-\u005B\u005D-\u007F])*\u0022)/; 

La herramienta que estoy usando para generar el analizador es Grako , que genera un analizador Packrat modificado que pretende admitir tanto la recursión a la izquierda directa como la indirecta.

Cuando ejecuto el analizador generado en esta cadena:

 input.filter(e -> e[0] in ['t', 'T']).map(e -> (e.len().str(), e)).map(e -> '(Line length: ' + e[0] + ') ' + e[1]).list() 

Obtuve el siguiente error:

 grako.exceptions.FailedParse: (1:13) Expecting end of text. : input.filter(e -> e[0] in ['t', 'T']).map(e -> (e.len().str(), e)).map(e -> '(Line length: ' + e[0] + ') ' + e[1]).list() ^ expr 

La depuración ha demostrado que el analizador parece llegar al final de la primera e[0] , y luego nunca retrocede hasta / llega a un punto en el que intentará coincidir con el token de entrada.

¿Hay algún problema con mi gramática de tal manera que un analizador Packrat compatible con recursión a la izquierda fallaría? ¿O debería presentar un problema en el rastreador de problemas de Grako?

Puede ser un error en la gramática, pero el mensaje de error no le indica dónde sucede realmente. Lo que siempre hago después de terminar una gramática es incrustar elementos de corte ( ~ ) a lo largo de la misma (después de palabras clave como if , operadores, paréntesis de apertura, en todas partes parece razonable).

El elemento de corte hace que el analizador generado por Grako se comprometa con la opción elegida en la opción más cercana en el árbol de análisis. De esa manera, en lugar de hacer que el analizador falle al principio en un if , informará de un error en la expresión que realmente no pudo analizar.

Algunos errores en las gramáticas son difíciles de detectar, y para eso simplemente paso por el rastreo de análisis para averiguar qué tan lejos en la entrada fue el analizador, y por qué decidió que no podía ir más lejos.

No utilizaré la recursión a la izquierda en un analizador PEG para el trabajo profesional, aunque puede estar bien para un trabajo académico más simple.

 boolean_or_expr = boolean_xor_expr {"or" boolean_xor_expr}; 

La asociatividad puede entonces ser manejada en una acción semántica.

También vea la discusión bajo el número 49 contra Grako. Dice que el algoritmo utilizado para soportar la recursión izquierda no siempre producirá la asociatividad esperada en el AST resultante.