Grammatically Rooting Oneself With Parse Trees

Vaidehi Joshi
Nov 20, 2017 · 17 min read
Image for post
Image for post
Grammatically rooting oneself with parse trees!

Parsing for the meaning of parsing

Image for post
Image for post
Parse tree: a definition.

A parse tree is a really just a “diagrammed” form of a sentence; that sentence could be written in any language, which means that it could adhere to any set of grammatical rules.

Image for post
Image for post
Simple sentence diagramming with parse trees.

In the case of the English language, the smallest “part” of every sentence is a word; words can be combined into phrases, like noun phrases or verb phrases, which can, in turn, be joined with other phrases to create a sentence epression.

Image for post
Image for post
What does it actually mean to parse something?

Parsing expressions like it’s our job

Image for post
Image for post
Finding the grammar in mathematical expressions.
Image for post
Image for post
Representing mathematical expressions as a parse tree.
Image for post
Image for post
The same expression could evaluate to different parse trees.
Image for post
Image for post
Ambiguous grammar in (parsing) action!

Here’s the rub, though: ambiguous grammar is problematic for a compiler!

Image for post
Image for post
Combating ambiguous grammar as a compiler

A token of my affection (for my parser)

Image for post
Image for post
Terminal symbols versus non-terminals
Image for post
Image for post
Identifying the unique parts of a syntax tree.

But what is the value of a parse tree, anyways? We don’t think about it as programmers, but it must exist for a reason, right?

Image for post
Image for post
Understanding the role of the parser
Image for post
Image for post
Reading like a parser would read.

Resources

basecs

Exploring the basics of computer science, every Monday, for…

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store