4
$\begingroup$

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)
  • META II

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

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ thanks. I'm clearly too novice on this topic. $\endgroup$
    – Foad
    Commented Jun 21, 2020 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$ Commented Jun 21, 2020 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
    Commented Jun 21, 2020 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$ Commented Jun 22, 2020 at 2:34
  • $\begingroup$ @AaronRotenberg can you please tell me what is canonical system as opposed to BNF ? I am reading book by John J. Donovan about system programming. But I couldn't understand what canonical systems are and how are they different than BNF. I tried to google it but didn't find anything relevant. $\endgroup$ Commented Aug 30, 2020 at 10:54
3
$\begingroup$

Here are a couple of pertinent references which support the idea "It mostly doesn't matter/write your own":

  1. different parsing approaches: https://code.jsoftware.com/wiki/Guides/Parsing
  2. a simple table-based (state machine) parser: https://www.jsoftware.com/help/dictionary/dicte.htm
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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