On 2011-03-23 00:27:51 +0200, Ilya Pupatenko said:
Hi,
First of all, I want to be polite so I have to introduce myself (you
can skip this paragraph if you feel tired of newcomer-students’ posts).
My name is Ilya, I’m a Master student of IT department of Novosibirsk
State University (Novosibirsk, Russia). In Soviet period Novosibirsk
became on of the most important science center in the country and now
there are very close relations between University and Academy of
Science. That’s why it’s difficult and very interesting to study here.
But I’m not planning to study or work this summer, so I’ll be able to
work (nearly) full time on GSoC project. My primary specialization is
seismic tomography inverse problems, but I’m also interested in
programming language implementation and compilation theory. I have good
knowledge of C++ and C# languages and “intermediate” knowledge of D
language, knowledge of compilation theory, some experience in
implementing lexers, parsers and translators, basic knowledge of
lex/yacc/antlr and some knowledge of Boost.Spirit library. I’m not an
expert in D now, but I willing to learn and to solve difficult tasks,
that’s why I decided to apply on the GSoC.
I’m still working on my proposal (on task “Lexing and Parsing”), but I
want to write some general ideas and ask some questions.
1. It is said that “it is possible to write a highly-integrated
lexer/perser generator in D without resorting to additional tools”. As
I understand, the library should allow programmer to write grammar
directly in D (ideally, the syntax should be somehow similar to EBNF)
and the resulting parser will be generated by D compiler while
compiling the program. This method allows integration of parsing in D
code; it can make code simpler and even sometimes more efficient.
There is a library for C++ (named Boost.Spirit) that follows the same
idea. It provide (probably not ideal but very nice) “EBNF-like” syntax
to write a grammar, it’s quite powerful, fast and flexible. There are
three parts in this library (actually there are 4 parts but we’re not
interested in Spirit.Classic now):
• Spirit.Qi (parser library that allows to build recursive descent parsers);
• Spirit.Karma (generator library);
• Spirit.Lex (library usable to create tokenizers).
The Spirit library uses “C++ template black magic” heavily (for
example, via Boost.Fusion). But D has greater metaprogramming
abilities, so it is possible to implement the same functionality in
easier and “clean” way.
So, the question is: is it a good idea if at least parser library
architecture will be somewhat similar to Spirit one? Of course it is
not about “blind” copying; but creating architecture for such a big
system completely from scratch is quite difficult indeed. If to be
exact, I like an idea of parser attributes, I like the way semantic
actions are described, and the “auto-rules” seems really useful.
2. Boost.Spirit is really large and complicated library. And I doubt
that it is possible to implement library of comparable level in three
months. That’s why it is extremely important to have a plan (which
features should be implemented and how much time will it take). I’m
still working on it but I have some preliminary questions.
Should I have a library that is proposed and accepted in Phobos before
the end of GSoC? Or there is no such strict timeframe and I can propose
a library when all features I want to see are implemented and tested
well?
And another question. Is it ok to concentrate first on parser library
and then “move” to other parts? Of course I can choose another part to
start work on, but it seems to me that parser is most useful and
interesting part.
3. Finally, what will be next. I’ll try to make a plan (which parts
should be implemented and when). Then I guess I need to describe the
proposed architecture in more details, and probably provide some usage
examples(?). Is it ok, if I publish ideas there to get reviews?
Anyway, I’ll need some time to work on it.
Ilya.
P.S. The funny thing is that I found minor bug in Phobos (#5736) while
trying (just for fun) to implement some tiny part of Spirit in D.
Submitting bugs seems to be important part of the task too.
Mimicking spirit might not be a good idea. It looks sort of like BNF
grammar, but because of operator abuse, there is just so many noise.
A better idea might be using D compile time function evaluation to
parse strings with grammars
