Search code examples
parsinggrammarlexerebnf

EBNF Grammar for list of words separated by a space

I am trying to understand how to use EBNF to define a formal grammar, in particular a sequence of words separated by a space, something like

<non-terminal> [<word>[ <word>[ <word>[ ...]]] <non-terminal>
  1. What is the correct way to define a word terminal?
  2. What is the correct way to represent required whitespace?
  3. How are optional, repetitive lists represented?
  4. Are there any show-by-example tutorials on EBNF anywhere?

Many thanks in advance!

Solution

  • You have to decide whether your lexical analyzer is going to return a token (terminal) for the spaces. You also have to decide how it (the lexical analyzer) is going to define words, or whether your grammar is going to do that (in which case, what is the lexical analyzer going to return as terminals?).

    For the rest, it is mostly a question of understanding the niceties of EBNF notation, which is an ISO standard (ISO 14977:1996 — and it is available as a free download from Freely Available Standards, which you can also get to from ISO), but it is a standard that is largely ignored in practice. (The languages I deal with — C, C++, SQL — use a BNF notation in the defining documents, but it is not EBNF in any of them.)

    1. Whatever you want to make the correct definition of a word. You need to think about how you'd want to treat the name P. J. O'Neill, for example. What tokens will the lexical analyzer return for that?
    2. This is closely related to the previous issue; what are the terminals that lexical analyzer is going to return.
    3. Optional repetitive lists are enclosed in { and } braces, or you can use the Kleene Star notation.
    4. There is a paper Extended BNF — A generic base standard by R. S. Scowen that explains EBNF. There's also the Wikipedia entry on EBNF.

    I think that a non-empty, space-separated word list might be defined using:

    non_empty_word_list = word { space word }

    where all the names there are non-terminals. You'd need to define those in terms of the relevant terminals of your system.