compilers/pge/README.pod

   1 # $Id$
   2
   3 =head1 Parrot Grammar Engine (PGE)
   4
   5 This is a regular expression/rules/grammar engine/parser designed to
   6 run in Parrot.  It's still a work in progress, but has a lot of
   7 nice features in it, including support for perl 6 regexes, globs,
   8 shift-reduce parsing, and some support for perl 5 regular expressions.
   9 It also includes the "pgc.pir" grammar compiler, which can convert
  10 an entire grammar specification into the appropriate PIR code
  11 for execution.
  12
  13 A nice feature of PGE is that one can easily combine many
  14 different parsing styles into a single interface.  PGE uses
  15 perl 6 rules for its top-down parsing, an operator precedence
  16 parser for bottom-up (shift/reduce) parsing, and allows control
  17 to pass freely between the two styles as well as to custom parsing
  18 subroutines.
  19
  20 =head1 Installation
  21
  22 PGE assumes that it is part of the parrot distribution in the
  23 F<compilers/pge> directory.   Simply type C<make> in this directory
  24 to build the various *.pbc files and install them into
  25 runtime/parrot/library.
  26
  27 The distribution comes with a small F<demo.pir> program that gives an
  28 example of using PGE.  To run the demo, simply do
  29 C<parrot demo.pir>.  The demo understands the following commands:
  30
  31     rule pattern      - compile a Perl 6 rule from "pattern"
  32     save name         - save the current rule as "name"
  33     text              - a text string to match against previously entered rule
  34     pir               - display the PIR code generated for current rule
  35     exp               - display the expression tree for the current rule
  36     trace             - toggle pattern execution tracing
  37     next              - repeat last match on target string
  38
  39 =head1 PGE's rule engine  (PGE::Perl6Regex)
  40
  41 Once PGE is compiled and installed, you generally load it using
  42 the load_bytecode operation, as in
  43
  44     load_bytecode 'PGE.pbc'
  45
  46 This imports the PGE::Perl6Regex compiler, which can be used to compile
  47 strings of Perl 6 regexes.  A sample compile sequence would be:
  48
  49     .local pmc p6regex_compile
  50     p6regex_compile = compreg 'PGE::Perl6Regex'         # get the compiler
  51
  52     .local string pattern
  53     .local pmc rulesub
  54     pattern = '^(From|Subject)\:'                  # pattern to compile
  55     rulesub = p6regex_compile(pattern)             # compile it to rulesub
  56
  57 Then, to match a target string we simply call the subroutine
  58 to get back a C<PGE::Match> object:
  59
  60     .local pmc match
  61     $S0 = 'From: pmichaud@pobox.com'               # target string
  62     match = rulesub($S0)                           # execute rule
  63
  64 The Match object is true if it successfully matched, and contains
  65 the strings and subpatterns that were matched as part of the capture.
  66 Parrot's "Data::Dumper" can be used to quickly view the results
  67 of the match:
  68
  69     load_bytecode 'dumper.pir'
  70     load_bytecode 'PGE/Dumper.pir'
  71
  72   match_loop:
  73     unless match goto match_fail                   # if match fails stop
  74     print "match succeeded\n"
  75     _dumper(match)
  76     match.'next'()                                 # find the next match
  77     goto match_loop
  78
  79   match_fail:
  80     print "match failed\n"
  81
  82 One can also get the intermediate PIR code that PGE generates for
  83 the rule subroutine -- just use
  84
  85     $S0 = p6regex_compile(pattern, 'target'=>'PIR')
  86
  87 and you can print/inspect the contents of $S0 to see the generated code.
  88
  89 See the STATUS file for a list of implemented and yet-to-be-implemented
  90 features.
  91
  92 =head1 Known limitations of the rule engine
  93
  94 PGE doesn't (yet) properly handle nested repetitions of zero-length
  95 patterns in groups -- that's coming soon.
  96
  97 Many well-known optimizations (e.g., Boyer-Moore) aren't
  98 implemented yet, although a variety of optimizations are being
  99 added as we generate code.
 100
 101 Lastly, error handling needs to be improved, but this will likely
 102 be decided as we discover how PGE integrates with the rest of
 103 Parrot.
 104
 105 =head1 Implementation notes
 106
 107 Basically, PGE is a compiler just like any other, except that its
 108 "language" is the Perl 6 regex syntax and its output is a subroutine
 109 that can match strings.  So, PGE consists of a series of parsers
 110 (for each pattern matching language), an intermediate expression
 111 format, and a code generator.
 112
 113 The parsers can be written using PIR subroutines or PGE's built-in
 114 operator precedence (shift/reduce) parser; the parser for Perl 6
 115 regexes is built with the operator precedence parser.  This parser
 116 produces a parse tree (in the form of a Match object) for a given
 117 Perl 6 regex.  The parse tree then goes through semantic analysis
 118 and reduction phases before being sent to code generation to
 119 produce a PIR subroutine.
 120
 121 The generated PIR code uses Parrot calling conventions for
 122 all interfaces with external callers/callees such as subrules.
 123
 124 PGE also uses Parrot coroutines for the matching
 125 engine, so that after a successful match is found, the
 126 next match within the same string can be found by simply
 127 returning control to the matching coroutine, which then
 128 picks up from where it had previously left off until
 129 another match is discovered.
 130
 131 The code still needs a fair amount of commenting.  In general,
 132 if you have a question about a particular section of code,
 133 send Pm an email and he'll write the comments for it.
 134
 135 =head1 AUTHOR
 136
 137 Patrick Michaud (pmichaud@pobox.com) is the author and maintainer.
 138 Patches and suggestions should be sent to the Perl 6 compiler list
 139 (perl6-compiler@perl.org).
 140
 141 =cut
 142