Как сбалансировать правила и терминалы в парсере Python Lark?

Question

Я использую Lark, отличную библиотеку разбора Python.

Он предоставляет парсер Earley и LALR(1) и определяется через пользовательский EBNF формат. (EBNF расшифровывается как расширенная форма Бэкуса-Наура).

Строчные определения - это правила, прописные - терминалы. Ларк также предоставляет вес для определений в верхнем регистре для определения приоритетов соответствия.

Я пытаюсь определить грамматику, но я застрял в поведении, которое я не могу сбалансировать.

У меня есть несколько правил с неназванными литералами (строки или символы между двойными кавычками):

directives: directive+
directive: "@" NAME arguments ?
directive_definition: description? "directive" "@" NAME arguments? "on" directive_locations
directive_locations: "SCALAR" | "OBJECT" | "ENUM"

arguments: "(" argument+ ")"
argument: NAME ":" value

union_type_definition: description? "union" NAME directives? union_member_types?

union_member_types: "=" NAME ("|" NAME)*

description: STRING | LONG_STRING    

STRING: /("(?!"").*?(?<!\\)(\\\\)*?"|'(?!'').*?(?<!\\)(\\\\)*?')/i
LONG_STRING: /(""".*?(?<!\\)(\\\\)*?"""|'''.*?(?<!\\)(\\\\)*?''')/is
NAME.2: /[_A-Za-z][_0-9A-Za-z]*/

Это хорошо работает для 99% случаев использования. Но если на моем разобранном языке я использую directive который называется directive все ломается

union Foo @something(test: 42) = Bar | Baz   # This works
union Foo @directive(test: 42) = Bar | Baz   # This fails

Здесь directive Строка соответствует безымянному литералу в directive_definition Правило, когда оно должно соответствовать NAME.2 Терминал.

Как я могу сбалансировать / отрегулировать это так, чтобы двусмысленность синтаксического анализатора LALR(1) была невозможна?

Answer 1

Автор жаворонка здесь.

Это неправильное толкование происходит потому, что "директива" может быть двумя разными токенами: строка "директива" или NAME. По умолчанию лексер Lark Lark всегда выбирает более конкретный, а именно строку.

Итак, как мы можем позволить лексеру знать, что @directive это имя, а не просто две постоянные строки?

Решение 1. Используйте контекстный лексер

Что, вероятно, помогло бы в этой ситуации (без полной грамматики трудно быть уверенным), это использовать контекстный лексер вместо стандартного лексера LALR(1).

Контекстный лексер может до некоторой степени взаимодействовать с анализатором, чтобы выяснить, какой терминал имеет больше смысла в каждой точке. Этот алгоритм уникален для Lark, и вы можете использовать его следующим образом:

parser = Lark(grammar, parser="lalr", lexer="contextual")

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

Решение 2 - Префикс терминала

Если контекстный лексер не решает вашу коллизию, более "классическим" решением этой ситуации было бы определение токена директивы, что-то вроде:

DIRECTIVE: "@" NAME

В отличие от вашего директивного правила, это не оставляет двусмысленности для лексера. Существует четкое различие между директивой и строкой "директивы" (или терминалом NAME).

И если ничего не помогает, вы всегда можете использовать парсер Earley, который ценой производительности будет работать с любой грамматикой, которую вы ему дадите, независимо от того, сколько может быть коллизий.

Надеюсь это поможет!