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

Software Engineering Teaching Meets LLMs

Software Engineering Teaching Meets LLMs Context: On 2023-05-26 I attended the  VERSEN  event  SEN Classrooms (26 May 2023) . (What is VERSEN? I quote from the VERSEN website: VERSEN is " the Dutch National Association for Software Engineering. Its mission is to bring together researchers, educators and practitioners in the field of software engineering ") (I haven't been in Utrecht in a while. It was great to be back. I love the campus and the science park.) My keynote presentation had the title " Software Engineering Career Planning in the Age of AGI+/- ". My slides are available here: [ .pdf ] Loads of relevant content is linked on those slides, but there is probably not much ROI from the slides alone. I want to call out though my DOs and the DON'Ts for teaching adaptation in software engineering. SE Teaching Adaptation — DON’Ts   Don’t ban the use of AI. Don’t ignore the new role of AI. Don’t grade homework likely done by LLM. Don’t aim at outsmarting th
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