README

LocoX is a parsing library and toolkit for PHP. Eventually, other languages will be supported as output targets. It is, by default, a recursive descent top-down parser. Again, other styles of parsing may be eventually supported and it is designed in such a way that such support is quite trivial.

These styles of parsers do not require a separate lexer step, but LocoX can still have a separate lexer/parser if you do so choose. One of the fastest way to perform parsing in PHP is to use regular expressions to generate a tokenization of the input text and then use a recursive-descent setup to recurse into the tokens. LocoX supports this style of parsing.

Or, if you do so choose, you may also completely skip the lexer and simply parse raw text in a recursive manner. This isn't very fast but it's, in 99% of cases, "fast enough". Again, LocoX supports this style of parsing.

In fact, LocoX supports a wide varity of parser styles (except table-driven parsers as mentioned):

LocoX can act as an "on-the-spot" parser or as a parser generator. You may feed it an object-oriented list of parser operators (and even create your own) as an array directly to create the desired grammar or use one of the many grammar notaitons below to generate a grammar.
LocoX can act as a parser-generator using any of the following grammar notations/expression grammars:
- BNF
- EBNF
- Wirth Notation
- Basic Regular Expression (Generate parsers based on regex fragments)
- Full PEG Grammar Support
- Extended Custom Grammars

LocoX uses single-valued parsers called MonoParsers. A conventional, "enthusiastic" parser returns a set of possible results, which is empty if parsing is not possible. A "lazy" parser returns one possible result on the first call, and then returns further results with each subsequent call until no more are possible. In contrast, MonoParsers simply return a single result or failure. This in turn makes backtracking impossible, which has two effects:

it reduces expressive power to only certain unambiguous context-free grammars
it prevents parsing time from becoming exponential.

LocoX directly to parses strings, requiring no intermediate lexing step.

LocoX detects infinite loops (e.g. (|a)*) and left recursion (e.g. A -> Aa) at grammar creation time.

Parsers in LocoX

`MonoParser`

Abstract base class from which all parsers inherit. Can't be instantiated. "Mono" means the parser returns one result, or fails.

Ab\LocoX\MonoParser has one important method, match($string, $i = 0), which either returns the successful match in the form of an array("j" => 9, "value" => "something"), or throws a Ab\LocoX\ParseFailureException.

There is also the more useful method parse($string), which either returns the parsed value "something" or throws a Ab\LocoX\ParseFailureException if the match fails or doesn't occupy the entire length of the supplied string.

`EmptyParser`

Finds the empty string (and always succeeds). Callback is passed no arguments. Default callback returns null.

new Ab\LocoX\Clause\Terminal\EmptyParser();
// returns null

new Ab\LocoX\Clause\Terminal\EmptyParser(
  function() { return array(); }
);
// return an empty array instead

`StringParser`

Finds a static string. Callback is passed one argument, the string that was matched. Yes, that's effectively the same function call each time. Default callback returns the first argument i.e. the string.

new Ab\LocoX\Clause\Terminal\StringParser("name");
// returns "name"

new Ab\LocoX\Clause\Terminal\StringParser(
  "name",
  function($string) { return strrev($string); }
);
// returns "eman"

`RegexParser`

Matches a regular expression. The regular expression must be anchored at the beginning of the substring supplied to match, using ^. Otherwise, there's no way to stop PHP from matching elsewhere entirely in the expression, which is very bad. Caution: formations like /^a|b/ only anchor the "a" at the start of the string; a "b" might be matched anywhere! You should use /^(a|b)/ or /^a|^b/.

Callback is passed one argument for each sub-match. For example, if the regex is /^ab(cd(ef)gh)ij/ then the first argument is the whole match, "abcdefghij", the second argument is "cdefgh" and the third argument is "ef". The default callback returns only the first argument, the whole match.

new Ab\LocoX\Clause\Terminal\RegexParser("/^'([a-zA-Z_][a-zA-Z_0-9]*)'/");
// returns the full match including the single quotes

new Ab\LocoX\Clause\Terminal\RegexParser(
  "/^'([a-zA-Z_][a-zA-Z_0-9]*)'/",
  function($match0, $match1) { return $match1; }
);
// discard the single quotes and returns only the inner string

`Utf8Parser`

Matches a single UTF-8 character. You can optionally supply a blacklist of characters which will not be matched.

new Ab\LocoX\Clause\Terminal\Utf8Parser(array("<", ">", "&"));
// any UTF-8 character except the three listed

