/ 
Parse-Marpa-0.001_068
/ Parse::Marpa

NAME

Parse::Marpa - (pre-Alpha) Jay Earley's general parsing algorithm, with LR(0) precomputation

BEWARE: THIS DOCUMENT IS UNDER CONSTRUCTION

VERSION

This is Pre-alpha software.

It's strictly a developer's version. Those not developing this module will want to wait for at least a released, beta version.

SYNOPSIS

The Easy Way

It's possible to specify the grammar and the text to be parsed all in one step

use Parse::Marpa;
my $value = Parse::Marpa::marpa(\$grammar, \$text_to_parse);

The syntax for $grammar can be found in the document for the Marpa Demonstration Language. and you can even include options if you make a hash ref the third argument.

my $value = Parse::Marpa::marpa(
    \$grammar,
    \$text_to_parse
    {
        warnings => 1,
    }
);

You can get all the values of an ambiguous parse by invoking Parse::Marpa::marpa in list context.

my @values = Parse::Marpa::marpa(\$ambiguous_grammar, \$text_to_parse);

Step by Step

First, set things up ...

use Parse::Marpa;

my @tests = split(/\n/, <<'EO_TESTS');
time  / 25 ; # / ; die "this dies!";
localtime  / 25 ; # / ; die "this dies!";
EO_TESTS

then create a grammar object, ...

my $g = new Parse::Marpa(
    warnings => 1,
    code_lines => -1,
);

and set the grammar.

my $mock_perl_grammar; { local($RS) = undef; $mock_perl_grammar = <DATA> };
$g->set( source => \$mock_perl_grammar);

Next, as many times as you like, ...

TEST: while (my $test = pop @tests) {

create a parse object, ...

my $parse = new Parse::Marpa::Parse($g);

pass text to the recognizer, ...

$parse->text(\$test);

evaluate the initial parse, ...

$parse->initial();
my @parses;
push(@parses, $parse->value);

... and get others, if there are any.

while ($parse->next) {
    push(@parses, $parse->value);
}

You're now ready to announce your results and continue the loop.

    say "I've got ", scalar @parses, " parses:";
    for (my $i = 0; $i < @parses; $i++) {
        say "Parse $i: ", ${$parses[$i]};
    }
}

__DATA__
...

DESCRIPTION

Parse::Marpa parses text given an arbitrary context-free grammar.

  • The grammar may be anything which can be specified in BNF.

  • This includes left-recursive grammars, right-recursive grammars, grammars with empty productions, grammars with cycles and ambigious grammars.

  • Ambiguous grammars are a Marpa specialty. They are useful even if you only want one parse. An ambiguous grammar is often the easiest and most sensible way to express a language. Human languages are ambiguous. We listen and pull out the parse that makes most sense. Marpa allows the user to prioritize rules so that a preferred parse comes up first.

  • Marpa can also return all the parses of an ambiguous grammar.

  • Marpa incorporates the latest academic research on Earley's algorithm, combining it with LR(0) precomputation.

  • Marpa adds its own innovations, such as the combination of Earley's with predictive lexing. and ambiguous lexing.

BEWARE! PRE-ALPHA SOFTWARE

Since this is pre-alpha software, users with immediate needs must look elsewhere. I've no personal experience with them, but Parse::Yapp and Parse::RecDescent are alternatives to this module which are well reviewed and much more mature and stable.

What to Expect Once Marpa Goes Alpha

The alpha version will be intended to let people look Marpa over and try it out. Uses beyond that are risky.

There will be bugs and misfeatures when I go alpha, all known bugs will be documented, and all bugs will all have workarounds. The documentation follows the industry convention of telling the user how Marpa should work. If there's a difference between that and how Marpa actually works currently, it's in the Bugs section, which you'll want to at least skim before using Marpa.

