Lambda the Ultimate

I'm sorry about the mistake. This wasn't very clear from the documentation at
http://spirit.sourceforge.net/distrib/spirit_1_8_3/libs/spirit/doc/scanner.html.

However to support what you say, I did find the following quote:

Typical parsers regard the processing of characters (symbols that form words or lexemes) and phrases (words that form sentences) as separate domains. Entities such as reserved words, operators, literal strings, numerical constants, etc., which constitute the terminals of a grammar are usually extracted first in a separate lexical analysis stage.

At this point, as evident in the examples we have so far, it is important to note that, contrary to standard practice, the Spirit framework handles parsing tasks at both the character level as well as the phrase level. One may consider that a lexical analyzer is seamlessly integrated in the Spirit framework.

Although the Spirit parser library does not need a separate lexical analyzer, there is no reason why we cannot have one. One can always have as many parser layers as needed. In theory, one may create a preprocessor, a lexical analyzer and a parser proper, all using the same framework

However, in the documentation there is much reference to a distinction between "character level parsing" and "phrase_level" parsing which indicated to me a distinction between tokenization and parsing. Furthermore the notion of "skip parser" is precisely a tokenizer. I am unfortunately unclear at this point whether the full range of parsing operators in Spirit apply equally to both "character level parsing" and "phrase level parsing".

Thanks Kalani. I just reviewed http://pdos.csail.mit.edu/papers/packrat-parsing:ford-ms.pdf and I see that a PEG expresses a TDPL which is not a superset of CFG. Sorry about this mistake.

However with regards to zero-width rules, in a parsing expression grammar these can be of arbitrary length and sophistication as opposed to single or even N token look-ahead.

From Brian's paper:

Another important part of this expressiveness is provided by the `&' and `!' operators demonstrated above. These operators represent syntactic predicates [16], which allow arbitrary syntactic patterns to be used to direct decisions without actually consuming any
input text.

The readability is not so different:

Spirit Example (from the docs):

    struct calculator : public grammar<calculator>
    {
        template <typename ScannerT>
        struct definition
        {
            definition(calculator const& self)
            {
                group       = '(' >> expression >> ')';
                factor      = integer | group;
                term        = factor >> *(('*' >> factor) | ('/' >> factor));
                expression  = term >> *(('+' >> term) | ('-' >> term));
            }

            rule<ScannerT> expression, term, factor, group;

            rule<ScannerT> const&
            start() const { return expression; }
        };
    };

YARD:

    namespace calculator
    {
       struct Expression; 

       struct Group :
          Seq<Token<'('>, Expression, Token<')'> > { };

        struct Factor :
          Or<Integer, Group> { };

        struct Term :
          Seq<Factor, Star<
            Or<
              Seq<Token<'*'>, Factor>,
              Seq<Token<'/'>, Factor>
            > { };

        struct Expression :
          Seq<Term, Star<
            Or<
              Seq<Token<'+'>, Term>,
              Seq<Token<'-'>, Term>
            > { };
    }

Notice YARD doesn't have a scanner, the scanner is integrated into the grammar. This is another big difference between the two.

As for the speed difference, it is more significant than you give YARD credit for.

Your example, simplified:

rule<> group = '(' >> expression >> ')';
rule<> factor = integer | group;
rule<> term = factor >> *(('*' >> factor) | ('/' >> factor));
rule<> expression  = term >> *(('+' >> term) | ('-' >> term));

Much more readable than YARD in my opinion.

As for the speed difference, it is more significant than you give YARD credit for.

You will be hard pressed to find significant differences in performance. Modern CPUs execute code through double dispatch (either by function pointer or table indexing) in the same speed as static calls, provided that the double dispatch target does not change much, which is the case in parsers.

The YARD-Spirit specific questions I've answered on my blog.

As for the discussion at http://lambda-the-ultimate.org/node/1599, I wasn't aware of it, thanks for bringing it up.

I have some issues with the basic premises of the original post:

