Entry
Compiler: Syntax: Parser: Operator: Priority: BNF: How to give operator higher or lower priority?
Oct 22nd, 2003 21:53
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 23 October 2003 - 06:17 pm --------------------
Compiler: Syntax: Parser: Operator: Priority: BNF: How to give
operator higher or lower priority?
---
For example:
some expression like 3 + 4 - 5 * 6
---
First case: I want to give the '*' symbol a higher priority.
So how do I write my grammar?
---
You have to write this example 3 + 4 - 5 * 6 in the most simple form
for
example in BNF or also in EBNF as:
So you put the nonterminal containing the symbol '*' more on the LEFT
of the expression line.
---
expression = FACTOR '-' term
FACTOR = digit '*' digit
term = digit '+' digit
---
The tree for this BNF is this
expression
|
-
/ \
/ \
/ \
/ \
/ \
FACTOR term
| |
* +
/ \ / \
digit digit digit digit
---
So if you do a top down parse of this tree, you see you will evaluate
the digit * digit part first, because it is in
the branches of the tree.
And as you usually use an INORDER or INFIX traversal of your tree, the
LEFT branch will be traversed first.
So you should put FACTOR on the LEFT side in that line of your
language.
---
---
Second case: I want to give the '+' symbol a higher priority.
So how do I write my grammar?
---
You have to write this example 3 + 4 - 5 * 6 in the most simple form
for
example in BNF or also in EBNF as:
So you put the NONTERMINAL containing the symbol '+' more on the LEFT
of the expression line.
---
expression = TERM '-' factor
TERM = digit '+' digit
factor = digit '*' digit
---
The tree for this BNF is this
expression
|
-
/ \
/ \
/ \
/ \
/ \
TERM factor
| |
+ *
/ \ / \
digit digit digit digit
---
So if you do a top down parse of this tree, you see you will evaluate
the digit + digit part first, because it is in
the branches of the tree.
And as you usually use an inorder or infix traversal of your tree, the
LEFT branch will be traversed first.
So you should put TERM on the LEFT side in that line of your language.
----------------------------------------------------------------------
