Gazelle Manual

This section offers a quick tour of Gazelle and its capabilities. It assumes you have already compiled and instaled Gazelle successfully; the instructions for doing so are in the README.

For our "Hello, World" example, we'll write a grammar for a language that is simply an integer surrounded by an arbitrary number of balanced parentheses. To begin, use a text editor to write this grammar to hello.gzl.

This text is a complete Gazelle grammar. It defines a single rule called "hello", which expands to either another (recursive) hello surrounded by parentheses, or a string of one or more numeric digits (and this terminal is named "digits").

This language will match any of the following inputs:

But none of these inputs will match:

The first step is to compile the text version of the grammar to bytecode. The Gazelle compiler analyzes the input grammar and builds a series of finite automata (state machines) that can do the real parsing. It writes this compiled version of the grammar to bytecode.

You won't see any output — that means that the grammar was compiled successfully. Just like gcc, gzlc is silent when things succeed. The default output filename is the input filename with gzl replaced with gzc.

If you want to see a bit more verbose output, run gzlc with -v.

Now, the magic moment where we do our first actual parsing. We'll write some valid input text for this language, then use gzlparse to actually parse it.

Again, by default Gazelle doesn't print any output when things were successful. If there had been a parse error, Gazelle would have printed an error and exited. If you want to see more output, the flags —dump-json and —dump-total will print a parse tree in JSON format and a total byte count, respectively.

The next thing you will want to do is use gzlc to produce an HTML dump of the grammar as the compiler sees it. This is an invaluable way to check and be sure that the compiler is seeing things the way you meant it to. If not, you might have misspecified the grammar, or you may have found a bug in the compiler (and these certainly exist).

Doing this HTML dump requires that Graphviz is installed. If ImageMagick is installed, this will also be used to create thumbnails.

Now open html/index.html in a web browser to view the HTML dump. You will see an illustration of the "hello" rule, and you should see that it corresponds to your intuitive understanding of this rule. There are two paths through the rule — either "(", hello, ")" or digits.

You will also see the state machine that does the lexing: it recognizes three different tokens: a left parenthesis, a right parenthesis, and one called "digits" that is a string of repeated numbers. Notice that Gazelle built a lexer for you based on the grammar you entered. You don't have to give Gazelle a separate lexer specification.

Creating a lexer was trivial in the above example because none of the different token types conflict. Because left parenthesis, right parenthesis, and "digits" are all distinct and do not conflict, Gazelle simply combined them all into a single DFA that breaks the input into tokens. But consider a more complicated example: a grammar to describe files of comma-separated values, where the values can either be strings or numbers. For example:

What makes this example more complicated is that outside of quotes, commas and digits mean one thing, but inside quotes they mean another. Here is a grammar to describe this format:

If you compile this grammar with gzlc -d and view the HTML output, you will see that Gazelle has generated two different IntFAs (DFAs used by the lexer) — one that is used inside strings that one that is used the rest of the time. Inside a string the text "42" will be lexed as the token "chars", but outside a string it will be lexed as the token "number."

This concludes the tour. Next you can read more about Gazelle's input language and experiment with your own grammars.

Gazelle's major limitation at the moment is that it cannot support removing whitespace or comments from the input. A feature to address this is coming, but for the moment please bear with me!

I hope you enjoy Gazelle!

This chapter focuses on the syntax of Gazelle grammars, and the considerations of making your grammar easily parseable.

Rules are at the heart of every grammar; they describe the patterns of all the constructs in your language. Here is a simple example that describes an assignment statement.

This declares that an assignment statement is an identifier followed by the string “=” followed by an expression. We say that assign is the rule's name; ident, "=", and expr are its components. We assume here that “ident” and “expr” are defined elsewhere in the grammar.

For every rule you write, Gazelle builds a graph that describes the possible paths that the input can take through this rule. Since this rule is very simple and doesn't have any kind of repetition, the graph is just a single path.

Often you will have a rule that can be expanded in more than one way. For example, you might have a boolean expression that can be either “true” or “false.” You can specify alternation to Gazelle with the vertical bar (|).

As you would expect, this produces a rule graph with two edges — one for each option.

You can use alternation freely throughout your rules. Alternation has the lowest precedence, but you can override that with parentheses. Here is a more complicated rule that demonstrates more extensive use of alternation.

The graph for this rule is naturally a bit more complicated, but looking at it should convince you that the possible paths through this rule are what you intended.

Repetition is our other main tool for rule-writing. Repetition isn't strictly necessary for writing context-free grammars (it can always be expressed as recursion), but using it can make grammars easier to write, understand, and ultimately parse.

