Lambda the Ultimate

Shriram Krishnamurthi's classic macro automaton example, well known from his LL1 presentation, is now written up as an educational pearl for JFP.

As you may recall, the example shows how to use Scheme macros to create an an automata DSL, and concentrates on the importance of proper tail-calls for achieving the desired semantics.

First I'll state my (admittedly fledgling) understanding of avoiding parser ambiguity in normal languages and then I'll ask my question about how it might be exploited instead of avoided in some "abnormal" languages.

My understanding is that normally it is imporant for the concrete syntax of a language to parse unambiguously, e.g. it is important that precedence be specified so that an expression like

a + b * c

will be parsed to give the same parse tree as either

a + (b * c)

or

(a + b) * c

(For this example, probably the former, but that is beside the point.)

In giving an abstract syntax, it seems that you can usually assume the concrete syntax is designed to parse unambiguously, i.e. the abstract syntax defines the syntax of parse trees rather than the syntax of the lexeme sequences that are parsed into those trees.

So, my question is, what if you want to design a language in which

a op1 b op2 c

means

(a op1 b) op3 (b op2 c)

i.e. the ambiguity is resolved by inserting an implicit operator (op3) and repeating the symbol in common between both sub-expressions (b). E.g. the expression

a < b < c

might (as it normally does in math) mean

a < b && b < c

So my question is, how does one present syntaxes (concrete and abstract) and semantics for such a language? It seems like traditional methods can't accomodate this way of resolving parsing ambiguity. Or maybe they can and I'm missing something; that would be great.

I hope this post's topic is appropriate to this site. I also hope my question isn't too vague or malformed: I admit I haven't thought about it a lot yet but thought some responses might be useful to point me in the right direction earlier rather than later so I don't go reinventing the wheel.