{"id":157,"date":"2016-11-16T01:01:07","date_gmt":"2016-11-16T01:01:07","guid":{"rendered":"http:\/\/www.onux.com\/jspp\/blog\/?p=157"},"modified":"2021-12-27T01:22:58","modified_gmt":"2021-12-27T01:22:58","slug":"glr-parsing-and-disambiguation","status":"publish","type":"post","link":"https:\/\/www.onux.com\/jspp\/blog\/glr-parsing-and-disambiguation\/","title":{"rendered":"Compiler Architecture: GLR Parsing and Disambiguation"},"content":{"rendered":"

Today I want to talk about GLR parsing and the internals of the JS++ parser.<\/p>\n

The Problem<\/h3>\n

In JS++, there is the potential for code to be “ambiguous”. For instance, consider the following example:<\/p>\n

\r\nFoo<bar> baz;\r\n<\/pre>\n
There are two interpretations for the above statement:<\/p>\n
1. A comparison operation: Foo<\/code> is less than bar<\/code> is greater than baz<\/code>.
\n2. A variable declaration with type Foo<bar><\/code> (where Foo<\/code> is a generic type with type argument bar<\/code>)<\/p>\n
Since JS++ is a superset of the JavaScript programming language, we would naturally expect the first case since JS++ inherited this from JavaScript. However, in order to achieve a concise syntax for generic types, we also need to consider how we can enable the second case.<\/p>\n
<\/p>\n
The Language Design and Why It Matters<\/h3>\n
Other JavaScript supersets use an ActionScript-like syntax:<\/p>\n
\r\nvar baz : Foo<bar>;\r\n<\/pre>\n
I have mentioned in the past<\/a> that JavaScript supersets have a preference for this syntax because it is easier to parse. However, I never specified why. I also have a certain disdain for this syntax because it involves more typing. var<\/code> is unnecessary and redundant. You also have to unnecessarily reach for the shift key to type a colon. In C-style languages (where JavaScript inherits its syntactic style), variables are traditionally declared with their type. Compare the “colon syntax” with JS++ which uses a more traditional C-style syntax:<\/p>\n
\r\nvar foo : string = \"abc\"; \/\/ Other languages\r\nstring foo = \"abc\";         \/\/ JS++\r\n<\/pre>\n
In JS++, you type less and there’s no need to reach for the shift key to declare variables. It might seem like a trivial matter, but variable declarations will be used so many times throughout a program that it’s critical to get this detail right. It shows we cared when we designed JS++. The “colon syntax” has the benefit of not creating ambiguity; the drawback is that it degrades the developer experience.<\/p>\n
In a nutshell: the colon syntax is easier for the compiler writers and harder for the developers, and the traditional C syntax is harder for the compiler writers and easier for the developers.<\/p>\n
Basic Disambiguation<\/h3>\n
We can achieve basic disambiguation with the following rule: If Foo<\/code> is declared as a generic class, we have a variable declaration; otherwise, we have a comparison operation.<\/p>\n
Variable Declaration<\/strong><\/p>\n
\r\nclass Foo<T> {}\r\nFoo<bar> baz;\r\n<\/pre>\n
Comparison Expressions<\/strong><\/p>\n
\r\nFoo<bar> baz;\r\n<\/pre>\n
Notice the only difference between the two snippets is the presence of a generic class declaration. We use a symbol table (built during parse time) to determine whether Foo<\/code> is a generic class. Furthermore, we use “unlimited lookahead” to determine if there is a need for disambiguation. Given these complexities, it should naturally follow that such a grammar cannot be achieved with parser generators like yacc\/bison, which only support LL(1) and LALR(1) (one-token lookahead) context-free<\/em> grammars.<\/p>\n
However, this strategy has a drawback: it only works if the class was declared locally in the same file.<\/p>\n
Imports and Cycles<\/h3>\n
JS++ is a multi-file, modular language. Therefore, a generic class can be declared in another file. It might seem<\/em> like the solution would be obvious: build a symbol table for each individual file and import the symbol tables.<\/p>\n
However, JS++ is tricky — not least because its intricate import system but because it allows cyclic imports<\/em>. If a file A.jspp depends on B.jspp, and B.jspp in turn depends on A.jspp, how will we determine which to import first? Furthermore, we are faced with a troubling dilemma: if a generic class was declared in one of the dependencies, how do we parse? It means Foo<bar> baz;<\/code> would be completely ambiguous.<\/p>\n
In JS++, the user is not<\/strong> required to specify an import order; the compiler will figure out the order to process the input files by itself; unfortunately, this import order can only be figured out after<\/em> the input files have been parsed (because JS++ imports based on identifiers and not file paths).<\/p>\n
This was almost the straw that broke the camel’s back.<\/p>\n
Disambiguation with GLR Parsing<\/h3>\n
To solve our problem, we introduced GLR parsing. When faced with an ambiguous parse (is it generic or is it a comparison?), we parse both… but only if it’s ambiguous.<\/p>\n
No, we do not parse the file twice with both interpretations. We simply parse the specific expression or statement under both interpretations. Additionally, we only parse both interpretations if it’s ambiguous. It’s not always ambiguous because the symbol might be defined locally and we’ll know we have a generic rather than a comparison right away.<\/p>\n
In a post-processing step (after all files have been parsed and all symbol tables have been built), we can disambiguate whether it’s a variable declaration or a comparison expression. For parsers that build the symbol table during parsing, it may not be possible to “complete” the symbol table until the post-processing step. This is because it’s not possible to determine if c<\/code> in a<b> c<\/code> should be added to the symbol table until disambiguation occurs.<\/p>\n
Advantages and Disadvantages<\/h3>\n
To ensure we design correctly before beginning implementation, we have consultants that review our architecture and designs. The consultants we hire typically have a PhD in computer science, and the particular consultant that we discussed this with is a contributor to the gcc compiler. He described several pros and cons for GLR parsing:<\/p>\n
Advantages<\/strong><\/p>\n