Algebraic Expression Languages

Fritz Ruehr • Willamette University CS 451 • Spring 2006

Algebraic expressions have a tree-like structure bulit from internal nodes holding operators (or their symbolic representations) and external or leaf nodes holding symbols (e.g., numerals) representing "atomic" values (e.g., numbers: note that this notion of "atomicity" might be a relative one, especially given our look at the structure of Peano numerals). As such, these expressions represent another quantum jump in the complexity of language, up from the linear structure of numerals: while they are still quite simple, a number of new phenomena emerge at this stage which are worth some attention.

One of these issues is the tension between linear/sequential string representations and hierarchical tree-like representations: in some sense both representations are syntactic, but there is modest work to be done between the two (parsing and showing/printing). But the tree-like expression structures also offer a more natural medium in which to do most of our work, one which highlights the important relationships (sub-expression structure) and finesses away some pettier issues (e.g., parenthesization).

For this reason we will start out concentrating on the middle area of the (recently enlarged) syntactic/semantic spectrum, the tree-like structures that are usually called "abstract syntax".

Contents