Unary And Binary Minus in Parse Tree

Question

I am creating a parse tree that will contain expressions similar to

3 - 4 * 8

or

8 * -5

or

-(10 * 1)

I need a way to distinguish between the unary and binary minus. The way my grammar is going now the binary minus is reached first, but I am thinking of changing that and adding a flag variable that holds the last variable.

Ex: if it is 5 - 6

The flag is holding 5 and if it sees minus and the flag is a number the skip unary and go to binary.

However I am not sure exactly how to implement this in C++

Any help would be greatly appreciated.

Thanks

Do you mean a way to distinguish them as you're doing the parsing, or a way to distinguish them in the parse tree? In the parse tree, it's trivial -- just have separate `UNARY_MINUS` and `BINARY_MINUS` operators. If you mean as you're parsing, a unary minus occurs when you're expecting an operand, not an operator. — Jerry Coffin, May 11 '12 at 18:09
In my parser I would like it to distinguish between a -5 and 4 -5. My next part converts the leafs of this Tree to as AST tree (which is working) but my parser sees everything as a binary minus (4 - 5). — Dfranc3373, May 11 '12 at 18:16

score 8 · Accepted Answer · edited Apr 14 '14 at 11:35

8

The easiest way to implement a parser is by the method of Recursive Descent. Make sure to give binary minus a higher priority than unary minus, like in the referenced site:

 E -->  | E "+" E
        | E "-" E
        | "-" E
        | E "*" E
        | E "/" E
        | E "^" E
        | "(" E ")"
        | v

edited Apr 14 '14 at 11:35

lukas.pukenis

13,057
12
47
81

answered May 11 '12 at 18:13

TemplateRex

69,038
19
164
304

After looking at the site I may re write my grammar rules to follow those of the site, but one problem with that is that this parser must also be able to handle = , < , <=, >, >=, and, or, not – Dfranc3373 May 11 '12 at 18:33
@Dfranc3373 see http://en.cppreference.com/w/cpp/language/operator_precedence for the complete operator precedence for C++ – TemplateRex May 11 '12 at 18:39
1

@Dfranc3373 Great! BTW, did you already read the FAQ http://stackoverflow.com/faq#howtoask on how to score answers? You have accepted an answer to every question that you asked, which is great, but you can also score any answer that you find useful. – TemplateRex May 11 '12 at 18:59

Unary And Binary Minus in Parse Tree

1 Answers1