Gazelle offers these repetition modifiers; place them after the component you want to modify.

Here is an example that uses repetition; it is the definition of an object in JSON:

So far we have neglected to describe in detail what can appear as a component on the right-hand-side of a rule. In the previous examples we have seen strings and nonterminals — in this section we flesh out exactly what can appear there.

There are four fundamental kinds of components that can appear on a right-hand-side.

Strings and regular expressions are referred to collectively as “tokens” or “nonterminals” because they represent actual strings of the input text. Gazelle can take the tokens defined in the grammar and use them to create a lexer-like component of the parser automatically.

All rule components must have a name that is unique within that rule. Names can be specified explicitly with the syntax:

The component names are important when it comes to pulling apart the resulting parse tree, which is why every component must have one. Strings, rules, and named regular expressions have default names:

The last case is important: regular expressions must have explicit names. This is for two reasons: one is that we don't have a good way to generate a reasonable default name for a regular expression. The second is that if regular expressions could be specified without an explicit name, Gazelle's grammar would be ambiguous:

Are these two rules, or one rule that has a long, multi-line regex in it? To avoid this ambiguity, every regular expression inside a rule must have an explicit name.

When a string appears on a right-hand-side, it specifies exactly what string we expect to see at this point in the input. Strings can be either single or double quoted. Backslashes can be used to quote the next character, but no special backslash sequences are currently recognized (this clearly needs to be fixed in future versions of Gazelle).

Regular expressions (regexes for short) describe patterns of text. Users of languages like Perl, Python, or Ruby, or of tools like grep, will find the regular expressions in Gazelle very familiar. The main difference that you will notice is that whitespace in Gazelle regular expressions is insignificant (as you would get in Perl with /x).

Regular expressions in Gazelle are delimited with / (forward slash):

In a regular expression, characters match themselves with the following exceptions:

A regular expression can be named and referred to later by using the named regular expression syntax.

This appears to be almost identical to declaring a rule with a single regex on the right-hand-side, like so:

The primary difference is that the named regular expression syntax avoids creating a trivial and useless nonterminal graph. While Gazelle could detect the case where a nonterminal graph is trivial, it is important that Gazelle preserves the structure of the grammar as specified, so that client programs can hook into this structure at parse time.

Definitions of nonterminals and tokens will be the bulk of most syntax files; however there are several commands that give Gazelle important information about the grammar that isn't expressed in rules.

The @start command tells Gazelle what the top-level nonterminal for a grammar is. If @start is not specified, Gazelle assumes that the first nonterminal in the grammar is the start symbol. The syntax of this command is simply:

@start is not required, and may not appear more than once per grammar.

The @allow command lets you tell Gazelle about syntax constructs that can appear in many different places througout your grammar. Its primary use case is whitespace — it lets you say that whitespace can appear between any two components of certain rules in your grammar. Its syntax is:

For example:

start_nonterm is very likely to be the top-level rule in your grammar — the rule you specified to @start. end_nonterm specifies what rule or rules do not allow whitespace (their child rules are automatically excluded also). All rules that are sub-rules start_nonterm (either directly or indirectly), but are not sub-rules of end_nonterm, will allow nonterm_to_allow in between any two components of the rule.

Some grammars are ambiguous, meaning that some input strings could be parsed in more than one way. The most common example of this is the classic if/then/else case:

If you try to compile this grammar, Gazelle will give you this error message:

Unfortunately, Gazelle cannot tell you with certainty that the problem is an ambiguous grammar — detecting whether a grammar is ambiguous is undecidable (impossible to compute in all cases). In the future a more detailed error message will make clear the root of the problem, which is that Gazelle cannot decide whether to match an "else" or not with input text like:

As the grammar is specified above, the "else" in this example could go with either if. This ambiguity exists in many language's grammars, but is explicitly resolved by saying "an else goes with the most recent if". You can express this ambiguity resolution directly to Gazelle by using its ambiguity resolution operators.

Here are examples of these operators in use:

Gazelle can only support some resolutions of ambiguity. For example, we can't use Gazelle to resolve the if/then/else problem the other way:

Because of Gazelle's overriding goal to ensure that the resulting parser is both efficient and as "on-line" as possible, Gazelle can't support all grammars or ambiguity resolutions. If you wanted to resolve the "else" problem the opposite way, you would need to write custom code that makes the decision of whether or not to match the "else", because the logic to do so is nontrivial.

Unfortunately, the same is true if you try to resolve if/then/else with prioritized choice:

The problem in this case is that you're trying to make Gazelle figure out before it's parsed an "if" whether or not it will have an "else", but that requires unbounded lookahead that has to count (it has to match the "ifs" that it sees with "elses").

