left/right derivations of grammars and parse trees 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-&gt; NP$ $V$ $NP$
$NP -&gt;$ the $N$
$N -&gt;$ cat | mouse
$V -&gt;$ ate
LEFT
$S-&gt; NP$ $V$ $NP$
$S-&gt;$ the $N$ $V$ $NP$
$S-&gt;$ the $N$ $V$ the $N$
$S-&gt;$ the cat $V$ the $N$
$S-&gt;$ the cat ate the $N$
$S-&gt;$ the cat ate the mouse
RIGHT
$S-&gt;NP$ $V$ $NP$
$S-&gt;NP$ $V$ the $N$
$S-&gt;$ the $N$ $V$ the $N$
$S-&gt;$ the $N$ $V$ the mouse
$S-&gt;$ the $N$ ate the mouse
$S-&gt;$ 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.
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.