Lambda the Ultimate

The quick answer is that it is a small library (~500 lines) and does not depend on boost. It was designed from a clean sheet, and tries to implement a minimal set of combinators. Spirit tries to fit operators to parsing so that they obey the C++ operator precedence (including overloading *), this only uses operators where their semantics obviously fit (&&, ||) and uses names elsewhere in line with the Concepts (as in the Stepanov definiton) underlying these operators.

In more detail, I think its a cleaner implementation, it doesn't use the curiously recurring template pattern (which I don't really understand the need for as you don't need a base class for static polymorphism). Also all parsers are treated as const values, as are any user-functors. You can of course pass a mutable object into your user-functor as a constructor argument for state (as shown in the example_expression parser). Parsers do not return a match object, rather you pass in a data-structure to store the results as an optional argument, which if null means the results are never stored. There are no parser-contexts, this is achieved through the user-functors and 'any' and 'all' combinators. There may be more differences I haven't noticed yet.

A further difference is that the purpose of posting it for discussion is to get feedback that may alter and improve the design, something that is harder to do with an established library even if you fork it (due to code size, complexity and dependencies).

Edit: It appears the principal difference is in the handling of polymorphism. My library handles nearly all the polymorphism statically, allowing inlined 'compiled' parsers to be generated and specialised for each grammar fragment. Dynamic (runtime) polymorphism is only used where explicitly requested by the programmer by use of a 'parser_handle'.

Yah. I don't really know what parse_line does though I can take an educated guess at its semantics. (Ah, it's a functor.)

I would like to see this evaluated with your combinators:

(ADD 3 (MUL 5 (DEC 7))

Okay. I think I get it. The confusing thing was the naming. "parse_int" isn't the actual parser but the epsilon rule/attribute evaluation. I would have preferred it if you would have called the parser expression which starts with "all" "parse_int"; and people likely would find it more readable if the epsilon rule would come as the last argument; or you just wrap it around whatever is done in all, it looks too specialized somehow.

(Then the other thing is that the parser combinators I once wrote are probably around a hundred lines in total. I don't get why you wouldn't be able to trivialize it further.)

Yes, that makes sense. I could call it "epsilon_int" and define "parse_int" as suggested to make it more readable. I'm afraid the variadic syntax needs the variable arguments to come last, so it has to be first. If you think that all arguments after the first are user-defined it kind of makes sense. Also it follows the pattern of a fold function where the accumulator is the first argument.

Yah. We discussed that and I told you I don't believe fold will buy you much in defining parsers. Attributes just have different types, "SUM" is a piece of text and "1" is an integer. (Though you also do type tricks in C++ I didn't think were possible.) And though lists of things emerge sometimes, they aren't that important usually that you would like to specialize in that direction.

The trick to observe is that if you can't do the attribute evaluation directly in the second level of the CFG part, or maybe don't want to, that you then push the attribute evaluation into epsilon rules which you then trickle around in your grammar. (Bison is an affix grammar with the epsilon rules last.) That would also hopefully keep the (intermediate) types of your parsers/production rules sane.

I didn't think it much trough but a specialized combinator probably would take care of that.

I got rid of the 'fold' (which was polymorphic) as the variadic form is much neater (the 'all' and 'any' combinators), you don't need multiple template definitions for each parser type, as single functor receives all the parsers as the appropriately typed argument. You can see this in "return_exp2", the first argument is the result, the rest are the parser results which are of type 'enum op' and 'int' respectively. These types must match the types returned by the parsers in those positions of the 'all' combinator, and this is enforced by the type system.

Here's an expression evaluator, no operator precedence however. These are the static definitions (const objects and types), a nice point to note is that no templates are needed in the user code, thats all contained in the library. The complete example is now on GitHub.

enum op {add = 0, sub = 1, mul = 2, div = 3};

struct return_int {
    return_int() {}
    void operator() (int *res, string &num) const {
        *res = stoi(num);
    }
} const return_int;

struct return_op {
    return_op() {}
    void operator() (enum op *res, int choice, string &add, string &sub, string &mul, string &div) const {
        *res = static_cast<enum op>(choice); // this relies on the order of parsers being the same as the enum.
    }
} const return_op;

struct state {
    int acc;
    state() {};
};

