I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct.

$S \to NP$ $V$ $NP$
$NP \to$ the $N$
$N \to$ cat | mouse
$V \to$ ate


$S\to NP$ $V$ $NP$
$S\to$ the $N$ $V$ $NP$
$S\to$ the $N$ $V$ the $N$
$S\to$ the cat $V$ the $N$
$S\to$ the cat ate the $N$
$S\to$ the cat ate the mouse


$S\to NP$ $V$ $NP$
$S\to NP$ $V$ the $N$
$S\to$ the $N$ $V$ the $N$
$S\to$ the $N$ $V$ the mouse
$S\to$ the $N$ ate the mouse
$S\to$ the cat ate the mouse

My Thoughts

My lecture material says that we operate on the left/rightmost non terminal. I'm not 100% sure how to differentiate terminals and non-terminals but I assumed that if it became an English word it was a terminal hence I skipped it as long as there was a production remaining with another identifier in it.

Parse Tree

I know that the parse tree should be the same for the left and right derivation of the above grammar, just don't know how to build one. All examples I find online are too complex for my understanding. I just started learning about this stuff very recently. I genuinely don't know how to create the parse trees.


1 Answer 1


A non-terminal is something with a production rule. You're correct that words aren't non-terminals. They are terminal precisely because there is no production which expands the word.

In a leftmost derivation, every step must expand the leftmost non-terminal. The leftmost non-terminal is the non-terminal which is closest to the left :-). In $\text{the N V NP}$ , the leftmost non-terminal is $\text{N}$. So if you choose a derivation step which expands $\text{NP}$, that's not a leftmost derivation.

In a parse tree, the root is whatever the root of the grammar is ($\text{S}$ in this case) and each node has as its children the symbols on the right-hand side of the production which is used the expand that particular non-terminal. Terminals are leaf nodes; they have no children.


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.