Как разрешить этот косвенный конфликт первого набора в грамматике?

Question

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

A -> B 
   | C 
   | intnum 
   | floatnum 
   | lpar D rpar 
   | not A 
   | E A .

B -> F I .

C -> G lpar rpar .

F -> id H F 
   | id .

G -> id H G 
   | id .

Я знаю, что и F, и G имеют конфликты первых наборов и что они могут быть решен следующим образом:

F  -> id F'
F' -> H F
    | .

G  -> id G'
G' -> H G
    | .

Но я заблудился относительно того, как разрешить косвенный конфликт первого набора с A. И B, и C указывают на разные символы, но F и G указывают на id. Я использовал этот инструмент , чтобы помочь, но он не может справиться с этим типом конфликта.

Answer 1

Поскольку F и G идентичны, анализатор, работающий сверху вниз, не сможет обработать грамматику, в которой оба возможных предсказания. (Здесь мы не видим определения I, но если случится так, что lpar ∈ FIRST(I), то даже у анализатора снизу вверх будут проблемы.)

Простое решение состоит в том, чтобы Устраните избыточность, используя только одно из этих производств в обоих контекстах.

Для синтаксического анализатора с нисходящим потоком вам все равно потребуется левосторонний фактор, поскольку B и C по-прежнему имеют одинаковые FIRST наборы. Простое решение может быть:

A ⇒ B'
  | intnum 
  | floatnum 
  | lpar D rpar 
  | not A 
  | E A .

B' ⇒ F C' .

C' ⇒ I
   | lpar rpar .

При условии, что lpar ∉ FIRST(I) (и аналогичные гарантии для E), этот фрагмент является LL (1).

Насколько это применимо к вашему полная грамматика зависит от степени упрощения этого фрагмента. Существуют варианты этой проблемы, которые чрезвычайно трудно решить для парсера LL (1), но относительно просты для парсера LR (1) (или парсера LR (k) для малых k). В частности, ваша оригинальная грамматика, даже с избыточностью F и G, является LALR (1) (протестировано с Bison).