Introduction

APaGeD stands for Attributed Parser Generator for D. It let's you write easy-to-read grammars and integrate semantic code for syntax tree traversal right with the syntactical rules.

Although it can generate GLR as well as LL parsers, the emphasis is now on the GLR parsers. This is mainly because they allow more flexible grammars, they have better performance and they provide good error handling with little effort. On the other hand, APaGeD does a lot to tackle the most stated disadvantage of LR parsers, which is the difficulty of debugging them.

This has come to a point where I feel, that debugging the LR parsers can even be easier than debugging an LL parser, because there is more, but not too much information available to analyze the situation. Of course, you need to understand how LR parsers work in order to be able to effectively debug them. And LR parsers are more difficult to understand.

Here is an overview of the features:

• Generates LL and LR parsers

  The LL parsers are backtracking top-down parsers with arbitrary lookahead. The LR parsers are generic LR (GLR) parsers based on LALR(1) tables.

• Supports non-regular whitespace

  For convenience, you can define whitespace separately from your grammar, such that you don't have to mention whitespace all over your rules. Many parser generators let you define whitespace only as a regular expression, though, effectively prohibiting nested comments, for example. APaGeD uses a secondary grammar to define whitespace, giving you maximum flexibility.

• Includes a linear-time lexical analyzer based on regular expressions using tagged DFAs

  Most lexical analyzers use backtracking to find the first longest match, which has a worst-case runtime that is exponential in the length of the input.

• Full multi-pass semantical analysis

  Most parser generators allow you to write actions that are executed whenever a non-terminal symbol is expanded (or reduced). Some let you return values from such an action, effectively enabling semantic analysis of s-attributed grammars (only synthetic attributes).

  APaGeD gives you full control of the semantic analysis phase, letting you evaluate all non-cyclic attributed grammars. It does so by letting you choose the order in which the non-terminals on the right-hand side of a rule get evaluated on a per-rule basis.

• Syntax is strongly oriented at curly-brace languages and makes grammar files look like an intuitive extension to plain D code

• Imports for grammar files

• Error recovery

• Automatically generated error messages

Unlike many other parser generators that allow semantic actions, APaGeD parses the input completely before applying any semantic code. That is a limitation, because you cannot change the parse tree depending on semantics. APaGeD follows D's philosophy of a strict separation of syntax and semantics here. It is generally favorable to have that separation, as it makes dealing with the grammar significantly easier and faster.