headerphoto

About Me

• 30+ years of programming experience
• C, C++, PHP, Java, JavaScript
• database front ends, telecom protocols, web development and more
• author of APG – a pet project since 2005
• author of apg-exp – a powerful new pattern-matching engine
• expert at developing SABNF grammars for data formats
• expert at writing parsers and translators for said data formats
• still actively developing
• still available for freelance work


Feel free to send me an email.

Lowell D. Thomas


Copyrights

APG was orginially developed under the auspices of Coast to Coast Research, Inc., a Florida Corporation which has now been dissolved. All copyrights to all versions of APG, past and present, have been assigned to Lowell D. Thomas.

A Short History of APG

Motivation: Here is the way I put it in the introduction to version 1.0:

"Around 1993, when the Internet was really taking off and HTML was hot, I tried to write an SGML parser. I learned two important things from that project - a) compiler writers are among the best programmers in the business and b) I wasn’t one of them. In the time since I’ve worked on many projects that required some level of text parsing and it has always reminded me of how difficult it is to do in a general way. But recently I’ve had the time and opportunity to revisit the text parsing problem and try to settle the score with an old nemesis.

"Many Internet standards and protocols are based on the Augmented Backus-Naur Form (ABNF) grammar definitions and parsers for these grammars are of considerable use. However, a quick search of the Internet did not turned up any general ABNF parser generators. The most popular parser generators seem to be those from yacc and others referenced there. Each of these has its own way of specifying the input grammar, requiring a grammar translation if it is originally in ABNF. I found an ABNF validator and several unanswered questions on bulletin boards asking about the availability of general ABNF parser generators, but I didn’t actually find an example of a tool to generate parsers directly from an ABNF grammar. So it seemed potentially useful to develop one …"

Version
Number
Release
Date
Description
1.0 05/12/2005 Needless to say, it was pretty clunky. It had lots and lots of inefficiencies which have been, for the most part, methodically eliminated over the following releases. But it worked. And its use of the ABNF-defined operators as the basic phrase-recognition building blocks is still the foundation of APG.
2.0
3.0
3.1
09/03/2005
09/15/2005
11/25/2005
Versions 2.0 - 3.1 mostly just cleaned up many of the most glaring inefficiencies.
4.0 06/02/2006 This was the last version written in C++ and had the ambitious goal of building a C++ parser. This challenge was only partially successful - a nearly complete pre-parser was developed - but it led to several important APG inovations. Most notably:
  • The first new operator was added to the ABNF-defined set. This was the first "Superset ABNF" or SABNF grammar. The operator, repeat-until, was a modification of the repetition operator. It would only repeat until a specified phrase was encountered. This was later recognized as a special case of the syntactic predicate AND and NOT operators and has since been replaced by them.
  • This was also the first version to used "first success disambiguation". Ambiguities were resolved by simply accepting the first successful match in a list of alternate expressions and ignoring the remaining alternates. The Parsing Expression Grammars (PEG) method terms this "prioritized-choice" which is now the preferred phrase.
5.0 10/15/2007 The first version written entirely in C. It still generated C++ parsers, but only as C++ wrappers for the underlying C code. This was the first and only version to utilize Partially-Predictive Parsing Tables. This is the recognition that any grammar can be preparsed to the extent that pre-defined responses can be prepared in advance for each possible single-character look ahead in the language alphabet. These are often, but not always, deterministic - hence the term "partially-predictive". This was an interesting development and did, in fact, improve parsing speeds by factors of 2-4. However, its implementation was complicated - difficult to write and difficult to maintain. A great idea, but it was never carried forward into future versions.
5.0.1 11/25/2007 This was the first Linux port and the first version to be released under the GNU GPL.
5.1 03/01/2009 The Linux build system was changed to the automake standard. The ABNF standard line ending \r\n was relaxed to accept just \n, the Linux standard, as well.
6.0 06/17/2009 In this version, the rule callback functions were allowed to override the ABNF parsing rules, disallowing matched phrases or even doing their own, hand-written phrase recognition. The precurser to UDTs. This version also cleaned up the messy business of selecting which rule names to include in the AST. Previous versions used grammar notation for this. In this version, these selections were moved to a runtime set up model.
JavaScript
Interactive APG
12/02/2009 I wanted an interactive web page for testing ABNF grammars. I wanted a tool that would not only validate the grammars but the grammar-defined language sentences as well. This required a JavaScript version of APG.
6.1 12/02/2009 Updated version 6.0 to also generate JavaScript parsers.
Java APG
1.0
10/23/2011 Inspired by the need for Java in mobile apps, I took up the challenge of learning it. What better way than to create a Java version of APG? I never got around to doing a mobile app, but I did get a version of APG with both the generator and the generated parsers written entirely in Java. Java APG introduced for the first time User-Defined Terminals (UDTs.)
6.2 This was version 6.1 converted to run on 64-bit operating systems. All previous C/C++ versions were restricted to 32-bit OSs. Released only under commercial licensing.
6.3 06/29/2012 A complete re-write of version 6.1, its primary new features are:
  • 64-bit operating systems.
  • Variable-width alphabet character codes – 8-, 16-, 32- and 64-bits wide.
  • User-Defined Terminals (UDTs).
  • Additional profiler optimizations.
  • Improved attributes algorithm.
JavaScript 2.0 10/31/2015 A complete re-write of JavaScript 1.0. Written with the main objectives in mind:
  • Updating its features to the full APG 6.3 and Java APG 1.0 complement.
  • Creating a user-local version of the parser generator as well as the parsing library (the version 1.0 generator was only available here as Interactive APG).
  • Developing it as node.js modules.
  • Publishing it to the npm registry for easy installation and use.
apg-exp 3/6/2016 apg-exp is a regex-like pattern-matching engine that uses SABNF syntax for pattern definitions and APG to generate and execute the pattern-matching parsers.