Actually I have just realised you might have been talking about the type of the AST nodes, rather than tagging the nodes with the types of the source language.
In any case it uses the parser-combinator library I wrote, and the AST tree is typed. Keean. On 11 June 2015 at 14:39, Keean Schupke <ke...@fry-it.com> wrote: > Have a look at this: > > https://github.com/keean/Compositional-Typing-Inference > > All parsers output typed fragments. Whenever there is a valid HM type for > fragment, this system gives the same principle type, but it can also type > open terms (which is a necessary for bottom up typing). In fact it can give > a principle typing (note: different from a principle type) for any valid > partial parse output. > > Keean. > > > On 11 June 2015 at 14:21, Jonathan S. Shapiro <s...@eros-os.org> wrote: > >> So now that we contemplate a typed AST, we run into a new problem: how to >> type the code emitted by the parser generator. >> >> If the parse algorithm is any of the "top down" family of algorithms (LL, >> PEG, GLL, others), there's no problem. Each production can be implemented >> as a procedure, and each procedure returns its result AST as a return >> value. The reason this can be typed using a conventional static type system >> is that we are't using a separate parse stack. >> >> But if the parse algorithm is one of the "bottom up" family of algorithms >> (LR, GLR, others), the typing seems more complicated, because all of the >> shift-reduce algorithms use a separate parse stack. >> >> The reason a separate parse stack is a bother is that a given "position" >> in the parse stack can have distinct types over time as the parse tree is >> constructed; we cannot assign any simple static type to a position. >> Off-hand, I can't even see how to type the parse stack using dependent >> types. I'm sure a way exists, and I'm pretty sure one of the type system >> wizards on the list will promptly trot it out and say "it's obvious", but >> I'm a simple-minded old-school hacker at heart, and it's not jumping out at >> me. Sure, you can use a union type as your stack slot, but it seems >> unfortunate to do that when the parse state already tells you what you need >> to know. >> >> Thankfully, there are many reasons to prefer recursive-descent techniques >> when they will solve your problem. Most notably error handling. But one of >> the places where the shift-reduce approach is actually *better* is in IDEs. >> In an IDE, you need to be able to deal with fragmented and/or incomplete >> input. Think of it as parse subtrees interspersed with junk. Under those >> conditions, the top-down approach simply doesn't work. >> >> You could, of course, make the parse stack element a union type, but then >> you'd end up doing a lot of run-time type checking that you don't need to >> do (because the parse state already encodes that). >> >> It dawned on me this morning that this is why most textbook presentations >> of ASTs use a weakly typed AST structure: doing so preserves the ability to >> use a separate parse stack. >> >> >> It seems curious that when relative strengths of parsing strategies are >> discussed, nobody ever talks about static typing. Or at least I've never >> *seen* anyone do so. >> >> >> shap >> >> _______________________________________________ >> bitc-dev mailing list >> bitc-dev@coyotos.org >> http://www.coyotos.org/mailman/listinfo/bitc-dev >> >> >
_______________________________________________ bitc-dev mailing list bitc-dev@coyotos.org http://www.coyotos.org/mailman/listinfo/bitc-dev
