У меня ошибка в грамматике или в инструменте генерации синтаксического анализатора?

Ниже приведен формат EBNF (в основном фактический синтаксис задокументирован здесь) грамматика, для которой я пытаюсь создать парсер:

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)/;

Для создания синтаксического анализатора я использую инструмент Grako, который создает модифицированный Парсер Packrat, который утверждает, что поддерживает как прямую, так и косвенную левую рекурсию.

Когда я запускаю сгенерированный анализатор этой строки:

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

Я получаю следующую ошибку:

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

Отладка показала, что синтаксический анализатор, кажется, доходит до конца первого e[0], а затем никогда не возвращается к/достигает точки, где он попытается сопоставить токен in.

Есть ли какая-то проблема с моей грамматикой, из-за которой синтаксический анализатор Packrat, поддерживающий левую рекурсию, не сработает? Или мне следует зарегистрировать проблему в системе отслеживания проблем Grako?


person Trey Brisbane    schedule 14.03.2015    source источник
comment
Можете ли вы упростить грамматику и формулировку, чтобы воспроизвести проблему?   -  person User    schedule 14.03.2015


Ответы (1)


Это может быть ошибка в грамматике, но сообщение об ошибке не говорит вам, где это происходит на самом деле. Что я всегда делаю после завершения грамматики, так это встраиваю в нее элементы cut (~) (после таких ключевых слов, как if, операторов, открывающих скобок, везде, где это кажется разумным).

Элемент cut заставляет созданный Grako синтаксический анализатор фиксировать параметр, выбранный в ближайшем выборе в дереве синтаксического анализа. Таким образом, вместо сбоя парсера в начале if, он сообщит об ошибке в выражении, которое он на самом деле не может проанализировать.

Некоторые ошибки в грамматике трудно обнаружить, и для этого я просто просматриваю трассировку синтаксического анализа, чтобы узнать, как далеко зашел синтаксический анализатор во входных данных и почему он решил, что не может идти дальше.

Я не буду использовать левую рекурсию в синтаксическом анализаторе PEG для профессиональной работы, хотя она может подойти для более простой академической работы.

boolean_or_expr = boolean_xor_expr {"or" boolean_xor_expr};

Затем ассоциативность может быть обработана в семантическом действии.

Также см. обсуждение в разделе проблема 49 против Grako. В нем говорится, что алгоритм, используемый для поддержки левой рекурсии, не всегда будет обеспечивать ожидаемую ассоциативность в результирующем AST.

person Apalala    schedule 14.03.2015
comment
Спасибо за подсказку по поводу вырезанных элементов. Я подозреваю, что это, вероятно, также немного ускорит синтаксический анализ, потому что сейчас он довольно медленный. - person Trey Brisbane; 17.03.2015
comment
Тем не менее, похоже, что я, вероятно, использую восходящий парсер, если хочу сохранить леворекурсивные грамматические правила. Что касается вашей точки зрения на ассоциативность - я не могу не задаться вопросом, какой смысл в том, что Packrat поддерживает левую рекурсию, если ассоциативность правил не сохраняется. Не проще ли просто сказать, что для этого вам нужен анализатор снизу вверх? - person Trey Brisbane; 17.03.2015
comment
@Trey Левая рекурсия упрощает написание грамматик для некоторых языков. Отсутствие гарантий относительно ассоциативности не является замыслом, а следствием используемого алгоритма и чем-то предметом исследования. Также обратите внимание, что желаемая ассоциативность, вероятно, будет сохранена для вашей конкретной грамматики. - person Apalala; 17.03.2015
comment
Приносим извинения за задержку; Я был занят с Юни. Спасибо за разъяснения. Хорошо знать. :) Я переработал грамматику, добавив вырезанные элементы, как вы предложили (новая грамматика доступна по адресу pastebin.com/eykU3V9K ). - person Trey Brisbane; 24.03.2015
comment
Учитывая ту же входную строку, проблема, по-видимому, возникает в литерале списка сразу после первого ключевого слова «in». Сгенерированный синтаксический анализатор успешно проанализирует первый элемент («t»), а затем запятую. Пытаясь проанализировать второй элемент («T»), синтаксический анализатор спускается к правилу power_expr, где он вызывает первое правило slice_expr и успешно анализирует «T». Затем он не может разобрать токен '**' и возвращается к второй опции power_expr, вызывая правило slice_expr во второй раз. - person Trey Brisbane; 24.03.2015
comment
Затем проблема проявляется, когда правило slice_expr пытается вызвать правило member_access_expr, потому что по какой-то причине в кэше мемоизации уже есть запись FailedLeftRecursion для правила member_access_expr, предотвращающая его вызов. Можете ли вы пролить свет на это? - person Trey Brisbane; 24.03.2015
comment
Кроме того, я заметил, что изменение power_expr = slice_expr "**" ~ power_expr | slice_expr; на power_expr = slice_expr [ "**" ~ power_expr ]; приводит к тому, что синтаксический анализатор требует времени для запуска (возможно, из-за катастрофического возврата?). Я бы подумал, что они эквивалентны, поскольку в первой форме, если синтаксический анализатор не смог сопоставить "**", он бы отменил все, что он видел с начала power_expr, а затем попробовал второй вариант? Я упускаю здесь что-то фундаментальное? - person Trey Brisbane; 25.03.2015
comment
@Tray, не могли бы вы опубликовать это как проблему в Bitbucket. Посмотрю на следующем проходе через Грако. - person Apalala; 05.04.2015
comment
@TreyBrisbane Вы разместили это там? У вас есть ссылка? - person Robert Siemer; 12.04.2016
comment
Ссылка там, где написано Bitbucket. bitbucket.org/apalala/grako/issues - person Apalala; 12.04.2016