On Wed, May 13, 2015 at 10:38 AM, Jonathan S. Shapiro <s...@eros-os.org> wrote: > It has occurred to me that this can be resolved, and I'm wondering if anyone > has already considered this approach somewhere. > > The construction of an [F]Parsec parser effectively performs compositions of > sub-parsers, with leaf parsers for tokens that are implemented using what > amount to built-in primitives. The "parser" object, or type, In the case of > FParsec, the Parser type is defined as: > > type Parser<'TResult, 'TUserState> = CharStream<'TUserState> -> > Reply<'TResult> > > But there is nothing magical about this definition. While the developer > *can* introduce new compositing operators, they typically do not do so. If > we take the list of compositing operators as non-extensible, then it appears > to me that we could implement an alternative version of the library in which > (a) the Parser type is defined as an AST node, and (b) the compositors > combine their input ASTs into a suitable combining output AST. Once an AST > for the input grammar is in hand, we could test it against various parse > algorithms to determine whether it is context-free. Once we *know* it is > context-free, it's perfectly fine to implement it using recursive descent or > any other sensible implementation.
So you hack up some funny versions of the combinators, so that the code to build the parser instead builds a stand-alone description of the grammar which you can then reason about. What if they actually build different parsers at parse time, based on what they've already seen? Does anyone do that? Well, I guess it's OK as long as you don't do that. So you can check that a "combinator grammar" is context-free? I guess you would pretend the choices are nondeterministic, and check that it's still unambiguous? _______________________________________________ bitc-dev mailing list bitc-dev@coyotos.org http://www.coyotos.org/mailman/listinfo/bitc-dev
