Does anyone know how BNF rules expecting the empty string ($\epsilon$ or the "") behave during creation of a parse tree using grammar from a string of symbols? For example the BNF grammar:

<r0> ::= <opt-whitespace> "a" <opt-whitespace> "b" <opt-whitespace>
<opt-whitespace> ::= " " <opt-whitespace> | ""

How is the $\epsilon$ read during creation of a parse tree for string in the language? From what I observe, when the parser is recursing <opt-whitespace> for each next symbol of input, eventually "a" will be read which is not in the rules for <opt-whitespace> and the string will not be recognized.

I understand the use of $\epsilon$ when using the grammatical rules to generate the strings of the language, however it causes confusion when I think of how to parse the input.

  • 1
    $\begingroup$ I'm not sure what kind of answer you're looking for. Your statements ("From what I observe...") look correct. Are you familiar with the definition of the language accepted by a context-free grammar? If not, I'd suggest consulting a textbook on formal language / automata theory. $\endgroup$ – D.W. Nov 13 '20 at 18:29

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.