LALR (1) сдвиг / уменьшение ошибки с использованием% для процентов и мод - PullRequest
Новая
       79

LALR (1) сдвиг / уменьшение ошибки с использованием% для процентов и мод

0 голосов
/ 24 апреля 2020

Я начал проект с грамматики, которая использовала % (и слово mod) для операторов модулей, и теперь я хотел бы добавить % в качестве конечного унарного оператора, чтобы разделить на 100.

Несколько замечаний: я не работаю с языком на C, я реализовал свой собственный токенизатор / компилятор, используя вывод XML от bison. И мой выбор шагов имеет решающее значение для моей реализации.

Есть ли способ заставить мою грамматику компилироваться без каких-либо ошибок сдвига / уменьшения в компиляторе LALR (1)?

В основном все следующие утверждения действительны:

  • 5% -> 0,05
  • 5%%5 -> 0,05 мод 5
  • 5%%%5 -> 0,0005 мод 5 et c.

Я просто не знаю, как сформулировать это в моей грамматике: 

%token S_NUM

%%

default: mod_term ;

mod_term: _mod_value
    | percent_term ;

_mod_value: mod_term O_PERCENT percent_term ;

percent_term: _percent_value
    | value ;

_percent_value: value O_PERCENT ;

value: S_NUM ;

%%

Я также скомпилировал ее, используя следующее выражение: bison -v --report=all --warnings=no-other -Werror=conflicts-sr --xml test.y -o test.y.xml

(Где я вынужден сдвигать / уменьшать как ошибки из-за моего окружения)

Есть идеи? Я играл со спецификаторами %left и %right, но не повезло.

Ответы [ 2 ]

0 голосов
/ 05 мая 2020

У вас есть неоднозначность между '%', являющимся постфиксным оператором и инфиксным оператором. Это очень похоже на проблему синтаксического анализатора общих выражений, когда '-' является одновременно префиксом и инфиксным оператором, и вы можете решить ее аналогичным образом с помощью явной директивы %prec. Традиционный способ написать это будет: 

%left '%'            /* left-associative infix operator */
%nonassoc POSTFIX    /* postfix operations are higher precedence */
%token VAL
%%

expr: expr '%' expr
    | expr '%' %prec POSTFIX
    | VAL
    ;

с использованием приоритета для решения как ассоциативной неоднозначности infix-%, так и неоднозначности приоритета между infix и postfix.

Чтобы решить ее без правила старшинства, вам нужно что-то вроде: 

%token S_NUM O_PERCENT
%%

default: mod_term ;

mod_term: _mod_value
    | _mod_value O_PERCENT mod_term ;

_mod_value: _mod_value O_PERCENT ;
    | S_NUM
    ;

, что делает правый инфикс%% вместо левого. К сожалению, я не вижу способа решить эту проблему без использования правил приоритета, что также делает infix-% левосторонним. Это связано с тем, что вы не можете решить, является ли данный '%' токен инфиксным или постфиксным, пока не увидите токен после , поэтому нетерминал перед '%' должен быть одинаково для обоих правил (_mod_value здесь или expr в коде% pre c)

0 голосов
/ 05 мая 2020

Если вы готовы принять увеличение сложности для вашего анализатора, вы всегда можете превратить его в анализатор GLR, добавив директиву %glr-parser. Это будет означать, что синтаксический анализатор разделит и исследует оба состояния, когда достигнет точки конфликта, а затем удалит любое состояние, которое не сможет проанализировать, как только он обработает достаточно токенов. Это требует достаточно новой версии бизона. Однако, как предполагают другие люди, может быть, лучше изменить язык. Использование анализатора GLR будет означать, что вы, вероятно, в конечном итоге будете использовать экспоненциальный объем памяти в количестве процентов, которое у вас будет в строке, учитывая существующие ограничения Bison для анализаторов GLR.

...