Grammar a BNF Like Ruby DSL Parsing

Talks

Eric Mahurin

1 talk

#domain-specific-language-dsl

#parsing

#duck-typing

#ruby

#abstract-syntax-tree-ast

#recursion

#compiler-design

Grammar a BNF Like Ruby DSL Parsing

by Eric Mahurin

The video titled "Grammar a BNF Like Ruby DSL Parsing" presented by Eric Mahurin at the LoneStarRuby Conf 2008 explores the development of a Domain Specific Language (DSL) for parsing using Ruby. Mahurin reflects on his journey from hand-crafted recursive descent parsers to creating a unified parser generator that combines lexer and parser functionality. This innovative approach allows developers to define grammars directly in Ruby instead of relying on separate BNF files.

Key points discussed include:

- Historical Context: Mahurin shares his experiences with different parser generators, specifically ANTLR and traditional tools like Racc and Yacc, emphasizing the need for a unified solution.

- Grammar Construction: A grammar in this DSL is represented as Ruby objects, built piece by piece using Ruby operators and methods, allowing for dynamic language parsing.

- Parsing Mechanism: The parsing process takes input that resembles a stream, utilizing grammar definitions to produce a sequence of outputs rather than traditional abstract syntax trees.

- Input Handling: A method called brackets retrieves the next item from the input stream, enabling comparisons between the pattern and the tokens or characters.

- Error Handling & Recursion: The parser is designed to handle left recursion effectively, enabling grammars to be defined in a more natural and straightforward manner. Mahurin illustrates this with examples such as parsing digits and handling nested parentheses.

- Output Options: The system allows for flexible outputs, supporting different methods for evaluating mathematical expressions and adjusting output to meet user needs.

- Performance Considerations: Mahurin discusses optimizations made to avoid excessive recursion and manage large input streams efficiently.
- Dynamic Code Generation: The grammar engine generates code dynamically, supporting a variety of engines including one that compiles to C for improved performance.

In conclusion, Mahurin's presentation delves into the innovative design of a Ruby-based DSL for parsing, highlighting the flexibilities of grammar construction, error handling, and performance optimization. He emphasizes the potential for further exploration and invites questions from the audience.

00:00:06.359 Video equipment rental costs paid for by PeepCode.

00:00:19.359 Good afternoon, everybody! Today, I am going to talk about yet another Domain Specific Language (DSL). This one will help you with parsing.

00:00:24.439 Let me first share a bit of the history of how I got to this point, where I wrote this package. In the past, many of you may have been in the same boat, having written custom parsers that were handcrafted.

00:00:35.640 Typically, these parsers are referred to as recursive descent parsers, but my experience was with Perl. Eventually, I got tired of that and started exploring different tools, one of which was ANTLR for parser generation.

00:00:49.079 However, that still wasn't good enough. What I was looking for was a parser generator that used the same language for generating the parser instead of requiring a separate side file for BNF or other formats.

00:01:02.039 I also wanted something that would unify both the lexer and the parser. Tools like Racc, Yacc, and Lex were separate processes. I wanted to create something that was unified. In my search, I learned Ruby because it has the right mix for what I needed—operator overloading, blocks, and duck typing.

00:01:24.600 This is my fourth rewrite of this package. First, I want to demonstrate how the grammar works to create a parser. To parse whatever language you need, you start with grammar objects. A grammar is essentially just a Ruby object that holds information for the language you want to parse.

00:01:43.240 To build a grammar for the language you want to parse, you construct it piece by piece, starting from the lowest level and building up. You simply use regular Ruby operators and methods, along with a few blocks to get your actions in place. You generate this grammar as a representation of the language you wish to parse. Then, a grammar engine takes that grammar and generates a concrete parser that will parse your input.

00:03:01.680 This entire structure consists of Ruby objects and methods. To contrast this with most commonly used parsers, which typically rely on regular expressions, let me show you a table that illustrates the equivalence between them. The left side features regular expressions that use various symbols and operations to work with strings, while on the right, we have the grammar approach using plain Ruby.