While Marpa is in alpha, you may not want to automatically upgrade as new versions come out. Versions will often be incompatible. MDL emphasizes this by requiring the version option, and insisting on an exact match with Marpa's version number. That's a hassle, but so is alpha software and that's the point. The version number regime will become less harsh before Marpa leaves beta.

Obviously, while Marpa is in alpha, you won't want to use it for anything mission-critical or with a serious deadline.

READING THESE DOCUMENTS

The Parse::Marpa::CONCEPTS should be read before using Marpa, in fact probably before your first careful reading of this document. The "concepts" in it are all practical -- the theoretical discussions went into Parse::Marpa::ALGORITHM. Even experts in Earley parsing will want to skim Parse::Marpa::CONCEPTS because, as one example, the use of ambiguous lexing has unusual implications for term token.

The Parse::Marpa::LANGUAGE documents what is currently Marpa's only high-level interface. Of Marpa's current documents, it is the most tutorial in approach.

THE EASY WAY

Parse::Marpa::marpa(grammar, text_to_parse, option_hash);

The marpa() method takes three arguments: a reference to a string containing a Marpa source description of the grammar in one of the high-level interfaces; a reference to a string with the text to be parsed; and (optionally) a reference to a hash with options.

In scalar context, marpa() returns the value of the first parse if there was one, and undefined if there were no parses. In list context, marpa() returns a list of references to the values of the parses. This is the empty list if there were no parses.

The description referenced by the grammar argument must use one of the high-level Marpa grammar interfaces. Currently the default (and only) high-level grammar interface is the Marpa Demonstration Language.

METHODS FOR FINER CONTROL

new Parse::Marpa(option => value, [option => value, ...])

Parse::Marpa::Parse::new() takes as its arguments a series of option, value pairs which are treated as a hash. It returns a new grammar object or throws an exception. For valid options see the options section.

new Parse::Marpa::Parse(option => value, [option => value, ...])

Parse::Marpa::Parse::new() takes as its arguments a series of option, value pairs which are treated as a hash. It returns a new parse object or throws an exception. The grammar option must be specified, and its value must be a grammar object with rules defined in it. For valid options see the options section.

Parse::Marpa::Parse::text(parse, text_to_parse)

Extends the parse in the parse object using the input text_to_parse, a reference to a string. Returns -1 if the parse is still active after the text_to_parse has been processed. Otherwise the offset of the character where the parse was exhausted is returned. Failures, other than exhausted parses, are thrown as exceptions.

The text is parsed using the one-earleme-per-character model. Terminals are recognized using the lexers that were specified in the source file or with the raw interface.

The character offset where the parse was exhausted is reported in characters from the start of text_to_parse. The first character is at offset zero. This means that a zero return from text() indicates that the parse was exhausted at the first character.

A parse is "exhausted" at a point in the input where a successful parse becomes impossible. In most contexts and for most applications, an exhausted parse is a failed parse.

Parse::Marpa::Parse::initial(parse, parse_end)

Performs the recognition phase of a parse. On successful recognition of a parse, initial() returns a value of 1. The user may then get value of the parse with Parse::Marpa::Parse::value(), and may iterate through any other parses with Parse::Marpa::Parse::next().

initial() returns undefined if it fails to recognize a parse. Other failures are thrown as exceptions.

The parse_end argument is optional. If provided, it must be the number of the earleme at which the parse ends. In the case of a still active parse in offline mode, the default is to parse to the end of the input.

In case of an exhausted parse, the default is to end the parse at the point at which the parse was exhausted. This default isn't very helpful, frankly, and if I think of anything better I'll change it. An exhausted parse is a failed parse unless you're trying advanced wizardry. Failed parses are usually addressed by fixing the grammar or the input. The Parse::Marpa::Parse::find_complete_rule() method, documented in the diagnostics document, may help if you want to try error recovery.