Callback is passed one argument, the string that was matched. The default callback returns the first argument i.e. the string.

For best results, alternate (see Ab\LocoX\Clause\Nonterminal\OrderedChoice below) with Ab\LocoX\Clause\Terminal\StringParsers for e.g. "<", ">", "&" and other HTML character entities.

`OrderedChoice`

This encapsulates the "alternation" parser combinator by alternating between several internal parsers. The key word here is "lazy". As soon as one of them matches, that result is returned, and that's the end of the story. There is no capability to merge the results from several of the internal parsers, and there is no capability for returning (backtracking) to this parser and trying to retrieve other results if the first one turns out to be bogus.

Callback is passed one argument, the sole successful internal match. The default callback returns the first argument directly.

new Ab\LocoX\Clause\Nonterminal\OrderedChoice(
  array(
    new Ab\LocoX\Clause\Terminal\StringParser("foo"),
    new Ab\LocoX\Clause\Terminal\StringParser("bar")
  )
);
// returns either "foo" or "bar"

`Sequence`

This encapsulates the "concatenation" parser combinator by concatenating a finite sequence of internal parsers. If the sequence is empty, this is equivalent to Ab\LocoX\Clause\Terminal\EmptyParser, above.

Callback is passed one argument for every internal parser, each argument containing the result from that parser. For example, new Ab\LocoX\Clause\Nonterminal\Sequence(array($a, $b, $c), $callback) will pass three arguments to its callback. The first contains the result from parser $a, the second the result from parser $b and the third the result from parser $c. The default callback returns the arguments in the form of an array: return func_get_args();.

new Ab\LocoX\Clause\Nonterminal\Sequence(
  array(
    new Ab\LocoX\Clause\Terminal\RegexParser("/^<([a-zA-Z_][a-zA-Z_0-9]*)>/", function($match0, $match1) { return $match1; }),
    new Ab\LocoX\Clause\Terminal\StringParser(", "),
    new Ab\LocoX\Clause\Terminal\RegexParser("/^<(\d\d\d\d-\d\d-\d\d)>/",     function($match0, $match1) { return $match1; }),
    new Ab\LocoX\Clause\Terminal\StringParser(", "),
    new Ab\LocoX\Clause\Terminal\RegexParser("/^<([A-Z]{2}[0-9]{7})>/",       function($match0, $match1) { return $match1; }),
  ),
  function($name, $comma1, $opendate, $comma2, $ref) { return new Account($accountname, $opendate, $ref); }
);
// match something like "<Williams>, <2011-06-30>, <GH7784939>"
// return new Account("Williams", "2011-06-30", "GH7784939")

`BoundedRepeat`

This encapsulates the "Kleene star closure" parser combinator to match single internal parser multiple (finitely or infinitely many) times. With a finite upper bound, this is more or less equivalent to Ab\LocoX\Clause\Nonterminal\Sequence, above. With an infinite upper bound, this gets more interesting. Ab\LocoX\Clause\Nonterminal\BoundedRepeat, as the name hints, will match as many times as it can before returning. There is no option for returning multiple matches simultaneously; only the largest match is returned. And there is no option for backtracking and trying to consume more or fewer instances.

Callback is passed one argument for every match. For example, new Ab\LocoX\Clause\Nonterminal\BoundedRepeat($a, 2, 4, $callback) could pass 2, 3 or 4 arguments to its callback. new BoundedRepeat($a, 0, null, $callback) has an unlimited upper bound and could pass an unlimited number of arguments to its callback. (PHP seems to have no problem with this.) The default callback returns all of the arguments in the form of an array: return func_get_args();.

Remember that a PHP function can be defined as function(){...} and still accept an arbitrary number of arguments.

new Ab\LocoX\Clause\Nonterminal\BoundedRepeat(
  new Ab\LocoX\Clause\Nonterminal\OrderedChoice(
    array(
      new Ab\LocoX\Clause\Terminal\Utf8Parser(array("<", ">", "&")),                         // match any UTF-8 character except <, > or &
      new Ab\LocoX\Clause\Terminal\StringParser("&lt;",  function($string) { return "<"; }), // ...or an escaped < (unescape it)
      new Ab\LocoX\Clause\Terminal\StringParser("&gt;",  function($string) { return ">"; }), // ...or an escaped > (unescape it)
      new Ab\LocoX\Clause\Terminal\StringParser("&amp;", function($string) { return "&"; })  // ...or an escaped & (unescape it)
    )
  ),
  0,                                                  // at least 0 times
  null,                                               // at most infinitely many times
  function() { return implode("", func_get_args()); } // concatenate all of the matched characters together
);
// matches a continuous string of valid, UTF-8 encoded HTML text
// returns the unescaped string

