Сдвиг-сокращение конфликтов в простой грамматике (?)

Question

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

%token A B C D SEP 

%% 

items   : /* empty */ 
       | items_nonempty 
       ; 

items_nonempty : item 
       | items_nonempty SEP item 
       ; 

item   :  B 
       |  B  SEP D 
       |  B SEP C 
       |  B SEP C SEP D 
       | A SEP B 
       | A SEP B  SEP D 
       | A SEP B SEP C 
       | A SEP B SEP C SEP D 
       ; 

«items» является (возможно, пустой) последовательность item элементов, разделенных SEP маркером.

Каждый элемент состоит из 4 жетонов (A B C D), в указанном порядке, разделенных SEP. Знаки A, C и D в элементе являются необязательными.

Обратите внимание на повторное использование одного и того же разделительного маркера SEP внутри каждого элемента и между самими элементами.

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

Используя грамматику, как указано, зубры сообщают о 4 смещениях/сокращениях конфликтов. Глядя на «выход», я понимаю, где они происходят и почему; но я в недоумении, как (и если) намеченная грамматика может быть написана, чтобы избавиться от конфликтов S/R.

Я не желаю использовать объявление %expect. Точно так же я не хочу, чтобы мой сканер потреблял токены разделителя, а не передавал их парсеру.

Любые подсказки о том, как дезинформировать эту грамматику, будем очень благодарны.

Answer 1

Грамматика действительно недвусмысленная, она LL (7) и (без проверки) Я считаю, что это LR (2), предположительно даже LALR (2). Поэтому, если бы у вас был генератор для любого из них, он выполнил бы эту работу.

Конфликты lookahead-1 возникают из-за использования одного и того же разделителя как между элементами, так и внутри элементов, и они исчезнут, если вы либо откажетесь от разделителя, либо структуры элемента.

Итак, что вы можете сделать, это разобрать дважды, с разными грамматиками. В первом проходе, можно проверить Сепараторы быть правильно установлены, и грамматика может быть что-то вроде

items   : 
       | items_nonempty 
       ; 
items_nonempty : item 
       | items_nonempty SEP item 
       ; 
item   : A 
       | B 
       | C 
       | D 
       ; 

Во втором (и более важным) пройти, вы бы проверить структуру элемента. Это может быть

items   : 
       | items_nonempty 
       ; 
items_nonempty : item 
       | items_nonempty item 
       ; 
item   : B 
       | B D 
       | B C 
       | B C D 
       | A B 
       | A B D 
       | A B C 
       | A B C D 
       ; 

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

Оба вышеуказанных являются LALR (1), первый - LL (1), а последний LL (4), но он может быть сделан LL (1) некоторым факторингом.

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

Answer 2

Это один сдвиг/уменьшить конфликт:

%token A B C D SEP 

%% 

items 
    : /* empty */ 
    | items_nonempty 
    ; 

items_nonempty 
    : item 
    | items_nonempty SEP item 
    ; 

item 
    : opt_a B opt_c_d_list 
    ; 

opt_a 
    : /* Nothing */ 
    | A SEP 
    ; 

opt_c_d_list 
    : /* Nothing */ 
    | opt_c_d_list c_or_d 
    ; 

c_or_d 
    : SEP C 
    | SEP D 
    ; 

Один только opt_a правила изменяет количество S/R от 4 до 2. Остаточной проблемы заключается в том, что тот же сентябрь sepaerates на C или D после того, как B и Yacc не могут смотреть вперед.Вам понадобится семантическая проверка, чтобы объявить вне закона «B SEP D SEP C»; приведенные выше правила позволят это.

Можете ли вы рассмотреть возможность изменения вашего токенизатора, чтобы вернуть C при чтении SEP C ?, а D при чтении SEP D? Вы можете использовать лексическую обратную связь и условие начала в flex, чтобы при чтении B вы переключали переключатель так, чтобы SEP C возвращался как только C, а SEP D возвращался как только D. Если это было возможно, следующее недвусмысленной грамматики будет работать без каких-либо S/R конфликтов:

%token A B C D SEP 

%% 

items 
    : /* empty */ 
    | items_nonempty 
    ; 

items_nonempty 
    : item 
    | items_nonempty SEP item 
    ; 

item 
    : opt_a B opt_c opt_d 
    ; 

opt_a 
    : /* Nothing */ 
    | A SEP 
    ; 

opt_c 
    : /* Nothing */ 
    | C 
    ; 

opt_d 
    : /* Nothing */ 
    | D 
    ; 

Answer 3

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

Есть целый ряд подходов, вы можете попробовать

• использовать btyacc или поддержку РВА Bison эффективно получить больше предпросмотра.

• написать грамматику, чтобы принять произвольный список отдельных элементов, а затем использовать пост-проход, чтобы перегруппировать их в наборы 1-4 элементов с по меньшей мере 1 B и отклонять искаженные наборы (Это предположение Гюнтера)

• используйте сканер, чтобы сделать больше lookahead - вместо того, чтобы возвращать простые токены SEP, вернуть SEP_BEFORE_A_OR_B или SEP_NOT_BEFORE_A_OR_B в зависимости от того, что следующий токен после SEP есть.

• комбинировать маркеры в сканере - возвращает SEP_C и SEP_D в виде отдельных лексем (сепаратор с последующим C или D)

Answer 4

Вы можете включать SEP следующие ваши другие маркеры в одном правиле. Написано очень лаконично, ваш грамматику можно было бы выразить так:

%token A B C D SEP 
%% 
items : /* empty */ | item | itemsSEP item ; 
item : a B | a b C | a b c D ; 
itemsSEP : itemSEP | itemsSEP itemSEP ; 
itemSEP : a b c d ; 
a : /* empty */ | A SEP ; 
b : B SEP ; 
c : /* empty */ | C SEP ; 
d : /* empty */ | D SEP ; 

Так что теперь у меня есть itemSEP для элемента, разделителя, но item для последнего, который не сопровождается разделителем. Они составлены из однобуквенных нетерминалов в нижнем регистре, каждый из которых включает в себя следующий разделитель, и позаботьтесь о некоторых аргументах, которые являются необязательными. Только последний аргумент item всегда является сырым терминалом, так как после него не будет разделителя.

С выраженной таким образом грамматикой вы не столкнетесь с конфликтами с уменьшением сдвига, так как грамматика теперь LALR (1). На каждом шагу он точно будет знать, какое сокращение применить, даже если основная точка этого правила избавляется от одного SEP, поэтому мы можем искать еще один маркер вперед.