The alternative to offline mode is online mode, which is bleeding-edge. In online mode there is no obvious "end of input". Online mode is not well tested, and Marpa doesn't yet provide a lot of tools for working with it. It's up to the user to determine where to look for parses, perhaps using her specific knowledge of the grammar and the problem space. Again, the Parse::Marpa::Parse::find_complete_rule() method, documented in the diagnostics document, may help.

Parse::Marpa::Parse::next(parse)

Takes a parse object, which must have already been evaluated once with Parse::Marpa::Parse::initial(), and performs the next evaluation. Returns 1 if there was another evaluation, undefined if there are no more values for this initialization of this parse object. Other failures are exceptions.

Parses are returned from rightmost to leftmost, but their order may be manipulated by assigning priorities to the rules and terminals.

Parse::Marpa::Parse::value(parse)

Takes a parse object, which has been set up with Parse::Marpa::Parse::initial() and may have been iterated with Parse::Marpa::Parse::next(), and returns a reference to its current value. Failures are thrown as exceptions.

Defaults, nulling rules, and non-existent optional items all have as their value a Perl undefined. value() will return these as a reference to an undefined.

In unusual cases, (probably be the result of advanced wizardry gone wrong), Marpa will not find a "calculated value" and the return value will be undefined instead of a pointer to undefined. This is considered a Marpa "no value". If you stay in offline mode and accept the default end parse location when you call the initial() method, a "no value" return from value() should never happen.

LESS USED METHODS

Several of the methods in this section explicitly run processing phases which Marpa typically performs indirectly. For example, when Parse::Marpa::Parse::new() is asked to create a new parse object from a grammar which has not been through the precomputation phase, that grammar is automatically precomputed and deep copied.

The most important uses of these methods are in connection with diagnostics. A user may want to trace Marpa's behavior during, or examine a Marpa object immediately after, a particular processing phase. In such cases, it can be helpful or even necessary to run that phase explicitly.

Parse::Marpa::compile(grammar) or $grammar->compile()

The compile method takes as its single argument a grammar object, and "compiles" it, that is, writes it out using Data::Dumper. It returns a reference to the compiled grammar, or throws an exception.

Parse::Marpa::decompile(compiled_grammar, [trace_file_handle])

The decompile static method takes a reference to a compiled grammar as its first argument. The second, optional, argument is a file handle. It is used both to override the compiled grammar's trace file handle, and for any trace messages produced by decompile() itself. decompile() returns the decompiled grammar object unless it throws an exception.

If the trace file handle argument is omitted, it defaults to STDERR and the new grammar's trace file handle reverts to the default for a new grammar, which is also STDERR. The trace file handle argument is needed because in the course of compilation, the grammar's original trace file handle may have been lost. For example, a compiled grammar can be written to a file and emailed. Marpa cannot rely on finding the original trace file handle available and open when the compiled grammar is decompiled.

Marpa compiles and decompiles a grammar as part of its deep copy processing phase. Internally, the deep copy processing phase saves the trace file handle of the original grammar to a temporary, then restores it using the trace file handle argument of decompile().

Parse::Marpa::precompute(grammar) or $grammar->precompute()

Takes as its only argument a grammar object and performs the precomputation phase on it. It returns the grammar object or throws an exception.

DIAGNOSTIC METHODS

Methods primarily useful for debugging grammars and parses are dealt with in the separate document on diagnostics.

OPTIONS

These are the options recognized by the Parse::Marpa::new(), Parse::Marpa::Parse::new(), and Parse::Marpa::set() methods. When the same option is specified in two different method calls, the most recent overrides any previous setting, unless stated otherwise in the description of the option.

Most options set Marpa predefineds, which can also be set using the high-level grammar interfaces. A few options don't deal with Marpa's predefined variables and are special to the new() and set() methods. These "method only" options are documented in this section.

The options which set Marpa's predefineds variables are documented in the section on predefineds, below. Options for debugging grammars and parses are dealt with in the separate document on diagnostics.

grammar

Takes as its value a grammar object. Only valid as an option to Parse::Marpa::Parse::new(), where it's a required option.