`Grammar`

All of the above is well and good, but it doesn't complete the picture. Firstly, it makes our parsers quite large and confusing to read when they nest too much. Secondly, it makes recursion very difficult; a parser cannot easily be placed inside itself, for example. Without recursion, all we can parse is regular languages, not context-free languages.

The Ab\LocoX\Grammar class makes this very easy. At its heart, Ab\LocoX\Grammar is just another Ab\LocoX\MonoParser. But Ab\LocoX\Grammar accepts an associative array of parsers as input -- meaning each one comes attached to a name. The parsers inside it, meanwhile, can refer to other parsers by name instead of containing them directly. Ab\LocoX\Grammar resolves these references at instantiation time, as well as detecting anomalies like left recursion, names which refer to parsers which don't exist, dangerous formations such as new Ab\LocoX\Clause\Nonterminal\BoundedRepeat(new Ab\LocoX\Clause\Terminal\EmptyParser(), 0, null), and so on.

Here's a simple Ab\LocoX\Grammar which can recognise (some) valid HTML paragraphs and return the text content of those paragraphs:

$p = new Ab\LocoX\Grammar(
  "paragraph",
  array(
    "paragraph" => new Ab\LocoX\Clause\Nonterminal\Sequence(
      array(
        "OPEN_P",
        "CONTENT",
        "CLOSE_P"
      ),
      function($open_p, $content, $close_p) {
        return $content;
      }
    ),

    "OPEN_P" => new Ab\LocoX\Clause\Terminal\StringParser("<p>"),

    "CONTENT" => new Ab\LocoX\Clause\Nonterminal\BoundedRepeat(
      "UTF-8 CHAR",
      0,
      null,
      function() { return implode("", func_get_args()); }
    ),

    "CLOSE_P" => new Ab\LocoX\Clause\Terminal\StringParser("</p>"),

    "UTF-8 CHAR" => new Ab\LocoX\Clause\Nonterminal\OrderedChoice(
      array(
        new Ab\LocoX\Clause\Terminal\Utf8Parser(array("<", ">", "&")),                         // match any UTF-8 character except <, > or &
        new Ab\LocoX\Clause\Terminal\StringParser("&lt;",  function($string) { return "<"; }), // ...or an escaped < (unescape it)
        new Ab\LocoX\Clause\Terminal\StringParser("&gt;",  function($string) { return ">"; }), // ...or an escaped > (unescape it)
        new Ab\LocoX\Clause\Terminal\StringParser("&amp;", function($string) { return "&"; })  // ...or an escaped & (unescape it)
      )
    ),
  )
);

$p->parse("<p>Your text here &amp; here &amp; &lt;here&gt;</p>");
// returns "Your text here & here & <here>"

Examples

Loco also comes with a collection of public domain examples:

examples/json.php

Parse JSON expressions and returns PHP arrays.

examples/regEx.php

Parse simple regular expressions and return PHP objects representing them.

examples/simpleComment.php

Recognise simple valid HTML text using <h5>, <p>, <em> and <strong>, with balanced tags and escaped entities.

examples/bnf.php

Defines $bnfGrammar, which parses a grammar presented in Backus-Naur Form and returns Ab\LocoX\Grammar object capable of recognising that grammar.

BNF is generally pretty low-tech and lacks a lot of features.

Sample grammar in Backus-Naur Form

This appears on Wikipedia. This is a pretty clunky example because it doesn't handle whitespace and doesn't define a whole lot of variables which I had to do myself. However, it gets the point across.

<postal-address> ::= <name-part> <street-address> <zip-part>
<name-part>      ::= <personal-part> <name-part> | <personal-part> <last-name> <opt-jr-part> <EOL>
<personal-part>  ::= <initial> "." | <first-name>
<street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>
<zip-part>       ::= <town-name> "," <state-code> <ZIP-code> <EOL>
<opt-jr-part>    ::= "Sr." | "Jr." | <roman-numeral> | ""

<last-name>     ::= 'MacLaurin '
<EOL>           ::= '\n'
<initial>       ::= 'b'
<first-name>    ::= 'Steve '
<house-num>     ::= '173 '
<street-name>   ::= 'Acacia Avenue '
<opt-apt-num>   ::= '7A'
<town-name>     ::= 'Stevenage'
<state-code>    ::= ' KY '
<ZIP-code>      ::= '33445'
<roman-numeral> ::= 'g'

