Jeffrey Kegler

Yale University, New Haven CT

• Lecturer, Yale Medical School, 1979 to 1981
• M.S., Computer Science, 1978
• B.A., Administrative Science, 1975

MarpaFounder and project leader, 2007 to present

Marpa is an efficient general BNF parser, based on Aycock and Horspool's and Joop Leo's modifications of the Earley algorithm. Marpa parses any language whose grammar can be written in BNF. That includes recursive grammars, ambiguous grammars, infinitely ambiguous grammars and grammars with useless or empty productions. Marpa does both left- and right-recursion in linear time -- if a grammar is in any class currently in practical use, Marpa will parse it in linear time.

Marpa::R2 is the latest CPAN release of the Perl version of the Marpa parsing algorithm.

• Marpa::R2 is Debian stable as of jessie.
• Marpa::R2 is in use at several major corporations, including IBM, which called it "an advanced high speed parsing/lexing system".
• Several videos are available online about Marpa:
  • A 2017 talk given in Amsterdam by Lars Dieckow. This was a "shoot-out" among parser generators -- Marpa was declared the winner. Video online.
  • A 2016 talk about Karel, a Marpa-driven game given by E. Choroba in Romania. Video online.
  • The FLOSS Weekly 321 videocast (2015). Video online.
  • A 2015 talk by Dr. Stephen Flitman in Phoenix. Video online.
  • A 2015 talk in Russian by Ruslan Zakirov in Moscow. Video online.
  • Talks about Marpa-driven parsing of the conlang Toki Pona, given by Maxim Vuets in 2015 at the Swiss Perl Workshop in Flörli Olten; the London Perl Workshop; and to the AmsterdamX Perl Mongers. Videos are online of both the Amsterdam and the London talks.
  • A 2014 talk by Jose Luis Perez Diez in Barcelona.
  • Talks by Andrew Rodland at Perl Oasis 2013 and at YAPC:NA in 2014, both in Orlando. A Video of the 2014 is online.
• Perl's own documentation suggests Marpa::R2 (perlfaq4)
• University courses with suggested Marpa readings have included the CS652 2014S at the University of San Franscisco and CS842 Fall 2013 at the University of Waterloo.
• Marpa is cited in
  • Ian Henriksen, Gianfranco Bilardi, and Keshav Pingali. "Derivative grammars: a symbolic approach to parsing with derivatives." Proc. ACM Program. Lang. 3, OOPSLA, Article 127 (October 2019). Available online.
  • Obua, Steven, Phil Scott, and Jacques Fleuriot. "Local Lexing." arXiv preprint arXiv:1702.03277 (2017). Available online.
  • Toloaca, Ion, and Michael Kohlhase. "Notation-based Semantification." FM4M/MathUI/ThEdu/DP/WIP@ CIKM. 2016. Available online.
  • Konitzer, Marius. Laufzeitanalyse und Optimierung von Parsern für LR-reguläre Grammatiken. Diss. Ph. D. thesis, Ruhr-University Bochum, 2013. Available online.
  • Ginev, Deyan, and Bruce R. Miller. "LATEXml 2012-a year of LATEXml." International Conference on Intelligent Computer Mathematics. Springer, Berlin, Heidelberg, 2013. Available online.
  • Simões, Alberto, Nuno Carvalho, and José João Almeida. "Generating flex lexical scanners for perl parse:: Yapp." 1st Symposium on Languages, Applications and Technologies. Vol. 21. Schloss Dagstuhl–Leibniz-Zentrum für Informatik GmbH, 2012. Available online.