source

This takes as its value a reference to a string containing a description of the grammar in the Marpa Demonstartion Language. It must be specified before any rules are added, and may be specified at most once in the life of a grammar object.

PREDEFINEDS

This section documents Marpa's predefined variables. There are two ways to set these. The most basic is as method options: options of the Parse::Marpa::new(), Parse::Marpa::Parse::new(), and Parse::Marpa::set() methods. The other way to set them is as high-level interface options: indirectly through one of Marpa's high-level grammar interfaces.

This section discusses the semantics of each of Marpa's predefineds, which is the same whether it is set as a method options or as a high-level interface option. It also discusses the details of setting predefineds as method options. The name of a Marpa predefined variables is always the same as the option name for the corresponding method option.

High level grammar interfaces are free to use their own conventions to deal with Marpa's predefined variables. The documentation of MDL describes, and the documentation of every high level interface should describe, which predefineds can be set through that interface, how they are set, along with any special considerations for that interface.

Unless specified otherwise, when a predefined is set more than once, a "later" setting replaces any previous one. When the predefined was set in two different method calls, the "later" setting is the one in the method that was called last. If the same predefined is set twice in a single method call, once as a high-level interface option in source provided as the value to a source method option, and once directly as a method option, the method option is be considered to be the "later" of the two.

ambiguous_lex

Treats its value as a boolean. If true, ambiguous lexing is used. This means that even if a terminal is matched by a closure or a regex, the search for other terminals at that location continues. If multiple terminals match, all the tokens found are considered in the parse and all may end up being used if the parse is ambiguous. Ambiguous lexing is the default.

If false, Marpa does unambiguous lexing, as is standard in parser generators. Lexing at each location ends when the first terminal matches, and the user must ensure the first terminal to match is the correct one. Traditionally, users have done this by making their lex patterns deterministic -- in other words, set up in such a way that every valid input can be lexed in one and only one way.

In Marpa, users opting for unambiguous lexing have a second alternative. The order in which terminals are tested can be manipulated by setting their priorities.

code_lines

If there is a problem with user supplied code, Marpa prints the error message and a description of where the code is being used. Marpa will display the code itself as well. The value of this option tells Marpa how many lines to print before truncating the code. If it's zero, no code is displayed. If it's negative, all the code is displayed, no matter how long it is. The default is 30 lines.

default_action

Takes as its value a string, which is expected to be Perl 5 code. For rules which don't have an explicitly specified action, the default is to return a Perl 5 undefined. This default is usually adequate, but it can be changed by setting the default_action predefined.

default_lex_prefix

The value must be a Perl 5 regex. The lexers allow every terminal to specify a lex prefix, a pattern to be matched and discarded before the pattern for the terminal itself is matched. This is typically used to handle leading whitespace.

The default is for there to be no lex prefix. Whitespace processing is often wanted, and when it is, it is usually the same for most or all terminals. This can be convenient to accomplish by changing the default lex prefix.

default_null_value

The value must be a string containing Perl 5 code. The null value of a symbol is its value when it matches the empty string in a parse. By default the value is a Perl undefined. This predefined allows you to reset that default. There's more about null values in the CONCEPTS document.

online

A boolean. If true, the parser runs in online mode. If false, the parser runs in offline mode.

In offline mode, which is the default, Marpa assumes the input has ended when the first parse is requested. It does some final bookkeeping, refuses to accept any more input, and sets its default parse to be a parse of the entire input, from beginning to end.

In online mode, which is under construction and poorly tested, new tokens may still be added, and final bookkeeping is never done. Marpa's default idea is still to parse the entire input up to the current earleme, but in online mode that may often not be what the user wants. If it's not, it up to her to determine the right places to look for complete parses, based on her knowledge of the structure of the grammar and the input. The method Parse::Marpa::Parse::find_complete_rule(), documented as a diagnostic method, may help.

preamble

