||Tue 2017-02-21 09:35|
|Aside: it now occurs to me that if you have a parser generator that supports this kind of subtype mechanism, then you could also use it as an alternative to the traditional |
%prec mechanism for resolving operator precedence without all that tedious mucking about with 11 subtly different nonterminals for 'expression'.
Instead, you have just one nonterm for 'expression', in the same way you would with
%prec. You endow each expression with metadata indicating what its outermost operator is, and then each grammar production that combines two expressions using a new operator will have a constraint that says how the new operator has to compare with the outermost ones in the subexpressions. For example,
where the careful use of
expr: expr[op_prec >= prec('+')] '+' expr[op_prec > prec('+')]
>= on the left and
> on the right also lets you control whether the operator is left- or right-associative.
In fact, using this technique, you could probably get away with having just one grammar production covering all binary operators – and now you've achieved a massive separation of concerns, because your language grammar becomes independent of the set of supported operators and their precedence levels, so you could add a new precedence level without having to regenerate your parser at all.
Of course, this use of symbol subtyping doesn't do any scope analysis – the
op_prec property I illustrate above can be both generated and checked with no need to look all the way back up the parse stack. But if you were really ambitious, you could combine the two techniques, and do scope analysis to determine the precedence of your binary operators – so that your language could support syntax in which you locally introduce a new binary operator token, or change the precedence of an existing one, and the changes are precisely scoped to only the small region of code in which the programmer actually thought it would make some specialist thing clearer...