display | more...

A handy graphical representation of how a string of symbols (or in the real world tokens) are parsed (or derived) from a certain grammar. A parse tree is useful because it helps humans visually understand the relationships that give the string meaning. Without knowing the rules of the grammar, one string can have multiple interpretations.

Take mathematical statements. Forget for a moment that you learned PEMDAS back in middle school, and look at the following statement.

1 + 2 × 3

What does this statement mean? Does is mean to multiply the sum of 1 and 2 by 3, or does is mean to add 1 to the product of 2 and 3? Well, if this string were generated by this unambiguous context-free grammar...

expressionexpression + term | term
      termterm × factor | factor
    factor → (expression) | 1 | 2 | 3

...it would have the following parse tree.

        expression
           /|\
          / | \
         /  |  \
        /   |   \
       /    |    \
      /     |     \    
     /      |      \
expression  |      term
    |       |       /|\
    |       |      / | \
    |       |     /  |  \
    |       |    /   |   \
  term      |  term  | factor
    |       |   |    |   |
  factor    | factor |   |
    |       |   |    |   | 
    1       +   2    ×   3

It is apparent that according to the grammar, this statement represents the sum of (the expression) 1 and (the term) 2 × 3. It is important to note, however, that were this grammar ambiguous, whe could not say that with certainty. Since an ambiguous grammar may generate the same string with different parse trees, it's interpretation would be unclear. This is one of the major differences between programming languages and natural languages. Programming languages have grammars which are carefully constructed to ensure they are unambiguous. Natural languages, on the other hand are fraught with ambiguity. A detailed definition of ambiguity, however, is a topic for another node.

Though they are a powerful tool, parse trees aren't really used in a formal way. Ambiguity is defined differently, but using parse trees makes it easy to see what it means. In the end, parse trees are just a helpful tool for wetware to understand how strings are derived from grammars.

Log in or register to write something here or to contact authors.