The preamble is a string which contains Perl 5 code. The preamble is run in a namespace special to the parse object. Semantic actions and lexing closures are run in this same namespace. The preamble is run first, and may be used to set up globals.

If multiple preambles are specified as method options, the most recent replaces any previous ones. This is consistent with the behavior of other method options, but different from the MDL, in which preambles are concatenated.

semantics

The value is a string specifying the semantics used in the semantic actions. The only available semantics at this writing is perl5.

trace_file_handle

The value is a file handle. Warnings and trace output go to the trace file handle. By default it's STDERR.

version

If present, the version option must match the current Marpa version exactly. This is because while Marpa is in alpha, features may change dramatically from version to version and no effort will be invested in making versions compatibile. This difficult version regime will be relaxed by the time Marpa leaves beta.

volatile

The volatile option is used to mark a grammar or parse object as volatile or non-volatile. Not using this option and accepting the default behavior is always safe.

A value of 1 marks the object volatile. A value of 0 marks it non-volatile. Parses inherit the volatility marking, if any, of the grammar they are created from. If a parse is created from a grammar without a volatility marking, and none is specified when it is created, the parse is marked volatile.

When a parse object is marked non-volatile, an optimization called "node value memoization" is enabled. Parses should only marked non-volatile only if a parse object's semantic actions can be safely memoized.

If an object is ever marked volatile, resetting it back to non-volatile is almost certainly a dangerous oversight. Marpa throws an exception if you do that. For this purpose a grammar and the parse created from it are considered to be the same object.

This exception will be thrown even when Marpa marked the grammar volatile on its own. Marpa often does this when a grammar has sequence productions.

For more details about volatility, see "the CONCEPTS document:Parse::Marpa::CONCEPTS".

warnings

The value is a boolean. If true, it enables warnings about inaccessible and unproductive rules in the grammar. Warnings are written to the trace file handle. By default, warnings are on.

Inaccessible rules are those which can never be produced by the start symbol. Unproductive rules are those which no possible input could ever match. Marpa is capable of simply ignoring these, if the remaining rules specify a useable grammar.

Inaccessible and unproductive rules sometimes indicate errors in the grammar design. But a user may have plans for them, may wish to keep them as notes, or may simply wish to look at them at another time.

IMPLEMENTATION NOTES

Namespaces

For semantic actions and lexing closures, there is a special namespace for each parse object, which is entirely the user's. In the Parse::Marpa Parse::Marpa::Lex Parse::Marpa::MDL and the Parse::Marpa::Parse namespaces, users should use only documented methods. In Parse::Marpa::Read_Only users should used only documented variables, and those on a read-only basis. (Staying read-only can be tricky when dealing with Perl 5 arrays. Be careful about auto-vivification!) Users should not rely on or modify anything in any of Marpa's other namespaces.

String References

It's often said by those experienced in Perl that passing string refs instead of strings is a pointless and even counter-productive optimization. I agree, but Marpa is an exception. Marpa expects to process and output entire files, some of which might be very long.

Object Orientation

Use of object orientation in Marpa is superficial. Only grammars and parses are objects, and they are not designed to be inherited.

Returns and Exceptions

Most Marpa methods return only if successful. On failure they throw an exception using croak(). If you don't want the exception to be fatal, catch it using eval.

A few failures are considered "non-exceptional" and returned. All non-exceptional faulures are described in the documentation for the method which returns them.

AUTHOR

Jeffrey Kegler

DEPENDENCIES

Requires Perl 5.10. Users who want or need the maturity and/or stability of Perl 5.8 or earlier probably are also best off with more mature and stable alternatives to Marpa.

LIMITATIONS

Speed

Speed seems remarkably good for an Earley's implementation. In fact, the current bottlenecks seem not to be in the Marpa parse engine, but in the lexing, and in the design of the Marpa Demonstration Language.

Ambiguous Lexing and Speed

