Можно ли сделать эту грамматику YACC однозначной? выражение: | выражение выражение

Я пишу простой калькулятор на yacc/bison.

Грамматика для выражения выглядит примерно так:

expr
: NUM
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| '+' expr %prec '*' { $$ = $1; }
| '-' expr %prec '*' { $$ = $1; }
| '(' expr ')' { $$ = $2; }
| expr expr { $$ = $1 '*' $2; }
;

Я объявил приоритет таких операторов.

%left '+' '-'
%left '*' '/'
%nonassoc '('

Проблема с последним правилом:

expr expr { $$ = $1 $2; }

Мне нужно это правило, потому что я хочу иметь возможность писать выражения типа 5(3+4)(3-24) в своем калькуляторе.

Можно ли сделать эту грамматику однозначной?


grammar ambiguity yacc bison ambiguous-grammar
person wefwefa3    schedule 18.10.2015    source источник
comment
Я думаю, что сайт Computer Science является более подходящим местом для такого типа вопросов.   -  person code_dredd    schedule 18.10.2015
comment
Спасибо за отзыв @Ray. Я скопировал этот вопрос и разместил его там с небольшими изменениями. Я не уверен, должен ли я закрыть это на stackoverflow, поэтому я оставлю его открытым, чтобы люди могли проголосовать за его закрытие, если оно не по теме.   -  person wefwefa3    schedule 18.10.2015
comment
Закрой его. Это не по теме здесь и уже размещено там, как вы упомянули. Я пытался проголосовать за закрытие, но сайт CS не отображался в других моих вариантах сайта обмена стеками :/   -  person code_dredd    schedule 18.10.2015
comment
@ray С каких это пор вопросы о yacc/bison здесь не по теме?   -  person sepp2k    schedule 18.10.2015
comment
@ray это вопрос программирования с использованием стандартного инструмента программирования, и он здесь так же актуален, как и любой другой вопрос программирования.   -  person rici    schedule 18.10.2015
comment
@sepp2k: я предложил это, потому что, насколько я могу судить, суть вопроса в том, чтобы исправить грамматику, чтобы сделать ее однозначной, а не в том, как использовать сами инструменты yacc/bison. Было бы то же самое, если бы он сделал пост, используя вместо этого BNF.   -  person code_dredd    schedule 19.10.2015
comment
@rici: ИМО, вопрос об исправлении грамматики больше касается теоретической информатики, чем фактического программирования. Смотрите мой комментарий в ответ на sepp2k.   -  person code_dredd    schedule 19.10.2015
comment
@ray: это то же самое, что спросить, как, например, избежать численной нестабильности при вычислении скользящего среднего. CS помогает программисту-практику решать такие проблемы, но решение конкретной проблемы — это вопрос программирования, будь то числовая нестабильность или нежелательная неоднозначность. В этом случае речь явно идет о реальном программировании, потому что OP фактически пишет реальную программу и включает соответствующие части с четким вопросом.   -  person rici    schedule 19.10.2015
comment
@rici: я не согласен с вашей оценкой и вашим сравнением. Мы смотрим на грамматику, которую хочет использовать OP, а не на код C/C++, который заставит грамматику работать. Очевидно, что между SO/CS есть некоторое совпадение, хотя тот факт, что CS помогает программисту-практику, кажется, не имеет отношения к нашему обсуждению, но я отвлекся. Кстати, я не сказал, что этот вопрос не по теме, как кто-то упоминал ранее, а просто сказал, что я считаю сайт CS более подходящим.   -  person code_dredd    schedule 19.10.2015
comment
@ray: мы смотрим на настоящий компилируемый код бизона, а не на какой-то абстрактный формализм. А функция приоритета bison (на самом деле не применимая в данном случае) — это языковая функция, которой нет в лежащей в основе теоретической модели.   -  person rici    schedule 19.10.2015
comment
@ray: кстати, ты не тот самый луч, который написал в комментарии Закрой, это не по теме? Как тут не сказать, что вопрос не по теме?   -  person rici    schedule 19.10.2015
comment
@rici: Да, но я имел в виду свой оригинальный пост, где я предложил сайт CS. Комментарий, который вы упомянули, был ответом на ОП, который, похоже, тоже подумал, что его пост немного не по теме; Я соглашался с ним. Кроме того, если я правильно вас понял, когда вы говорите, что ОП пытается реализовать что-то, чего не существует в базовой теоретической модели, это, кажется, подтверждает мою первоначальную точку зрения. Я думаю, что теоретическая основа будет необходима, прежде чем тратить время на реализацию. Вероятно, это похоже на попытку написать P-алгоритм для задачи NP без предварительного доказательства.   -  person code_dredd    schedule 19.10.2015
comment
@ray: Хорошо, я сдаюсь. Я совсем не это имел в виду, поэтому, наверное, не в состоянии адекватно объяснить вам свои мысли. (Это было бы похоже на передачу вопроса об операторе утверждения вперед, реализованном различными библиотеками регулярных выражений, в CS на том основании, что он связан с формальной теорией регулярных языков: формальная теория не поможет вам, потому что она не актуальна. , но у практикующего вполне может быть хороший совет. Или отсылка вышеупомянутого программиста с плавающей запятой на сайт теории математики, когда ей нужен практический совет о порядке сложения.)   -  person rici    schedule 19.10.2015
comment
@rici: я думаю, что мы оба делаем некоторые правильные выводы. Я не пытаюсь опровергнуть вашу точку зрения. Я думаю, в том, что мы оба говорим, есть смысл. Как я уже говорил ранее, темы пересекаются, поэтому все может сводиться к тому конкретному аспекту, на котором мы решили сосредоточиться немного больше. Тем не менее, я допускаю, что есть шанс, что я мог неправильно понять намерения ОП с этим постом. Ваше здоровье.   -  person code_dredd    schedule 19.10.2015
comment
Также опубликовано на CS.SE. Пожалуйста, не публикуйте один и тот же вопрос на нескольких сайтах. Каждое сообщество должно иметь честный шанс ответить без чьей-либо траты времени. Если вы не получите удовлетворительного ответа через неделю или около того, смело отмечайте перенос. @ray, в будущем, если вы предложите другой сайт, напомните людям не размещать перекрестные сообщения и расскажите им, как перенести их сообщение, чтобы вы не поощряли людей делать то, что нарушает правила сайта. Спасибо!   -  person D.W.    schedule 19.10.2015
comment
@D.W.: Я действительно сделал -_-   -  person code_dredd    schedule 19.10.2015
comment
@ray, вы это сделали, и я благодарю вас за это, но, к сожалению, вы упомянули об этом только после того, как вопрос уже был опубликован, и в этот момент уже слишком поздно. В будущем было бы лучше упомянуть об этом заранее, когда вы впервые упоминаете другой сайт, такой как CS.SE. Не пытаюсь критиковать или придираться к вам, просто делаю предложение, которое, я думаю, может помочь улучшить опыт для людей, плохо знакомых со Stack Exchange. Спасибо за Ваше внимание!   -  person D.W.    schedule 19.10.2015