• My own writings about Marpa have been translated into Russian, Japanese and Korean.
• Marpa has a large, active user community, whose members maintain a web site, a mailing list, and an IRC channel (#marpa at freenode.net).
• Marpa::R2 is open source and available on CPAN and Github.

"Parsing: a timeline"

A summary of the history of Parsing Theory. This piece proved very popular, getting over 10,000 views in a 48 hour period, which is a stunning number for mathematical web page with no illustrations. (The Russian translation did add a picture.)

"What is the Marpa algorithm?"

This piece is a very short, very high-level overview of the theory behind Marpa.

"Marpa, a practical general parser: the recognizer"March 2012

This paper contains the details of the theory behind the recognizer portion of the Marpa algorithm, including proofs of correctness, and of the complexity claims.

"Perl and Undecidability"Spring to Fall, 2008

A three part series published in The Perl Review:

• "The Halting Problem", Volume 4, Issue 2, Spring 2008, pp. 21-25;
• "Rice's Theorem", Volume 4, Issue 3, Summer 2008, pp. 23-29; and
• "Perl Is Undecidable", Volume 5, Issue 0, Fall 2008, pp. 7-11.

According to Wikipedia's "Programming Languages" article, these contain the first proof of undecidability for the syntax of a programming language.

The God Proof2007

A novel based on Kurt Gödel's ontological proof of the existence of God, available at Amazon or as a free download

Thirty books in the Dollars and Cents of Shopping Centers series

(As co-author with the Urban Land Institute.) The books I co-authored with are in the studies for years 1990, 1993, 1995, 1997 and 1998.

"A Polynomial Time Generator for Minimal Perfect Hash Functions"

This paper appeared in Communications of the ACM, vol. 29, no. 6, pp. 556-557, 1986.

Applied Materials Senior Sysadmin, 2005 to 2007

• Translated requirements from Accounting and Security into operator-actionable procedures,
• obtained sign-off from Accounting and Security that they in fact regarded adherence to these procedures as SOX compliance, and
• tracked and coordinated follow-through of the procedures.

Sun MicrosystemsIT Consultant, 1997 to 2001

• Engagement Architecture:
  • In Sun's small Custom Engineering group, sorted and routed raw leads.
  • On the productive leads, determined the customer's requirements, and from these established scope, customer responsibilities, deliverables, acceptance criteria and level of effort.
  • Explained and sold these and the resulting price to the customer and closed the deal.
  • Carried out many of the engagements, with Sun billing the work on an hourly basis.
• Solaris Device Driver Development:
  • Custom Engineering team's technical lead, with a specialty in device drivers and streams modules.
  • Wrote device driver for Quatech and another on internal project for Sun.
  • Other clients wrote the software themselves, calling on me when they had questions or hit difficulties. These ``technical assistance'' clients included Lockheed Martin, General Dynamics, Integrated Telecom Solutions, and Lucent.
• Solaris Systems Software Development:
  • Wrote Solaris systems software for the Idaho State Lottery, Motorola, Telefonica and Colegio de Registradores (the last two in Spain).
  • Provided technical assistance on the writing of systems software to Riolabs, TCSI and IBM.
• Performed a C++ compiler enhancement for Silicon Metrics.
• Provided technical assistance on application software to Urban Land Institute.

Algorists, Inc.President and Owner, 1984 to 1998

• Technical Sales: For Algorists' entire history, full responsibility for sales cycle.
• Management: At various times, responsible for management of other consultants. These included partners within Algorists, and consultants hired by Algorists or its clients.
• Email Server Development: For Sun Microsystems, developed a large distributed email server using sendmail and wrappers written in C.
• UNIX Device Driver Development: Developed device drivers for clients ICL Datachecker, SCOPE, NOVA, Contel, KSE and ACS.
• UNIX Systems Programming: UNIX systems programming for clients Hewlett Packard, Applied Materials, ICL Datachecker, ITM, Telenet and AT\&T. Also for HP, HP/UX internals.
• For Sun Microsystems, diagnosed network throughput issues, and installed firewalls.
• Developed firmware for ICL Datachecker and SAIC.
• Developed application and database software for Urban Land Institute, Kendrick and Company, the National Association of Realtors and TYX.
• Consulted at the Federal Aviation Administration.