D Backend for Bison

[edi33416]

Description

GNU Bison is a general-purpose parser generator that converts an annotated context-free grammar into a deterministic LR or generalized LR (GLR) parser employing LALR(1) parser tables. Bison can also generate IELR(1) or canonical LR(1) parser tables. Generalized LR (GLR) parsers allow to analyze ambiguous (or locally ambiguous) languages by splitting the parser to follow several parses simultaneously, in a memory-efficient way.

Compared to other LR parser generators, Bison provides an extensive range of features, such as location tracking, rich and internationalizable and customizable syntax error messages, reentrant parsers, push parsers (with autocompletion), named references, reports (graphical, XML) on the generated parser, and support for several programming languages (C, C++, Java). D support was recently added, but only as an experimental feature.

What are rough milestones of this project?

The short-term goal of this project is to complete Bison's D backend.

To this end, there's a number of steps to follow.

1. First, the existing backend must be audited to assess whether the generated parser and the interface are idiomatic D.
2. Second, the documentation must be written, and existing tests should be improved.
3. Finally, D should catch up with existing features implemented in other backends. This ranges from simple features (customized error messages, look-ahead correction, push parser interface, autocompletion, ...) up to the much more ambitious implementation of GLR support.

You are strongly recommended to extend the existing example of a D parser in Bison to show the new features, similarly to what the Bistromathic example does for C. However, using Bison's D support in a real world project would also be a very nice means to ensure that the D backend works properly (not just correction, but the API).

The long-term goal is to have a committed support of the D community for Bison. The project is looking for an ambassador who would listen to the concerns of the D community and consequently improve the backend. Someone who will also update the backend when new features are added to Bison.

How does this project help the D community?

Bison support for D.

Recommended skills

• R parsing theory
• C for the implementation of bison, D for the backend
• Knowing M4, using to implement backends, would be a bonus. Existing backends (C, C++ and Java) are good sources of inspiration, so knowing C, C++ and Java is useful.
• Grit and perseverance

(If applicable, e.g. GSoC/SAoC)

What can students expect to get out of doing this project?

An understanding of how LR and GLR parsers work.

Point of Contact

@akimd, @edi33416, @RazvanN7

References

<NG discussions, GitHub PRs, Bugzilla issues, ...>

https://forum.dlang.org/thread/valuirejusffuhwfkucj@forum.dlang.org https://forum.dlang.org/thread/fjuvegjdvcunqqvvbdbi@forum.dlang.org https://forum.dlang.org/thread/1c3d8e77-ce4c-6310-0afd-e6518728299f@erdani.org

[Geod24]

CC @ibuclaw

[mdparker]

This was implemented for SAoC 2020.

[RazvanN7]

@edi33416 Could you please provide some links to the implementations?

[edi33416]

@adelavais Could you please provide some links and details?

[adelavais]

Hello!

The D backend will be officially available starting with the next major release. At the moment, the LALR(1) parser is available on the master branch (unofficial repo on GitHub [0]; official repo on savannah.gnu [1]; as far as I am concerned they are mirrors, as the GitHub repo belongs to Akim Demaille, one of Bison's comaintainers).

There are examples [2] on how to use it, and documentation [3].

Some important features supported by the LALR(1) D backend:

• location tracking
• error messages (simple, detailed, custom)
• internationalisation
• lookahead correction
• "pull", "push" and "both" parser options
• token constructors
• reset of the error recovery counter (yyerrok)
• a unified lexer return value (the Symbol struct, which binds together the TokenKind, the value, and the location)

You can find out more about these features in the manual [3] and on my SAOC2020 posts [4].

If you want to use the D backend at the moment, I recommend cloning the repo and then running:

sudo apt-get install \
  autoconf automake autopoint flex gperf graphviz help2man texinfo valgrind
git submodule update --init && ./bootstrap && ./configure && make

More details here [5].

[0] https://github.com/akimd/bison [1] https://git.savannah.gnu.org/cgit/bison.git [2] https://github.com/akimd/bison/tree/master/examples/d [3] https://github.com/akimd/bison/tree/master/doc [4] https://forum.dlang.org/thread/pveavaoydgqaciokfwnv@forum.dlang.org?page=1 [5] https://github.com/akimd/bison/blob/master/README-hacking.md