thisContext

putting production rules to work

In a traditional EBNF grammar, production rules describe all the allowed relationships between a language’s terminal symbols. By expressing them as live objects with behavior, they can parse and compile as well. They form a definitive reference network in which to record parsed terminals, making them ideally suited as parse trees. Individual rules also function as search terms in other rules which use them. Epigram is a framework for doing this. Let’s explore these features with an example.

We’ll use the grammar for Smalltalk methods. The production rules are included in the book Smalltalk-80: The Language and Its Implementation by Adele Goldberg and Dave Robson. They are depicted visually, with railroad diagrams (a few of them are shown above).

Each diagram shows a path going through one or more symbols. An EBNF production rule, or grammar symbol, is indicated by the name of the rule in a box. A terminal symbol is indicated by a circle with the symbol inside. An alternation is indicated by a path’s divergence through multiple symbols, converging afterward. A compound rule is indicated by a path going directly through multiple symbols. A repetition is indicated by a loop through a sequence of symbols, representing one or more occurrences of that sequence. EBNF also supports the option, which is no or one occurrence of a symbol, and the difference, which matches one rule but not another. These kinds of rules are sufficient for the Smalltalk grammar. There are other grammars, like XML, that extend BNF further, but we won’t discuss them here.

production rules as code

We can express these diagrams as code. For a terminal symbol, we can use a literal string. For an alternation, we can use a “|” (“or”) operator. For a compound rule, we can use a “||” (“then”) operator (after changing the Smalltalk compiler so that it doesn’t confuse “||” with “|”). For repetitions and options, we can use the unary messages “repetition” and “option”. We can store entire production rules as shared variables (pool variables in Squeak).

For example, we can write the first diagram as:

Digit := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'.

Digit is an instance of class Alternation, and can be a variable in a SmalltalkProductionRules pool. We can write the second diagram as:

Digits := Digit repetition.

Digits is an instance of class Repetition. A rule which uses a compound rule is:

SymbolConstant := '#' || Symbol.

We can write each rule in this way, culminating with Method.

parsing

Once we’ve created all the rules for our grammar, we can ask the topmost rule, Method, to parse the source code of a method. To parse, a rule creates a stream on the proposed content, and attempts to accept the next character in the stream until the stream is empty. For example, a terminal symbol for ‘3’ will accept the next character if it is $3.

A symbol which consists of other symbols will delegate parsing to those symbols. An alternation between the terminal symbols for ‘3’ and ‘4’ will accept the next character if it is $3 or $4, but it decides this by delegating the parse to each of those symbols, and noting which of them was able to accept the next character. A symbol’s parse succeeds if it is able to accept enough characters to match every character in its string, if it’s a terminal symbol, or a sufficient set of subsymbols, if it’s a compound rule, alternation or repetition.

If a symbol doesn’t succeed, it fails and resets the stream’s position as it was before parsing began. Control is returned to the delegating symbol. This is called backtracking. If the overall parse backtracks all the way to the topmost rule without having emptied the stream, and the next character is unacceptable, then the entire parse fails and the content is ungrammatical. Having reached this point, however, we have information about which rules failed and how far the parse got in the stream. This is useful information to present to the user, with an exception.

The complexity of a grammar can make backtracking very expensive in time; reducing this cost is the main challenge in Epigram development currently. Informed choices of alternation orders in a grammar (as with a parsing expression grammar) and primitives (described below) yield dramatic performance increases.

compilation

If a parse is successful. We are left with a graph of successful production rules, each with a record of the characters it accepted, and its successful constituent symbols. We can use this graph as we would have used a traditional parse tree. Compilers can use the parse graph to create objects representing the source content in a useful structure. For example, we can create a CompiledMethod of Smalltalk virtual machine instructions, embodying the behavior specified by the source code.

For example, if our source code were:

The successful rules in our parse, in chronological order, would be:

• Letter ($a)
• Letter ($d)
• Letter ($d) — further Letter successes are elided.
• Identifier (‘add’)
• UnarySelector (‘add’)
• MessagePattern (‘add’)
• SpecialCharacter (carriage return)
• SpecialCharacter (tab)
• Comment (‘”Add two numbers and answer the result.”‘)
• Digit ($3)
• Number (‘3’)
• Literal (‘3’)
• SpecialCharacter ($+)
• BinarySelector (‘+’)
• Literal (‘4’)
• BinaryExpression (‘3 + 4’)
• MessageExpression (‘3 + 4’)
• Expression (‘3 + 4’)
• Statements (‘3 + 4’)
• Method (‘add “…” ^3 + 4’)

To get the intended method selector (#add), a compiler holding this parse history can simply ask the Method rule for its MessagePattern. The compiler can also ask the Expression to generate the Smalltalk stack machine instructions that carry it out.

searching

Since MessagePattern is a well-known shared variable in the SmalltalkProductionRules pool, the compiler can use it as a search term in queries to Method:

selector := (Method at: MessagePattern) terminals

Using production rules as search terms is a very useful way of navigating the grammatical structure of the parse tree, allowing the compiler writer to apply their knowledge of the grammar. Rather than focusing on how parsing works, or how to manipulate a parse tree which is separate from the grammar, one may express compilation entirely with the grammar’s rules.

performance optimization: primitives

It’s very convenient and clear to express a grammar as EBNF rules, but it can lead to alternations between many options, with expensive parsing behavior. Since the grammar keeps a complete history of the accepted rules for a parse, we can easily see which rules are most popular and consume the most time. For these rules, we can specify Smalltalk code equivalent to their parsing work, providing primitives. For XML, which has frequently-used alternations between thousands of Unicode characters, primitives provide speedups of 200 times or more.

enforcing constraints

Some grammars specify additional constraints on parsed content. For example, the HTML grammar requires an element’s opening and closing tags to match. Epigram supports adding constraints to production rules, in the form of block closures which must evaluate to true after parsing has taken place.

resolving ambiguities

Some grammars include points of intentional ambiguity. In Smalltalk, for example, there’s a grammatical ambiguity between chains of unary and binary messages. Epigram supports noting ambiguities, and resolving them through constraints. In the Smalltalk example, the ambiguity is resolved through constraint considering the scope in which parsing occurs. Which variable names are currently bound, and which unary and binary messages are actually defined, lead to a single interpretation.

decompilation

Writing a Smalltalk decompiler with reified production rules is also easier. The rule for a method declaration can dispatch decompilation for each bytecode to the corresponding instruction class, resulting in a set of equivalent instruction instances. An instruction which pops the virtual machine stack corresponds to a Smalltalk statement, and it can construct a structure of production rules equivalent to that statement, as if created from a parse. The rule structure can answer terminal symbols which are the equivalent source code. I’m writing an extended example of this decompilation process, as an Observable active essay with a live Caffeine session embedded inside it.

special thanks

Special thanks to Chris Thorgrimsson and Lam Research, for supporting this open-source work through commercial use cases.

This entry was posted on 28 June 2022 at 4:23 am and is filed under Appsterdam, Caffeine, consulting, Context, livecoding, Smalltalk, SqueakJS, Uncategorized with tags compiler, decompiler, JavaScript, livecoding, parsing, smalltalk, squeak. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.