CODEWITHSUNDEEP
grammaroperator-precedencecontext-free-grammar
myName
myName

Reputation: 45

Grammars: How to add a level of precedence

So lets say I have the following Context Free Grammar for a simple calculator language:

S->TS'
S'->OP1 TE'|e
T->FT'
T'->OP2 FT'|e
F->id|(S)
OP1->+|-
OP2->*|/

As one can see the * and / have higher precedence over + and -. However, how can I add another level of precedence? Example would be for exponents, ^, (ex:3^2=9) or something else? Please explain your procedure and reasoning on how you got there so I can do it for other operators.

Upvotes: 3

Views: 772

Answers (1)

rici
rici

Reputation: 241971

Here's a more readable grammar:

expr: sum

sum : sum add_op term
    | term

term: term mul_op factor
    | factor

factor: ID
      | '(' expr ')'

add_op: '+' | '-'
mul_op: '*' | '/'

This can be easily extended using the same pattern:

expr: bool

bool: bool or_op conj
    | conj

conj: conj and_op comp
    | comp

/* This one doesn't allow associativity. No a < b < c in this language */ 
comp: sum comp_op sum

sum : sum add_op term
    | term

term: term mul_op factor
    | factor

/* Here we'll add an even higher precedence operators */
/* Unlike the other operators, though, this one is right associative */
factor: atom exp_op factor
    | atom

atom: ID
    | '(' expr ')'

/* I left out the operator definitions. I hope they are obvious. If not,
 * let me know and I'll put them back in
 */

I hope the pattern is more or less obvious there.

Those grammars won't work in a recursive descent parser, because recursive descent parsers choke on left recursion. The grammar you have has been run through a left-recursion elimination algorithm, and you could do that to the grammar above as well. But note that eliminating left recursion more or less erases the difference between left- and right-recursion, so after you identify the parse with a recursive descent grammar, you need to fix it according to your knowledge about the associativity of the operator, because associativity is no longer inherent in the grammar.

For these simple productions, eliminating left-recursion is really simple, in two steps. We start with some non-terminal:

foo: foo foo_op bar
   | bar

and we flip it around so that it is right associative:

foo: bar foo_op foo
   | bar

(If the operator was originally right associative, as with exponentiation above, then this step isn't needed.)

Then we need to left-factor, because LL parsing requires that every alternative for a non-terminal has a unique prefix:

foo : bar foo'
foo': foo_op foo
    | ε

Doing that to every recursive production above (that is, all of them except for expr, comp and atom) will yield a grammar which looks like the one you started with, only with more operators.

In passing, I emphasize that there is no mysterious magical force at work here. When the grammar says, for example:

term: term mul_op factor
    | factor

what it's saying is that a term (or product, if you prefer) cannot be the right-hand argument of a multiplication, but it can be the left-hand argument. It's also saying that if you're at a point in which a product would be valid, you don't actually need something with a multiplication operator; you can use a factor instead. But obviously you cannot use a sum, since factor doesn't parse expressions with a sum operator. (It does parse anything inside parentheses. But those are things inside parentheses.)

That's the sense in which both associativity and precedence are implicit in the grammar.

Upvotes: 5

Related Questions