String in the sample grammar

Steve MacLaurin \n173 Acacia Avenue 7A\nStevenage, KY 33445\n

examples/wirth.php

Defines $wirthGrammar, which parses a grammar presented in Wirth syntax notation and returns a Ab\LocoX\Grammar object capable of recognising that grammar.

Wirth syntax notation is okay, but I don't like the use of . (which in my mind usually means "any character" (when used in a regex), or the string concatenation operator) as a line ending (which I usually think of as a semicolon or an actual \n). I also dislike the use of square brackets for optional terms, and braces for Kleene star closure. Neither of these are unambiguous enough in their meaning.

Sample grammar in Wirth syntax notation

SYNTAX     = { PRODUCTION } .
PRODUCTION = IDENTIFIER "=" EXPRESSION "." .
EXPRESSION = TERM { "|" TERM } .
TERM       = FACTOR { FACTOR } .
FACTOR     = IDENTIFIER
           | LITERAL
           | "[" EXPRESSION "]"
           | "(" EXPRESSION ")"
           | "{" EXPRESSION "}" .
IDENTIFIER = letter { letter } .
LITERAL    = """" character { character } """" .
digit      = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
upper      = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" 
           | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" 
           | "U" | "V" | "W" | "X" | "Y" | "Z" .
lower      = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" 
           | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" 
           | "u" | "v" | "w" | "x" | "y" | "z" .
letter     = upper | lower .
character  = letter | digit | "=" | "." | """""" .

This example grammar happens to be the grammar which describes Wirth syntax notation itself - if it had all whitespace removed from it. Observe:

String in the sample grammar

SYNTAX={PRODUCTION}.

examples/ebnf.php

Defines $ebnfGrammar, which parses a grammar presented in Extended Backus-Naur Form and returns a Grammar object capable of recognising that grammar.

This is a big improvement on vanilla BNF (comments are a must!) but the need for commas between tokens is irritating and again, braces and square brackets aren't ideal in my mind.

$ebnfGrammar can't handle "specials" (strings contained between two question marks), since these have no clear definition. It also can't handle "exceptions" (when a - is used to discard certain possibilities), because these are not permissible in context-free grammars or possible with naive Ab\LocoX\MonoParsers, and so would require special modification to Loco to handle.

Sample grammar in Extended Backus-Naur Form

(* a simple program syntax in EBNF - Wikipedia *)
program = 'PROGRAM' , white space , identifier , white space ,
           'BEGIN' , white space ,
           { assignment , ";" , white space } ,
           'END.' ;
identifier = alphabetic character , { alphabetic character | digit } ;
number = [ "-" ] , digit , { digit } ;
string = '"' , { all characters } , '"' ;
assignment = identifier , ":=" , ( number | identifier | string ) ;
alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G"
                     | "H" | "I" | "J" | "K" | "L" | "M" | "N"
                     | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
                     | "V" | "W" | "X" | "Y" | "Z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
white space = ( " " | "\n" ) , { " " | "\n" } ;
all characters = "H" | "e" | "l" | "o" | " " | "w" | "r" | "d" | "!" ;

String in the sample grammar

PROGRAM DEMO1
BEGIN
  A0:=3;
  B:=45;
  H:=-100023;
  C:=A;
  D123:=B34A;
  BABOON:=GIRAFFE;
  TEXT:=\"Hello world!\";
END."

examples/locoNotation.php

Defines $locoGrammar, which parses a grammar presented in "Loco notation" and returns a Ab\LocoX\Grammar object capable of parsing that grammar.

"Loco notation" (for lack of a better name) is an extension of Backus-Naur Form which gives access to all the Ab\LocoX\MonoParsers that Loco makes available. The following parsers are already effectively available in most grammar notations:

Ab\LocoX\Clause\Terminal\EmptyParser - Just have an empty string or an empty right-hand side to a rule. Some notations also permit an explicit "epsilon" symbol.
Ab\LocoX\Clause\Terminal\StringParser - Invariably requires a simple string literal in single or double quotes.
Ab\LocoX\Clause\Nonterminal\Sequence - Usually you put multiple tokens in a row and they will be matched consecutively. In EBNF, commas must be used as separators.
Ab\LocoX\Clause\Nonterminal\OrderedChoice - Alternation is achieved using a pipe, |, between possibilities.
Ab\LocoX\Clause\Nonterminal\BoundedRepeat - Most notations provide some ability to make a match optional (typically square brackets), and/or to match an unlimited number of times (typically an asterisk or braces).

