CODEWITHSUNDEEP
compiler-constructiongrammarcontext-free-grammar
Ashkan Kazemi
Ashkan Kazemi

Reputation: 1097

How to tell the precedence of operators in a context free grammar

How can we know which of the following logical operations ( or, and, not ) in the bellow context free grammar have higher precedence? Is there a general approach to this kind of problems?

X → X or Y | Y

Y → Y and Z | Z

Z → not Z | (X) | true | false

Upvotes: 5

Views: 5580

Answers (1)

Lucas Trzesniewski
Lucas Trzesniewski

Reputation: 51330

Here's an example approach:

expr -> addExpr;
addExpr -> multExpr (('+'|'-') multExpr)*;
multExpr -> terminalExpr (('*'|'/') terminalExpr)*;
terminalExpr -> integer | variable | '(' expr ')';

But the associativity is ambiguous. Here's a more explicit way in BNF:

expr -> addExpr;
addExpr -> addExpr '+' multExpr | addExpr '-' multExpr | multExpr;
multExpr -> multExpr '*' terminalExpr | multExpr '/' terminalExpr | terminalExpr;
terminalExpr -> integer | variable | '(' expr ')';

These grammars define the operators * and / as having more precedence as + and -. You declare the operation with higher precedence deeper in the parse tree, so they will be tried first by the parser.

Upvotes: 15

Related Questions