Почему мой синтаксический анализатор сообщает, что эта грамматика LALR (1) не является LALR (1)?

Question

Хорошо, мои приключения с моим генератором парсеров продолжаются. На этот раз я получил классическую c грамматику, которая, как говорят, является грамматикой LALR:

start -> a a
a -> "A" a
a -> "B"

Когда я помещаю ее в свой генератор парсера, он дает мне такой результат:

LIST OF STATES:
-----------------------
<0: S' -> . start , $
start -> . a a , $
a -> . "A" a , "A" / "B"
a -> . "B" , "A" / "B"
{NTerm(start): 1, Term(A): 2, Term(B): 3, NTerm(a): 4}>(3104365621624877555)

--------------------
<1: S' -> start .  , $
{}>(3969511602615904846)

--------------------
<2: a -> "A" . a , "A" / "B"
a -> . "A" a , "A" / "B"
a -> . "B" , "A" / "B"
{Term(A): 2, Term(B): 3, NTerm(a): 5}>(5490562805113673592)

--------------------
<3: a -> "B" .  , "A" / "B"
{}>(-4845209343945471034)

--------------------
<4: start -> a . a , $
a -> . "A" a , $
a -> . "B" , $
{Term(A): 6, Term(B): 7, NTerm(a): 8}>(598157158659875896)

--------------------
<5: a -> "A" a .  , "A" / "B"
{}>(436327415052220213)

--------------------
<6: a -> "A" . a , $
a -> . "A" a , $
a -> . "B" , $
{Term(A): 6, Term(B): 7, NTerm(a): 9}>(5490562805113673592)

--------------------
<7: a -> "B" .  , $
{}>(-4845209343945471034)

--------------------
<8: start -> a a .  , $
{}>(5795088700656730485)

--------------------
<9: a -> "A" a .  , $
{}>(436327415052220213)

POSSIBLE STATES TO JOIN: (2, 6), (3, 7), (5, 9)
ATTEMPTING CONVERSION TO LALR GRAMMAR...FAILED
CONTINUING WITH CLR(1)...

Эти состояния соответствуют тому, что я могу прочитать в других источниках о компиляции грамматик LALR - этот шаг выглядит нормально, он производит правильные состояния, как если бы я делал это вручную. Генератор предлагает - опять же, это то, что говорят другие источники о преобразовании грамматики CLR (1) в LALR, - в котором говорится, что (2,6), (3,7), (5,9) можно объединить, но он не может этого сделать. Когда я смотрю на созданные таблицы action и goto , я понимаю, почему:

Как вы можете см. состояния 2 и 6 не могут быть объединены, потому что есть несовместимые элементы s2 <> s6, s3 <> s7 и так далее.

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

Означает ли это, что эта классическая c "LALR" грамматика является LALR только тогда, когда человек делает компиляцию вручную? Что мой генератор парсеров делает иначе?

Answer 1

Я думаю, проблема здесь:

Как видите, состояния 2 и 6 не могут быть объединены, потому что есть несовместимые элементы s2 <> s6, s3 <> s7 и т. Д. .

На самом деле это не совсем так. Обратите внимание, что в состоянии 2 элементы сдвига переводят вас, соответственно, в состояния 2 и 3. В состоянии 6 элементы сдвига переводят вас, соответственно, в состояния 6 и 7. Но здесь нет несовместимости, потому что вы пытаетесь объединить состояния 2 и 6 вместе и объединить состояния 3 и 7 вместе. Другими словами, да, эти сдвиги делают в настоящее время говорят go в разные места, но после того, как вы объедините все состояния с одним и тем же ядром вместе, вы закончите тем, что все они скажут go в то же место.

В общем, я не верю, что есть случай, когда слияние двух состояний LR (1) вызовет конфликт «сдвиг / сдвиг». Чтобы понять, почему это так, обратите внимание, что каждое состояние LR (1) соответствует состоянию в анализаторе LR (0), за исключением того, что каждый элемент LR был аннотирован набором элементов просмотра вперед. При переходе от LR (1) к LALR (1) вы объединяете вместе состояния LR (1) с одними и теми же элементами, игнорируя опережающие просмотры, что означает, что вы по существу объединяете вместе состояния LR (1), которые соответствуют одному и тому же LR ( 0).

В результате, если у вас есть состояние LR (1) S, которое говорит: «go для состояния T на символе a», то состояние LR (0), соответствующее S, имеет переход в состояние LR (0), соответствующее T, и это также будет верно для любого состояния LR (1), с которым будет объединяться S.

Единственные конфликты, которые могут возникнуть в ходе При построении парсера LALR (1) возникают конфликты уменьшения / уменьшения, и это то, чего вам нужно быть начеку.

Answer 2

Я не знаю, что делает ваш генератор парсеров, но стандартные генераторы парсеров не имеют проблем с этой грамматикой. Вот, например, таблица переходов состояний bison, созданная с помощью:

bison --report-file=aa.output --report=all --graph=aa.dot --output=/dev/null \
      <(printf "%%%%\n%s" "start: a a; a: 'A' a | 'B'")
dot -o aa.png -Tpng aa.dot

(Bison - действительно удобный инструмент; даже если вы пишете собственный генератор синтаксического анализатора, вы можете воспользоваться его возможностями. См. Также его вывод XML.)

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

Grammar

    0 $accept: start $end
    1 start: a a
    2 a: 'A' a
    3  | 'B'

State 0
    0 $accept: . start $end
    1 start: . a a
    2 a: . 'A' a
    3  | . 'B'

    'A'  shift, and go to state 1
    'B'  shift, and go to state 2

    start  go to state 3
    a      go to state 4

State 1
    2 a: . 'A' a
    2  | 'A' . a
    3  | . 'B'

    'A'  shift, and go to state 1
    'B'  shift, and go to state 2

    a  go to state 5

State 2
    3 a: 'B' .

    $default  reduce using rule 3 (a)

State 3
    0 $accept: start . $end

    $end  shift, and go to state 6

State 4
    1 start: a . a
    2 a: . 'A' a
    3  | . 'B'

    'A'  shift, and go to state 1
    'B'  shift, and go to state 2

    a  go to state 7

State 5
    2 a: 'A' a .

    $default  reduce using rule 2 (a)

State 6
    0 $accept: start $end .

    $default  accept

State 7
    1 start: a a .

    $default  reduce using rule 1 (start)