The moral of the story is this: in most cases you should avoid ambiguities in your grammar. In some cases you can't avoid them and these ambiguity resolution operators will be a satisfactory solution (if/then/else is the most likely case for this). In other cases ambiguity resolution won't suffice and you'll have to get down and dirty with some imperative Lua code.

You will notice that regular expressions and rules both give you the ?, *, and + operators. Given this, there are are many situations where you will find that you can use either regular expressions or rules. For example, consider this regular expression that describes a number:

You could express the same pattern using a rule instead:

In this case, the rule version is much longer and more verbose, because the regular expression offers a useful tool that strings in rules do not offer: the character class. In addition, the second form could make the grammar as a whole more expensive to parse by requiring more tokens of lookahead. Since a number is no longer a single token, it cannot be used as a single unit of lookahead.

Does this mean that we should prefer regular expressions whenever we can? Not always. Consider this example of a quoted string that contain backslash escapes:

We could write a Gazelle grammar to parse this using a single regular expression.

However, if we write it this way, we lose the information about where each backslash escape was in the string, because regular expressions in Gazelle do not have capture groups. In Gazelle, you find boundaries for subexpressions by making those subexpressions their own components. In this case, writing the pattern using rules is superior, because it preserves all the important information about where each sequence was seen.

So what general rule can we extrapolate from this? In general, you should only use regular expressions to match strings that don't have any logical sub-parts. If you find that your regular expression has sub-parts that you might want to pull apart later, make each sub-part into its own component.

Gazelle uses an algorithm known as LL(*) for parsing. The benefit of this algorithm is that it is very fast and uses very little memory. The drawback is that it cannot parse all grammars. Using all the tools that Gazelle gives you, it should be able to parse all real-world languages, it just might require you to rearrange your grammar a bit.

For anyone with unpleasant memories of trying to debug LALR(1) parsers like yacc or Bison, it bears mentioning that debugging Gazelle grammars should eventually be significantly easier than debugging Bison grammars. The LL(*) grammar analysis that Gazelle performs is far easier for humans to understand than LALR tables. However currently some of Gazelle's error messages do not give you the amount of information you really need to debug the problem. This will improve in future versions of Gazelle.

What follows is a list of errors your grammar can have, what they mean, and how to fix them.

As a top-down parser, Gazelle cannot handle left-recursion. Left-recursion is simply a rule whose first component is a recursive invocation of the same rule. Examples are:

Trying to compile any of these grammars will cause Gazelle to throw the error:

In the future this message will give more information about which rule(s) were left-recursive. For the moment you have to figure this out yourself.

Eliminating left-recursion is not difficult. The most common reason for writing left-recursion is to express some kind of list:

The way to fix this is to express the list using repetition operators instead of left-recursion.

The earlier section on ambiguity resolution discussed ambiguity some. A grammar is ambiguous if there is input text that could be interpreted more than one way according to the grammar. Examples are:

In these cases, Gazelle knows that the grammar is ambiguous and can tell you so in the error message:

This is telling you simply that in matching a single terminal "X" Gazelle was able to take two different paths through the grammar and end up in the same place (the definition of an ambiguity). Here is the error message from the last example above of three rules:

As you can see, Gazelle saw that it could either enter b and then c or just enter c.

To fix problems of ambiguity, you need to rewrite the grammar such that the given input text cannot be interpreted in more than one way. Another option is to use the ambiguity resolution operators.

Note that while Gazelle can detect some cases where the grammar is ambiguous (such as the above examples), in other cases it may only detect that the grammar is not LL(*) but not realize that this is because of an ambiguity. This is the case in the if/then/else example.

Every rule must have at least one non-recursive alternative. For example this rule is invalid, because it can never stop recursing:

Gazelle complains with this error message:

The solution is simple: every rule must have one alternative that stops recursing. For example, you can fix the above rule like so:

Like left-recursion, two or more rules can work together to create this error:

These can be the trickiest errors to solve — more information about solving them will be in future versions of the manual.

The C Runtime is documentated in the header files in runtime/include/gazelle. You can browse them online at GitHub: the header files for the latest version of Gazelle. For an example of how to use the runtime, see utilities/gzlparse.c, which you can also view online at GitHub.

This section describes Gazelle's parsing algorithm. Unlike LALR(1) tables with their reputation for being mysterious and hard to understand, the top-down algorithm that Gazelle uses should be easy for the average programmer to understand. Gazelle users are encouraged to read this section to understand the way your grammars are analyzed and parsed.