1) the stack can easily overflow, especially when parsing deeply-nested rules.

This is not a problem I have ever encountered in a recursive-descent parser, and I use them exclusively for all of my parsing work, and you know how much that is :-)

2) some of the results may be thrown away, making parsing slow.

How slow depends on how many results are thrown away. Interestingly one solution is "memoization" used in packrat parsing. In general speed has never been an issue for me R-D parsers.

3) left-recursive grammars can not be handled.

This is not a limitation of R-D parsing, but of LL grammars.

4) backtracking has a cost.

Not a significant cost: just a few return instructions, and pointer ... sorry I meant input iterator ... assignments.

I have done an implementation of the idea expressed ...

Can you share it?

cdiggins: This is not a problem I have ever encountered in a recursive-descent parser, and I use them exclusively for all of my parsing work, and you know how much that is :-)

It's a good idea to check for stack overflow when a parser is deployed where a malicious bit of source code might take down a server using a recursive descent parser on client requests. This is especially true in servers using threads to parse requests. (Single threaded Unix apps might assume the stack can get aribitrarily large and spiral into death by page thrashing before death by overflow.)

For example, if you're using pthreads and the default stack size is 1MB and this seems too large for many threads you might want to have in pool, you might choose a smaller default size (like 256K I saw recently). Then suddenly it's not hard to construct a request that's not especially big that can overflow this stack in a parser.

What I've done in the past is reify stack overflows as an explicit AST node. (The node says "you overflowed the stack here blah blah blah" so this propagates to the server response.) A lot of error conditions can be turned into parse tree nodes to put off what should be done about them, so the parser needn't do it. [cf]

This is a very good point. Thanks for bringing it up.

This is not a problem I have ever encountered in a recursive-descent parser, and I use them exclusively for all of my parsing work, and you know how much that is :-)

It's very easy to overflow the stack. I had encountered the problem when I coded a Java-like grammar with many operator levels. Expressions like foo * bar(3, 2) + (new Item({1, 2, 3})).getSum()...) can easily create an overflow, especially if they are deeply nested (expressions in statements in methods of anonymous classes declared deeply inside expressions of methods of classes).

How slow depends on how many results are thrown away. Interestingly one solution is "memoization" used in packrat parsing. In general speed has never been an issue for me R-D parsers.

And for me, speed has never been an issue, since I did it only for testing. But it might be an issue in real world scenarios.

This is not a limitation of R-D parsing, but of LL grammars.

But it can be handled easily, especially if you use stacks.

Not a significant cost: just a few return instructions, and pointer ... sorry I meant input iterator ... assignments.

Very significant cost, especially if the error is in many levels deep. For example, if parsing fails in a complex expression in a statement in a method in a class, return from so many functions is incredibly significant.

Can you share it?

I only I had it...but if I have time, I will try to make something. It's not too difficult though to try it yourself. Parser classes should have a method where they accept a parser context, where the parser context has two stacks: a stack of continuations and a stack of backtrackings. Sequence parsers place the next element of the sequence in the continuations stack, where as choice parsers place the alternative path in the sequence of backtrackings, along with the parser status (i.e. an index of the current token at the point of backtracking).

The parser loop pops a parser from the continuation stack and invokes its 'parse' method. If that method returns failure, then the parse context is popped from the backtracking stack, and execution continues from there. Parsing succeeds when all tokens are consumed and the continuation stack is empty.

With a little imagination, you can handle left recursion as well.

My next attempt on parsers is to make a table-driven parser constructed lazily out of a Spirit-like grammar: each visitation in a parser node will create a table of tokens; next visitation will not ask the parser node to parse anything but it will do a table lookup. Each table entry will contain a token id and a pointer to the table that represents the next parser state. Gradually, as the input is parsed, a table-driven parser will be built up, allowing for merging of the same tokens at the same positions, resolving of the problem of left recursion and identification of shift-reduce and reduce-reduce errors.

EDIT:

after an hour of furious coding, here it is:

parser1.zip