CODEWITHSUNDEEP
language-designgrammarrulesebnfoperator-precedence
Dan Walmsley
Dan Walmsley

Reputation: 2821

Extended Backus–Naur Form order of operations

I am creating a formal spec for a very simple rule language, very simple. I want to use EBNF as this is a standard but I can't figure out how to specify order of operations. Here is the specification so far.

rule = statement, { (‘AND’|’OR’), statement};

variable = ‘$’,alphabetic character, {alphabetic character | digit};

statement = variable, [ ‘count’,[white space ],’>’,[white space],number ];

alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G"
                     | "H" | "I" | "J" | "K" | "L" | "M" | "N"
                     | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
                     | "V" | "W" | "X" | "Y" | "Z" ;

number = [ "-" ] , digit , { digit } ;

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

white space = ? white space characters ? ;

The question I have is how do I show that things in brackets should be evaluated first. So something like this 

$strap AND ($greenSticker count > 5 OR ($greenSticker AND $redSticker))

It seems like a common feature to most languages, but my Google skills are failing me and I can't seem to find an example.

Upvotes: 6

Views: 3747

Answers (1)

Austin Henley
Austin Henley

Reputation: 4633

Given this as a simplified example LL grammar:

expression -> (+|-|ε) term ((+|-) term)*
term -> factor ((*|/) factor)*
factor -> var | number | (expression)

As you can see, the operators with lower precedence (+ and -) are in a more general rule than the higher precedence operators (* and /). It is all about producing the correct parse tree. But as a rule of thumb, "outer" or more general rules have less precedence, which is why the addition and subtraction operators are placed beside term, because term must be further derived. If you look at more complicated grammars you will see that this is taken into an extreme to have proper precedence.

Upvotes: 12

Related Questions