Gazelle's algorithm takes a great deal of inspiration from ANTLR, the LL(*) parser generator written by Terence Parr. While Gazelle seeks to augment the theory that Terence developed, the foundations of Gazelle are strongly based in ANTLR's achievements. Like ANTLR, Gazelle is a top-down parser that models its lookahead as possibly-cyclic state machines. Gazelle's algorithm for generating this lookahead is based on ANTLR's algorithm.

Compared to ANTLR, Gazelle adds the following capabilities:

Compared to ANTLR, Gazelle does not yet support syntactic or semantic predicates, but these (or capabilities like them) are planned for the future.

Gazelle's parsing algorithm boils down to nothing more than a stack of state machines. Each byte of the input transtions these state machines one or more times, and the entire state of the parse can be represented by the stack of state machines that are currently active and which state each one is in.

These are the four different kinds of state machines. Each is explained in detail in the following sections:

In addition, operator-precedence parsing is supported by sandwiching the shunting yard algorithm between layers of the RTN stack.

Language rules that cannot be represented using pure context-free grammars (and all but the simplest languages have such complications) are accommodated with a variety of strategies that let the grammar implementor "hook in" to the above process with imperative code.

Gazelle's algorithm is based around making each rule in a grammar into a graph that resembles a syntax diagram. Syntax diagrams are a common way to describe syntax in a way that is easy for humans to understand visually. Here are some examples of such diagrams:

Syntax diagrams like the ones above visually specify what syntax patterns are allowed by the language. You read them by following the the lines from one grammar element to the next. If there is a fork in the road you can take either path, since both options are valid according to the language. Syntax diagrams are also known as "railroad diagrams" because they are like a network of railroad tracks that have switches at all the decision points.

Gazelle turns each rule into a similar kind of diagram, but Gazelle's diagrams are represented a little bit differently. Here is Gazelle's rendering of the same JSON rule as the first example:

Gazelle calls these "rule graphs" or RTNs (for "Recursive Transition Network"). Rule graphs are state machines, and are one of the several kinds of state machines Gazelle uses to track its parsing state as a whole. You can view the rule graphs for any Gazelle grammar by compiling the grammar with gzlc -d and viewing the HTML output.

In rule graphs the grammar elements (like "string", "value," etc.) are on the edges instead of being the nodes. Also, in rule graphs the lines (the graph edges) don't have decisions or "forks in the road" — the decisions come from deciding what edge to take out of a state. Finally, in a rule graph you reach the "end" of the rule by transitioning to a final state, which is drawn as a state with a double circle. When the parser reaches this state, the rule it was parsing can be considered finished (but need not be — final states can also have transitions out of them).

While the rule graph may look more chaotic than the nicely-laid-out railroad diagram above, Gazelle's rule graph has one important advantage. In Gazelle's rule graph, the states represent real states that the parser can be in. The states in a railroad diagram are not as easy to identify. At any time you can inspect Gazelle's parsing state and see what rule graph state it is in. This is also the basis of how Gazelle can save and restore its parsing state.

The edges of rule graphs can be both terminals and nonterminals. Terminals are physical tokens of input like { and }, while nonterminals are references to other rules like string and value above.

When the parser takes a nonterminal transition, it temporarily stops processing the current rule and moves to a sub-rule corresponding to that nonterminal. To remember where it was, the parser pushes the destination state of the nonterminal transition onto a runtime stack. This whole process is easy to understand when viewed in the context of an example, which will be included in future versions of the manual.

You may have noticed that we glossed over one important detail in the previous section. How do we decide what transition in the rule graph to take? Rule graphs can be nondeterministic: there can be more than one transition out of a state for the same terminal. There can also be final states that have transitions out of them. This means that while Gazelle is parsing, there can be more that one option for what transition to take. How does Gazelle pick the right one?

There are two situations where knowing what transition to take is difficult. First, if any of the transitions that lead out of our RTN state are nonterminals (references to other rules), we need a way to know what strings in the input imply what transitions. For example, consider the rule:

If we are in the start state for word and we see a "5" in the input, what transition should we take? You might guess that we should take numbers, but that's entirely dependent on the definition of numbers and letters. We need a way to "see into" those definitions, so we know what transition to take based on what we see in the input.

The second difficulty is similar, but slightly different. What if we are in a final state that has transitions out of it? Consider this rule:

If we are in the start state for sentence, should we return from the current rule since we are in a final state, or should we stay and match more words? To answer this question we need not only the ability to "see into" word, but also the ability to "see up from" whatever set of rules we are currently recursed into.

