Using functional notation to extend BNF

"Bill Fenlason" <>
8 Jan 2007 23:35:32 -0500

          From comp.compilers

Related articles
Using functional notation to extend BNF (Bill Fenlason) (2007-01-08)
RE: Using functional notation to extend BNF (Ralf Lammel) (2007-01-09)
Re: Using functional notation to extend BNF (Daniel C. Wang) (2007-01-09)
Re: Using functional notation to extend BNF (Roar) (2007-01-09)
Re: Using functional notation to extend BNF (2007-01-15)
| List of all articles for this month |

From: "Bill Fenlason" <>
Newsgroups: comp.compilers
Date: 8 Jan 2007 23:35:32 -0500
Organization: Road Runner High Speed Online
Keywords: parse, functional
Posted-Date: 08 Jan 2007 23:35:32 EST

I'm writing a BNF specification for a good sized language and it
occurred to me that a nice way to do it is to extend BNF with
functional notation. There is generally "nothing new under the sun",
but I wondered if this approach has been used before. In casual
searches of the web I didn't find anything like it. Perhaps I missed
it or it was tried and discarded long ago.

The functions can be thought of as "production functions" or "nonterminal

For example, things like:
        oneOrMore(1) ::= 1 | oneOrMore(1) 1 ;
        optional(1) ::= | 1 ;
        inParens(1) ::= "(" 1 ")" ;
        commaList(1) ::= 1 | commaList(1) "," 1 ;
        separatedList(1,2) ::= 1 | separatedList(1,2) 2 1 ;

etc. can be defined as part of the specification. By convention the
left paren immediately following an identifier indicates a function,
and the comma separated arguments can be any terminal, nonterminal,
concatenation, set of alternatives or other production functions.
Substitution is straight forward, and as with other forms of EBNF,
nothing new is added to the capabilities of BNF. (Integers were used
for the args above to avoid confusion with nonterminals).

argumentList ::= optional( inParens( optionalCommaList(expression | "*")));

means "an argumentList is optional and enclosed by parens, consisting
of an optional comma separated list of expressions or asterisks."

statementList ::= separatedList( ("this" | "that" | "other") argumentList ,
";") ;

means "A statementList is a list, separated by semicolons, of a keyword
followed by an argumentList . The keyword may be "this", "that" or "other".

This approach does not conflict with conventional EBNF, so things like
optionList ::= inParens( [ commaList(option) ] ) ; can be used.

Writing a translator for this form of EBNF to pure BNF would appear to be
straight forward - perhaps macros or a preprocessor could be used.

While this is not quite as succinct as conventional EBNF (with *,+,? [], {}
etc), I think in some cases it is more expressive and understandable.

Interesting, or just old news?

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.