[SAOC] "D backend for Bison" thread
adela.vais99 at gmail.com
Wed Sep 9 19:59:45 UTC 2020
My name is Adela Vais, and I am a 4th-year student at the
"Politehnica" University of Bucharest, where I study Computer
I love learning new programming languages and during the Formal
Languages and Automata course I took at university I became
interested in LR theory.
Eduard Stăniloiu and Răzvan Nițu made my introduction to D, at a
workshop that took place during the “Ideas and Projects Workshop”
Summer School 2019, and I found the language interesting because
of its high expressiveness and its fast memory safety feature.
This is why I decided to do this summer an internship at my
university, learning and making contributions to Dlang and GNU
Bison. I consider SAoC a great way to get involved in the D
The project I will pursue during SAoC aims to complete the D
backend for Bison, by creating the GLR Parser for the D language.
Currently, Bison supports only the LALR1 Parser for D. While
simple and fast, this parser has its limitations: it cannot
handle non-deterministic or ambiguous grammars. A GLR Parser
would be able to handle such a grammar, without the constraint of
only one token lookahead.
Combining my love for D, for learning programming languages, and
for LR theory, this project is a tremendous learning opportunity
What I intend to do during SAoC, for each milestone, is:
Milestone 1 - Understand the already existing code
- Analyze the LALR1 D language parser and the C and C++ GLR
- Understand M4 (the language I will partly write the parser in)
by working in the GNU Bison repository, doing smaller tasks
(adding functionalities like lookahead correction, and starting
working at a push parser, which will further my understanding of
the LALR1 D parser).
- Creating (at least) 4 small programs that will make me
understand the differences between the C and C++’s LALR1 and GLR
parsers, using ambiguous and non-ambiguous grammars.
Milestone 2 - Write the GLR support for the D language
- Create the glr.d file. Similar to the C++ code, this parser
will be a class that wraps around the C GLR parser (for easier
- Provide the same interface to that of the LALR1 parser. The
user should not be able to feel any difference on their end. Add
support so that the user is able to provide input from both stdin
and files, and create the Lexer interface that allows the user to
create a class implementing a lexer method, an error reporting
method, and location tracking.
Milestone 3 - Write the GLR support for the D language
- Continue working on the interface. Add the declarations
currently supported by the LALR1 parser: %error-verbose,
%parse-param, %union, %code, %locations, %initial-action.
- Merge the glr.d and lalr1.d files. The two files will likely
end up duplicating a lot of code, so a merge will be needed.
Milestone 4 – Test and write documentation
- Pass all unit tests, fix any bug that appears.
- If the time allows, I plan to integrate this parser in a
project made by a third party, to further test the correctness.
- Write the documentation.
I will post weekly (or biweekly) updates with my progress.
I already made some changes to the existing D language support
and I will continue to do so beyond SAoC, too. I intend to pursue
this project for my undergraduate thesis topic and continue as an
ambassador on behalf of the D community after that.
More information about the Digitalmars-d