Ullman's Introduction to Automata, Languages and Computing (1979) says
10.6 LR(0) GRAMMARS
...
A right-sentential form is a sentential form that can be derived by a rightmost derivation.
Is every sentential form also a right-sentential form, by definition? (I guess so.) In Chapter 4 Context Free Grammars, I learned that
Given a CFG, a sentential form is a string of terminals and nonterminals which can be derivable from the start symbol.
Since a sentential form is derivable from the start symbol, there exists at least one parse tree from the start symbol and the sentential form.
-
If w is in L(G) for CFG G, then w has at least one parse tree, and corresponding to a particular parse tree, w has a unique leftmost and a unique rightmost derivation.
I think the same can be generalized from a string of terminals to a sentential form.
So isn't it that each sentential form always has at least one rightmost derivation? Therefore, isn't every sentential form also a right-sentential form, by definition? Why is the concept of "right sentential form" introduced?
Thanks.
$$\begin{align}S&\to A B\\ A&\to a\\ B&\to b\\ \end{align} $$ For this grammar, $aB$ is not a right sentential form because $A$ was not the rightmost non-terminal when it was replaced. So $aB$ cannot appear in any rightmost derivation even though it can be derived.