Regexp::Grammars - Add grammatical parsing features to Perl 5.10 regexes
This document describes Regexp::Grammars version 1.002
use Regexp::Grammars; my $parser = qr{ (?: <Verb> # Parse and save a Verb in a scalar <.ws> # Parse but don't save whitespace <Noun> # Parse and save a Noun in a scalar <type={ rand > 0.5 ? 'VN' : 'VerbNoun' }> # Save result of expression in a scalar | (?: <[Noun]> # Parse a Noun and save result in a list (saved under the key 'Noun') <[PostNoun=ws]> # Parse whitespace, save it in a list # (saved under the key 'PostNoun') )+ <Verb> # Parse a Verb and save result in a scalar (saved under the key 'Verb') <type={ 'VN' }> # Save a literal in a scalar | <debug: match> # Turn on the integrated debugger here <.Cmd= (?: mv? )> # Parse but don't capture a subpattern (name it 'Cmd' for debugging purposes) <[File]>+ # Parse 1+ Files and save them in a list (saved under the key 'File') <debug: off> # Turn off the integrated debugger here <Dest=File> # Parse a File and save it in a scalar (saved under the key 'Dest') ) ################################################################ <token: File> # Define a subrule named File <.ws> # - Parse but don't capture whitespace <MATCH= ([\w-]+) > # - Parse the subpattern and capture # matched text as the result of the # subrule <token: Noun> # Define a subrule named Noun cat | dog | fish # - Match an alternative (as usual) <rule: Verb> # Define a whitespace-sensitive subrule eats # - Match a literal (after any space) <Object=Noun>? # - Parse optional subrule Noun and # save result under the key 'Object' | # Or else... <AUX> # - Parse subrule AUX and save result <part= (eaten|seen) > # - Match a literal, save under 'part' <token: AUX> # Define a whitespace-insensitive subrule (has | is) # - Match an alternative and capture (?{ $MATCH = uc $^N }) # - Use captured text as subrule result }x; # Match the grammar against some text... if ($text =~ $parser) { # If successful, the hash %/ will have the hierarchy of results... process_data_in( %/ ); }
use Regexp::Grammars; Allow enhanced regexes in lexical scope %/ Result-hash for successful grammar match
<grammar: GRAMMARNAME> Define a named grammar that can be inherited <extends: GRAMMARNAME> Current grammar inherits named grammar's rules
<rule: RULENAME> Define rule with magic whitespace <token: RULENAME> Define rule without magic whitespace <objrule: CLASS= NAME> Define rule that blesses return-hash into class <objtoken: CLASS= NAME> Define token that blesses return-hash into class <objrule: CLASS> Shortcut for above (rule name derived from class) <objtoken: CLASS> Shortcut for above (token name derived from class)
<RULENAME> Call named subrule (may be fully qualified) save result to $MATCH{RULENAME} <%HASH> Match longest possible key of hash <ALIAS= RULENAME> Call subrule, save result in $MATCH{ALIAS} <ALIAS= %HASH> Match a hash key, save in $MATCH{ALIAS} <ALIAS= ( PATTERN )> Match pattern, save match in $MATCH{ALIAS} <ALIAS= (?{ CODE })> Execute code, save value in $MATCH{ALIAS} <.SUBRULE> Call any kind of subrule (as above), but don't save the result in %MATCH <[SUBRULE]> Call any kind of subrule (as above) but append result instead of overwriting it <SUBRULE1> ** <SUBRULE2> Match one or more repetitions of SUBRULE1 as long as they're separated by SUBRULE2
$CAPTURE Alias for $^N (the most recent paren capture) $CONTEXT Another alias for $^N $INDEX Current index of next matching position in string %MATCH Current rule's result-hash $MATCH Magic override value (returned instead of result-hash) $DEBUG Current match-time debugging mode
<require: (?{ CODE })> Fail if code evaluates false <debug: COMMAND > Change match-time debugging mode <error: TEXT|CODEBLOCK> Queue text or value as an error message <logfile: LOGFILE> Change debugging log file (default: STDERR) <log: (?{ CODE }) > Explicitly add a message to the log
This module adds a small number of new regex constructs that can be used within Perl 5.10 patterns to implement complete recursive-descent parsing.
Perl 5.10 already supports recursive=descent matching, via the new (?<name>...) and (?&name) constructs. For example, here is a simple matcher for a subset of the LaTeX markup language:
(?<name>...)
(?&name)
$matcher = qr{ (?&File) (?(DEFINE) (?<File> (?&Element)* ) (?<Element> \s* (?&Command) | \s* (?&Literal) ) (?<Command> \\ \s* (?&Literal) \s* (?&Options)? \s* (?&Args)? ) (?<Options> \[ \s* (?:(?&Option) (?:\s*,\s* (?&Option) )*)? \s* \]) (?<Args> \{ \s* (?&Element)* \s* \} ) (?<Option> \s* [^][\$&%#_{}~^\s,]+ ) (?<Literal> \s* [^][\$&%#_{}~^\s]+ ) ) }xms
This technique makes it possible to use regexes to recognize complex, hierarchical--and even recursive--textual structures. The problem is that Perl 5.10 doesn't provide any support for extracting that hierarchical data into nested data structures. In other words, using Perl 5.10 you can match complex data, but not parse it into an internally useful form.
An additional problem when using Perl 5.10 regexes to match complex data formats is that you have to make sure you remember to insert whitespace-matching constructs (such as \s*) at every possible position where the data might contain ignorable whitespace. This reduces the readability of such patterns, and increases the chance of errors (typically caused by overlooking a location where whitespace might appear).
\s*
The Regexp::Grammars module solves both those problems.
If you import the module into a particular lexical scope, it preprocesses any regex in that scope, so as to implement a number of extensions to the standard Perl 5.10 regex syntax. These extensions simplify the task of defining and calling subrules within a grammar, and allow those subrule calls to capture and retain the components of they match in a proper hierarchical manner.
For example, the above LaTeX matcher could be converted to a full LaTeX parser (and considerably tidied up at the same time), like so:
use Regexp::Grammars; $parser = qr{ <File> <rule: File> <[Element]>* <rule: Element> <Command> | <Literal> <rule: Command> \\ <Literal> <Options>? <Args>? <rule: Options> \[ <[Option]> ** (,) \] <rule: Args> \{ <[Element]>* \} <rule: Option> [^][\$&%#_{}~^\s,]+ <rule: Literal> [^][\$&%#_{}~^\s]+ }xms
Note that there is no need to explicitly place \s* subpatterns throughout the rules; that is taken care of automatically.
If the Regexp::Grammars version of this regex were successfully matched against some appropriate LaTeX document, each rule would call the subrules specified within it, and then return a hash containing whatever result each of those subrules returned, with each result indexed by the subrule's name.
That is, if the rule named Command were invoked, it would first try to match a backslash, then it would call the three subrules <Literal>, <Options>, and <Args> (in that sequence). If they all matched successfully, the Command rule would then return a hash with three keys: 'Literal', 'Options', and 'Args'. The value for each of those hash entries would be whatever result-hash the subrules themselves had returned when matched.
Command
<Literal>
<Options>
<Args>
'Literal'
'Options'
'Args'
In this way, each level of the hierarchical regex can generate hashes recording everything its own subrules matched, so when the entire pattern matches, it produces a tree of nested hashes that represent the structured data the pattern matched.
For example, if the previous regex grammar were matched against a string containing:
\documentclass[a4paper,11pt]{article} \author{D. Conway}
it would automatically extract a data structure equivalent to the following (but with several extra "empty" keys, which are described in "Subrule results"):
{ 'file' => { 'element' => [ { 'command' => { 'literal' => 'documentclass', 'options' => { 'option' => [ 'a4paper', '11pt' ], }, 'args' => { 'element' => [ 'article' ], } } }, { 'command' => { 'literal' => 'author', 'args' => { 'element' => [ { 'literal' => 'D.', }, { 'literal' => 'Conway', } ] } } } ] } }
The data structure that Regexp::Grammars produces from a regex match is available to the surrounding program in the magic variable %/.
%/
Regexp::Grammars provides many features that simplify the extraction of hierarchical data via a regex match, and also some features that can simplify the processing of that data once it has been extracted. The following sections explain each of those features, and some of the parsing techniques they support.
Just add:
use Regexp::Grammars;
to any lexical scope. Any regexes within that scope will automatically now implement the new parsing constructs:
use Regexp::Grammars; my $parser = qr/ regex with $extra <chocolatey> grammar bits /x;
Note that you will need to use the /x modifier when declaring a regex grammar. Otherwise, the default "a whitespace character matches exactly that whitespace character" behaviour of Perl regexes will mess up your grammar's parsing.
/x
Once the grammar has been processed, you can then match text against the extended regexes, in the usual manner (i.e. via a =~ match):
=~
if ($input_text =~ $parser) { ... }
After a successful match, the variable %/ will contain a series of nested hashes representing the structured hierarchical data captured during the parse.
A Regexp::Grammars specification consists of a start-pattern (which may include both standard Perl 5.10 regex syntax, as well as special Regexp::Grammars directives), followed by one or more rule or token definitions.
For example:
use Regexp::Grammars; my $balanced_brackets = qr{ # Start-pattern... <paren_pair> | <brace_pair> # Rule definition... <rule: paren_pair> \( (?: <escape> | <paren_pair> | <brace_pair> | [^()] )* \) # Rule definition... <rule: brace_pair> \{ (?: <escape> | <paren_pair> | <brace_pair> | [^{}] )* \} # Token definition... <token: escape> \\ . }xms;
The start-pattern at the beginning of the grammar acts like the "top" rule of the grammar, and must be matched completely for the grammar to match.
The rules and tokens are declarations only and they are not directly matched. Instead, they act like subroutines, and are invoked by name from the initial pattern (or from within a rule or token).
Each rule or token extends from the directive that introduces it up to either the next rule or token directive, or (in the case of the final rule or token) to the end of the grammar.
The difference between a token and a rule is that a token treats any whitespace within it exactly as a normal Perl regular expression would. That is, a sequence of whitespace in a token is ignored if the /x modifier is in effect, or else matches the same literal sequence of whitespace characters (if /x is not in effect).
In a rule, any sequence of whitespace (except those at the very start and the very end of the rule) is treated as matching the implicit subrule <.ws>, which is automatically predefined to match optional whitespace (i.e. \s*).
<.ws>
You can explicitly define a <ws> token to change that default behaviour. For example, you could alter the definition of "whitespace" to include Perlish comments, by adding an explicit <token: ws>:
<ws>
<token: ws>
<token: ws> (?: \s+ | #[^\n]* )*
But be careful not to define <ws> as a rule, as this will lead to all kinds of infinitely recursive unpleasantness.
To invoke a rule to match at any point, just enclose the rule's name in angle brackets (like in Perl 6). There must be no space between the opening bracket and the rulename. For example::
qr{ file: # Match literal sequence 'f' 'i' 'l' 'e' ':' <name> # Call <rule: name> <options>? # Call <rule: options> (it's okay if it fails) <rule: name> # etc. }x;
If you need to match a literal pattern that would otherwise look like a subrule call, just backslash-escape the leading angle:
qr{ file: # Match literal sequence 'f' 'i' 'l' 'e' ':' \<name> # Match literal sequence '<' 'n' 'a' 'm' 'e' '>' <options>? # Call <rule: options> (it's okay if it fails) <rule: name> # etc. }x;
If a subrule call successfully matches, the result of that match is a reference to a hash. That hash reference is stored in the current rule's own result-hash, under the name of the subrule that was invoked. The hash will, in turn, contain the results of any more deeply nested subrule calls, each stored under the name by which the nested subrule was invoked.
In other words, if the rule sentence is defined:
sentence
<rule: sentence> <noun> <verb> <object>
then successfully calling the rule:
<sentence>
causes a new hash entry at the current nesting level. That entry's key will be 'sentence' and its value will be a reference to a hash, which in turn will have keys: 'noun', 'verb', and 'object'.
'sentence'
'noun'
'verb'
'object'
In addition each result-hash has one extra key: the empty string. The value for this key is whatever string the entire subrule call matched. So, for example, a successful call to <sentence> might add something like the following to the current result-hash:
sentence => { "" => 'I saw a dog', noun => 'I', verb => 'saw', object => { "" => 'a dog', article => 'a', noun => 'dog', }, }
Note, however, that if the result-hash at any level contains only the empty-string key (i.e. the subrule did not call any sub-subrules or save any of their nested result-hashes), then the hash is "unpacked" and just the matched substring itself if returned.
For example, if <rule: sentence> had been defined:
<rule: sentence>
<rule: sentence> I see dead people
then a successful call to the rule would only add:
sentence => 'I see dead people'
to the current result-hash.
This is a useful feature because it prevents a series of nested subrule calls from producing very unwieldy data structures. For example, without this automatic unpacking, even the simple earlier example:
would produce something needlessly complex, such as:
sentence => { "" => 'I saw a dog', noun => { "" => 'I', }, verb => { "" => 'saw', }, object => { "" => 'a dog', article => { "" => 'a', }, noun => { "" => 'dog', }, }, }
It is not always convenient to have subrule results stored under the same name as the rule itself. Rule names should be optimized for understanding the behaviour of the parser, whereas result names should be optimized for understanding the structure of the data. Often those two goals are identical, but not always; sometimes rule names need to describe what the data looks like, while result names need to describe what the data means.
For example, sometimes you need to call the same rule twice, to match two syntactically identical components whose positions give then semantically distinct meanings:
<rule: copy_cmd> copy <file> <file>
The problem here is that, if the second call to <file> succeeds, its result-hash will be stored under the key 'file', clobbering the data that was returned from the first call to <file>.
<file>
'file'
To avoid such problems, Regexp::Grammars allows you to alias any subrule call, so that it is still invoked by the original name, but its result-hash is stored under a different key. The syntax for that is: <alias=rulename>. For example:
<alias=rulename>
<rule: copy_cmd> copy <from=file> <to=file>
Here, <rule: file> is called twice, with the first result-hash being stored under the key 'from', and the second result-hash being stored under the key 'to'.
<rule: file>
'from'
'to'
Note, however, that the alias before the = must be a proper identifier (i.e. a letter or underscore, followed by letters, digits, and/or underscores). Aliases that start with an underscore and aliases named MATCH have special meaning (see "Private subrule calls" and "Result distillation" respectively).
=
MATCH
Aliases can also be useful for normalizing data that may appear in different formats and sequences. For example:
<rule: copy_cmd> copy <from=file> <to=file> | dup <to=file> as <from=file> | <from=file> -> <to=file> | <to=file> <- <from=file>
Here, regardless of which order the old and new files are specified, the result-hash always gets:
copy_cmd => { from => 'oldfile', to => 'newfile', }
If a subrule call is quantified with a repetition specifier:
<rule: file_sequence> <file>+
then each repeated match overwrites the corresponding entry in the surrounding rule's result-hash, so only the result of the final repetition will be retained. That is, if the above example matched the string "foo.pl bar.py baz.php", then the result-hash would contain:
"foo.pl bar.py baz.php"
file_sequence { "" => 'foo.pl bar.py baz.php', file => 'baz.php', }
Usually, that's not the desired outcome, so Regexp::Grammars provides another mechanism by which to call a subrule; one that saves all repetitions of its results.
A regular subrule call consists of the rule's name surrounded by angle brackets. If, instead, you surround the rule's name with <[...]> (angle and square brackets) like so:
<[...]>
<rule: file_sequence> <[file]>+
then the rule is invoked in exactly the same way, but the result of that submatch is pushed onto an array nested inside the appropriate result-hash entry. In other words, if the above example matched the same "foo.pl bar.py baz.php" string, the result-hash would contain:
file_sequence { "" => 'foo.pl bar.py baz.php', file => [ 'foo.pl', 'bar.py', 'baz.php' ], }
This "listifying subrule call" can also be useful for non-repeated subrule calls, if the same subrule is invoked in several places in a grammar. For example if a cmdline option could be given either one or two values, you might parse it:
<rule: size_option> -size <[size]> (?: x <[size]> )?
The result-hash entry for 'size' would then always contain an array, with either one or two elements, depending on the input being parsed.
'size'
Listifying subrules can also be given aliases, just like ordinary subrules. The alias is always specified inside the square brackets:
<rule: size_option> -size <[size=pos_integer]> (?: x <[size=pos_integer]> )?
Here, the sizes are parsed using the pos_integer rule, but saved in the result-hash in an array under the key 'size'.
pos_integer
Aliases can also be given to standard Perl subpatterns, as well as to code blocks within a regex. The syntax for subpatterns is:
<ALIAS= (SUBPATTERN) >
In other words, the syntax is exactly like an aliased subrule call, except that the rule name is replaced with a set of parentheses containing the subpattern. Any parentheses--capturing or non-capturing--will do.
The effect of aliasing a standard subpattern is to cause whatever that subpattern matches to be saved in the result-hash, using the alias as its key. For example:
<rule: file_command> <cmd=(mv|cp|ln)> <from=file> <to=file>
Here, the <cmd=(mv|cp|ln)> is treated exactly like a regular (mv|cp|ln), but whatever substring it matches is saved in the result-hash under the key 'cmd'.
<cmd=(mv|cp|ln)>
(mv|cp|ln)
'cmd'
The syntax for aliasing code blocks is:
<ALIAS= (?{ your($code->here) }) >
Note, however, that the code block must be specified in the standard Perl 5.10 regex notation: (?{...}). A common mistake is to write:
(?{...})
<ALIAS= { your($code->here } >
instead, which will attempt to interpolate $code before the regex is even compiled, as such variables are only "protected" from interpolation inside a (?{...}).
$code
When correctly specified, this construct executes the code in the block and saves the result of that execution in the result-hash, using the alias as its key. Aliased code blocks are useful for adding semantic information based on which branch of a rule is executed. For example, consider the copy_cmd alternatives shown earlier:
copy_cmd
Using aliased code blocks, you could add an extra field to the result- hash to describe which form of the command was detected, like so:
<rule: copy_cmd> copy <from=file> <to=file> <type=(?{ 'std' })> | dup <to=file> as <from=file> <type=(?{ 'rev' })> | <from=file> -> <to=file> <type=(?{ 'fwd' })> | <to=file> <- <from=file> <type=(?{ 'bwd' })>
Now, if the rule matched, the result-hash would contain something like:
copy_cmd => { from => 'oldfile', to => 'newfile', type => 'fwd', }
Note that, in addition to the semantics described above, aliased subpatterns and code blocks also become visible to Regexp::Grammars' integrated debugger (see Debugging).
By default, every subrule call saves its result into the result-hash, either under its own name, or under an alias.
However, sometimes you may want to refactor some literal part of a rule into one or more subrules, without having those submatches added to the result-hash. The syntax for calling a subrule, but ignoring its return value is:
<.SUBRULE>
(which is stolen directly from Perl 6).
For example, you may prefer to rewrite a rule such as:
<rule: paren_pair> \( (?: <escape> | <paren_pair> | <brace_pair> | [^()] )* \)
without any literal matching, like so:
<rule: paren_pair> <.left_paren> (?: <escape> | <paren_pair> | <brace_pair> | <.non_paren> )* <.right_paren> <token: left_paren> \( <token: right_paren> \) <token: non_paren> [^()]
Moreover, as the individual components inside the parentheses probably aren't being captured for any useful purpose either, you could further optimize that to:
<rule: paren_pair> <.left_paren> (?: <.escape> | <.paren_pair> | <.brace_pair> | <.non_paren> )* <.right_paren>
Note that you can also use the dot modifier on an aliased subpattern:
<.Alias= (SUBPATTERN) >
This seemingly contradictory behaviour (of giving a subpattern a name, then deliberately ignoring that name) actually does make sense in one situation. Providing the alias makes the subpattern visible to the debugger, while using the dot stops it from affecting the result-hash. See "Debugging non-grammars" for an example of this usage.
If a rule name (or an alias) begins with an underscore:
<_RULENAME> <_ALIAS=RULENAME> <[_RULENAME]> <[_ALIAS=RULENAME]>
then matching proceeds as normal, and any result that is returned is stored in the current result-hash in the usual way.
However, when any rule finishes (and just before it returns) it first filters its result-hash, removing any entries whose keys begin with an underscore. This means that any subrule with an underscored name (or with an underscored alias) remembers its result, but only until the end of the current rule. Its results are effectively private to the current rule.
This is especially useful in conjunction with result distillation.
One of the commonest tasks in text parsing is to match a list of unspecified length, in which items are separated by a fixed token. Things like:
1, 2, 3 , 4 ,13, 91 # Numbers separated by commas and spaces g-c-a-g-t-t-a-c-a # Bases separated by dashes /usr/local/bin # Names separated by directory markers /usr:/usr/local:bin # Directories separated by colons
The usual construct required to parse these kinds of structures is either:
<rule: list> <item> <separator> <list # recursive definition | <item> # base case
Or, more efficiently, but less prettily:
<rule: list> <[item]> (?: <separator> <[item]> )* # iterative definition
Because this is such a common requirement, Regexp::Grammars provides a cleaner way to specify the iterative version. The syntax is taken from Perl 6:
<rule: list> <[item]> ** <separator> # iterative definition
This is a repetition specifier on the first subrule (hence the use of ** as the marker, to reflect the repetitive behaviour of *). However, the number of repetitions is controlled by the second subrule: the first subrule will be repeatedly matched for as long as the second subrule matches immediately after it.
**
*
So, for example, you can match a sequence of numbers separated by commas with:
<[number]> ** <comma> <token: number> \d+ <token: comma> \s* , \s*
Note that it's important to use the <[...]> form for the items being matched, so that all of them are saved in the result hash. You can also save all the separators (if that's important):
<[number]> ** <[comma]>
The repeated item must be specified as a subrule call fo some kind, but the separators may be specified either as a subrule or a bracketed pattern. For example:
<[number]> ** ( , )
The separator must always be specified in matched delimiters of some kind: either matching <...> or matching (...). A common error is to write:
<...>
(...)
<[number]> ** ,
You can also use a pattern as the item matcher, but it must be aliased into a subrule:
<[item=(\d+)]> ** ( , )
In some situations a grammar may need a rule that matches dozens, hundreds, or even thousands of one-word alternatives. For example, when matching command names, or valid userids, or English words. In such cases it is often impractical (and always inefficient) to list all the alternatives between | alterators:
|
<rule: shell_cmd> a2p | ac | apply | ar | automake | awk | ... # ...and 400 lines later ... | zdiff | zgrep | zip | zmore | zsh <rule: valid_word> a | aa | aal | aalii | aam | aardvark | aardwolf | aba | ... # ...and 40,000 lines later... ... | zymotize | zymotoxic | zymurgy | zythem | zythum
To simplify such cases, Regexp::Grammars provides a special construct that allows you to specify all the alternatives as the keys of a normal hash. The syntax for that construct is simply to put the hash name inside angle brackets (with no space between the angles and the hash name).
Which means that the rules in the previous example could also be written:
<rule: shell_cmd> <%cmds> <rule: valid_word> <%dict>
provided that the two hashes (%cmds and %dict) are visible in the scope where the grammar is created.
%cmds
%dict
Internally, the construct is converted to something equivalent to:
<rule: shell_cmd> (<.hk>) <require: exists $cmds{$CAPTURE}> <rule: valid_word> (<.hk>) <require: exists $dict{$CAPTURE}>
The special <hk> rule is created automatically, and defaults to \S+, but you can also define it explicitly to handle other kinds of keys. For example:
<hk>
\S+
<rule: hk> .+ # Key may be any number of chars on a single line <rule: hk> [ACGT]{10,} # Key is a base sequence of at least 10 pairs
Matching a hash key in this way is typically significantly faster than matching a large set of alternations. Specifically, it is O(length of longest potential key) ^ 2, instead of O(number of keys).
All the grammars shown so far are confined to a single regex. However, Regexp::Grammars also provides a mechanism that allows you to defined named grammars, which can then be imported into other regexes. This gives the a way of modularizing common grammatical components.
You can create a named grammar using the <grammar:...> directive. This directive must appear before the first rule definition in the grammar, and instead of any start-rule. For example:
<grammar:...>
qr{ <grammar: List::Generic> <rule: List> <MATCH=[Item]> ** <Separator> <rule: Item> \S++ <token: Separator> \s* , \s* }x;
Thsi creates a grammar named List::Generic, and installs it in the module's internal caches, for future reference.
List::Generic
Note that there is no need (or reason) to assign the resulting regex to a variable, as the named grammar cannot itself be matched against.
To make use of a named grammar, you need to incorporate it into another grammar, by inheritance. To do that, use the <extends:...> directive, like so:
<extends:...>
my $parser = qr{ <extends: List::Generic> <List> }x;
The <extends:...> directive incorporates the rules defined in the specified grammar into the current regex. You can then call any of those rules in the start-pattern.
Subrule dispatch within a grammar is always polymorphic. That is, when a subrule is called, the most-derived rule of the same name within the grammar's hierarchy is invoked.
So, to replace a particular rule within grammar, you simply need to inherit that grammar and specify new, more-specific versions of any rules you want to change. For example:
my $list_of_integers = qr{ <List> # Inherit rules from base grammar... <extends: List::Generic> # Replace Item rule from List::Generic... <rule: Item> [+-]? \d++ }x;
You can also use <extends:...> in other named grammars, to create hierarchies:
qr{ <grammar: List::Integral> <extends: List::Generic> <token: Item> [+-]? <MATCH=(<.Digit>+)> <token: Digit> \d }x; qr{ <grammar: List::ColonSeparated> <extends: List::Generic> <token: Separator> \s* : \s* }x; qr{ <grammar: List::Integral::ColonSeparated> <extends: List::Integral> <extends: List::ColonSeparated> }x;
As shown in the previous example, Regexp::Grammars allows you to multiply inherit two (or more) base grammars. For example, the List::Integral::ColonSeparated grammar takes the definitions of List and Item from the List::Integral grammar, and the definition of Separator from List::ColonSeparated.
List::Integral::ColonSeparated
List
Item
List::Integral
Separator
List::ColonSeparated
Note that grammars dispatch subrule calls using C3 method lookup, rather than Perl's older DFS lookup. That's why List::Integral::ColonSeparated correctly gets the more-specific Separator rule defined in List::ColonSeparated, rather than the more-generic version defined in List::Generic (via List::Integral). See perldoc mro for more discussion of the C3 dispatch algorithm.
perldoc mro
Instead of replacing an inherited rule, you can augment it.
For example, if you need a grammar for lists of hexademical numbers, you could inherit the behaviour of List::Integral and add the hex digits to its Digit token:
Digit
my $list_of_hexadecimal = qr{ <List> <extends: List::Integral> <token: Digit> <List::Integral::Digit> | [A-Fa-f] }x;
If you call a subrule using a fully qualified name (such as <List::Integral::Digit>), the grammar calls that version of the rule, rather than the most-derived version.
<List::Integral::Digit>
Note, however, that fully qualified subrule calls are not (yet) polymorphically dispatched. This means that you cannot currently just specify the name some ancestor grammar (or SUPER or NEXT for that matter) and have the grammar find the correct inherited version of the subrule. At present you must specify the name of the exact ancestor grammar whose rule you want. This limitation will be removed in a future release.
SUPER
NEXT
Named grammars are independent of each other, even when inherited. This means that, if debugging is enabled in a derived grammar, it will not be active in any rules inherited from a base grammar, unless the base grammar also included a <debug:...> directive.
<debug:...>
This is a deliberate design decision, as activating the debugger adds a significant amount of code to each grammar's implementation, which is detrimental to the matching performance of the resulting regexes.
If you need to debug a named grammar, the best approach is to include a <debug: same> directive at the start of the grammar. The presence of this directive will ensure the necessary extra debugging code is included in the regex implementing the grammar, while setting same mode will ensure that the debugging mode isn't altered when the matcher uses the inherited rules.
<debug: same>
same
Normally, calls to subrules produce nested result-hashes within the current result-hash. Those nested hashes always have at least one automatically supplied key (""), whose value is the entire substring that the subrule matched.
""
If there are no other nested captures within the subrule, there will be no other keys in the result-hash. This would be annoying as a typical nested grammar would then produce results consisting of hashes of hashes, with each nested hash having only a single key (""). This in turn would make postprocessing the result-hash (in %/) far more complicated than it needs to be.
To avoid this behaviour, if a subrule's result-hash doesn't contain any keys except "", the module "flattens" the result-hash, by replacing it with the value of its single key.
So, for example, the grammar:
mv \s* <from> \s* <to> <rule: from> [\w/.-]+ <rule: to> [\w/.-]+
doesn't return a result-hash like this:
{ "" => 'mv /usr/local/lib/libhuh.dylib /dev/null/badlib', 'from' => { "" => '/usr/local/lib/libhuh.dylib' }, 'to' => { "" => '/dev/null/badlib' }, }
Instead, it returns:
{ "" => 'mv /usr/local/lib/libhuh.dylib /dev/null/badlib', 'from' => '/usr/local/lib/libhuh.dylib', 'to' => '/dev/null/badlib', }
That is, because the 'from' and 'to' subhashes each have only a single entry, they are each "flattened" to the value of that entry.
This flattening also occurs if a result-hash contains only "private" keys (i.e. keys starting with underscores). For example:
mv \s* <from> \s* <to> <rule: from> <_dir=path>? <_file=filename> <rule: to> <_dir=path>? <_file=filename> <token: path> [\w/.-]*/ <token: filename> [\w.-]+
Here, the from rule produces a result like this:
from
from => { "" => '/usr/local/bin/perl', _dir => '/usr/local/bin/', _file => 'perl', }
which is automatically stripped of "private" keys, leaving:
from => { "" => '/usr/local/bin/perl', }
which is then automatically flattened to:
from => '/usr/local/bin/perl'
Regexp::Grammars also offers full manual control over the distillation process. If you use the reserved word MATCH as the alias for a subrule call:
<MATCH=filename>
or a subpattern match:
<MATCH=( \w+ )>
or a code block:
<MATCH=(?{ 42 })>
then the current rule will treat the return value of that subrule, pattern, or code block as its complete result, and return that value instead of the usual result-hash it constructs. This is the case even if the result has other entries that would normally also be returned.
For example, in a rule like:
<rule: term> <MATCH=literal> | <left_paren> <MATCH=expr> <right_paren>
The use of MATCH aliases causes the rule to return either whatever <literal> returns, or whatever <expr> returns (provided it's between left and right parentheses).
<literal>
<expr>
Note that, in this second case, even though <left_paren> and <right_paren> are captured to the result-hash, they are not returned, because the MATCH alias overrides the normal "return the result-hash" semantics and returns only what its associated subrule (i.e. <expr>) produces.
<left_paren>
<right_paren>
It's also possible to control what a rule returns from within a code block. Regexp::Grammars provides a set of reserved variables that give direct access to the result-hash.
The result-hash itself can be accessed as %MATCH within any code block inside a rule. For example:
%MATCH
<rule: sum> <X=product> \+ <Y=product> <MATCH=(?{ $MATCH{X} + $MATCH{Y} })>
Here, the rule matches a product (aliased 'X' in the result-hash), then a literal '+', then another product (aliased to 'Y' in the result-hash). The rule then executes the code block, which accesses the two saved values (as $MATCH{X} and $MATCH{Y}), adding them together. Because the block is itself aliased to MATCH, the sum produced by the block becomes the (only) result of the rule.
'X'
'+'
'Y'
$MATCH{X}
$MATCH{Y}
It is also possible to set the rule result from within a code block (instead of aliasing it). The special "override" return value is represented by the special variable $MATCH. So the previous example could be rewritten:
$MATCH
<rule: sum> <X=product> \+ <Y=product> (?{ $MATCH = $MATCH{X} + $MATCH{Y} })
Both forms are identical in effect. Any assignment to $MATCH overrides the normal "return all subrule results" behaviour.
Assigning to $MATCH directly is particularly handy if the result may not always be "distillable", for example:
<rule: sum> <X=product> \+ <Y=product> (?{ if (!ref $MATCH{X} && !ref $MATCH{Y}) { # Reduce to sum, if both terms are simple scalars... $MATCH = $MATCH{X} + $MATCH{Y}; } else { # Return full syntax tree for non-simple case... $MATCH{op} = '+'; } })
Note that you can also partially override the subrule return behaviour. Normally, the subrule returns the complete text it matched under the "empty key" of its result-hash. That is, of course, $MATCH{""}, so you can override just that behaviour by directly assigning to that entry.
$MATCH{""}
For example, if you have a rule that matches key/value pairs from a configuration file, you might prefer that any trailing comments not be included in the "matched text" entry of the rule's result-hash. You could hide such comments like so:
<rule: config_line> <key> : <value> <comment>? (?{ # Edit trailing comments out of "matched text" entry... $MATCH = "$MATCH{key} : $MATCH{value}"; })
Some more examples of the uses of $MATCH:
<rule: FuncDecl> # Keyword Name Keep return the name (as a string)... func <Identifier> ; (?{ $MATCH = $MATCH{'Identifier'} }) <rule: NumList> # Numbers in square brackets... \[ ( \d+ (?: , \d+)* ) \] # Return only the numbers... (?{ $MATCH = $CAPTURE }) <token: Cmd> # Match standard variants then standardize the keyword... (?: mv | move | rename ) (?{ $MATCH = 'mv'; })
Using code blocks in rules, it's often possible to fully process data as you parse it. For example, the <sum> rule shown in the previous section might be part of a simple calculator, implemented entirely in a single grammar. Such a calculator might look like this:
<sum>
my $calculator = do{ use Regexp::Grammars; qr{ <Answer> <rule: Answer> <X=Mult> \+ <Y=Answer> <MATCH= (?{ $MATCH{X} + $MATCH{Y} })> | <X=Mult> - <Y=Answer> <MATCH= (?{ $MATCH{X} - $MATCH{Y} })> | <MATCH=Mult> <rule: Mult> <X=Pow> \* <Y=Mult> <MATCH= (?{ $MATCH{X} * $MATCH{Y} })> | <X=Pow> / <Y=Mult> <MATCH= (?{ $MATCH{X} / $MATCH{Y} })> | <X=Pow> % <Y=Mult> <MATCH= (?{ $MATCH{X} % $MATCH{Y} })> | <MATCH=Pow> <rule: Pow> <X=Term> \^ <Y=Pow> <MATCH= (?{ $MATCH{X} ** $MATCH{Y}; })> | <MATCH=Term> <rule: Term> <MATCH=Literal> | \( <MATCH=Answer> \) <token: Literal> <MATCH= ( [+-]? \d++ (?: \. \d++ )?+ )> }xms }; while (my $input = <>) { if ($input =~ $calculator) { say "--> $/{Answer}"; } }
Because every rule computes a value using the results of the subrules below it, and aliases that result to its MATCH, each rule returns a complete evaluation of the subexpression it matches, passing that back to higher-level rules, which then do the same.
Hence, the result returned to the very top-level rule (i.e. to <Answer>) is the complete evaluation of the entire expression that was matched. That means that, in the very process of having matched a valid expression, the calculator has also computed the value of that expression, which can then simply be printed directly.
<Answer>
It is often possible to have a grammar fully (or sometimes at least partially) evaluate or transform the data it is parsing, and this usually leads to very efficient and easy-to-maintain implementations.
The main limitation of this technique is that the data has to be in a well-structured form, where subsets of the data can be evaluated using only local information. In cases where the meaning of the data is distributed through that data non-hierarchically, or relies on global state, or on external information, it is often better to have the grammar simply construct a complete syntax tree for the data first, and then evaluate that syntax tree separately, after parsing is complete. The following section describes a feature of Regexp::Grammars that can make this second style of data processing simpler and more maintainable.
When a grammar has parsed successfully, the %/ variable will contain a series of nested hashes (and possibly arrays) representing the hierarchical structure of the parsed data.
Typically, the next step is to walk that tree, extracting or converting or otherwise processing that information. If the tree has nodes of many different types, it can be difficult to build a recursive subroutine that can navigate it easily.
A much cleaner solution is possible if the nodes of the tree are proper objects. In that case, you just define a process() or traverse() method for eah of the classes, and have every node call that method on each of its children. For example, if the parser were to return a tree of nodes representing the contents of a LaTeX file, then you could define the following methods:
process()
traverse()
sub Latex::file::explain { my ($self, $level) = @_; for my $element (@{$self->{element}}) { $element->explain($level); } } sub Latex::element::explain { my ($self, $level) = @_; ( $self->{command} || $self->{literal})->explain($level) } sub Latex::command::explain { my ($self, $level) = @_; say "\t"x$level, "Command:"; say "\t"x($level+1), "Name: $self->{name}"; if ($self->{options}) { say "\t"x$level, "\tOptions:"; $self->{options}->explain($level+2) } for my $arg (@{$self->{arg}}) { say "\t"x$level, "\tArg:"; $arg->explain($level+2) } } sub Latex::options::explain { my ($self, $level) = @_; $_->explain($level) foreach @{$self->{option}}; } sub Latex::literal::explain { my ($self, $level, $label) = @_; $label //= 'Literal'; say "\t"x$level, "$label: ", $self->{q{}}; }
and then simply write:
if ($text =~ $LaTeX_parser) { $/{LaTeX_file}->explain(); }
and the chain of explain() calls would cascade down the nodes of the tree, each one invoking the appropriate explain() method according to the type of node encountered.
explain()
The only problem is that, by default, Regexp::Grammars returns a tree of plain-old hashes, not LaTeX::Whatever objects. Fortunately, it's easy to request that the result hashes be automatically blessed into the appropriate classes, using the <objrule:...> and <objtoken:...> directives.
<objrule:...>
<objtoken:...>
These directives are identical to the <rule:...> and <token:...> directives (respectively), except that the rule or token they create will also bless the hash it normally returns, converting it to an object of a specified class.
<rule:...>
<token:...>
The generic syntax for these types of rules and tokens is:
<objrule: CLASS::NAME = RULENAME > <objtoken: CLASS::NAME = TOKENNAME >
<objrule: LaTeX::Element=component> # ...Defines a rule that can be called as <component> # ...and which returns a hash-based LaTeX::Element object <objtoken: LaTex::Literal=atom> # ...Defines a token that can be called as <atom> # ...and which returns a hash-based LaTeX::Literal object
Note that, just as in aliased subrule calls, the name by which something is referred to outside the grammar (in this case, the class name) comes before the =, whereas the name that it is referred to inside the grammar comes after the =.
You can freely mix object-returning and plain-old-hash-returning rules and tokens within a single grammar, though you have to be careful not to subsequently try to call a method on any of the unblessed nodes.
If an <objrule:...> or <objtoken:...> is defined with a class name that is not followed by = and a rule name, then the rule name is determined automatically from the classname. Specifically, the final component of the classname (i.e. after the last ::, if any) is used.
::
<objrule: LaTeX::Element> # ...Defines a rule that can be called as <Element> # ...and which returns a hash-based LaTeX::Element object <objtoken: LaTex::Literal> # ...Defines a token that can be called as <Literal> # ...and which returns a hash-based LaTeX::Literal object <objtoken: Comment> # ...Defines a token that can be called as <Comment> # ...and which returns a hash-based Comment object
Regexp::Grammars provides a number of features specifically designed to help debug both grammars and the data they parse.
All debugging messages are written to a log file (which, by default, is just STDERR). However, you can specify a disk file explicitly by placing a <logfile:...> directive at the start of your grammar:
<logfile:...>
$grammar = qr{ <logfile: LaTeX_parser_log > \A <LaTeX_file> \Z # Pattern to match <rule: LaTeX_file> # etc. }x;
You can also explicitly specify that messages go to the terminal:
<logfile: - >
Whenever a log file has been directly specified, Regexp::Grammars automatically does verbose static analysis of your grammar. That is, whenever it compiles a grammar containing an explicit <logfile:...> directive it logs a series of messages explaining how it has interpreted the various components of that grammar. For example, the following grammar:
<logfile: parser_log > <cmd> <rule: cmd> mv <from=file> <to=file> | cp <source> <[file]> <.comment>?
would produce the following analysis in the 'parser_log' file:
info | Processing the main regex before any rule definitions | | | |...Treating <cmd> as: | | | match the subrule <cmd> | | \ saving the match in $MATCH{'cmd'} | | | \___End of main regex | info | Defining a rule: <cmd> | |...Returns: a hash | | | |...Treating ' mv ' as: | | \ normal Perl regex syntax | | | |...Treating <from=file> as: | | | match the subrule <file> | | \ saving the match in $MATCH{'from'} | | | |...Treating <to=file> as: | | | match the subrule <file> | | \ saving the match in $MATCH{'to'} | | | |...Treating ' | cp ' as: | | \ normal Perl regex syntax | | | |...Treating <source> as: | | | match the subrule <source> | | \ saving the match in $MATCH{'source'} | | | |...Treating <[file]> as: | | | match the subrule <file> | | \ appending the match to $MATCH{'file'} | | | |...Treating <.comment>? as: | | | match the subrule <comment> if possible | | \ but don't save anything | | | \___End of rule definition
This kind of static analysis is a useful starting point in debugging a miscreant grammar, because it enables you to see what you actually specified (as opposed to what you thought you'd specified).
Regexp::Grammars also provides a simple interactive debugger, with which you can observe the process of parsing and the data being collected in any result-hash.
To initiate debugging, place a <debug:...> directive anywhere in your grammar. When parsing reaches that directive the debugger will be activated, and the command specified in the directive immediately executed. The available commands are:
<debug: on> - Enable debugging, stop when entire grammar matches <debug: match> - Enable debugging, stope when a rule matches <debug: try> - Enable debugging, stope when a rule is tried <debug: same> - Continue debugging (or not) as currently <debug: off> - Disable debugging and continue parsing silently <debug: continue> - Synonym for <debug: on> <debug: run> - Synonym for <debug: on> <debug: step> - Synonym for <debug: try>
These directives can be placed anywhere within a grammar and take effect when that point is reached in the parsing. Hence, adding a <debug:step> directive is very much like setting a breakpoint at that point in the grammar. Indeed, a common debugging strategy is to turn debugging on and off only around a suspect part of the grammar:
<debug:step>
<rule: tricky> # This is where we think the problem is... <debug:step> <preamble> <text> <postscript> <debug:off>
Once the debugger is active, it steps through the parse, reporting rules that are tried, matches and failures, backtracking and restarts, and the parser's location within both the grammar and the text being matched. That report looks like this:
===============> Trying <grammar> from position 0 > cp file1 file2 |...Trying <cmd> | |...Trying <cmd=(cp)> | | \FAIL <cmd=(cp)> | \FAIL <cmd> \FAIL <grammar> ===============> Trying <grammar> from position 1 cp file1 file2 |...Trying <cmd> | |...Trying <cmd=(cp)> file1 file2 | | \_____<cmd=(cp)> matched 'cp' file1 file2 | |...Trying <[file]>+ file2 | | \_____<[file]>+ matched 'file1' | |...Trying <[file]>+ [eos] | | \_____<[file]>+ matched ' file2' | |...Trying <[file]>+ | | \FAIL <[file]>+ | |...Trying <target> | | |...Trying <file> | | | \FAIL <file> | | \FAIL <target> <~~~~~~~~~~~~~~ | |...Backtracking 5 chars and trying new match file2 | |...Trying <target> | | |...Trying <file> | | | \____ <file> matched 'file2' [eos] | | \_____<target> matched 'file2' | \_____<cmd> matched ' cp file1 file2' \_____<grammar> matched ' cp file1 file2'
The first column indicates the point in the input at which the parser is trying to match, as well as any backtracking or forward searching it may need to do. The remainder of the columns track the parser's hierarchical traversal of the grammar, indicating which rules are tried, which succeed, and what they match.
Provided the logfile is a terminal (as it is by default), the debugger also pauses at various points in the parsing process--before trying a rule, after a rule succeeds, or at the end of the parse--according to the most recent command issued. When it pauses, you can issue a new command by entering a single letter:
m - to continue until the next subrule matches t or s - to continue until the next subrule is tried r or c - to continue to the end of the grammar o - to switch off debugging
Note that these are the first letters of the corresponding <debug:...> commands, listed earlier. Just hitting ENTER while the debugger is paused repeats the previous command.
While the debugger is paused you can also type a 'd', which will display the result-hash for the current rule. This can be useful for detecting which rule isn't returning the data you expected.
<log:...>
Both static and interactive debugging send a series of predefined log messages to whatever log file you have specified. It is also possible to send additional, user-defined messages to the log, using the <log:...> directive.
This directive expects either a simple text or a codeblock as its single argument. If the argument is a code block, that code is expected to return the text of the message; if the argument is anything else, that something else is the literal message. For example:
<rule: ListElem> <Elem= ( [a-z]\d+) > <log: Checking for a suffix, too...> <Suffix= ( : \d+ ) >? <log: (?{ "ListElem: $MATCH{Elem} and $MATCH{Suffix}" })>
User-defined log messages implemented using a codeblock can also specify a severity level. If the codeblock of a <log:...> directive returns two or more values, the first is treated as a log message severity indicator, and the remaining values as separate lines of text to be logged. For example:
<rule: ListElem> <Elem= ( [a-z]\d+) > <Suffix= ( : \d+ ) >? <log: (?{ warn => "Elem was: $MATCH{Elem}", "Suffix was $MATCH{Suffix}", })>
When they are encountered, user-defined log messages are interspersed between any automatic log messages (i.e. from the debugger), at the correct level of nesting for the current rule.
It is possible to use Regexp::Grammars without creating any subrule definitions, simply to debug a recalcitrant regex. For example, if the following regex wasn't working as expected:
my $balanced_brackets = qr{ \( # left delim (?: \\ # escape or | (?R) # recurse or | . # whatever )* \) # right delim }xms;
you could instrument it with aliased subpatterns and then debug it step-by-step, using Regexp::Grammars:
use Regexp::Grammars; my $balanced_brackets = qr{ <debug:step> <.left_delim= ( \( )> (?: <.escape= ( \\ )> | <.recurse= ( (?R) )> | <.whatever=( . )> )* <.right_delim= ( \) )> }xms; while (<>) { say 'matched' if /$balanced_brackets/; }
Note the use of amnesiac aliased subpatterns to avoid needlessly building a result-hash. Alternatively, you could use listifying aliases to preserve the matching structure as an additional debugging aid:
use Regexp::Grammars; my $balanced_brackets = qr{ <debug:step> <[left_delim= ( \( )]> (?: <[escape= ( \\ )]> | <[recurse= ( (?R) )]> | <[whatever=( . )]> )* <[right_delim= ( \) )]> }xms; if ( '(a(bc)d)' =~ /$balanced_brackets/) { use Data::Dumper 'Dumper'; warn Dumper \%/; }
Assuming you have correctly debugged your grammar, the next source of problems will likely be invalid input (especially if that input is being provided interactively). So Regexp::Grammars also provides some support for detecting when a parse is likely to fail...and informing the user why.
The <require:...> directive is useful for testing conditions that it's not easy (or even possible) to check within the syntax of the the regex itself. For example:
<require:...>
<rule: IPV4_Octet_Decimal> # Up three digits... <MATCH= ( \d{1,3}+ )> # ...but less that 256... <require: (?{ $MATCH <= 255 })>
A require expects a regex codeblock as its argument and succeeds if the final value of that codeblock is true. If the final value is false, the directive fails and the rule starts backtracking.
Note, in this example that the digits are matched with \d{1,3}+ . The trailing + prevents the {1,3} repetition from backtracking to a smaller number of digits if the <require:...> fails.
\d{1,3}+
+
{1,3}
The module has limited support for error reporting from within a grammar, in the form of the <error:...> and <warning:...> directives and their shortcuts: <...>, <!!!>, and <???>
<error:...>
<warning:...>
<!!!>
<???>
The <error: MSG> directive queues a conditional error message within @! and then fails to match (that is, it is equivalent to a (?!) when matching). For example:
<error: MSG>
@!
(?!)
<rule: ListElem> <SerialNumber> | <ClientName> | <error: (?{ $errcount++ . ': Missing list element' })>
The error message is conditional in the sense that, if any surrounding rule subsequently matches, the message is automatically removed from @!. This implies that you can queue up as many error messages as you wish, but they will only remain in @! if the match ultimately fails. Moreover, only those error messages originating from rules that actually contributed to the eventual failure-to-match will remain in @!.
If a code block is specified as the argument, the error message is whatever final value is produced when the block is executed. Note that this final value does not have to be a string (though it does have to be a scalar).
<rule: ListElem> <SerialNumber> | <ClientName> | <error: (?{ # Return a hash, with the error information... { errnum => $errcount++, msg => 'Missing list element' } })>
If anything else is specified as the argument, it is treated as a literal error string (and may not contain an unbalanced '<' or '>', nor any interpolated variables).
'<'
'>'
However, if the literal error string begins with "Expected " or "Expecting ", then the error string automatically has the following "context suffix" appended:
, but found '$CONTEXT' instead
qr{ <Arithmetic_Expression> # ...Match arithmetic expression | # Or else <error: Expected a valid expression> # ...Report error, and fail # Rule definitions here... }xms;
On an invalid input this example might produce an error message like:
"Expected a valid expression, but found '(2+3]*7/' instead"
The value of the special $CONTEXT variable is found by looking ahead in the string being matched against, to locate the next sequence of non-blank characters after the current parsing position. This variable may also be explicitly used within the <error: (?{...})> form of the directive.
<error: (?{...})>
As a special case, if you omit the message entirely from the directive, it is supplied automatically, derived from the name of the current rule. For example, if the following rule were to fail to match:
<rule: Arithmetic_expression> <Multiplicative_Expression> ** ([+-]) | <error:>
the error message queued would be:
"Expected arithmetic expression, but found 'one plus two' instead"
Note however, that it is still essential to include the colon in the directive. A common mistake is to write:
<rule: Arithmetic_expression> <Multiplicative_Expression> ** ([+-]) | <error>
which merely attempts to call <rule: error> if the first alternative fails.
<rule: error>
Sometimes, you want to detect problems, but not invalidate the entire parse as a result. For those occasions, the module provides a "less stringent" form of error reporting: the <warning:...> directive.
This directive is exactly the same as an <error:...> in every respect except that it does not induce a failure to match at the point it appears.
The directive is, therefore, useful for reporting non-fatal problems in a parse. For example:
qr{ \A # ...Match only at start of input <ArithExpr> # ...Match a valid arithmetic expression (?: # Should be at end of input... \s* \Z | # If not, report the fact but don't fail... <warning: Expected end-of-input> <warning: (?{ "Extra junk at index $INDEX: $CONTEXT" })> ) # Rule definitions here... }xms;
Note that, because they do not induce failure, two or more <warning:...> directives can be "stacked" in sequence, as in the previous example.
The module also provides three useful shortcuts, specifically to make it easy to declare, but not define, rules and tokens.
The <...> and <???> directives are equivalent to the directive:
<error: Cannot match RULENAME (not implemented)>
The <???> is equivalent to the directive:
<warning: Cannot match RULENAME (not implemented)>
For example, in the following grammar:
<grammar: List::Generic> <rule: List> <[Item]> ** (\s*,\s*) <rule: Item> <...>
the Item rule is declared but not defined. That means the grammar will compile correctly, (the List rule won't complain about a call to a non-existent Item), but if the Item rule isn't overridden in some derived grammar, a match-time error will occur when List tries to match the <...> within Item.
If you intend to use a grammar as part of a larger program that contains other (non-grammatical) regexes, it is more efficient--and less error-prone--to avoid having Regexp::Grammars process those regexes as well. So it's often a good idea to declare your grammar in a do block, thereby restricting the scope of the module's effects.
do
my $grammar = do { use Regexp::Grammars; qr{ <file> <rule: file> <prelude> <data> <postlude> <rule: prelude> # etc. }x; };
Because the effects of Regexp::Grammars are lexically scoped, any regexes defined outside that do block will be unaffected by the module.
Causes all regexes in the current lexical scope to be compile-time processed for grammar elements.
$str =~ $grammar
$str =~ /$grammar/
Attempt to match the grammar against the string, building a nested data structure from it.
This hash is assigned the nested data structure created by any successful match of a grammar regex.
This array is assigned the queue of error messages created by any unsuccessful match attempt of a grammar regex.
<rule: IDENTIFIER>
Define a rule whose name is specified by the supplied identifier.
Everything following the <rule:...> directive (up to the next <rule:...> or <token:...> directive) is treated as part of the rule being defined.
Any whitespace in the rule is replaced by a call to the <.ws> subrule (which defaults to matching \s*, but may be explicitly redefined).
<token: IDENTIFIER>
Everything following the <token:...> directive (up to the next <rule:...> or <token:...> directive) is treated as part of the rule being defined.
Any whitespace in the rule is ignored (under the /x modifier), or explicitly matched (if /x is not used).
<objrule: IDENTIFIER>
<objtoken: IDENTIFIER>
Identical to a <rule: IDENTIFIER> or <token: IDENTIFIER> declaration, except that the rule or token will also bless the hash it normally returns, converting it to an object of a class whose name is the same as the rule or token itself.
<require: (?{ CODE }) >
The code block is executed and if its final value is true, matching continues from the same position. If the block's final value is false, the match fails at that point and starts backtracking.
<error: (?{ CODE }) >
<error: LITERAL TEXT >
<error: >
This directive queues a conditional error message within @! and then fails to match (that is, it is equivalent to a (?!) when matching).
<warning: (?{ CODE }) >
<warning: LITERAL TEXT >
This directive is exactly the same as an <error:...> in every respect except that it does not induce a failure to match at the point it appears. That is, it is equivalent to a (?=) ["succeed and continue matching"], rather than a (?!) ["fail and backtrack"].
(?=)
<debug: COMMAND >
During the matching of grammar regexes send debugging and warning information to the specified log file (see <logfile: LOGFILE>).
<logfile: LOGFILE>
The available COMMAND's are:
COMMAND
<debug: continue> ___ Debug until end of complete parse <debug: run> _/ <debug: on> ___ Debug until next subrule match <debug: match> _/ <debug: try> ___ Debug until next subrule call or match <debug: step> _/ <debug: same> ___ Maintain current debugging mode <debug: off> ___ No debugging
See also the $DEBUG special variable.
$DEBUG
During the compilation of grammar regexes, send debugging and warning information to the specified LOGFILE (or to *STDERR if - is specified).
*STDERR
-
If the specified LOGFILE name contains a %t, it is replaced with a (sortable) "YYYYMMDD.HHMMSS" timestamp. For example:
%t
<logfile: test-run-%t >
executed at around 9.30pm on the 21st of March 2009, would generate a log file named: test-run-20090321.213056
test-run-20090321.213056
<log: (?{ CODE }) >
<log: LITERAL TEXT >
Append a message to the log file. If the argument is a code block, that code is expected to return the text of the message; if the argument is anything else, that something else is the literal message.
If the block returns two or more values, the first is treated as a log message severity indicator, and the remaining values as separate lines of text to be logged.
<IDENTIFIER>
Call the subrule whose name is IDENTIFIER.
If it matches successfully, save the hash it returns in the current scope's result-hash, under the key 'IDENTIFIER'.
'IDENTIFIER'
<IDENTIFIER_1=IDENTIFIER_2>
Call the subrule whose name is IDENTIFIER_1.
If it matches successfully, save the hash it returns in the current scope's result-hash, under the key 'IDENTIFIER_2'.
'IDENTIFIER_2'
In other words, the IDENTIFIER_1= prefix changes the key under which the result of calling a subrule is stored.
IDENTIFIER_1=
<.IDENTIFIER>
Call the subrule whose name is IDENTIFIER. Don't save the hash it returns.
In other words, the "dot" prefix disables saving of subrule results.
<IDENTIFIER= ( PATTERN )>
Match the subpattern PATTERN.
If it matches successfully, capture the substring it matched and save that substring in the current scope's result-hash, under the key 'IDENTIFIER'.
<.IDENTIFIER= ( PATTERN )>
Match the subpattern PATTERN. Don't save the substring it matched.
<IDENTIFIER= %HASH>
Match a sequence of non-whitespace then verify that the sequence is a key in the specified hash
If it matches successfully, capture the sequence it matched and save that substring in the current scope's result-hash, under the key 'IDENTIFIER'.
<%HASH>
Match a key from the hash. Don't save the substring it matched.
<IDENTIFIER= (?{ CODE })>
Execute the specified CODE.
Save the result (of the final expression that the CODE evaluates) in the current scope's result-hash, under the key 'IDENTIFIER'.
<[IDENTIFIER]>
If it matches successfully, append the hash it returns to a nested array within the current scope's result-hash, under the key <'IDENTIFIER'>.
<[IDENTIFIER_1=IDENTIFIER_2]>
If it matches successfully, append the hash it returns to a nested array within the current scope's result-hash, under the key 'IDENTIFIER_2'.
<ANY_SUBRULE> ** <ANY_OTHER_SUBRULE>
<ANY_SUBRULE> ** (PATTERN)
Repeatedly call the first subrule. Keep matching as long as the subrule matches, provided successive matches are separated by matches of the second subrule or the pattern.
In other words, match a list of ANY_SUBRULE's separated by ANY_OTHER_SUBRULE's or PATTERN's.
Note that, if a pattern is used to specify the separator, it must be specified in some kind of matched parentheses. These may be capturing [(...)], non-capturing [(?:...)], non-backtracking [(?>...)], or any other construct enclosed by an opening and closing paren.
(?:...)
(?>...)
$CAPTURE
$CONTEXT
These are both aliases for the built-in read-only $^N variable, which always contains the substring matched by the nearest preceding (...) capture. $^N still works perfectly well, but these are provided to improve the readability of code blocks and error messages respectively.
$^N
$INDEX
This variable contains the index at which the next match will be attempted within the string being parsed. It is most commonly used in <error:...> or <log:...> directives:
<rule: ListElem> <log: (?{ "Trying words at index $INDEX" })> <MATCH=( \w++ )> | <log: (?{ "Trying digits at index $INDEX" })> <MATCH=( \d++ )> | <error: (?{ "Missing ListElem near index $INDEX" })>
This variable contains all the saved results of any subrules called from the current rule. In other words, subrule calls like:
<ListElem> <Separator= (,)>
stores their respective match results in $MATCH{'ListElem'} and $MATCH{'Separator'}.
$MATCH{'ListElem'}
$MATCH{'Separator'}
This variable is an alias for $MATCH{"="}. This is the %MATCH entry for the special "override value". If this entry is defined, its value overrides the usual "return \%MATCH" semantics of a successful rule.
$MATCH{"="}
$_
At the start of any code blocks inside any regex, the variable $_ contains the complete string being matched against. The current matching position within that string is given by: pos($_).
pos($_)
This variable stores the current debugging mode (which may be any of: 'off', 'on', 'run', 'continue', 'match', 'step', or 'try'). It is set automatically by the <debug:...> command, but may also be set manually in a code block (which can be useful for conditional debugging). For example:
'off'
'on'
'run'
'continue'
'match'
'step'
'try'
<rule: ListElem> <Identifier> # Conditionally debug if 'foobar' encountered... (?{ $DEBUG = $MATCH{Identifier} eq 'foobar' ? 'step' : 'off' }) <Modifier>?
See also: the <log: LOGFILE> and <debug: DEBUG_CMD> directives.
<log: LOGFILE>
<debug: DEBUG_CMD>
The additional regex constructs this module provides are implemented by rewriting regular expressions. This is a (safer) form of source filtering, but still subject to all the same limitations and fallibilities of any other macro-based solution.
In particular, rewriting the macros involves the insertion of (a lot of) extra capturing parentheses. This means you can no longer assume that particular capturing parens correspond to particular numeric variables: i.e. to $1, $2, $3 etc. If you want to capture directly use Perl 5.10's named capture construct:
$1
$2
$3
(?<name> [^\W\d]\w* )
Better still, capture the data in its correct hierarchical context using the module's "named subpattern" construct:
<name= ([^\W\d]\w*) >
No recursive descent parser--including those created with Regexp::Grammars--can directly handle left-recursive grammars with rules of the form:
<rule: List> <List> , <ListElem>
If you find yourself attempting to write a left-recursive grammar (which Perl 5.10 may or may not complain about, but will never successfully parse with), then you probably need to use the "separated list" construct instead:
<rule: List> <[ListElem]> ** (,)
Grammatical parsing with Regexp::Grammars can fail if your grammar places "non-backtracking" directives (i.e. the (?>...) block or the ?+, *+, or ++ repetition specifiers) around a subrule call. The problem appears to be that preventing the regex from backtracking through the in-regex actions that Regexp::Grammars adds causes the module's internal stack to fall out of sync with the regex match.
?+
*+
++
For the time being, you need to make sure that grammar rules don't appear inside a "non-backtracking" directive.
Similarly, parsing with Regexp::Grammars will fail if your grammar places a subrule call within a positive look-ahead, since these don't play nicely with the data stack.
This may be an internal problem with perl itself or it may simply be a bug (or perhaps an intrinsic limitation) in the current implementation. Investigations are proceeding.
For the time being, you need to make sure that grammar rules don't appear inside a positive lookahead.
Fully qualified subrule calls are not (yet) polymorphically dispatched. At present you must specify the name of the exact ancestor grammar whose rule you want to use. This limitation will be removed in a future release.
Note that (because the author cannot find a way to throw exceptions from within a regex) none of the following diagnostics actually throws an exception.
Instead, these messages are simply written to the specified parser logfile (or to *STDERR, if no logfile is specified).
However, any fatal match-time message will immediately terminate the parser matching and will still set $@ (as if an exception had been thrown and caught at that point in the code). You then have the option to check $@ immediately after matching with the grammar, and rethrow if necessary:
$@
if ($input =~ $grammar) { process_data_in(\%/); } else { die if $@; }
Found call to %s, but no %s was defined in the grammar
You specified a call to a subrule for which there was no definition in the grammar. Typically that's either because you forget to define the rule, or because you misspelled either the definition or the subrule call. For example:
<file> <rule: fiel> <---- misspelled rule <lines> <---- used but never defined
Regexp::Grammars converts any such subrule call attempt to an instant catastrophic failure of the entire parse, so if your parser ever actually tries to perform that call, Very Bad Things will happen.
Entire parse terminated prematurely while attempting to call non-existent rule: %s
You ignored the previous error and actually tried to call to a subrule for which there was no definition in the grammar. Very Bad Things are now happening. The parser got very upset, took its ball, and went home. See the preceding diagnostic for remedies.
This diagnostic should throw an exception, but can't. So it sets $@ instead, allowing you to trap the error manually if you wish.
Can't match against <grammar: %s>
The regex you attempted to match against defined a pure grammar, using the <grammar:...> directive. Pure grammars have no start-pattern and hence cannot be matched against directly.
You need to define a matchable grammar that inherits from your pure grammar and then calls one of its rules. For example, instead of:
my $greeting = qr{ <grammar: Greeting> <rule: greet> Hi there | Hello | Yo! }xms;
you need:
qr{ <grammar: Greeting> <rule: greet> Hi there | Hello | Yo! }xms; my $greeting = qr{ <extends: Greeting> <greet> }xms;
Multiple definitions for <%s>
You defined two or more rules or tokens with the same name. The first one defined will be used, the rest will be ignored.
To get rid of the warning, get rid of the extra definitions (or, at least, comment them out).
Possible invalid subrule call %s
Your grammar contained something of the form:
<identifier <.identifier <[identifier
which you might have intended to be a subrule call, but which didn't correctly parse as one. If it was supposed to be a Regexp::Grammars subrule call, you need to check the syntax you used. If it wasn't supposed to be a subrule call, you can silence the warning by rewriting it and quoting the leading angle:
\<identifier \<.identifier \<[identifier
Possible invalid directive: %s
<identifier:
but which wasn't a known directive like <rule:...> or <debug:...>. If it was supposed to be a Regexp::Grammars directive, check the spelling of the directive name. If it wasn't supposed to be a directive, you can silence the warning by rewriting it and quoting the leading angle:
\<identifier:
Repeated subrule %s will only capture its final match
You specified a subrule call with a repetition qualifier, such as:
<ListElem>*
or:
<ListElem>+
Because each subrule call saves its result in a hash entry of the same name, each repeated match will overwrite the previous ones, so only the last match will ultimately be saved. If you want to save all the matches, you need to tell Regexp::Grammars to save the sequence of results as a nested array within the hash entry, like so:
<[ListElem]>*
<[ListElem]>+
If you really did intend to throw away every result but the final one, you can silence the warning by placing the subrule call inside any kind of parentheses. For example:
(<ListElem>)*
(?: <ListElem> )+
Regexp::Grammars requires no configuration files or environment variables.
This module only works under Perl 5.10 or later.
This module is likely to be incompatible with any other module that automagically rewrites regexes. For example it may conflict with Regexp::DefaultFlags, Regexp::DeferredExecution, or Regexp::Extended.
No bugs have been reported.
Please report any bugs or feature requests to bug-regexp-grammars@rt.cpan.org, or through the web interface at http://rt.cpan.org.
bug-regexp-grammars@rt.cpan.org
Damian Conway <DCONWAY@CPAN.org>
<DCONWAY@CPAN.org>
Copyright (c) 2009, Damian Conway <DCONWAY@CPAN.org>. All rights reserved.
This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself. See perlartistic.
BECAUSE THIS SOFTWARE IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE SOFTWARE, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE SOFTWARE "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE SOFTWARE IS WITH YOU. SHOULD THE SOFTWARE PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR CORRECTION.
IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE SOFTWARE AS PERMITTED BY THE ABOVE LICENCE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE SOFTWARE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE SOFTWARE TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
To install Regexp::Grammars, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Regexp::Grammars
CPAN shell
perl -MCPAN -e shell install Regexp::Grammars
For more information on module installation, please visit the detailed CPAN module installation guide.