I'm implementing a simple calculator in modulo arithmetic (ring Z_p, so I have {0, 1, 2, ..., p - 1} where p is prime). If the input is -x I want to print the correct value p-x on the output. My grammar:
exp: num { std::cout << $1 << " "; $$ = $1; }
| '-' exp %prec NEG { $$ = negate($2); os << "~ "; } // for expressions
num:
MINUS NUMBER %prec NEG { $$ = negate($2); }
| NUMBER { $$ = $1; }
Previosuly I had NUMBER where now num is in exp. The thing is then printed x and not p-x. I don't see any other way to do this - how can I know if in the next step I will have terminal? So I came up with this. However, it gives me warnings about reduction/reduction conflicts (well, I can see why) but it gives correct results.
My question is: how can I do this better? Can I get rid of warnings but still have what I want?
EDIT:
Assume that p= 7.
Then if I write -(8+5) I want the output (reverse polish notation) to be 1 5 + as 8mod7=1. This can be handled by the second rule in exp.
But if I write -5 then I want to display 2 as it is the correct value. And this cannot be done with rule only in exp because I print the exact number there:
exp:
NUMBER { std::cout << $1 << " "; $$ = $1; } /* value of rule is $1 */
| exp PLUS exp { $$ = add($1, $3); std::cout << "+ "; }
| MINUS exp %prec NEG { $$ = negate($2); }
;
These rules don't work the way I want, so I came up with workaround I presented above.
I guess what you're trying to do is this:
Accept as input arithmetic expressions, using signed integer operands and the usual range of algebraic operators, including unary negation.
Ambiguity is avoided by requiring the argument of unary negation to be something other than an integer literal.
Evaluate each expression in the ring Zp, for a given prime p.
Also, for each expression print out the equivalent in reverse polish, with all integer operands normalised modulo p.
It's the last requirement which makes this problem different from the usual calculator. Normally, the advice would be to abandon trying to distinguish between different uses of the unary negation operator, since it's unnecessary.
But if you really want to distinguish the two uses, you can do that. You just need to write more explicit rules. That means giving up on operator precedence for the negation operator, since that rule needs to unambiguously define what the possible operands are.
To start with, we have two ways of writing numeric constants, both of which need to print out the constants (normalised) value.
num : NUMBER { $$ = ring.normal($1); std::cout << $$ << ' '; }
negnum
: '-' NUMBER { $$ = ring.negate(ring.normal($2)); std::cout << $$ << ' '; }
Why did I write that as two different non-terminals? Because the next step is to identify which syntactic constructs can be the operand of the unary negative operator. num cannot, because -3 must be parsed as a negnum and printed as 4. But a negnum can (presumably) be the operand of unary negation; --3 should be printed as 4 ~ (assuming p == 7). So they have to be kept separate. Other things which can be the operand of a unary negative are parenthesized expressions and the result of applying unary negative. (Also, maybe, variables, if there are such things. That's not clear in the question, so I left them out):
neg : negnum
| '(' expr ')' { $$ = $2; }
| '-' neg { $$ = ring.negate($2); std::cout << "~ "; }
With that done, we can now write the syntax of expressions. For this part, we can use precedence in the normal way (although the cascading grammar is also pretty simple):
%left '+' '-' ;
%left '*' '/' ;
expr: num
| neg
| expr '+' expr { $$ = ring.add($1, $3); std::cout << "+ "; }
| expr '-' expr { $$ = ring.sub($1, $3); std::cout << "- "; }
| expr '*' expr { $$ = ring.mul($1, $3); std::cout << "* "; }
| expr '/' expr { $$ = ring.div($1, $3); std::cout << "/ "; }
Test (with a top-level production which prints the evaluated result of each expression):
$ ./ringcalc 7
> 3
3 = 3
> 3+4
3 4 + = 0
> 3-4
3 4 - = 6
> 3+4*5
3 4 5 * + = 2
> 3*4+5
3 4 * 5 + = 3
> -3
4 = 4
> --3
4 ~ = 3
> -(8+5)
1 5 + ~ = 1