Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Unambiguous grammar for arithmetic expression with Unary + and -

I have just started self-studying the Dragon book of Compiler Design. I am working on a problem that says to design grammar for an expression containing binary +,-,*,/ and unary +,-

I came up with following

E -> E+T | E-T | T
T -> T*P | T/P | P
P -> +S | -S | S
S -> id | constant | (E)

However, there is an obvious flaw in it. According to this grammar, expressions like

1--3

are valid, which is an error in all programming languages I know. Though, expressions like

1+-+3
and
1- -3

must be valid. How can such a grammar be designed?

like image 209
patentfox Avatar asked Dec 22 '25 06:12

patentfox


1 Answers

I believe your problem is with tokenization. You are identifying 1--3 as an error because you think it should be resolved as 1 --3 rather than 1 - -3, the latter being perfectly valid. So I think you problem comes because when you tokenize the string you are getting:

['1', '-', '-' , '3']

rather than:

['1', '--', '3']

like image 189
justin.m.chase Avatar answered Dec 24 '25 11:12

justin.m.chase



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!