headerphoto

About Me

I'm a retired computer programmer with a continuing passion for geeky computer fun. I learned programming writing FORTRAN on 80-column punched cards for the IBM 360. Back then I was doing large-scale, scientific number crunching applications and programming was just a necessary means to an end. But later, especially with the coming of personal desktop computers, my interests gave way to full-time software development. I've done many projects in many venues but mostly in some sort of freelance capacity.

APG has been an on-again, off-again pet project of mine since 2005. With no formal Computer Science training and it has been primarily an amateur, hobby project. Nonetheless, I have worked very hard to make it an industrial-strength program - small, fast, versatile and bug-free. And it has been very rewarding that a number of large corporations have asked for my help to make APG a part of their commercial products.

I've done nothing with APG at all since the release of version 6.3 in 2012. But now (12/2014) that I have finally gotten around to reorganizing this website and taking advantage of Git and GitHub, it's getting interesting again. There always seems to be just one more idea to try. Who knows, there may be another version sometime yet.

Lowell D. Thomas

email: reCAPTCHA

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.