1
$\begingroup$

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?

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

2 Answers 2

1
$\begingroup$

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:

A'
A
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.)

$\endgroup$
0
$\begingroup$

You can eliminate B by substituting all its expansions wherever it appears, giving the equivalent grammar

A' -> A
A -> if A
A -> if A else S
A -> null
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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