Блог

Я пытаюсь выяснить, как удалить косвенную левую рекурсию из логических выражений ключевых слов в моем порту Rust синтаксического анализатора Ruby (https://github.com/kenaniah/ruby-parser/blob/master/ruby-parser/src/parsers/expression/logical.rs). Грамматика выглядит как:

 E --> N | A | O | t
N --> n E
A --> E a E
O --> E o E
  

 E = expression
A = keyword_and_expression
O = keyword_or_expression
N = keyword_not_expression
  

Как бы я преобразовал это, чтобы удалить рекурсию в A и O ?

Согласно этому инструменту факторизации, результирующая грамматика будет:

 E  -> N
    | A
    | O
    | t
N  -> n E
A  -> n E a E A'
    | O a E A'
    | t a E A'
O  -> n E o E O'
    | n E a E A' o E O'
    | t a E A' o E O'
    | t o E O'
A' -> a E A'
    | ϵ
O' -> a E A' o E O'
    | o E O'
    | ϵ
  

Похоже, что факторизации для A и O оказались довольно сложными благодаря многочисленным производствам E .

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

Если бы это была просто косвенная рекурсия, вы могли бы просто заменить правые части N , A и O , исключив косвенную рекурсию:

 E → n E
  | E a E
  | E o E
  | t
  

Чтобы избавиться от прямой левой рекурсии, вы можете использовать левый фактор:

 E → n E
  | E A'
  | t
A'→ a E
  | o E
  

а затем удалите оставшуюся левую рекурсию:

 E → n E E'
  | t E'
E'→ ε
  | A' E'
A'→ a E
  | o E
  

В ней нет левой рекурсии, прямой или косвенной, и каждое правило начинается с уникального терминала. Однако это не LL(1), потому что существует конфликт first / follow.

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

Эта таблица указывает, что AND и OR являются левоассоциативными операторами с одинаковым приоритетом (немного необычное решение), в то время как NOT является унарным оператором с более высоким приоритетом. Это, в свою очередь, означает, что BNF должен был быть написан примерно так:

 N → n N
  | t
E → A
  | O
  | N
A → E a N
O → E o N
N → n N
  | t
  

Единственным отличием от грамматики в OP является устранение двусмысленности, как указано в таблице приоритетов.

Опять же, первым шагом является замена нетерминалов A и O , чтобы сделать левую рекурсию прямой:

 E → E a N
  | E o N
  | N
N → n N
  | t
  

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

 E  → N E'
E' → a E
   | o E
   | ε
N  → n N
   | t