Ответы (1)


arrow_upward
3
arrow_downward

Неоднозначность возникает из-за того, что вы разрешаете унарные операторы (- expr), поэтому 2 - 2 можно анализировать либо как простое вычитание (получающее 0), либо как неявное произведение (2 и -2, дающее -4).

Понятно, что предполагается вычитание (иначе вычитание было бы невозможно представить), поэтому необходимо запретить производство expr: expr expr, если второе expr в правой части является унарной операцией.

Это невозможно сделать с помощью объявлений приоритета (или, по крайней мере, это нельзя сделать очевидным образом), поэтому лучшее решение — написать грамматику явно, не полагаясь на приоритет для устранения неоднозначности.

Вам также нужно будет точно решить, каков приоритет неявного умножения: либо такой же, как явное умножение/деление, либо сильнее. Это влияет на то, как анализируется ab/cd. Насколько мне известно, единого мнения нет, так что это более или менее зависит от вас.

В дальнейшем я предполагаю, что неявное умножение связывает более тесно. Я также гарантирую, что -ab анализируется как (-a)b, хотя -(ab) имеет тот же конечный результат (пока вы не начнете иметь дело с такими вещами, как неарифметические типы и автоматические преобразования). Так что просто возьмите это как пример.

term: NUM
    | '(' expr ')'
unop: term
    | '-' unop
    | '+' unop
conc: unop
    | conc term
prod: conc
    | prod '*' conc
    | prod '/' conc
expr: prod
    | expr '+' prod
    | expr '-' prod
person rici    schedule 18.10.2015