Parse tree

A syntax, derivation or parse tree is a term used in theoretical computer science and describes a tree-like representation of a derivation.

Consider a context-free grammar. A derivation tree for this is a tree whose nodes are labeled with symbols from (ie, terminal and non- terminal symbols and the empty word). The tree is ordered, that is, the children of each node have a fixed order, and applies for the inscription:

  • The root is labeled with the start symbol. This property is sometimes not required. A tree that they met is called a complete derivation tree.
  • If the children of a node with label inside with the symbols are labeled ( in that order), the grammar must contain the rule.
  • The leaves of the tree are labeled with symbols from.
  • Is a leaf labeled with, it is the only successor of his predecessor node.

The internal nodes are exactly those labeled with nonterminal symbols nodes; the leaves are labeled with terminal symbols or the empty word.

Given a derivation without rules of the derivation tree is unique. For a derivation tree but can exist different derivations, depending on the order in which the rules are applied (see rightmost derivation ). However, these different derivations produce all the same word, which can be seen on the leaves or determined by a depth-first search on the derivation tree.

Various derivations to a derivation tree not mean here that the grammar is ambiguous: There must be several derivation trees that produce the same word.

In the literature, it happens that syntax and parse tree are not used interchangeably. In particular, the compiler is the abstract syntax tree of importance, who proceeds by removing internal nodes with only one child out of the derivation tree. The actual derivation tree is often referred to distinction as a concrete syntax tree or parse tree.

Example

We consider a grammar with the start symbol and the following rules:

A possible derivation tree for this grammar looks like this:

By reading the terminal symbols of the sheets from left to right is obtained, the derived word aab. Derivations for this tree include the leftmost derivation

And the rightmost derivation

  • Compiler
  • Theory of formal languages
24450
de