Ambiguous lexing has a cost, and grammars which can turn ambiguous lexing off can expect to parse twice as fast. Right now when Marpa tries to lex multiple regexes at a single location, it does so using an individual regex match for each terminal, one after another.

There may be a more efficient way to use Perl 5 regexes to return all of the matches from a set of alternatives. A complication is that precompilation is not possible. Marpa does predictive lexing and the possibilities are not known until shortly before the match is attempted, But I believe that lazy evaluation and memoizing could have big payoffs in the cases of most interest.

The Marpa Demonstration Language and Speed

The Marpa Demonstration Language was written to show off a wide range of Marpa's capabilities. A high-level grammar interface written without this agenda might easily run faster.

As a reminder, if the MDL's parsing speed becomes an issue with a particular grammar, that grammar can be precompiled. Subsequent runs from the precompiled grammar won't incur the overhead of either MDL parsing or precomputation.

About Speed and Parsers

In considering speed, it's useful for users to be aware of Marpa's position in the hierarchy of grammars. Marpa parses many grammars which bison, yacc, Parse::Yapp, and Parse::RecDescent cannot. For these, it's clearly faster. When it comes to time efficiency, never is not hard to beat.

Marpa allows grammars to be expressed in their most natural form. It's ideal where programmer time is important relative to running time. Right now, special-purpose needs are often addressed with regexes. This works wonderfully if the grammar involved is regular, but across the Internet many man-years are being spent trying to shoe-horn non-regular grammars into Perl 5 regexes.

Marpa is also a good alternative whenever another parser requires backtracking. Earley's parsers never need to backtrack. They find every possible parse the first time through. Backtracking is a gamble, and one you often find you've made against the odds.

There are grammars with constructs which control backtracking. but to my mind this control at a very high price. Solutions built this way are completely non-intuitive, and hard to work with.

If you know you will be writing an LALR grammar or a regular one, it is a good reason not to use Marpa. When a grammar is LALR or regular, Marpa takes advantage of this and runs faster. But such a grammar will run faster yet on a parser designed for it: bison, yacc and Parse::Yapp for LALR; regexes for regular grammars.

Finally, there are the many situations we need to do some parsing as a one-shot and don't want to have to care what subcategory our grammar falls in. We want to write some quick BNF, do the parsing, and move on. For this, there's Marpa.

BUGS AND MISFEATURES

A More Exhaustive Test Suite

Testing has been intensive, but not exhaustive. The parse engine has been very well exercised, but many combinations of options and features have yet to be tried. To get an idea for what's been well tested, look in the t, or test, directory of the distribution. Any feature not tested there can be assumed to have been only lightly exercized.

Options Code Poorly Organized and Probably Buggy

My strategy for dealing with options to the method calls evolved over time and the code shows it. Most options are only valid at certain points in the parsing, but this is haphazardly enforced and poorly documented. There are probably some just plain ol' bugs. The options code needs to be cleaned up, and the documentation tightened up.

Timing of Semantics Finalization

The value of null objects is calculated while rules are being added. The rest of a parse's semantics are not finalized until the parse object is created. For consistency, Marpa needs to be changed so that value of a null object is not finalized until the creation of the parse object.

Priority Conflicts

If non-default priorities are given to rules, it's possible two rules with different priorities could wind up in the same node of the Marpa SDFA. I won't explain the details of SDFA's (see the as yet unwritten internals document), but Marpa can't proceed when that happens.

I've actually never seen this happen, and one reason the problem is not fixed is that I need to contrive a case where the problem occurs before I make a fix. Otherwise, I can't test it. But if you're the unlucky first person to encounter this, here are the workarounds.

Workaround 1: Marpa will report the rules which caused the conflict. If they can be changed to have the same priority, the problem is solved.

Workaround 2: Instead of using priorities, use multiple parses. That is, instead of using priorities to make the desired parse first in order, allow the "natural" order and iterate through the parses until you get the one you want.

