Как этот код YACC создает конфликт сдвиг / уменьшение (очень просто) - PullRequest
Новая
       4

Как этот код YACC создает конфликт сдвиг / уменьшение (очень просто)

0 голосов
/ 07 мая 2019

Я действительно пытался понять, почему это создает конфликт, но я думаю, что что-то упустил. 

%token D
%start a

%%

a
    : b
    | a '+' b
    ;

b
    : c
    | c '+' '+'
    ;

c
    : D
    ;

Я обнаружил, что те же символы '+' создают проблему, но я не могу найти никакой двусмысленности в этом коде ...

Я действительно ценю заранее

1 Ответ

1 голос
/ 07 мая 2019

Давайте обозначим ваши альтернативы следующим образом: 

a
    : b          // a1
    | a '+' b    // a2
    ;

b
    : c          // b1
    | c '+' '+'  // b2
    ;

Теперь, если парсер только что проанализировал c, а следующий токен - '+', есть две возможности: + может быть частью c '+' '+', и в этом случае следует выбрать b2 или + может быть частью a '+' b, в этом случае следует выбрать b1, а затем будет a2. Однако парсер не может знать, какой из этих случаев имеет место, не видя второго +, а YACC, являясь генератором парсера LALR(1), может смотреть только на один токен, а не на два.

Так вот почему у вас возникает конфликт. Как уже указывалось, решение этой проблемы - сделать ++ единственным токеном. Это также имеет то преимущество, что пробелы в ++ больше не допускаются, что более точно соответствует синтаксису существующих языков.

...