A collapsible non-terminal? is one which is replaced by its child nodes in the derivation tree after it has been used in a derivation. An example will help:
Consider the grammar
S → Sa | a
which generates the language a+. Consider the string
aaa, which has the derivation tree
S
|
Sa
|
Sa
|
a
It's rather ugly and inconvenient to have such a deep tree for such a simple
derivation. Parse trees like this are an artifact of how grammars work; for
convenience, we can declare the right-hand S in the rule S
→ Sa to be collapsible. Then, whenever that rule is applied, the
S on the right side will be collapsed to whatever its child nodes
turn out to be.
So, if we collapse the above tree, we get
S S S
| | |
Sa => Sa => aaa
| |
Sa aa
|
a
This is much more convenient to work with, although the tree is no longer a proper parse tree.