Грамматика парсера Lark работает с Эрли, но не с LALR

Question

Рассмотрим этот простой тест парсера Python Lark:

GRAMMAR = '''
start: container*

container: string ":" "{" (container | attribute | attribute_value)* "}"
attribute: attribute_name "=" (attribute_value | container)
attribute_value: string ":" _value ("," _value)*
_value: number | string

attribute_name: /[A-Za-z_][A-Za-z_#0-9]*/

string: /[A-Za-z_#0-9]+/
number: /[0-9]+/

    %import common.WS
    %ignore WS
'''

data = '''outer : {
 inner : {
 }
}'''

parser = Lark(GRAMMAR, parser='lalr')
parser.parse(data)

Это работает с parser='earley' но это не с parser='lalr', Я не понимаю почему. Сообщение об ошибке:

UnexpectedCharacters: не определен терминал для '{' в строке 2, столбец 12

внутренний: {

Это просто MWE. Моя настоящая грамматика страдает от той же проблемы.

Answer 1

Причина, по которой это не удается с LALR, заключается в том, что он имеет прогнозирование 1 (в отличие от Эрли, который имеет неограниченный просмотр), и он путается между attribute_name а также string, Как только это соответствует одному из другого (в этом случае, attribute_name), для него невозможно вернуться назад и соответствовать другому правилу.

Если вы используете более низкий приоритет для терминала attribute_name, он будет работать. Например:

attribute_name: ATTR

ATTR.0: /[A-Za-z_][A-Za-z_#0-9]*/

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

Оба подхода (изменение приоритета или объединение терминалов) решат вашу проблему.