Workaround 3: Make a small change in the grammar. Be aware that the code which creates the SDFA is smart enough so that you'll probably need to make some sort of real change to the target language. Simply writing different rules with the same effect probably won't make the problem go away.

I believe there's a fix to this problem, but it will require not just concocting a way to make it occur, but at least a bit of mathematics. Here's what I think is the fix: Change the SDFA to be a little more non-deterministic, so that there are different SDFA nodes for the different priorities, with empty transitions between them. (Aren't you sorry you asked?)

With a fix of this kind, testing examples (even if they were easier to find) is not sufficient to show correctness. I'll need to show that the current and the fixed SDFA's are "equivalent". That demonstration may need to be a mathematical proof. For now, there's the comfort that the problem seems to be quite rare.

Non-intuitive Parse Order in Unusual Cases

This problem occurs when a production has more than two nullable symbols on the right hand side, so that it is ambiguous, and the semantics are such that order of the parses matters. This doesn't happen in any practical grammars I've tried, perhaps because it's a unnatural way to set up the semantics. But it does happen in textbook grammars.

There is a very straightforward workaround, described below. But the problem needs to be fixed, certainly before Marpa goes beta.

Details: The problem occurs because these productions are rewritten internally by CHAF. A rightmost parse comes first as I have documented, but it is a rightmost parse for the grammar as rewritten by CHAF. This is a bug for pendantic reasons, because CHAF rewritting is supposed to be invisible. It's a bug for practical reasons because the CHAF-driven order is not intuitive, and I can't picture it ever being the desired first choice. Priorities are not a workaround, because priorites cannot be set for rules within a CHAF rewrite.

Workaround: Rewrite the rule for which this is a problem. The problem only occurs where a rule is subject to CHAF rewriting, and CHAF rewrites are only done to rules with more than two nullables on the right hand side. It is always possible to break up a rule into other rules such that at most two nullables occur on the right hand side.

Priorities Cannot Be Set in MDL for Terminals

Priorities cannot be set in MDL for terminals. Fix this before going beta.

Workaround: Use the priorities for rules. Extra rules can be added to simulate terminal priorities.

What! You Found Even More Bugs!

Please report any bugs or feature requests to bug-parse-marpa at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Parse-Marpa. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

You can find documentation for this module with the perldoc command.

perldoc Parse::Marpa

You can also look for information at:

ACKNOWLEDGMENTS

Marpa is the parser described in John Aycock and R. Nigel Horspool's "Practical Earley Parsing", The Computer Journal, Vol. 45, No. 6, 2002, pp. 620-630. I've made significant changes to it, which are documented separately (Parse::Marpa::ALGORITHM). Aycock and Horspool, for their part, built on the algorithm discovered by Jay Earley, and described in his "An efficient context-free parsing algorithm", Communications of the Association for Computing Machinery, 13:2:94-102, 1970.

I'm grateful to Randal Schwartz for his encouragement over the years that I've been working on Marpa. My one conversation about Marpa with Larry Wall was brief and long ago, but his openness to the idea is a major encouragement, and his insights into how humans do programming, how they do languages, and how those two endeavors interconnect, a major influence. More recently, Allison Randal and Patrick Michaud have been generous with their valuable time. They might have preferred that I volunteered as a Parrot cage-cleaner, but if so, they were too polite to say so.

Many at perlmonks.org answered questions for me. Among others, I used answers from chromatic, dragonchild, samtregar and Juerd in the writing this module. I'm equally grateful to those whose answers I didn't use. My inquiries were made while I was thinking out the code and it wasn't always 100% clear what I was after. If the butt is moved after the round, it shouldn't count against the archer.

In writing the Pure Perl version of Marpa, I benefited from studying the work of Francois Desarmenien (Parse::Yapp), Damian Conway (Parse::RecDescent) and Graham Barr (Scalar::Util).

COPYRIGHT & LICENSE

Copyright 2007 Jeffrey Kegler, all rights reserved.

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.