Parsing Mixfix Expressions
Diplom Informatiker, Jacob Lyng Wieland · 2009
ing from precedence between operators and of typing, every expression can be seen as a sequence of so-called operator backbones (or operator backbone instantiations). An operator backbone is the sub-sequence of tokens of an instantiated visible operator, starting from the beginning of its leftmost visible separator up to the end of its rightmost visible separator. If an expression is split into such a sequence, the hierarchy between the operator instantiations inside the expression is forgotten. We call concatenations of backbones backbone expressions. The set of backbone expressions is a superset of the set of type-correct mixfix expressions, ignoring precedence, typing and problems caused by adjacent operands. A more formal definition of backbones can be found in section 3.2 on page 47. Example 22 If v1, v2 and v3 are backbone expressions, the list of terminal symbols of the form [for]++ v1 ++[ := ]++ v2 ++[to]++ v3 ++[do] is a possible backbone of the operator with pattern for := to do . We can derive a (generally ambiguous) context-free backbone grammar which describes all such concatenations for a given set of mixfix operators (cf. 3.2.1). The language recognized by this grammar is the set of backbone expressions. In essence, this grammar abstracts from typing, precedences between operators and adjacent operands inside operators in the following way: • All left-open or right-open operands (and those directly and indirectly adjacent to them) are ignored (by stripping them from the operator patterns) and the parse trees thus are flattened, causing the inner parts of the operators to stand beside each other instead of being put into a hierarchy. • The problems caused by adjacent operands between non-empty separators are ignored by subsuming adjacent inner operands into a single operand. This does not cause our backbone language to change, because adjacent operands are already a concatenation of expressions. Therefore, since every expression is a sequence of backbones, sequences of adjacent instantiated operands can already be seen as a backbone expression. It should be easy to see how a mapping from parse trees to backbone interpretations (which is a sequence of sequence of tokens) can be defined (cf. definition 17 on page 47). Thus, if an expression does not have an interpretation in the backbone language, it cannot have an interpretation in the expression language. Moreover, if an expression is unambiguous in the backbone language, all possible syntactic ambiguity in the expression can only be related to precedence (which is influenced by typing) or adjacent operands. If, on the other hand, there is more than one backbone interpretation for an expression we have an ambiguity in the expression language that can not in general be resolved by use of precedences or by the restrictions on adjacent operands. Therefore, we must reject expressions which have this so-called backbone ambiguity as ambiguous during parsing, as we have no means to disambiguate them (other than letting the user add parentheses).