struct return_exp1 {
    state &s;
    return_exp1(state &s) : s(s) {}
    void operator() (int *res, int &left) const {
        s.acc = left;
        *res = s.acc;
    }
};

struct return_exp2 {
    state &s;
    return_exp2(state &s) : s(s) {}
    void operator() (int *res, enum op &opr, int &right) const {
        switch (opr) {
            case op::add:
                s.acc += right;
                break;
            case op::sub:
                s.acc -= right;
                break;
            case op::mul:
                s.acc *= right;
                break;
            case op::div:
                s.acc /= right;
                break;
        }
        *res = s.acc;
    }
};

auto const recognise_number = some(accept(is_digit));
auto const recognise_space = many(accept(is_space));
auto const parse_operand = all(return_int, recognise_number) && discard(recognise_space);
auto const parse_operator = any(return_op, accept(is_char('+')), accept(is_char('-')),
    accept(is_char('*')), accept(is_char('/'))) && discard(recognise_space);

Here is the stateful bit called from inside a function, there's no global state so it should be thread-safe:

state my_state;
return_exp1 e1(my_state);
return_exp2 e2(my_state);
auto const parse = all(e1, parse_operand) && many(all(e2, parse_operator, parse_operand));
decltype(parse)::result_type a;
b = parse(in, &a);

This correctly evaluates 3 * 2 + 1 as 7. There is one slight 'trick' used here, because the result type is a plain int (parsed by nullable-reference, aka pointer) it gets repeatedly overwritten as the parser progresses, as return_exp1, and return_exp2 return the current accumulator state. You could easily replace this with a vector<int> and push each update into this, which would give a history/timeline of the accumulator as the expression evaluation progressed.

Well. That took me a while. You're an interesting exercise in getting my own arguments right, as well as upgrading my C++.

Passing information between parsers under water with a hidden state looks like a pretty bad idea to me. This works on your trivial grammar without operator precedence rules which evaluates left to right but I don't see it scale. Why don't you just wrap the parse definition in another "all" rule? (If you can't, then I'ld say that hints at an expressive weakness in your library.)

I understand that stuff automagically going out of scope and turning into garbage is a problem in C++ but I don't think this is the manner to handle that.

Ah well. You rely on deterministic LL(1) over character streams, which simplifies a number of problems, whereas I want (backtracking) LL(k) over a search space which introduces its own quagmires. It's just not general enough for me.

You can wrap with as many 'all' combinators as you like.

Passing information in hidden state is the same way monad based combinators work. I can make it so there is no hidden state, but why would I want to do that. Are there any actually reasons not to do this, or is it just a vague personal preference. I would need to be convinced the alternative is better.

I think you should look at Boost Spirit and Phoenix, as it does LL(k) and every combinator can have "attributes" using the Phoenix functional library.

If you want to do more than just evaluate tiny arithmetical expressions it quickly becomes obvious that you don't want to have a state shared between different expression parsers.

Of course I look at Boost Spirit, I am figuring that out at the moment. But I have higher-order backtracking LL(k) attribute grammar specifications. And I use everything of that. Fifty lines of code.

I doubt Spirit can express analytical information and I am almost completely certain it doesn't have higher-order functionality. But still reading.

It's just an academic exercise to keep me busy though. I don't care much about it.

