Josh Haberman

I’m digging back into Gazelle after a several-month dormancy. If you happen to be someone who syndicates my commits, either directly or via your GitHub news feed (don’t laugh — I have 18 “watchers” on GitHub!) you’ll notice a flurry of commits from the last few days. I’ve been working on whitespace handling, and progress is refreshingly brisk: I have things pretty well working after only a few days of work.

Whitespace handling was for a long time the biggest thing preventing Gazelle from being actually useful. I had a whitespace-handling mechanism back in 0.1, but had to rip it out in 0.2 because it was naive and premature. It’s back now, and while it looks mostly the same from the user’s perspective, it’s totally different under the hood.

Here’s the current picture of a JSON grammar, using the new whitespace facility:

// Grammar for JSON, as defined at json.org.

@start object;

object   -> "{" (string ":" value) *(,) "}";
array    -> "[" value *(,)              "]";

str_frag -> .chars=/[^\\"]+/ |
            .unicode_char=/\\u ([0-9A-Fa-f]{4})/ |
            .backslash_char=/\\[ntbr"\/\\]/;
string   -> '"' str_frag* '"';

number   -> .sign="-"?
            .integer=/ 0 | ([1-9][0-9]*) /
            .decimal=/ \. [0-9]+ /?
            .exponent=/ [eE] [+-]? [0-9]+ /? ;

value    -> string | number | "true" | "false" | "null" | object | array;

whitespace -> .whitespace=/[\r\n\s\t]+/;

@allow whitespace object ... number, string;

It’s the @allow statement at the end that triggers the whitespace facility (which are more generally called “subparsers”). That statement means that any time the parser is inside an object (eg. all the time), but not inside a number or a string, whitespace can appear anywhere. More specifically, for all states in such rules, the @allow statement defines a “whitespace” transition back to the same state.

As a result, the rule graphs start looking like this:

All the whitespace transitions are a little bit annoying to look at, and I’ll definitely have to tweak the visualization to show them in a nicer way. But this gives you an idea for what’s going on.

What’s nice about this scheme is that you get to specify the whitespace rules in a simple way (”whitespace is allowed everywhere except in these certain rules”), but then the whitespace becomes a part of the same grammar data structure and is analyzed by the same algorithms as everything else.

It’s worth mentioning that this design is significantly different than the traditional design, which is to have a separate lexer simply discard whitespace and comments before they ever hits the parser. The lovely thing about doing it my way is that the whitespace becomes a part of the parse tree (if you want it to — you’ll be able to turn this off). This means:

1. round-trips from text -> parse tree -> text are lossless
2. therefore programs can operate on the parse tree to do whitespace-preserving transformations
3. programs can also analyze the parse tree with regard to how it follows style rules
4. programs like doxygen that consider comments and whitespace significant could operate on a Gazelle parse tree

Things have been pretty quiet here lately. All I can say about that is “life happens!” But I’m very pleased to announce that I am ready to release Gazelle 0.3! The download link is on the Gazelle homepage.

See the Release Notes for what has improved since the last release. The gist of is it that the compiler is a lot more robust: it catches more error cases and will never hang due to errors in the input. There is also explicit ambiguity resolution, which makes it possible to resolve the ambiguous “if then else” case explicitly. And this is all accompanied by a large test suite, since this grammar analysis is difficult and subtle.

The biggest remaining problem that keeps Gazelle from being practical is still the lack of whitespace handling. And this is exactly what the next release will fix.

As I’m adding more capabilities to the Gazelle grammar description language, I’ve come up against a problem for which I can’t find any solution I like. So I’m putting it to you, my esteemed readers, to suggest a solution I will like more than the ones I’ve already brainstormed.

Here’s the problem. I’m at a point where I want to support prioritized choice in Gazelle grammars. Prioritized choice is a way of letting grammar writers explicitly resolve ambiguities that have crept into their grammar. Take the following grammar rule:

s -> "X" | "Y";

The two alternatives in this rule (X and Y) have equal priority. That doesn’t actually matter in this case, since no text can match them both, but now consider changing the rule a bit:

s -> "X" | "X";

Now there is a problem, because an X matches both alternatives. There are two legal parse trees that are both correct according to the grammar. As a result this grammar is ambiguous. A parser doesn’t have any reason to choose one over the other, because they are of equal priority.

The solution to the problem is to let the user specify which alternative should be taken when both match. If we allow users to do this by introducing prioritized choice, our solution looks very much like how Parsing Expression Grammars (also known as PEG’s) work. And the syntax that has become very standard in the PEG literature is to use “/” as the operator for prioritized choice. So our ambiguous grammar would be made unambiguous by using prioritized choice:

s -> "X" / "X";

Now the parser will always choose the first alternative, and the grammar is no longer ambiguous. You might wonder “what’s the point?”, since the second alternative will never be taken, but in many other cases of ambiguity, the choice of lesser priority will be taken. The classic example of ambiguity (which can be resolved in this way) is if-then-else:

stmt -> "if" expr "then" stmt |
        "if" expr "then" stmt "else" stmt |
        expr;
expr -> "true" | "false" | /[0-9]+/;

This grammar is ambiguous, because the fragment:

if true then if true then 1 else 2

…can be parsed in two different ways. The “else” could be assigned to either “if” — both are valid according to the grammar.

So I definitely know I will be introducing prioritized choice. The question is what syntax to use. Like I mentioned before, I would really really like to use “/” since there is a strong convention from the PEG world for it. But unfortunately this introduces a major ambiguity in Gazelle’s own grammar, because it conflicts with the syntax for regex literals. What does this mean?

s -> a / b;
a -> c / d;

Is that two rules that both use prioritized choice, or is it one rule that has a giant regular expression in it?

s -> a / b;
a -> c / d;

I really don’t want to give up using slashes to introduce regular expression literals, because that is a really strong convention that a lot of programmers are familiar with. But I also really don’t want to give up using the really strongly established convention of using slash for prioritized choice.

Anyone have an idea for a compromise I might like? The only one I can think of is adding a prefix to the regex literals sort of like Perl’s m{} form for regular expressions. It could be something like m/regex/. But I hate to add that uglification to the grammar, especially since regular expressions are going to be SO much more common than prioritized choice.

Any ideas, anyone?

Bonus: the other form of ambiguity resolution

Choice/alternation isn’t the only possible source of grammar ambiguity. Gazelle’s constructs for optional and/or repeating grammar fragments can also be ambiguous. The if-the-else example is perhaps more idiomatically written in Gazelle like so:

s -> "if" expr "then" stmt ("else" stmt)? | expr;

It’s written differently, but it’s just as ambiguous as before. So we need the same sort of tool to resolve this ambiguity — a way to say “prefer to match the optional part” or “prefer to NOT match the optional part.” This is equivalent to defining a “greedyness” to these operators like Perl lets you do in regexes. The syntax I am planning for these is:

s -> a b?; // no preference to match the b or not
s -> a b+; // no preference to keep matching b or not
s -> a b*; // no preference to keep matching b or not

non-greedy variants
s -> a b?-; // prefer to NOT match b (non-greedy)
s -> a b+-; // prefer to STOP matching b (non-greedy)
s -> a b*-; // prefer to STOP matching b (non-greedy)

greedy variants
s -> a b?+; // prefer to KEEP matching b (greedy)
s -> a b++; // prefer to KEEP matching b (greedy)
s -> a b*+; // prefer to KEEP matching b (greedy)

I’m not following the Perl convention here (Perl uses “?” instead of “-” to make the match non-greedy). But on the other hand:

1. Perl doesn’t have a way to explicitly make the match greedy — matches are greedy by default. So it has no convention for a “make greedier” operator.
2. not very many people know/use Perl’s greediness operator anyway

So to write the if-then-else example with explicit ambiguity resolution, you would write:

"if" expr "then" stmt ("else" stmt)?+ | expr;

…because when there is an ambiguity, we want to bind the else to the most recent if.

An aside: “great, so I can just start slapping greedy and non-greedy modifiers on everything, just to be safe, right?”

Not so fast there. Ambiguity resolution isn’t something you should take lightly, because a grammar with an ambiguity in it presents a user-facing irregularity in your language. For example, the if-then-else example is a user-facing issue: either “else” pairing makes logical sense, and it’s totally arbitrary how you decide to resolve the ambiguity. You have to tell your users about it. You should strive to absolutely minimize the numbers of such ambiguities in your language whenever you can!

The danger of using ambiguity resolution operators willy-nilly is that you don’t necessarily know if they’re actually resolving ambiguities. For example, if you wrote:

s -> "X" / "Y";

…the prioritized choice here is completely extraneous, since this grammar is unambiguous already. Because ambiguities are so important to keep track of and educate your users about, you don’t want to have to wonder whether a prioritized choice is resolving an ambiguity or not. You want to know that it is.

To this end, Gazelle will keep track of all ambiguity-resolution operators and error if any of them are never actually used to resolve an ambiguity. So you can’t just sprinkle them around “just to be safe,” you must only use them where they are effective. And this will make Gazelle grammars much more useful, because you will know exactly where all your ambiguities are.

By the way, Gazelle can’t detect any ambiguity in your grammar; calculating whether an arbitrary context-free grammar is ambiguous or not is undecidable. Basically, all grammars fall into one of several categories:

1. Gazelle can handle the grammar (ie. the grammar is in the green region of the diagram in my previous entry).
2. Gazelle can handle the grammar except for the fact that it’s ambiguous.
3. Gazelle cannot handle the grammar, and would still not be able to even if you resolved the ambiguities.

If your grammar falls into category 3, Gazelle doesn’t know whether the grammar is ambiguous or not. But for grammars in categories 1 or 2, Gazelle knows exactly where the ambiguities are.

Bonus #2: a word about Parsing Expression Grammars

Something you might say (especially if you’re a PEG fan) is “gosh Josh, if you’re going to all this work to introduce ambiguity resolution, why not just use PEG’s flat-out and abandon all this LL(*) nonsense?” Because essentially what I’m doing is supporting both PEG-based constructs (like ordered choice) and context-free grammar constructs like non-ordered choice. And PEG’s support a larger set of grammars than Gazelle ever will (I believe they support any non-left-recursive PEG, though I don’t have a reference for this).

There are two really major reasons why I don’t think PEG’s are the way to go. The first one is related to the point I was making before. With PEG’s all choice is prioritized choice. However, with PEG-based tools you have no idea if there are real ambiguities in your grammar or not. PEG’s are defined such that ambiguity does not exist, but this does not make if-then-else style issues go away, it just sweeps them under the rug. Even if you don’t call it “ambiguity,” it is still a user-facing issue that you as a language designer definitely want to know about! If you have the following in a PEG:

s -> a / b;

…you have no way of knowing if this represents an ambiguity, which means that you don’t know if changing the grammar to:

s -> b / a;

…will make a substantive difference or not! You’re flying blind.

The second reason is that Gazelle’s parsing algorithm will be far, far faster than packrat parsing (which is the algorithm used to parse PEG’s). Both algorithms will have linear asymptotic complexity (though as I briefly mentioned before, I believe that LL(*) grammars can degrade to n^2 in degenerate cases; though I will argue that this will never happen in any sane language). But though both are linear, packrat parsing’s constant factor is far higher, and packrat parsing uses O(n) space where n is the size of input.

This might all sound like hot air, but check out these real, hard numbers. On the homepage of the Aurochs parser generator, which uses PEG’s and packrat parsing to parse JavaScript, they say:

How much memory does it use?

An awful lot.

Grammar	Input size	Memory consumption	CPU time	Memory overhead
Javascript	140kb	380Mb	1s	2700
Javascript	71kb	180Mb	0.45s	2500
Javascript	1717	5.6Mb	0.01s	3200

I can’t vouch for whether this is a great implementation of packrat parsing, but the authors sure seem to know what they’re doing. I hope you’ll agree that 380Mb of memory just to parse 140kb of text is horrendous, and 1s is quite slow too. Gazelle can’t parse JavaScript yet, but here is a rough ballpark estimate of what the performance will be like to parse 140kb of text once it can:

• memory: Gazelle uses 24 bytes per entry on its stack, plus 12 bytes for every token of lookahead. These are the only non-fixed costs. If we assume a parse tree that goes 100 deep, and an input that requires 100 tokens of lookahead (both ridiculously large assumptions), Gazelle’s memory footprint is 3.6kb. This is 0.0009% of the packrat parser’s memory requirement.
• CPU: Gazelle currently parses JSON at 18.8Mb/s. JavaScript will be more complicated than JSON to parse, but Gazelle will also undergo a lot of optimization that hasn’t been done yet, so I’ll go with the 18.8Mb/s figure. That’s 134x faster than the 140kb/s Aurochs is quoting.

Like I said, the Aurochs authors seem to be very smart — I’m not saying they’ve done a bad job. I’m just saying that if Aurochs is any indication of what we can expect from packrat parsing, it is orders of magnitude slower, and takes enormous amounts of memory even for modest amounts of input text. If anyone has better numbers to show for packrat parsing, I’m all ears.

So even though it’s more work, I’m 110% convinced that using this combination of LL(*) with explicit ambiguity resolution is the way to go, and is the best way to achieve the goals that I have set out for this project.

I wanted to follow-up a bit more on my recent posts about the grammars Gazelle and competing parsing frameworks can handle. Here is an Euler diagram showing my current understanding of what grammars Gazelle can handle compared with the well-known Strong-LL language classes as well as competing parsing frameworks.

Gazelle can currently generate lookahead for any LL(k) grammar, all LL(*) grammars that ANTLR can handle, and a few LL(*) grammars (namely tail-recursive ones) that ANTLR cannot. ANTLR can handle all LL(k) grammars and many LL(*) ones. SLK can handle only LL(k).

Since my last entry, I gave Gazelle the capability to correctly generate lookahead for all LL(k) languages, as long as the user specifies a maximum k. This is in-line with what SLK and ANTLR do, since the problem is undecidable in general. By default I still use my heuristic that I think will detect in most cases whether a grammar will be LL(*) or LL(k) without making the user specify a maximum k, but this heuristic will be foiled in some cases. So if the user really thinks their grammar is LL(k) even though it failed the heuristic, they can specify a maximum “k” and Gazelle will keep searching until it hits that “k”.

Just in case I wasn’t clear enough in my last entry, I strongly dispute the claims on the SLK website that SLK is the only framework that does true Strong-LL(k) analysis. As you can see from the diagram, both ANTLR and Gazelle can handle not only LL(k) but a superset thereof. Current and potential SLK customers: don’t be fooled by SLK’s claims! They haven’t been true for years — ANTLR has been able to handle LL(k) for a long time!

Here are some examples of grammars that fall within the different regions of that Euler diagram:

Strong-LL(*) but can’t be handled by Gazelle or ANTLR:
s: a | b;
a -> "(" a ")" | "X";
b -> "(" b ")" | "Y";

Can be handled by Gazelle but not ANTLR:
s -> a "X" | a "Y";
a -> ("Z" a)?;

Can be handled by ANTLR but not SLK (and is not Strong-LL(k)):
s -> a "X" | a "Y";
a -> "Z"*;

A note about generalized parsing

When I have talked about what grammars ANTLR can “handle,” I’m specifically talking about the grammars it can generate LL(*) lookahead for, without the help of syntactic or semantic predicates. Put more plainly, these are the grammars that ANTLR can parse efficiently and without any hints from the user.

Why the caveats? Well you can put ANTLR and comparable tools in a mode where it parses by depth-first search, using backtracking to abandon search attempts that did not work out. This is equivalent to what most regexp implementations (Perl, Python, Ruby, etc) do, and as Russ Cox has demonstrated this technique has severe (exponential) worst case performance. If you want to trade space for time, you can memoize this depth-first search and get linear time at the cost of some space. While I think these techniques are totally legitimate as a way of expanding the grammars the tool can handle, I personally am singularly focused on parsing in linear time with very low space overhead. I am doing everything I possibly can to parse real languages (everything from JSON to C++) without going outside these bounds. That’s what’s going to make it practical to use Gazelle grammars for things like syntax highlighting in text editors.

Secondly, ANTLR has features that let the user help the parser out with its decisions, either by writing Java code (semantic predicates) or by specifying syntax fragments that the user promises will properly disambiguate alternatives (syntactic predicates). It’s always useful to have more tools of this sort, and Gazelle will certainly include some with time, but again this is an apples to oranges comparison.

Finally, Adrian Thurston (author of the popular Ragel state machine compiler) mentioned on one of my previous entries that there exist general (eg. can handle any grammar) algorithms for top-down parsing, which are automatically more powerful than Gazelle. While this is true, none of them are what I consider practical. Gazelle’s time/space complexity are:

Time: linear
(actually LL(*) could probably become quadratic in degenerate cases, but LL(k) is definitely linear and LL(*) is too, for all intents and practical purposes).

Space: max stack depth + max lookahead depth
Both can be capped. In a bit more detail:

• The maximum stack depth represents the nesting level (for example, number of nested parentheses).
• The maximum lookahead depth represents the number of tokens we have to look ahead in the worst case to disambiguate alternatives.
• Input text that doesn’t respect the maximum depth limits will be rejected (even if it is valid according to the grammar), but that’s the only way to prevent malicious input text from consuming arbitrary amounts of memory. Clients that don’t mind getting DoS’d can just set these limits to unlimited.

No general method can approach this space/time complexity. And I think it is for this reason that no tool (AFAIK) which is aimed at practical use implements a generalized top-down method.

I’d like to post a slightly more detailed run-down of the generalized methods Adrian mentioned when I have the time to take a closer look at them.

So to make a long story short, I stand by my previous claim that Gazelle is (at least briefly) the most powerful practical top-down parsing framework there is.

From a theoretical standpoint, my last entry was incorrect when I said that my new algorithm in Gazelle can decide whether a grammar is strong-LL(k) or strong-LL(*). I had proofs against me — these problems have actually been proven undecidable.

Once I heard this result, I spent hours trying to think of a grammar that is strong-LL(k), but that Gazelle will say is not. I am fairly certain that Gazelle’s algorithm will always terminate, so if the proof is to be believed, there must be a grammar that Gazelle falsely claims is not strong-LL(k) or strong-LL(*).

After many hours, I came up with one. Here it is:

s -> "X"* "Y" "Y" "Z"| "X" c;
c -> "Y" c "Y" | "Q";

This grammar is strong-LL(5), but Gazelle falsely claims it is not strong-LL(k) for any k. ANTLR can handle it (as long as the recursion depth is set high enough).

I’m thinking, though, that this isn’t really a problem. My intuition says that it will be rare that anyone actually tries to write a grammar that fails in this way — after all, it took an evening of specifically trying to exercise this case before I could find a grammar that did. I don’t think real grammars will run into this problem.

So even though I can’t handle all of strong-LL(*), I think I can handle the grammars that will actually come up in practical use, and I still have the extremely desirable property of being able to decide whether a grammar fits or not without forcing the user to tweak recursion depth constants. So although my result isn’t as theoretically significant as I thought, I think that from a practical standpoint I’m still in good shape: I have a terminating algorithm that can handle a very useful set of grammars.