8

I have written tokenizer and expression evaluator for a preprocessor language that I plan to use in my later projects. I started thinking that maybe I should describe the language with EBNF (Extended Backus–Naur Form) to keep the syntax more maintainable or even use it to generate later versions of a parser.

My first impression was that EBNF is used for tokenizing process and syntax validation. Later I discovered that it can also be used to describe operator precedence like in this post or in the Wikipedia article:

expression ::= equality-expression
equality-expression ::= additive-expression ( ( '==' | '!=' ) additive-expression ) *
additive-expression ::= multiplicative-expression ( ( '+' | '-' ) multiplicative-expression ) *
multiplicative-expression ::= primary ( ( '*' | '/' ) primary ) *
primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary

I can see how that allows generator to produce code with operator precedence built in but is this really how precedence should be expressed? Isn't operator precedence more about semantics and EBNF about syntax? If I decide to write description of my language in EBNF, should I write it with operator precedence taken into account or document that in a separate section?

Community
  • 1
  • 1
Mika Lammi
  • 1,278
  • 9
  • 21
  • 2
    No. Operator precedence is not semantic, it is about syntax and grouping, and it is implemented at parse time, not subsequently. There's no reason not to express it in the EBNF. – user207421 Aug 13 '14 at 19:10
  • Great question. Exactly what I am struggling with right now. – Noel Widmer Jan 22 '18 at 18:37

1 Answers1

6

Did a similar stuff for my collegue degree.

I suggest DO NOT use the operator precedence feature, even if looks easier like "syntact sugar".

Why ? Because most languages to be described by EBNF, use a lot of operators with different features, that are better to describe & update, with EBNF expressions, instead of operator precedence.

Some operators are unary prefix, some unary posfix, some are binary (a.k.a. "infix"), some binary are evaluated from left to right, & some are evaluated from right to left. Some symbols are operators in some context, and used as other tokens, in other context, example "+", "-", that can be binary operators ("x - y"), unary prefix operators ("x - -y"), or part of a literal ("x + -5").

In my experience its more "safe" to describe them with EBNF expressions. Unless the programming language you describe, is very small, with very few and similar syntax operators (example: all binary, or all prefix unary).

Just my 2 cents.

umlcat
  • 4,091
  • 3
  • 19
  • 29
  • I’d recommend to sort out literal signs during lexical analysis. This way we’ll only have to consider unary and binary operators during syntactic analysis. Life is also getting a lot easier when no postfix unary operators are used. Rust is a great example for a powerful language without postfix unaries. If it is easier to parse - it is most likely easier to read for the human eye. – Noel Widmer Jan 22 '18 at 18:44