![]() |
![]() |
![]() |
![]() |
![]() |
Parse Trees
A parse tree pictorially shows how the start symbol of a grammar derives a string in the language. If nonterminal A has a production as:
A -> X Y Zthen a parse tree may have an interior node labelled A with three children labelled X, Y and Z, from left to right:
Formally, given a context-free grammar, a parse tree is a tree with the following properties:
- The root is labelled by the start symbol.
- Each leaf is labelled by a token or empty.
- Each interior node is labelled by a nonterminal.
- If A is the nonterminal labelling some interior node, and X1, X2, ..., Xn (where Xi are terminals or nonterminals) are the labels of the children of that node, then
A -> X1 X2 ..., Xn
is a production in the grammar.The leaves of a parse tree read from left to right form the yield of the parse tree, which is the string generated or derived from the nonterminal at the root of the parse tree. Any tree imparts a natural left-to-right order to its leaves, based on the idea that if a and b are two children with the same parent, and a is to the left of b, then all descendants of a are to the left of descendants of b.
Another definition of a language generated by a grammar is as the set of strings that can be generated by some parse tree. The process of finding a parse tree for a given string of tokens is called parsing that string.
http://www.ibm.com/rational |
![]() |
![]() |
![]() |
![]() |