Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

PEG (parsing expression grammar) compiler for PHP

branch: master
README.md

PHP PEG - A PEG compiler for parsing text in PHP

This is a Paring Expression Grammar compiler for PHP. PEG parsers are an alternative to other CFG grammars that includes both tokenization and lexing in a single top down grammar. For a basic overview of the subject, see http://en.wikipedia.org/wiki/Parsing_expression_grammar

Quick start

  • Write a parser. A parser is a PHP class with a grammar contained within it in a special syntax. The filetype is .peg.inc. See the examples directory.
  • Compile the parser. php ./cli.php ExampleParser.peg.inc > ExampleParser.php
  • Use the parser (you can also include code to do this in the input parser - again see the examples directory):

    $x = new ExampleParser( 'string to parse' ) ;
    $res = $x->match_Expr() ;

Parser Format

Parsers are contained within a PHP file, in a special comment block that starts with /*Parser:NameOfParser and continues until the comment is closed. During compilation this block will be replaced with a set of matching functions.

Lexically, the parser is a name token, a matching rule and a set of functions. The name token must not start with whitespace, contain no whitespace and end with a : character. The rule and function set are on the same line or on the indented lines below.

Rules

PEG matching rules try to follow standard PEG format, summarised thusly:

    token* - Token is optionally repeated
    token+ - Token is repeated at least one
    token? - Token is optionally present

    tokena tokenb - Token tokenb follows tokena, both of which are present
    tokena | tokenb - One of tokena or tokenb are present, prefering tokena

    &token - Token is present next (but not consumed by parse)
    !token - Token is not present next (but not consumed by parse)

    ( expression ) - Grouping for priority

But with these extensions:

     - Optionally match whitespace
    [ or ] - Require some whitespace

Tokens

Tokens may be

  • bare-words, which are recursive matchers - references to token rules defined elsewhere in the grammar,
  • literals, surrounded by " or ' quote pairs. No escaping support is provided in literals.
  • regexs, surrounded by / pairs.
  • expressions - single words (match \w+) starting with $ or more complex surrounded by ${ } which call a user defined function to perform the match
Regular expression tokens

Automatically anchored to the current string start - do not include a string start anchor (^) anywhere. Can specify flags on stand-alone regexs. Currently doesn't handle flags on regexs with rules.

Expressions

Expressions allow run-time calculated matching. You can embed an expression within a literal or regex token to match against a calculated value, or simply specify the expression as a token to (optionally) internally handle matching and generate a result.

Expressions will try a variety of scopes to find a value. It will look for variables already set in the current result, rule-attached functions and a variety of other functions and constants.

Tried in this order

  • against current result
  • against containing expression stack in order (for sub-expressions only)
    • against parser instance as variable
    • against parser instance as rule-attached method INCLUDING $ ( i.e. function $foo() )
    • against parser instance as method INCLUDING $
    • as global method
  • as constant
Tricks and traps

Be careful against matching against results


    quoted_good: q:/['"]/ string "$q"
    quoted_bad:  q:/['"]/ string $q

"$q" matches against the value of q again. $q simply returns the value of q, without doing any matching

Named matching rules

Tokens and groups can be given names by prepending name and :, e.g.,


    rulea: "'" name:( tokena tokenb )* "'"

There must be no space betweeen the name and the :


    badrule: "'" name : ( tokena tokenb )* "'"

Recursive matchers can be given a name the same as their rule name by prepending with just a :. These next two rules are equivilent


    rulea: tokena tokenb:tokenb
    rulea: tokena :tokenb

Rule-attached functions

Each rule can have a set of functions attached to it. These functions can be defined

  • in-grammar by indenting the function body after the rule
  • in-class after close of grammar comment by defining a regular method who's name is {$rulename}_{$functionname}, or {$rulename}{$functionname} if function name starts with _
  • in a sub class

All functions that are not in-grammar must have PHP compatible names (see PHP name mapping). In-grammar functions will have their names converted if needed.

All these definitions define the same rule-attached function


    class A extends Parser {
    /**Parser
    foo: bar baz
      function bar() {}
    * /

      function foo_bar() {}
    }

    class B extends A {
      function foo_bar() {}
    }

PHP name mapping

Rules in the grammar map to php functions named match_{$rulename}. However rule names can contain characters that php functions can't. These characters are remapped:


    '-' => '_'
    '$' => 'DLR'
    '*' => 'STR'

Other dis-allowed characters are removed.

Results

Results are a tree of nested arrays.

Without any specific control, each rules result will just be the text it matched against in a ['text'] member. This member must always exist.

Marking a subexpression, literal, regex or recursive match with a name (see Named matching rules) will insert a member into the result array named that name. If there is only one match it will be a single result array. If there is more than one match it will be an array of arrays.

You can override result storing by specifying a rule-attached function with the given name. It will be called with a reference to the current result array and the sub-match - in this case the default storage action will not occur.

If you specify a rule-attached function for a recursive match, you do not need to name that token at all - it will be call automatically. E.g.


    rulea: tokena tokenb
      function tokenb ( &$res, $sub ) { print 'Will be called, even though tokenb is not named or marked with a :' ; }

You can also specify a rule-attached function called *, which will be called with every recursive match made


    rulea: tokena tokenb
      function * ( &$res, $sub ) { print 'Will be called for both tokena and tokenb' ; }

Silent matches

By default all matches are added to the 'text' property of a result. By prepending a member with . that match will not be added to the ['text'] member. This doesn't affect the other result properties that named rules' add.

TODO

  • Allow configuration of whitespace - specify what matches, and wether it should be injected into results as-is, collapsed, or not at all
  • Allow inline-ing of rules into other rules for speed
  • More optimisation
  • Make Parser-parser be self-generated, instead of a bad hand rolled parser like it is now.
  • Slighly more powerfull expressions: ${parent.q}, ${foo()->bar}, etc.
  • Need to properly escape all literals. Expressions currently need to be in '', not ""
  • PHP token parser, and other token streams, instead of strings only like now
Something went wrong with that request. Please try again.