# 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-> 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.

## 1 Answer

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.