5

I am writing a simple calculator in yacc / bison.

The grammar for an expression looks somewhat like this:

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; }
;

I have declared the precedence of the operators like this.

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

The problem is with the last rule:

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

I want this rule because I want to be able to write expressions like 5(3+4)(3-24) in my calculator.

Is it possible to make this grammar unambiguous?

wefwefa3
  • 3,872
  • 2
  • 29
  • 51
  • I think the [Computer Science](https://cs.stackexchange.com/) site is a more appropriate place for this type of question. – code_dredd Oct 18 '15 at 10:24
  • Thank you for the feedback @ray. I copied this question and posted it there with minor changes. I am not sure if I should close this one on stackoverflow so I will leave it open so people can vote to close it if it is off-topic. – wefwefa3 Oct 18 '15 at 10:39
  • Close it. It's off-topic here and posted there already, as you mentioned. I tried to vote for close, but the CS site did not show up in my other stack exchange site options :/ – code_dredd Oct 18 '15 at 11:05
  • 1
    @ray Since when are yacc/bison questions off topic here? – sepp2k Oct 18 '15 at 13:48
  • 1
    @ray it is a programming question using a standard programming tool and is just as on-topic here as any other programming question. – rici Oct 18 '15 at 17:26
  • @sepp2k: I had suggested that because, from what I can tell, the point of the question is about fixing a grammar to make it unambiguous, not about how to use the yacc/bison tools themselves. It'd be the same thing if he had made the post using BNF instead. – code_dredd Oct 18 '15 at 22:00
  • @rici: IMO, a question about fixing a grammar is more about theoretical computer science than it is about actual programming. See my comment responding to sepp2k. – code_dredd Oct 18 '15 at 22:01
  • @ray: it is no different than asking how, for example, to avoid numerical instability in the computation of a running average. CS helps the practical programmer resolve such issues, but the resolution of a *specific* problem is a programming question, whether about numerical instability or unwanted ambiguity. In this case, it is clearly about actual programming because OP is actually writing an actual program and has included the relevant parts with a clear question. – rici Oct 18 '15 at 22:41
  • @rici: I disagree with your assessment and your comparison. We're looking at the grammar the OP wants to use, not the C/C++ code that would make the grammar work. There's obviously some overlap between SO/CS, though the fact that CS helps the practical programmer does not seem relevant to our discussion, but I digress. BTW, I did *not* say that this question was "off-topic" as someone else mentioned previously, but merely that I thought the CS site was *more appropriate*. – code_dredd Oct 18 '15 at 23:51
  • @ray: we are looking at real compilable bison code, not some abstract formalism. And bison's precedence feature (not actually usable in this case) is a language feature which does not exist in the underlying theoretical model. – rici Oct 19 '15 at 00:27
  • @ray: by the way, are you not the same ray who wrote in a comment "Close it, *it's off-topic here*"? How is that not saying that the question is off-topic? – rici Oct 19 '15 at 00:48
  • @rici: Yes, but I was referring to my original post, where I suggested the CS site. The comment you mention was in response to the OP, who also seemed to think his post was slightly off-topic; I was agreeing with him. Also, if I understand you correctly, when you say that the OP is trying to implement something that "does not exist in the underlying theoretical model", it seems to prove my original point. I'd think a theoretical foundation would be necessary before putting time into an implementation. It's probably like trying to write P algorithm for a NP problem without a proof first. – code_dredd Oct 19 '15 at 01:52
  • @ray: Ok, I give up. That's not at all what I meant, so I'm probably incapable of explaining my thoughts adequately for you. (It would be similar to referring a question about the forward lookahead assertion operator implemented by various regex libraries to CS, on the basis that it's related to the formal theory of regular languages: the formal theory doesn't help you because it is not relevant, but a practitioner may well have good advice. Or referring the aforementioned floating point programmer to a math theory site, when she needs some practical advice about the order of addition.) – rici Oct 19 '15 at 02:22
  • @rici: I think we're both making some valid points. I'm not trying to negate your perspective. I think there's merit to what we're both saying. As I previously said, there is overlap between the topics, so it might boil down to whatever specific aspect we've chosen to focus on a bit more. Still, I accept there's a chance I could've misunderstood the OP's intentions with the post. Cheers. – code_dredd Oct 19 '15 at 02:39
  • 1
    [Also posted on CS.SE](http://cs.stackexchange.com/q/48385/755). Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. @ray, in the future, if you suggest another site, please remind people not to cross-post and tell them how to have their post migrated, so you don't encourage people to do things that violate site rules. Thank you! – D.W. Oct 19 '15 at 07:29
  • @D.W.: I actually did -_- – code_dredd Oct 19 '15 at 07:34
  • @ray, you did, and I thank you for that -- but unfortunately you mentioned it only after the question had already been cross-posted, and at that point it's basically too late. In the future it would be better to mention this up front, when you initially mention another site like CS.SE. Not trying to criticize or pick on you, just making a suggestion that I think might help improve the experience for folks new to Stack Exchange. Thank you for your attention! – D.W. Oct 19 '15 at 17:38

1 Answers1

3

The ambiguity results from the fact that you allow unary operators (- expr), so 2 - 2 can be parsed either as a simple subtraction (yielding 0) or as an implicit product (of 2 and -2, yielding -4).

It's clear that subtraction is intended (otherwise subtraction would be impossible to represent) so it is necessary to ban the production expr: expr expr if the second expr on the right-hand side is a unary operation.

That can't be done with precedence declarations (or at least it cannot be done in an obvious way), so the best solution is to write out the grammar explicitly, without relying on precedence to disambiguate.

You will also have to decide exactly what is the precedence of implicit multiplication: either the same as explicit multiplication/division, or stronger. That affects how ab/cd is parsed. There is no consensus that I know of, so it is more or less up to you.

In the following, I assume that implicit multiplication binds more tightly. I also ensure that -ab is parsed as (-a)b, although -(ab) has the same end result (until you start dealing with things like non-arithmetic types and automatic conversions). So just take it as an example.

term: NUM
    | '(' expr ')'
unop: term
    | '-' unop
    | '+' unop
conc: unop
    | conc term
prod: conc
    | prod '*' conc
    | prod '/' conc
expr: prod
    | expr '+' prod
    | expr '-' prod
rici
  • 234,347
  • 28
  • 237
  • 341