I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of all possible notations and the most prevalent one. Though it looks like to be an ancient piece of art. Now I'm wondering that if you want to invent a new programing language what modern alternative you should use and why?

These are what I have found so far:

  • ISO extended Backus–Naur form (EBNF)
  • W3C-BNF
  • augmented Backus–Naur form (ABNF)
  • Extreme BNF (XBNF)
  • Translational Backus–Naur form
  • ANother Tool for Language Recognition (ANTLR)
  • Wirth syntax notation (WSN)
  • Van Wijngaarden grammar
  • Microsoft “M” modeling language
  • Compiler Description Language (CDL)
  • Xtext grammar language
  • definite clause grammar (DCG)

I would like to know what are the advantages and disadvantages of these options?


Answer 1: The question is meaningless as written.

You are mixing different kinds of notations here that are intended for different purposes.

  • BNF and ABNF are concrete notations for writing the abstract concept of a context-free grammar.
  • "Van Wijngaarden grammar" refers either to an abstract type of grammar a la "context-free grammar", or to a concrete notation for writing this type of grammar. Van Wijngaarden grammars are strictly more expressive than context-free grammars. In fact, parsing them is undecidable in general, making them more like an esoteric programming language in some respects.
  • ANTLR is a particular software tool for generating parsers. It has a language for writing grammars that it accepts as input. Like most other parser generators, ANTLR includes specialized features in its grammar language for manipulating the generated parser code. For example, it is possible in an ANTLR input file to directly insert Java code that is to be executed by the generated parser when a certain token is encountered. This sort of feature only makes sense in the context of a parser generator.

Answer 2: It mostly doesn't matter.

If, as you say, "you want to invent a new programing language," there are two situations where writing down a grammar is relevant:

  1. Writing a parser as part of the compiler implementation. Your choice of how to express the grammar here is dictated by how your parser is implemented. Whether you use an ANTLR/Yacc/Bison-style parser generator, a parser combinator library, etc. will determine what your grammar looks like in the source code.

  2. Writing a language specification. Most programming language specifications are written to be read by humans, not computers. Therefore, anything that is sufficiently clear to a human reader is an acceptable choice of notation. It is common for a language specification to define its own grammar notation, rendering the particular choice of notation largely irrelevant. For example, the "Lexical Structure" chapter of the Haskell 2010 Language Report starts with a "Notational Conventions" section that defines how the grammar will be written.

| cite | improve this answer | |
  • $\begingroup$ thanks. I'm clearly too novice on this topic. $\endgroup$ – Foad Jun 21 at 12:24
  • 1
    $\begingroup$ @Foad Don't let my clickbait-y headings get you down! Keep researching and try to focus on the distinctions between mathematical concepts, standardized notations, and software implementations. $\endgroup$ – Aaron Rotenberg Jun 21 at 12:28
  • $\begingroup$ One thing that I think was misunderstood about my question is that ANTLR also has it's own flavor/dialect of BNF. See here for example. $\endgroup$ – Foad Jun 21 at 20:49
  • 1
    $\begingroup$ @Foad I did mention this in my answer. "It [ANTLR] has a language for writing grammars that it accepts as input." However, I have edited my answer to further elaborate on this point. $\endgroup$ – Aaron Rotenberg Jun 22 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.