left/right derivations of grammars and parse trees

Question

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-> NP$ $V$ $NP$

$NP ->$ the $N$

$N ->$ cat | mouse

$V ->$ ate

LEFT

$S-> NP$ $V$ $NP$

$S->$ the $N$ $V$ $NP$

$S->$ the $N$ $V$ the $N$

$S->$ the cat $V$ the $N$

$S->$ the cat ate the $N$

$S->$ the cat ate the mouse

RIGHT

$S->NP$ $V$ $NP$

$S->NP$ $V$ the $N$

$S->$ the $N$ $V$ the $N$

$S->$ the $N$ $V$ the mouse

$S->$ the $N$ ate the mouse

$S->$ 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 genuinely don't know how to create the parse trees and I appreciate any input in helping me figure it out.

edit: I forgot to mention, 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.

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.