00:03:48.200 With grammar, you don’t put the definitions into a string or a file; rather, you use a DSL that utilizes the operators of Ruby itself. For example, I use the vertical bar for alternation, the plus sign for sequences, and a method for lookahead assertions. At the top of this structure are the leaves of the grammar that you start with to build up, typically character ranges.

00:05:10.520 Next, let's discuss the input sequence. It can be anything; it just needs to resemble an external iterator. I'm using a brackets method to retrieve the next item in the sequence, which can be characters—like those used in regular expressions—or tokens resulting from lexing. The lowest level of this grammar contains what's called an element, which takes tokens from the input stream and compares them with a pattern you provide.

00:06:22.400 The pattern can be anything, but it has to work with whatever is in the input stream. The output of the parsing process varies; other parser generators typically produce abstract syntax trees, but I might describe my parsing process in terms of abstract syntax forced. Instead of generating a tree, this engine produces a sequence of outputs. The default output stream matches the input stream, and various methods allow discarding or redirecting this output.

00:07:11.800 For example, you can apply a discard method to any grammar, which prevents it from reflecting the input in the output stream. You can also redirect it to a temporary buffer where you can perform actions as needed. Additionally, the group method helps create hierarchical structures within your grammar, forming an abstract syntax tree.

00:08:07.919 I want to provide some simple examples to illustrate these concepts. Here's a unit test for the grammar. At the top, I create some helper methods, like the input method that prepares the input into the format I need for my input iterator. For instance, I convert a string into a StringIO object, and the get_c method returns something resembling a lambda that retrieves the next token from my string input.

00:09:45.360 In this first example, I parse a single digit. The grammar simply specifies a character range of 0 to 9. Subsequently, I demonstrate parsing the first digit in a string and appending to the previous output. I also display some invalid conditions based on this parsing structure.

00:10:35.800 Building on that, we move to a sequence of digits. To achieve this, I implement a method called repeat_one, which allows for one or more digits. This time, I assert that the digits must be followed by an end-of-file (EOF) assertion. Therefore, an error occurs if the sequence includes unexpected characters that are not valid.

00:11:35.800 Furthermore, grammars can also connect outputs from one grammar to the input of another. A grammar remains agnostic about the elements in these input and output streams, meaning any grammar can act as a parser or lexer. I have one method called Supply, which connects a single token grammar to form a lexer, linking that to a parser represented by another grammar. Additionally, there is a Pipe method that supports multi-threaded lexer-parser combinations.

00:12:40.000 You can chain these processes together, so a pre-processor could feed a lexer, which in turn feeds a parser. Each step would take an input stream, process it, and generate an output stream, gradually refining the structure based on your requirements.

00:13:16.120 I want to talk about the type of parser this project implements, known as an LL parser. If you've written your own parser, you'll find that they typically parse from left to right, and they are often LL parsers as well. What I'm essentially doing is generating a parser that behaves like a hand-written one, parsing one character at a time, though you might use regular expressions for a lookahead in some instances.

00:14:10.160 Yet, my approach includes a backtrack method, allowing you to look further ahead when making parsing decisions. This effectively provides you with unlimited lookahead capability. Moving on to recursion, another fascinating aspect of the grammar, you can create a grammar that exhibits recursive structures. You can define inner and outer grammar sections, where inner represents the recursive part and outer serves as the culmination of that recursion.

00:15:43.400 Whenever you hit a recursion point, it refers back to the complete grammar. I also look at the positioning of the inner grammar to apply optimizations. If inner is in the middle of a parsing sequence, plain recursion is used; however, if it appears at the end of a structure without any following elements, I implement a loop, akin to tail-call optimizations used in compilers. This prevents excessive recursion that could cause the stack to explode during parsing and provides a significant speed advantage.

