[bitc-dev] Quick haskell question

[Mark P. Jones]

> On Wed, Aug 11, 2010 at 5:19 PM, Ben Karel <eschew at gmail.com> wrote:
> ...you implement the shunting yard algorithm (or whatever) as a post-processing pass, like Mark P. Jones described.
>  
> This is a great example of a place where "lore" got in my way. The "shunting yard algorithm" is apparently a well-known technique, but I haven't found mention of it in anything that I have tried to read on the subject of mixfix parsing.

If it is any consolation, I hadn't heard this term previously either :-)
But that's probably because it is just a special case of LR parsing (think
shift/reduce, yacc, etc...).  I've been using this algorithm for years in
compiler classes as an example to explain and motivate shift and reduce
steps in parsing, but always channelling Knuth rather than Dijkstra.

Also, just to be pedantic, the suggestion that I was making previously
was not so much to use "shunting", but rather to postpone that process
(or some alternative) until the main parsing task is complete.

> Mark: with the introduction of expression operators in the constraint space, as you have done in Habit, is there anything unusual that I need to be anticipating here?

Nothing particularly surprising, no.  I'd recommend that you
use separate fixity information for value expressions and type
expressions.  Unfortunately, this also means having two versions
of the code for removing "deferred infix" expressions, unless
you are writing in a language with good support for either macros
or higher-order functions.  Also, if you allow user-defined
fixities, then this means having two forms of fixity declaration
in the surface syntax.  We have:

  infix[r|l]? [prec]? operators

for values and

  infix[r|l]? type [prec]? operators

for types.  (? = optional, prec = integer literal specifying a
precedence value.)

Hope that helps.

Mark