Choosing a production with $\lambda$ in Context-Free Grammars

Question

Given the context-free grammar

\begin{align*} & S \rightarrow AA \\ & A \rightarrow xA \\ & A \rightarrow B \\ & B \rightarrow yB \\ & B \rightarrow \lambda \end{align*} What is the meaning of $\lambda$? $\lambda$ itself means the empty string and will match anything without consuming it, but in terms of the productions, how do you know which one to use? Do you use the last $B$ production only if $B \mapsto yB$ cannot be used? Or can both be used interchangably?

For example, parsing the string $xyy$ could give two different results:

Is there a formal way to prefer one of the two possible options? Which one is the "default"?

Answer 1

I think you have understood this backwards. The CFG defines the language. All strings that can be derived by using the rules defined in the CFG are present in the language. The empty string itself is a terminal variable. You would substitute it in the string that you're deriving and is just empty.

What you are arriving at with the parse trees is called ambiguity of the grammar that you have defined. When the same string can be derived in more than one leftmost derivation, then the grammar is ambiguous. You could use two different substitutions and still arrive at the same string. So, yes, you could use either derivation, but the string itself does not change.

I would say the formal way to derive your string in exactly one particular way is to use a grammar without ambiguity.