00:17:27.200 Left recursion is another interesting topic. Traditionally, left recursion is linked to parsers like Racc or Yacc, commonly known as LR parsers. However, my parser operates as an LL parser while incorporating left recursion. I believe there are very few LL parsers capable of handling left recursion effectively. To explain how I achieve this, if you have a grammar that involves left recursion, I divide it into two segments. The first substitution triggers a failure, while the second assesses it through a loop.

00:18:30.920 For typical LL parsers, grammar would need to be structured away from left recursion, but in this LL parser, you can write grammar naturally in left recursion, which is often the most straightforward approach.

00:19:10.280 Let's revisit the digits parsing example, expanding it a bit. Previously, when parsing the digits '23', it returned the individual characters '2' and '3', which wasn't incredibly useful. Instead, I want it to convert that to an integer. In this case, I implemented a group method to push the results of grammar parsing into a block, converting it into an integer to achieve the desired result.

00:20:36.640 We can expand the grammar further to include recursion and parentheses. By encountering parentheses, we can recurse back into the original expression, ensuring that we can parse complex structures. This showcases an error condition as well; if there’s a mismatch in parentheses, that should be flagged.

00:21:27.360 Next, lets add unary operators. If we encounter a negative sign, we may want to discard it during parsing since it's not needed in the output stream. I also show how to negate the last output if necessary or treat it as a primary number instead.

00:22:50.760 This setup allows us to recognize left recursion where the product appears on the left side. By observing this structure, we ensure that if we see a product followed by another unary operator, it calculates the product accordingly and adds it back to the output stream.

00:23:54.879 Ultimately, we reach our final expression grammar that combines sums, products, and potential unary expressions, so the grammar reflects a complete mathematical expression including terms, products, possible unary negatives, and parentheses.

00:25:07.680 Here's a brief example of consuming the expression, where I evaluate it in its entirety. This setup grants flexibility, as you could choose to output a tree structure instead; the actions I defined have made it evaluate directly.

00:26:15.240 Going back to the grammar engine, it acts as a visitor that traverses the tree of grammars. While traversing the grammar, it plays a role in generating a parser. I offer several engines to accomplish this. One engine is Ruby Zero, which performs parsing without generating a separate parser—this was my initial prototype.

00:27:48.000 Other engines I developed include a Ruby parser, which generates parser code for later use, and one that compiles down to C for performance improvements. I believe we can explore the possibilities further, creating engines that generate C or C++ code.

00:28:15.760 Furthermore, the grammar layer is lightweight—it’s ultimately a user-defined layer that facilitates creating grammars without burdening the generated engine, which can be of a different type entirely.

00:29:03.680 You may have noticed that the action blocks look like standard Ruby code, yet they behave differently in terms of execution. These action blocks are responsible for generating code dynamically, not executing it right away. When, for example, I call a simple method, it doesn't convert at that moment—rather, it generates the corresponding code to execute later.

00:30:29.100 As a result, utilizing methods and blocks liberally adds flexibility. Initially, I attempted to create versatile methods that could handle multiple tasks, but I discovered it to be more efficient to maintain simple methods that do one thing well, while ensuring ease of debugging.

00:31:39.760 To achieve performance numbers I’ve obtained, I focus on minimizing object creation and method calls. The parsers generated are nearly entirely flat, which boosts performance. Adhering to the principle of staying simple allows the parsing of common structures without overhead.

00:32:19.920 In previous examples, we noted that parsing expressions generates clean, readable code, but care must be taken to ensure efficiency and clarity. This line demonstrates that the numeric characters must return as digits and not fixed ASCII values.

00:34:00.640 I should note that while smaller expressions can be handled easily, the overall capacity for parsing remains high, able to process large streams with ease. For instance, I can handle gigs of inputs and manage memory accordingly without generating unnecessary overhead.

00:36:00.720 Finally, I want to extend my gratitude for the opportunity to share this work with you. As we advance, I am eager to hear from all of you with any questions you may have regarding these concepts or implementations.

00:37:09.280 I would like to thank PeepCode for providing the equipment rental costs.

LoneStarRuby Conf 2008