Parser Upgrade

The Generator has gotten a parser upgrade. The parser, part of qooxdoo’s tool chain, transforms the JavaScript of the class code, both of the framework as well as the application classes and any additional contribution, into a tree structure, the syntax tree. This syntax tree is then the basis for many follow-up actions that are related to creating a running application, like the dependency analysis, optimizations, and compression. The api-data generation, part of the Apiviewer, and the pretty-printing feature are based on syntax trees as well.

The traditional parser in qooxdoo was a hand-written recursive-descent parser. It had several issues, was unwieldy and hard to maintain. The syntax tree it created was rather idiosyncratic, sometimes  inconsistent and even semantically wrong. Particularly, it did not correctly represent precedence in complex expressions. This impeded further optimization of code parts that could have otherwise been reduced. It was difficult to oversee the effect of changes while fixing bugs or adding new features.

The new parser is based on an algorithm called top-down operator precedence parsing, or Pratt parsing.  The latter refers to Vaughn Pratt who conceived the algorithm in the ’70s. More recently, Douglas Crockford has made it popular in the JavaScript community (basing his JSlint code on it), and Fredrik Lundh picked it up for the Python realm. Based on this algorithm, the new parser constructs a slightly sanitized syntax tree with correct precedences, and is supposed to be faster than simple recursive-descent parsers that achieve the same (as it uses less stack depth). We also hope that it will be more maintainable, and more amenable for new features.

The new parser is now deployed for the “compile pipeline”, where it is used for dependency analysis, optimization and compression. The old parser is still in use for  the “api-data” and “pretty-print pipelines” which are less critical. Those will be addressed in future steps.

Comments are closed.