I'm a bit confused by the role of the empty string in this ambiguous grammar:

A' -> A
A -> if A B
A -> null
B -> [empty string]
B -> else S

So what does B -> empty string mean/do? Does that mean B could transition to A? And "if", "else", and "null are terminals, then what is the empty string?

  • $\begingroup$ It appears that "empty string" is also a terminal. Also, your first production should be $S\rightarrow A$. $\endgroup$ Nov 15 '21 at 16:21

In a grammar when a rule transitions to the empty string, that means that the symbol just disappears. For example, here is a possible derivation:

if A B
if null B
if null

Notice that on the last line, B is replaced by the empty string -- nothing. It goes away. (We could have instead decided to replace B by else S.)


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.