I had to invent new notation for the following:

Ab\LocoX\Clause\Terminal\RegexParser - Put your regex between slashes, just like in Perl.
Ab\LocoX\Clause\Terminal\Utf8Parser - To match any single UTF-8 character, put a full stop, .. To blacklist some characters, put the blacklisted characters between [^ and ].

In both cases I borrowed notation from the standard regular expression syntax, because why not stay with the familiar?

In all cases where a "literal" is provided (strings, regexes, UTF-8 exceptions), you can put the corresponding closing delimiter (i.e. ", ', / or ]) inside the "literal" by escaping it with a backslash. E.g.: "\"", '\'', /\//, [^\]]. You can also put a backslash itself, if you escape it with a second backslash. E.g.: "\\", '\\', /\\/, [^\\].

Sample grammar in Loco notation

Remember examples/simpleComment.php? Here is that grammar in Loco notation.

comment    ::= whitespace block*
block      ::= h5 whitespace | p whitespace
p          ::= '<p'      whitespace '>' text '</p'      whitespace '>'
h5         ::= '<h5'     whitespace '>' text '</h5'     whitespace '>'
strong     ::= '<strong' whitespace '>' text '</strong' whitespace '>'
em         ::= '<em'     whitespace '>' text '</em'     whitespace '>'
br         ::= '<br'     whitespace '/>'
text       ::= atom*
atom       ::= [^<>&] | '&' entity ';' | strong | em | br
entity     ::= 'gt' | 'lt' | 'amp'
whitespace ::= /[ \n\r\t]*/

See how I've put /[ \n\r\t]*/ to match an unlimited sequence of whitespace. This could be achieved using more rules and StringParsers, but RegexParsers are more powerful and more elegant.

Also see how I've put [^<>&] to match "any UTF-8 character except a <, a > or a &".

String in the sample grammar

<h5>  Title<br /><em\n><strong\n></strong>&amp;</em></h5>
   \r\n\t 
<p  >&lt;</p  >

About Loco

Loco was created because I wanted to let people use XHTML comments on my website, and I wanted to be able validate that XHTML in a flexible way, starting with a narrow subset of XHTML and adding support for more tags over time. I believed that writing a parsing library would be more effective and educational than hand-writing (and then constantly hand-rewriting) a parser.

Loco, together with the Loco grammar examples/simpleComment.php, fulfilled the first objective. These were kept in successful use for several years. Later, I developed examples/locoNotation.php which things even simpler for me. However, there were some drawbacks:

Grammars had to be instantiated every time the comment-submission PHP script ran, which was laborious and inelegant. PHP doesn't make it possible to retrieve the text content of a callback, so the process of turning Loco from a parser library into a true parser generator stalled.
Lack of backtracking meant I had to be inordinately careful in describing my CFG so that it would be unambiguous and work correctly. This need for extra effort kind of defeated the point.
As I now realise, one of the most important things to consider when parsing user input is generating meaningful error messages when parsing failed. Loco is sort of bad at this, and users found it difficult to create correct HTML to keep it pleased.
PHP is horrible.

Before beginning the project, I also observed that PHP had no parser combinator library, and I decided to fill this niche. Again, I ran into some problems:

I didn't actually know what the term "parser combinator" meant at the time. It is not "a parser made up from a combination of other parsers". It is "a function or operator which accepts one or more parsers as input and returns a new parser as output". You can see the term being misused several times above. There is still no parser combinator library for PHP, to my knowledge.
I knew, and still know, barely anything about parsing in general.
PHP is horrible.

Overall I would say that this project fulfilled my needs at the time, and if it fulfills yours now that is probably just a coincidence. I would exercise caution when using Loco, or inspecting its code.

ab / lx-parser

Maintainers

Details

README

Parsers in LocoX

`MonoParser`

`EmptyParser`

`StringParser`

`RegexParser`

`Utf8Parser`

`OrderedChoice`

`Sequence`

`BoundedRepeat`

`Grammar`

Examples

examples/json.php

examples/regEx.php

examples/simpleComment.php

examples/bnf.php

Sample grammar in Backus-Naur Form

String in the sample grammar

examples/wirth.php

Sample grammar in Wirth syntax notation

String in the sample grammar

examples/ebnf.php

Sample grammar in Extended Backus-Naur Form

String in the sample grammar

examples/locoNotation.php

Sample grammar in Loco notation

String in the sample grammar

About Loco