Parse Tree

Given a set of variables and a set of terminal symbols , a parse tree is a tree with labelling such that:

1. if is a leaf then
2. if is not a leaf then

We always look at this tree as being rooted at the top and then having a notion of left to right. For example, if is a Grammar and the parse tree “respects” and say is a rewrite rule, then is the leftmost descendent of , is the middle descendent of , while is the rightmost descendent of .

Parse Tree 2025-05-10 22.38.00.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Excalidraw Data

Text Elements

Link to original

Note that parse tree is not meant to simulate a grammar. It is merely here to represent one derivation (and it may not exist for certain derivations in some grammars)

Write for the word consisting of leaves read from left to right.

Proposition

Let be a context-free grammar which produces a word . Then there exists a (not necessarily unique) parse tree such that .