This set of problems turns out to be somewhat difficult to solve — in fact, it is exactly the problem that LL parsing aims to solve. Part of what makes it tricky is that depending on how the grammar is written, we might not have enough information at this point in the text to possibly know what transition to take. We always have to look at the next token of input to decide, but in some cases we might have to look ahead 2, 3, or even more tokens before we have enough information to make a decision. It is even possible to write grammars where the token that tells us the difference is arbitrarily far away. These classes of grammars are known as LL(k) if we have to look k tokens ahead to make a decision, or LL(*) if that decision can be arbitrarily far away.

So how do we decide what transition to take in the rule graph? The answer is that Gazelle analyzes the grammar at compile time, and figures out for each rule graph state what tokens we expect to see here, and what transition each series of tokens implies. This information is encoded into a DFA known as a GLA — a Grammar Lookahead Automaton. If after analyzing the grammar Gazelle determines that it is possible to build a GLA for every rule graph state, it builds them and encodes it into the byte-code. If it is not possible to build the GLA (which implies that that the grammar is not LL(k)), Gazelle interrupts the compilation with an error.

When Gazelle is actually parsing, it stops at every rule graph state and tries to determine what transition to take next. To make this decision, Gazelle finds the GLA for this rule graph state and runs it for the tokens of the input until the it hits a final state. That final state will tell the rule graph what transition to take.

TODO: flesh out this section with more examples

In the previous section, we assumed that we had a stream of tokens to feed into the GLA. But where do these tokens come from? The answer is that another layer of DFA's processes the characters of the input text and breaks them into tokens. These DFAs are known as IntFAs, since the characters of the input text are represented as integers (this is not a particularly good name, and may change). IntFAs in Gazelle fulfill the role traditionally performed by separate lexers.

Most programmers have some familiarity with regular expressions, because they are pervasive in modern programming. With Gazelle you describe tokens using strings and regular expressions, and Gazelle compiles these into DFAs using well-known algorithms (unlike what most scripting languages do today — they use an algorithm with much worse worst-case performance, as Russ Cox argues in his article Regular Expression Matching Can Be Simple And Fast).

Lexing using Gazelle has one key advantage over independent lexers: the Gazelle lexing component knows what sorts of language constructs it is expecting to see at this point in the input. A traditional lexer just breaks the input into words without having any idea what sort of construct it's in. For example, suppose you are a traditional C lexer and you see the input:

A traditional C lexer in this case will return the tokens:

It treats "while" as a keyword, even though it is in a context where "while" doesn't make sense. Of course, this is required by the C standard, since keywords cannot be variable names, but suppose we were dealing with a language that did not have this restriction. What do we do? Our traditional lexer design is too weak to return the token WHILE in contexts where it makes sense and an IDENTIFIER named "while" in contexts where an identifier is expected. Another strategy will be required, adding complexity to the parser.

Gazelle, on the other hand, can handle this situation just fine, because parsing and lexing are combined. The key is that every GLA state knows what tokens are valid at this point in the input, so it can choose an IntFA that only recognizes the valid tokens. In the above example, when a Gazelle parser/lexer reached while in the input, the current GLA state would select an IntFA that recognizes IDENTIFIER tokens (because they make sense here) but not a WHILE keyword token (because it does not make sense here). Therefore languages that allow keywords as variables names are easily and naturally supported.

Of course, Gazelle also needs to support languages where keywords are not allowed to be variable names. This can be easily achieved by making the regular expression for identifiers explicitly exclude all keywords. This more explicitly describes the rules of the language anyway — when a language specifications includes text like "variable names may not be any of these reserved words," you can express this directly to Gazelle by explicitly listing the patterns an identifier is not allowed to have.

There is one final detail that is not handled by any of the previous layers: where do the characters come from that are fed into the IntFAs? In the case of ASCII or other single-byte encodings, the answer is simple: the bytes are the characters. However, more and more programming languages are moving towards allowing their source to be in encodings other than ASCII, most commonly Unicode. We need a character decoding step to handle the intracacies of multi-byte encodings.

Many applications handle Unicode encodings such as UTF-8 without representing their character decoding stage as a DFA, so you may wonder why Gazelle takes this route. The benefit of using a DFA is that it provides a way to sanely process partial characters. If we are parsing text that is coming off the network, and the final byte of the buffer ends mid-character, what should we do? We could drop it and re-process it later, but that requires either Gazelle or the application to store it for later re-processing. Worse, it throws away the work we have already done making sense of this byte or bytes. By using a DFA, we can advance the state of the collective machine for every single byte of input, whether or not it is a full character. When we are fed more bytes, we pick up exactly where we left off.

It is also possible that introducing custom processing at this stage could provide an easy and efficient way to process very difficult language corner cases like C's trigraphs.