[Solved]: How to represent whitespace in a context-free grammar?

Problem Detail: 

Say we want to support: xx

The following grammar does accept it:

• S -> xAx
• A -> ε.

because S => xAx => xx.

But what about supporting: x x

I realize this might be a stupid question but I'm really unable to find a definite answer. Especially as

• S -> xAx
• S -> x A x

appear to be equivalent representations in most references.

Asked By : Xpl0

Answered By : babou

This is a classical confusion between language and metalanguage.

More generally, you have the same problem when you want to include in your symbols, expecially terminal symbols, characters that have syntactic meaning in the syntax of grammars, for example the symbol "|" which is often used to give on the same line all possible right-hand-sides for a given non-terminal.

In such a case, you do what I just did: use some mechanism for quotation, such as "|", or " " in the case of a space. Some form of quoting is the usual technique to avoid confusion between language and metalanguage. And as you remarked, the language of grammars already uses the space for its own (lack of) purposes.

So you write:

S -> xAx A -> " " 

Of course, the spaces outside the quotes still play the same role as before, wherever allowed. So the grammar could be written as well:

S ->  x A  x A  ->   " " 

Whatever is within quote must be written exactly as expected.

However, in many contexts (such as programming language syntax), it is implicit that you can add spaces wherever you want between terminal. So you have to be clear whather you just want one compulsory space where you have the terminal " ", or whether you forbid spaces, unless specified by the syntax as done here.

The quotation marks are metasyntax, i.e. part of the language used to write the grammar, like the arrow. The analyser (whether LR(1) or any other) will ignore the quotes, as it ignores the arrow ->. It would work as well with a grammar written as [(S,xAx)(A," ")]. Some metalanguages for writing grammars, such as BNF, simplify the issue by making the quotes compulsory around terminals ... though there is still a problem when terminals include the quoting symbols ... but this has solutions.

Another question you may want to look at is: What are the meanings of metalanguage and metasyntax and EBNF?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33744