Bottom-Up? Top-Down?

   28 February 2004, terribly early in the morning

A parser will take an input source file and produce a parse tree. The parse tree can then be used to do some context-sensitive analysis of the language, i.e. making sure that variables are declared before they are used, or that break statements occur within loops.

Usually this type of analysis is done by attaching attributes to each of the nodes in the parse tree, and calculating the values of these attributes using information from the lexer, and the structure of the tree.

You can compute some attributes in a bottom-up fashion. That is, the attribute at a particular node is computed using information from its children. Such attributes are said to be synthesized attributes. We can do a bottom-up walk through the tree using a depth-first search type traversal. You can compute some attributes in a top-down fashion. The attribute at a particular node inherits its value from its parent. These attributes are referred to as inherited attributes. We can do a top-down talk through the tree with a breadth-first search type traversal.

Sometimes things get more complicated then that. Sometimes things get much more complicated then that.

|  

Comments

Don't be shy, you can comment too!

 
Some things to keep in mind: You can style comments using Textile. In particular, *text* will get turned into text and _text_ will get turned into text. You can post a link using the command "linktext":link, so something like "google":http://www.google.com will get turned in to google. I may erase off-topic comments, or edit poorly formatted comments; I do this very rarely.