(Ah well. They call analytical information "inherited" these days. Lousy. Oh. It's something different.)

Passing information between parsers under water with a hidden state looks like a pretty bad idea to me.

I think it could be done pretty well with (for example) a concatenative programming metaphor. Parse this, parse that, pop two parsed items off the stack then combine them...

But in your vocabulary, he doesn't "pop" explicitly between parsing. It just lingers somewhere in the global void. Like a half-baked product.

I am not sure what you mean? Which value is lingering in the global void? Each parser _returns_ its result (as a pass by reference parameter).

What is the simplest example that shows (requires) the higher order behaviour you want?

state my_state;

If state would be a symbol table it would make sense. But this? For a piece of synthesized information, an integer? And now it's halfway in between synthesized and global information anyway. Lousy.

(Ah well. I guess you wanted to show that you can thread something like a symbol table. But then make a language where that makes sense like evaluate "1 + 2 * myaccount" where "myaccount" is in a thread scoped context.)

Here is a version that communicates only using the return values of the parsers without any threaded state:

enum op {add = 0, sub = 1, mul = 2, div = 3};

struct return_int {
    return_int() {}
    void operator() (int *res, string const& num) const {
        *res = stoi(num);
    }
} const return_int;

struct return_op {
    return_op() {}
    void operator() (
        enum op *res, int choice, string const& add,
        string const& sub, string const& mul, string const& div
    ) const {
        *res = static_cast<enum op>(choice);
    }
} const return_op;

struct return_left {
    return_left() {}
    void operator() (int *res, int left) const {
        *res = left;
    }
} const return_left;

struct return_right {
    return_right() {}
    void operator() (int *res, enum op opr, int right) const {
        switch (opr) {
            case op::add:
                *res += right;
                break;
            case op::sub:
                *res -= right;
                break;
            case op::mul:
                *res *= right;
                break;
            case op::div:
                *res /= right;
                break;
        }
    }
} const return_right;

auto const recognise_number = some(accept(is_digit));
auto const recognise_space = many(accept(is_space));
auto const parse_operand = discard(recognise_space) && all(return_int, recognise_number);
auto const parse_operator = discard(recognise_space) && any(return_op, accept(is_char('+')), accept(is_char('-')),
    accept(is_char('*')), accept(is_char('/')));
auto const parse = all(return_left, parse_operand) && many(all(return_right, parse_operator, parse_operand));

Now the parser is entirely const, so all the definition is in the const type section, with just a simple call in the function:

        decltype(parse)::result_type a;
        b = parse(in, &a);

Is that better?

It was already quite good; and the C++ is excellent as far as I can judge (I can't, really.) You would need to test it against a number of grammars but it convinces me one can write reasonable LL(1) interpreters over character streams with your solution.

You're still stuck with a bit of an academic exercise, sorry to inform you. Some people will still prefer pointer bumping for lexing, even if this solves their problem more declarative, and some lexemes are sometimes complex even when written as regular expressions (which will be a pain to express LL(1)).

If I were you I would put it into a blog post, explain some of the ideas behind it, and explain how it's used. Then forget about it. Unless you think they're doing it wrong in Boost Spirit; if you can show people to do it better, that's always interesting.

Meanwhile, I'll think over my own problems and see if I can steal some of your code to fix my own problems. It's a nice manner of learning C++ and (I really don't know yet) you have some more modern ideas on type abuse in C++.

Actually I have a whole heap of things that use parsers that I intend to use it for (including the language I am working on). I am more concerned with the academic exersize than how many people actually use it. That's why I am looking for feedback here. I am looking to contribute towards an ongoing discussion (in code) of the definitive definitions of such things. I really like Stepanov's concept of algorithms as a shared mathematical dialog. I still don't think there is a place for publishing such things which is a shame.

My conclusion is that Boost Spirit is doing it more or less right, and that Phoenix is interesting. I think if I were to take the next steps to actually using Phoenix then I would be better using Spirit too, although I prefer the simpler way I handled return values polymorphically, leave threading state to the user, and don't try and overload every operator breaking the algebraic axioms of many operators. For example unary * normally is a pointer dereference, using it as a prefix kleene star makes things hard to read at best.

Parsing a parenthesized term. With the functional approach you can write a user-defined function which takes a parser and returns a parser which parses the production rule enclosed by parentheses. Looks like your parsers are functions, so it should be trivial.

(It's higher-order since you can write functions over parsers and impossible to express in, for example, Bison or that Moony Early thing here. It's a nice to have.)

That'll be nice to showcase.

I have been working on a sort of fix point combinator, and I have got it working so that you can add runtime polymorphism at certain points in the parser. Because the parsers all have different types, and its recursive, this is a kind of polymorphic-recursion.

As expected we have to add some runtime polymorphism which is achieved in c++ with a base class with a pure virtual method, and a teplated subclass to hold the parser of any type. We can't directly instanciate the base class so we need a handle class to hold a reference or pointer to the base-class. We are almost there, but we need to handle copying and assignment of the handle. If we do this in a const way we need to cope with the self-reference being uninitialised in the definition, and as the parser objects copy their arguments we need something const they can copy that can point to the as yet uninitialised self reference. If we do this dynamically we need something slightly different, where we have a shared pointer in the handle so it can be copied when assigning the self referential parser to the polymorphic handle.

I just need to either get these two methods to work together, or if I can't, chose the one I prefer. This how the static version looks:

parser_handle<int> p = ... && ref(p);

And the dynamic:

parser_handle<int> p;
...
p = ... && p;

Well. All the type theory question and language philosophy got me wondering about module systems, the role of impure constructs, and how they solved that in ocaml. Did you notice they already solved the question of applicative vs generative in Ocaml? I.e.: If a class is a reinstantiatable abstract module declaration, then they solved the question.

Since I now believe I want fundamental hard-core impurity over functional methods in my language I wonder how they solved that in ocaml. And how to design my language that way.

I don't know why you do fixed points now, but the question is a bit passe for me at the moment. Sorry. Bit of a butterfly mind.

"fundamental hard-core impurity over functional methods"?

I want OO in the sense of reinstantiable module declaration since the reinstantiable implies it'll buy me more than any other module system; at least, in terms of software engineering in the large concepts.

So, a module systems where values, or a value, is part of the interface declaration and the rest is mostly pure, but sometimes impure, so impure anyway. (If default OO is OO over an imperative language I want OO over an impure functional language. So, Ocaml.)

Think: reinstantiable signatures with values as first-class citizens of the language.

(It'll be done somewhere else. So I am looking at Ocaml, and I'll have a look at OHaskell sometime. Possibly I don't need much more than the interfaces I have in my language anyway. But I am just goofing around with my spare time; no idea whether I'll do it. Maybe I'll just decide that if type theoretical questions can't be solved I'll just not solve them and go untyped anyway.)

(Then again. Without types I'll end up implementing Lisp/Javascript so that doesn't add up too.)

I'm trying to understand if what you mean in the end is some variation of "first-class modules" (in the functional programming community) and/or some variation of virtual classes — including Scala itself, path-dependent types, and lots more I'm not expert on (including the Beta language, dependent classes). If so, Ocaml is not appropriate IIUC because it does not have first-class modules. Viceversa, Scala is designed to subsume ML modules — see the intro of "A nominal theory of objects with dependent types".
Moreover, those names might help you in your search.

If you go this road, you'll end up facing a different question (which often is mixed up with the above): should you just make ML modules first-class, or should you switch to mixin modules (as in Scala or in Derek Dreyer's work)?
IMO, mixins face similar tradeoffs with inheritance — they're really convenient (because they remove explicit wiring you'd often need with delegation) but they don't enforce modular reasoning (similarly to aspects — aspects and before/after advices come from CLOS mixins, so the similarity is rather deep). It is somewhat clear by now that aspects are not the right direction, but the field is still open. (Some work simply generates the wiring as needed, such as "Forsaking Inheritance: Supercharged Delegation in DelphJ", but I don't know the details).

Final warning: it's probably not obvious that the different things I'm talking about have anything to do with each other. IMHO studying the literature makes it somewhat clear (see "A nominal theory of objects with dependent types"'s intro, again), and that's probably known to the experts in the field, but I don't know if anybody's bothered to write it down. If not, such a write-up could IMHO be published (I'd be interested in working on this, in my copious free time).

This is close to where I am going, which is first class modules (hence the type system with principle typings). Classes and other similar things will be implemented as meta language constructs (predicates on types).

Nit: Scala does not subsume ML modules, see e.g. my recent answer on SO. Also, the νObj calculus is quite different from actual Scala: more expressive but less decidable.

No, as I said, and you indicated to understand with the word "road," it's a general idea of the direction I want to take a typechecker once I get interested.

The idea is to conflate, possibly, higher-rank type impure type constructors as a first citizen within the language.

And since I want neither MLs value restriction as well as neither co-/contravariance that implies a number of things.

Don't think I will solve it but, yeah, interested.

So the parser combinators build a parser using static polymorphism. This is like compile time generative programming. The result of executing the template program at compile time is a specialised parser for the grammar. That makes it fast and efficient. Rather than using runtime polymorphism everywhere and paying an order of magnitude performance penalty we invoke runtime polymorphism explicitly where needed. This turns out to be precisely any point of recursion (hence reference to fix-point). I have uploaded the code to github as I am mostly happy with it. There are currently two types of reference I would like to combine, and I need to update the example.

You probably already know about this paper, but if not, maybe it can help you.

Not interested. Or not interested, yet. Unsure. (I am reading the Scala language definition which is far more appropiate for the simple things I want.)

Anyway, the general informal ideas I have are:

I want to be able to type

f = \x. (1, f)

I would like to type, without higher ranks,

g = \f x y. (f x, f y)

And I want to conflate data type, mutable object, and module. And avoid covariance and contravariance.

And that all in some bash replacement; uh, no REPL though. I.e., implemented in C, and reasonably fast. Uh, and the other stuff I had in my language I guess, like exceptions and type cases and stuff.

If I correctly understand that the first allows open recursion, then you may want to keep it for modularity reasons (despite the fact that most often you don't actually need the extra flexibility and the second form is just fine). Here is the use-case I have in mind:

  additive_expr(expr1) = (expr1 '+' expr1) | (expr1 '-' expr1)
  mutilplicative_expr(expr1) = (expr1 '*' expr1) | (expr1 '/' expr1)

  expr = additive_expr(expr) | multiplicative_expr(expr)

You are able to separately define the additive and the multiplicative operation, and later tie the knot to get expressions that may have either form of operators at any recursion level. Note the difference with:

  expr1 = (expr1 '+' expr1) | (expr1 '-' expr1)
  expr2 = (expr2 '*' expr2) | (expr2 '/' expr2)
  expr = expr1 | expr2

That would make sense if the parser was LL(K), it seems of limited use with LL(1)... but might still be useful. Maybe I will just have to implement more backtracking.

In another discussion I was pointed to uu-parsinglib. From what I've seen so far it is really amazing. See also this paper: http://www.staff.science.uu.nl/~swier101/Papers/2003/p224-swierstra.pdf

They have unlimited lookahead while still being incremental by doing breadth first instead of depth first backtracking. Another amazing thing is that they can handle ambiguous grammars in polynomial time with an amb combinator: amb : Parser<a> -> Parser<List<a>>. It's beautiful how this integrates controlled nondeterminism in otherwise deterministic parsers so you don't have to buy into nondeterminsm everywhere.

So if you do want to implement backtracking at some point, it's probably worth looking at how they do that.

Question about the above? Where is the parser for plain numbers? Would it be:

expr = additive_expr(expr) | multiplicative_expr(expr) | parse_int

Also is there a left recursion problem here?

In my experience the amount of backtracking relies on the language designer. It's a reason why I don't like your parser works on character stream. Informally, not tokenizing blows up the amount of backtracking with a rather large constant.

But backtracking LL(k) isn't a good solution on highly ambiguous grammars out of your control, I agree.

Tokenizing would make no difference to the stack size, as we simply store the stream position on the backtrack stack and then seek to it. The number of choice points and hence the backtrack stack size is the same tokenized or non-tokenized. The stream-buf buffer size is fixed, so there is no difference there, and its up to the operating system how it uses its page cache to satisfy seek requests. Userspace buffering seems to make very little performance difference.

The problem has little to do with the ambiguity of the grammar. Take a CSV file where each number is separated by a comma or a newline. before parsing each number we have to create a backtrack checkpoint in case something fails later, so with a 1000 by 1000 CSV you get 1 million checkpoints on the backtrack stack. So its each choice point (in this case comma or return) that causes the problem, you really need a cut operator after such choices to indicate that later failures cannot undo earlier choices. What I really need is a backtrack stack of deferred parsers, rather than stream positions. That way you can perform a cut by just popping the top parser off the stack...

The problem with tokenisers is sequences like "name123" and "name 123". You have to have a global definition of what a name looks like, and then there are literal strings etc...

Tokenizing would make no difference to the stack size, as we simply store the stream position on the backtrack stack and then seek to it.

Man. Too bored to answer and read your code. The above statement can't be true unless you're reinventing a form of bottom-up parsing. Maybe you are, no idea.

I didn't think anyone still used tokenizers due to the problems with string literals etc. You end up with a horrible mess trying to feed information back to the tokenizer from the parser...

Uhm. Everybody uses tokenizers? And all attempts to do without have failed? Unless you know more than I do, of course.

http://wikipedia.org/wiki/Scannerless_parsing

As you note it also lists the disadvantages of LL(1). Ever seen a TeX error? Though I guess there were good reasons to design TeX the manner in which it was designed and nobody has done a better job so far.

Knuth is one of the few computer scientists I take seriously.

As I stated, backtracking LL(k) is a 95% solution for PLs. The there mentioned author is interested in 100% solutions. Unfortunately, backtracking higher-order attribute grammar parsers probably go beyond what is solvable in his system. But, yeah, research.

I have never used a tokenizer outside of academic requirements. All the real world parsers I have implemented have been scannerless. I have a lot of respect for Knuth, and am proud to be an account holder at the bank of San Serriffe, although I could do with saving a bit more :-)

In any case, maybe I could arrange it so you could use an optional tokenizer, I just wanted to avoid another template parameter, or the cost of virtual functions.

I am now seriously considering building an AST of the grammar from the combinators, allowing grammar composition, followed by a tree rewrite into a character at a time parser with no backtracking. What do you think?

Well, if you can pull it off with your language you should. I am not stopping you.

An idea I have. I actually used a grammar work bench a long time ago to check whether a certain grammar met certain conditions. Maybe that's an idea? You'll be able to test whether your language meets LL(1) reasonably fast. Not sure they're still in existence though.

I am green with envy.

Improved language design can result in much better parsing diagnostics.

Please see the following:
Language Design Issues

Regards,
Carl

Are you memoizing results in case a backtrack leads to retrying some of the same parse?

In BNF

 S ::= A B C 
     | A B D

In some code for a parser combinator library I haven't posted, I had a database of parse results indexed by the pair (character-stream-offset, parser-id). It was highly influenced by a parser combinator system I found somewhere written in JavaScript. I did not evaluate this for performance.

In the current version of these parser combinators, you can force no-backtracking by deleting the copy constructor on the inherited-attribute (threaded state). This works because backtracking has to undo side effects of failed parsers on this state, and this required copies of the state to be made. For an example see the sample Prolog parser:
https://github.com/keean/Parser-Combinators/blob/master/prolog.cpp

What makes prolog's parser interesting is that one can define new operators INLINE in code being parsed, specifying left, right or none associative infix operators, prefix operators and postfix operators with arbitrary precedence.

Prolog also has a built in parsing technology, definite clause grammars, which are more powerful than parsers generally in use but is surprisingly useless for implementing the preceding inline operator definition feature.

I don't know if Parser-Combinators have either power, I doubt it since DCG can even be somewhat context sensitive.

Does your prolog parser implement the custom operator feature?

Can't respond for OP, but if I understand the question correctly I'd say that it should be possible in the sense that the PEG/parser combinator approach does not prevent it...

For the PEGTL we have examples with the operators, their precedence, and associativities, being part of the structure of the grammar (Lua 5.3 example), and with a run-time data structure that can handle arbitrary many binary operators of arbitrary precedence and associativity and could be changed at any time (calculator example) including from a semantic action in the middle of parsing something.

This is probably not textbook PEG, but in practice it's easy to use additional data structures, see also how we handle the Lua long/raw string literals (which start with [=[ and end with ]=] where the number of '=' is arbitrary but must match).

if you analyse it with low precedence operators, you'll find that each operator has to go into the grammar in an arbitrary number of points depending on the other operators.

Using any kind of grammar that doesn't explicitly have operators has that problem.

I have just added right associative operator support for the example prolog parser (left will follow once I have decided how to declare the difference). You can see the updated source for the example parser at: https://github.com/keean/Parser-Combinators/blob/master/prolog.cpp

The combinators can be named, and can generate an EBNF like printout, that is used in the error reports, which look like this (if you don't catch any exceptions from the combinators):

example.cl
terminate called after throwing an instance of 'parse_error'
  what():  failed parser consumed input at line: 46 column: 84
    expr(Fun, C1, arrow(A, B)), a(X) -> b(X) -> c(X), a(X -> Y -> Z), X -> Y -> Z, Z     expr(Arg, C2, A),
                                                                                   ^----^
expecting: variable, operator, op-list
where:
	atom = lowercase, {alphanumeric | '_'};
	op-list = term, [operator, op-list];
	operator = {punctuation - ('_' | '(' | ')' | ',')}- - "." - ":-";
	struct = atom, ['(', op-list, {',', op-list}, ')'];
	term = variable | struct;
	variable = (uppercase | '_'), {alphanumeric | '_'};

Aborted

I think that's pretty readable, and its auto generated from the combinator declarations. I am interested in any suggestions for improving.

I also think the combinators currently require quite a lot of boilerplate user-functors when combining parsers with different result types, and I am interested in ways of reducing this.

Disabling the backtracking is useful to be able to do, but what about extracting things like LR items and first/follow sets so that I can run a check for parse ambiguities? Not during a production run, but perhaps during a distinguished test or validation compile.

I guess I am not seeing where the ambiguities come from. If you allow backtracking the grammar can be ambiguous, but without it I don't see how you can build an ambiguous parser. To me the parser would be correct by construction and not need a validation pass, but maybe I am not seeing how the ambiguity can get in?

I haven't looked at your implementation, so perhaps you have done something clever that I don't know about. Many combinator packages implement recursive descent naively, relying on backtracking to deal with things that (in a traditional static parser) would be disambiguated by lookahead.

What I think I'm saying is that it's very easy to write grammars in any system that would have shift/shift or shift/reduce conflicts without realizing that one has done so. This can easily result in matching a language other than the one intended, and that is still true if the recursive descent mechanism is non-backtracking. The question is how to have confidence that what I wrote is what I actually intended.

So: I'd really like a way to take a combinator-written parser, extract the kinds of tables used by a conventional statically compiled parser, and run the algorithms necessary to determine that such conflicts and potential ambiguities do not exist.

Merely defining them away by enforcing determinism certainly eliminates the conflicts, but it doesn't address whether I'm matching what I intend to match.

Also it's easy for a backtracking parser to include some context sensitive elements or do semantic tests and processing while it parses, doing those with lookahead would require new parsing constructs and is probably less powerful.

for instance a couple examples of the known context sensitive grammar
aⁿbⁿcⁿ in prolog

s --> a(N), b(N), c(N).
a(0) --> [].
a(M) --> [a], a(N), {M is N + 1}.
b(0) --> [].
b(M) --> [b], b(N), {M is N + 1}.
c(0) --> [].
c(M) --> [c], c(N), {M is N + 1}.

or

s --> symbols(Sem,a), symbols(Sem,b), symbols(Sem,c).
symbols(end,_) --> [].
symbols(s(Sem),S) --> [S], symbols(Sem,S).

Parser combinators like these allow no lookahead or backtracking normally, and all combinators are ordered (which parser is tried first is clear from the syntax). In this case it is an error for a parser that has consumed input to fail. So a combinator (A || B), will throw an exception if A fails after consuming input. So grammars have to be LL(1) and have no ambiguity.

You have to intentionally introduce ambiguity by using the 'attempt' combinator (attempt(A) || B), which saves the parser state before trying A and restores it (backtracking both the input position and the state of inherited attributes) before trying B in the case A fails.

Parsers are tried left to right, so there is really no ambiguity in the grammar because we know A will be tried first, then B (hence the choice to use the short-circuit 'and' and 'or' operators for the combinators in C++).

As there is no ambiguity, would generating parser tables still be useful?

shap's point is not that the described grammar may be ambiguous (it isn't by property of PEG parsers), but that the *intended* grammar may be ambiguous, and that creating a path of least resistance where users will never be told about the ambiguity in their *intent* (because the translation into the tool is lossy by default) is harmful in some cases.

If I want ambiguity I need to explicitly indicate it. Therefore if your intent is ambiguous you will have explicit "attempt" parsers. So you are told about it. What am I missing?

This point is made with much details in this blog post.

Another strategy is to abandon context-free grammars completely and use a formalism like parsing expression grammars that is unambiguous by definition. Parsing expression grammars avoid ambiguity by forcing all grammar rules to be defined in terms of prioritized choice, so in cases where multiple grammar rules match the input the first one is correct by definition. [...]

Prioritized choice is a great tool for resolving some ambiguities; it works perfectly for the solving the dangling else problem. But while this has given us a tool for resolving ambiguity, it hasn't solved the problem of finding ambiguities. Every rule in PEGs is required to be defined in terms of prioritized choice, which means that every PEG rule could be hiding a "conceptual" ambiguity [...]

// Is this PEG rule equivalent to a <- c / b ?
a lt;- b / c
 
// We can't know (it's undecidable in general),
// so every rule could be hiding an ambiguity we don't know about.

I call this a "conceptual" ambiguity because even though a PEG-based tool does not consider this ambiguous, it still looks ambiguous to a user. Another way of thinking about this is that you have resolved the ambiguity without ever being aware the ambiguity existed, thus denying you the opportunity to think about it and make a conscious choice about how it should be resolved. Prioritized choice doesn't make the dangling else problem go away, it just hides it. Users still see a language construct that could plausibly be interpreted in two different ways, and users still need to be informed which option the parser will choose. [...]

And unlike GLR, Packrat Parsing (the linear-time algorithm for parsing PEGs) doesn't tell you even at parse time if the input string is ambiguous. So with a Packrat-Parsing-based strategy, you are really flying blind about whether there are "conceptual" ambiguities in your grammar. It's also possible for entire alternatives or rules of a PEG to be unreachable (see here for a bit more discussion of this). The net result is that with PEGs you know very little about the properties of your grammar.

So far none of the options we've discussed can actually help us find ambiguities up-front. Surely there must be a way of analyzing our grammar ahead of time and proving that it's not ambiguous, as long as the grammar isn't too crazy? Indeed there is, but the answer brings us back to where we started: LL and LR parsers.

I think I understand. You are saying that even though there is no ambiguity because of prioritised choice, it is useful to see where there would have been ambiguity if we ignore the prioritised choice?

I am not sure why this would be the case. For example consider expressions containing only '1' and '+':

1 + 1 + 1

There are two ways to parse this ignoring associativity, which means there are two valid parse trees:

(1 + 1) + 1
1 + (1 + 1)

but if the parser only outputs one, even if it is arbitrary, why does it matter?

It would probably matter more with an example where the two parse trees have different semantics. Change those pluses to minuses.

But I think the even more important example is where you have two unrelated expression forms that interact ambiguously. For modularity reasons, it's nice to be able to view various expression forms as unambiguous choice, rather than prioritized choice - with prioritized choice you have to think about all pairs of expressions and figure out which production should come first. It's much easier if you can just throw all of the productions at the compiler and have it warn you that this pair here might conflict. Bonus if it can also give you an example of an ambiguous parse. Then you can insert an explicit prioritization to resolve the ambiguity if that's the right solution.

My original intent with the prolog parser was to construct obvious parsers for things like expressions and then join them together. The problem is that backtracking gets out of hand rapidly, and we have to cope with backtracking changes to the already parsed abstract-syntax when it backtracks.

In practice it seemed easier to build the prolog parser mostly LL(1), with controlled backtracking only where necessary.

I am not sure if the idea of combining separate parsers actually works well, for example:

exp = var | exp, +, exp | exp, *, exp

it seems easer to do

exp = var, option((+ | *), exp)

What is the best way to validate powerful intuitive grammars, e.g.,
the one at the following location:
Intuitive Grammar

Best is not a very good choice of word here. Do you mean fastest, or perhaps easiest for the programmer to compose and read?

Excellent question!

We are looking for intuitive ways to validate grammars that produce understandable diagnostics.

Parser combinators seem a good way to express the parser part, providing you have a good minimal set of primitives. The parsers are declarative and much easier to change than hand written parsers.

Errors can be reasonably good because you can track the choice points, and where things go wrong (with backtracking) and you can generate something approximating EBNF for what the parser was expecting.

Synthesised attributes seem easy as the parser should be able to report errors during sythesis. Inherited attributes seem harder and you might want to keep a reference to the parser that generated the attribute.

I think a compiler from a formal attribute grammer to code (or a language with built in support for attribute grammars and backtracking) would be more in line with your goals.

The goals here are maximum understandability and good error reporting without compromising performance, and embedded in the host language (C++). In my project this will eventually be replaced by a self hosted parser that should be a lot nicer, but a long way to go to get there.

Unfortunately, parser combinators are not good enough to make a competitive IDE for a sophisticated language like ActorScript.

Because the syntax for ActorScript is very tight, it is possible to have very good interactive diagnostics. However, it does not seem to be feasible to express the diagnostic process using parser combinators.

Can you describe the problem in more detail? How does the diagnostic process work and why does that have anything to do with parser-combinators?

The problem is to produce good diagnostics as a program is typed into an IDE.

I am not sure what you mean by diagnostics, but I don't see a problem with the parser combinator approach. The parser combinators can compose a data structure that represents the parsing, that you can then interpret how you want including giving interactive feedback.

My research topic!

But on the way, I found actors to be incredibly unsuited to the incremental computations to solve such problems.

Duplicate post.