Language processing for dummies

I enjoyed reading recently "Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages" by Terence Parr (the ANTLR guy) as available from The Pragmatic Bookshelf. The book uses a design pattern style to present techniques for language processing. Eventually the book gets to leverage ANTLR for many problems, but it also explains language processing in terms of patterns that require regular programming effort without the help of a program generator. This is a clever way of teaching some basics of grammars, parsing, tree walking and other concepts that can be explained all too easily (elsewhere) in a too complicated manner, or in a manner requiring substantial background.

In my (very) advanced Bachelor's course Programming techniques and technologies, I face students who don't know much yet about formal languages and certainly nothing about compiler construction; they are aware though of context-free grammars (EBNFs) for the purpose of syntax definition. The course covers many programming techniques and technologies, and I am willing to dedicate two lectures to language processing. Hence, I designed patterns that are really simple and that allow me to discuss a number of language processors for 101companies in a systematic manner.

"Manual" patterns
  • The Chopper Pattern: Chop input into pieces for classification and iterator-based processing.
  • The Lexer Pattern: Transform character stream into token stream for iterator-based processing.
  • The Copy/Replace Pattern: Implement text transformation by copying tokens from input to output while replacing tokens of interest.
  • The Acceptor Pattern: Implement a context-free grammar with procedures for parsing input and signaling acceptance or rejection.
  • The Parser Pattern: Advance the Acceptor Pattern such that semantic actions are to be executed along with parsing input.

"Generative" patterns
  • The Lexer Generation Pattern: Use a lexer/parser generator to derive a character-to-token stream conversion from a grammar generatively.
  • The Acceptor Generation Pattern: Use a parser generator to derive an acceptor from a grammar generatively.
  • The Parser Generation Pattern: Use a parser generator to derive an parser from a grammar with associated semantic actions generatively.
  • The Text-to-object Pattern: Instantiate the Parser (Generation) Pattern such that the semantic actions construct objects that resemble the syntactical structure of the input.
  • The Object-to-text Pattern: Implement an operation on an object model that writes out the object graph in the underlying textual notation.

Associated 101companies implementations

Slide decks (.pdf): [1]. [2]

Lecture videos (.mov): [1]. [2]

Regards,
PF

Comments

Post a Comment

Popular posts from this blog

SWI-Prolog's Java Interface JPL

I would like to mix Java and Prolog code on a number of occasions. Together with a student of mine (Joachim Pehl), we just convinced ourselves that the JPL library of SWI-Prolog is really cool. Basically JPL allows you to call Prolog from Java and Java from Prolog. But the question is, of course, how easy is it and can you easily go back and forth . For instance, can we call Prolog from Java and call back Java from Prolog and share Java state throughout? Sure it works! PROLOG PORTION FOLLOWS % This library is all we need to call Java from Prolog :- ensure_loaded(library(jpl)). main :- % Create an object jpl_new(class([],['Test']), [], X), % Printing objects is like printing object ids write(X),nl, % Access a field of the object; happens to be static jpl_get(X, state, Y), % Prints whatever the state's value is write(Y),nl. JAVA PORTION FOLLOWS // This jar is all we need to call Prolog from Java import jpl.*; public class Test { public static int state = 0;
Read more

Lecture series on advanced (functional) programming concepts

[ Added 10 Aug 2010: Here is the link to the first lecture's video: " The Expression Problem ". ] If you are a programming nerd or something of a similar species, you may know of C9 Lectures at http://channel9.msdn.com/tags/C9+Lectures . Several of the lectures are given by Erik Meijer who has turned many chapters of Graham Hutton 's book " Programming in Haskell " into videos. In my recent, recorded lecture on " Programming Paradigms and Formal Semantics ", I also incorporated Graham's text, but you should really watch Erik's lectures, if you haven't---they are more fun. I am inspired by his ability to present relatively simple content in such a crisp, insightful, and enjoyable manner. In the aforementioned lecture, I covered all kinds of "crazy stuff" though, and in the end, I had to deliver body bags to my Bachelor students---in the form of a radically simple examination. Thanks a lot btw to @grammarware for helping with t
Read more

Should I declare defeat on the research topic of API migration?

Of course, I won't, but perhaps I should! Then, I could turn to lower-hanging fruits in research, which I first need to spot, which I can't though because I am a bit obsessed with API migration (and admittedly some other stuff such as megamodeling ). Sigh! It was around 2004 that I became interested in API migration and I have talked about it here and there ever since. Perhaps I am thinking that talking about a difficult problem of interest helps in discovering the solution of the problem, or at least a sensible path to go. Wishful thinking so far! In theory , the objective of API migration made a lot of sense while I was on the XML team at Microsoft because there are obviously way too many XML APIs. In practice , nothing happened on this front because I didn't understand automated API migration well enough back then. Add to this that API migration is something that is potentially risky for the API provider and the API migrator . So you need to mash up a rocket scientist
Read more