Extending Pegged to Parse Another Programming Language
Bastiaan Veelo
May 6 @ 12:00
Duration: 50 minutes
Talk type: Presentation
Level: Intermediate
Code samples
Slides: PDF
Video
Abstract:
Pegged is an elegant library for generating packrat parsers in D. Packrat parsers are parsers for parsing expression grammars (PEGs) that operate in guaranteed linear time through the use of memoization. PEGs are an alternative to context free grammars for formally specifying syntax, and have been gaining in popularity during the last decade. PEG parsers are top-down recursive descent parsers.
The Pegged implementation showcases many features of D, and has come out as a far more elegant product than similar implementations in other languages. Its use is beautifully simple, and its implementation comprehensible to outsiders. Due to D’s powerful template system and compile time function evaluation, it is even possible — within the same source file — to define a simple grammar and some input string, have the compiler generate a parser at compile time, parse the input at compile time and use the result right there at compile time, if you need to. The Pegged project was started by Philippe Sigaud in 2012.
The traditional PEG formalism is very effective for small grammars and new grammar designs, but has some limitations that make it unsuitable for generating parsers for certain existing more complex languages. This talk presents how these limitations were successfully eliminated from Pegged, most notably by implementing discoveries from recent research on left-recursive PEGs. At the same time, this talk is a demonstration that the D programming language and its community are attractive to non-computer scientists. Because the motivation for this effort is not scientific curiosity, but the pragmatic need of a bunch of programming naval architects to translate their extensive design software from an archaic and dying programming language to a language with future; and that language might as well be D.
Speaker Bio:
Bastiaan Veelo came to know about D shortly after it was released some sixteen years ago, while trying to write a flex/bison parser for C++ to pretty-print his code in a literate programming report. He found out the hard way that C++ is a pain to parse, and as D advertised with being developed with fast and easy parsing in mind, it quickly got his attention. Since then, he has been following D’s evolution continuously, without the opportunity to use the language professionally. Recently, he has been investing time to change that and help create that opportunity, which has led him to work on parsers once again — this time in D.
Bastiaan is the lead developer of a specialised program for the computer aided geometric design of ship hulls called Fairway, for the company SARC in the Netherlands. He holds a B.Eng. in naval architecture from the Haarlem Polytechnic, an M.Sc. in marine technology and a Ph.D. in mechanical engineering from NTNU, the Norwegian University of Science and Technology.
