What is a Parse Tree? + Example

Here we introduce parse trees, which are a visual representation of context-free grammars, specifically in their derivations. We give an example of a parse tree, namely for balanced parentheses. Additionally, we give reasoning as to why (leftmost) derivations are equivalent to parse trees, and that we can then without loss of generality talk about parse trees as a result.

(This is a re-record of a video with the same general material, uploaded in 2020.)

Timeline:
0:00 - Intro
0:24 - Context-Free Grammar for Balanced Parentheses
1:00 - Example Derivation of a String
5:00 - Creating the Parse Tree
10:15 - How to read a string in a Parse Tree?
12:00 - What purpose does a Parse Tree have?

If you like this content, please consider subscribing to my channel:    / @easytheory  

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.