On Tue, 22 Mar 2011 18:27:51 -0400, Ilya Pupatenko
<pupate...@gmail.com> wrote:
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.
I'm not qualified to speak on Spirits internal architecture; I've only
used it
once for something very simple and ran into a one-liner bug which
remains
unfixed 7+ years later. But the basic API of Spirit would be wrong for
D. “it
is possible to write a highly-integrated lexer/perser generator in D
without
resorting to additional tools” does not mean "the library should allow
programmer to write grammar directly in D (ideally, the syntax should be
somehow similar to EBNF)" it means that the library should allow you to
write a
grammar in EBNF and then through a combination of templates, string
mixins and
compile-time function evaluation generate the appropriate (hopefully
optimal)
parser. D's compile-time programming abilities are strong enough to do
the code
generation job usually left to separate tools. Ultimately a user of the
library
should be able to declare a parser something like this:
// Declare a parser for Wikipedia's EBNF sample language
Parser!`
(* a simple program syntax in EBNF − Wikipedia *)
program = 'PROGRAM' , white space , identifier , white space ,
'BEGIN' , white space ,
{ assignment , ";" , white space } ,
'END.' ;
identifier = alphabetic character , { alphabetic character | digit } ;
number = [ "-" ] , digit , { digit } ;
string = '"' , { all characters − '"' } , '"' ;
assignment = identifier , ":=" , ( number | identifier | string ) ;
alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G"
| "H" | "I" | "J" | "K" | "L" | "M" | "N"
| "O" | "P" | "Q" | "R" | "S" | "T" | "U"
| "V" | "W" | "X" | "Y" | "Z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
white space = ? white space characters ? ;
all characters = ? all visible characters ? ;
` wikiLangParser;
