9.4.解析树

\(9.4.\)Parse Tree

1.Parse tree introduction

  In this part we are going to be specific about the grammatical structure. Take the sentence "the dog ate my homework" for example, here's the grammatical structure of it:

  It's recorded using a parse tree. The tree is a recursive structure, and the grammatical structure of the inputs are recursive, too.

  • The sentence consists of two lower-level sub parse tree.
  • We continue to expanding the tree until get to the boundary of the tree, called leaves or terminal nodes. In the case of lexical analysis, they are the tokens from which the input is constructed.

  Then let's move to Jack. Take the input while (count < 100) {let count = count + 1;} for example:

The notion of a parse tree is an obstruct artifact that sits somewhere above all these nice diagrams. And this diagram here is just one way to describe this parse tree.

  To motivate this, let's focus on some subset of the prase tree:

  Another way of describing the same parse tree can be XML format:

  • In XML, we describe the structure of data using markup tags.