1
$\begingroup$

Sometimes in a context free language we'd like to require spaces between productions, and sometimes not. For example take the following part from a grammar describing grammars:

production = lhs '=' rhs.
lhs = nonterminal.
rhs = nonterminal | terminal |rhs_rest.
rhs_rest = nonterminal rhs_rest | terminal rhs_rest | null.
nonterminal = char chars.
chars = char chars | null.
terminal = '"' char chars '"'.

Note that I intentionally didn't account for spaces. Now consider the input string:

abc = abc"def"aa aa bb "ab""bc"

so abc"def"aa contains three objects, nonterminal+terminal+nonterminal, even though a space is not separating between them. However abc must be interpreted as a single object, not for example ab+c. So we require to have a space between two nonterminal expressions, but not between two terminals or two subsequent nonterminal and a terminal. This would've been easy if we had only pairs, but the rhs may contain many nonterminals and terminals. How to write a grammar that correctly accounts for required and non-required spaces?

$\endgroup$
  • $\begingroup$ Normally this is handled during "lexing" or "tokenizing", before the CFG gets invoked. Is there a reason you want to handle it inside the CFG itself? $\endgroup$ – Draconis Apr 13 at 0:44
  • $\begingroup$ yes i have reasons, very important for my current project, just it would be long and unnecessary to explain. anyway we can think of how to express it using regular expressions as in en.wikipedia.org/wiki/Lexical_grammar it just makes no positive difference vs doing it in cfg $\endgroup$ – Troy McClure Apr 13 at 0:47

Your Answer

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

Browse other questions tagged or ask your own question.