Debian Codegraph @

README

raw
1 NAME
2
3 Parser::MGC - build simple recursive-descent parsers
4
5 SYNOPSIS
6
7 package My::Grammar::Parser;
8 use base qw( Parser::MGC );
9
10 sub parse
11 {
12 my $self = shift;
13
14 $self->sequence_of( sub {
15 $self->any_of(
16 sub { $self->token_int },
17 sub { $self->token_string },
18 sub { \$self->token_ident },
19 sub { $self->scope_of( "(", \&parse, ")" ) }
20 );
21 } );
22 }
23
24 my $parser = My::Grammar::Parser->new;
25
26 my $tree = $parser->from_file( $ARGV[0] );
27
28 ...
29
30 DESCRIPTION
31
32 This base class provides a low-level framework for building
33 recursive-descent parsers that consume a given input string from left
34 to right, returning a parse structure. It takes its name from the m//gc
35 regexps used to implement the token parsing behaviour.
36
37 It provides a number of token-parsing methods, which each extract a
38 grammatical token from the string. It also provides wrapping methods
39 that can be used to build up a possibly-recursive grammar structure, by
40 applying a structure around other parts of parsing code.
41
42 Backtracking
43
44 Each method, both token and structural, atomically either consumes a
45 prefix of the string and returns its result, or fails and consumes
46 nothing. This makes it simple to implement grammars that require
47 backtracking.
48
49 Several structure-forming methods have some form of "optional"
50 behaviour; they can optionally consume some amount of input or take
51 some particular choice, but if the code invoked inside that
52 subsequently fails, the structure can backtrack and take some different
53 behaviour. This is usually what is required when testing whether the
54 structure of the input string matches some part of the grammar that is
55 optional, or has multiple choices.
56
57 However, once the choice of grammar has been made, it is often useful
58 to be able to fix on that one choice, thus making subsequent failures
59 propagate up rather than taking that alternative behaviour. Control of
60 this backtracking is given by the commit method; and careful use of
61 this method is one of the key advantages that Parser::MGC has over more
62 simple parsing using single regexps alone.
63
64 Stall Detection
65
66 Most of the methods in this class have bounded execution time, but some
67 methods ("list_of" and "sequence_of") repeatedly recuse into other code
68 to build up a list of results until some ending condition is reached. A
69 possible class of bug is that whatever they recurse into might
70 successfully match an empty string, and thus make no progress.
71
72 These methods will automatically detect this situation if they
73 repeatedly encounter the same string position more than a certain
74 number of times (given by the stallcount argument). If this count is
75 reached, the entire parse attempt will be aborted by the "die" method.
76
77 CONSTRUCTOR
78
79 new
80
81 $parser = Parser::MGC->new( %args );
82
83 Returns a new instance of a Parser::MGC object. This must be called on
84 a subclass that provides method of the name provided as toplevel, by
85 default called parse.
86
87 Takes the following named arguments
88
89 toplevel => STRING
90
91 Name of the toplevel method to use to start the parse from. If not
92 supplied, will try to use a method called parse.
93
94 patterns => HASH
95
96 Keys in this hash should map to quoted regexp (qr//) references, to
97 override the default patterns used to match tokens. See PATTERNS
98 below
99
100 accept_0o_oct => BOOL
101
102 If true, the token_int method will also accept integers with a 0o
103 prefix as octal.
104
105 stallcount => INT
106
107 Since version 0.21.
108
109 The number of times that the stall-detector would have to see the
110 same position before it aborts the parse attempt. If not supplied, a
111 default of 10 will apply.
112
113 PATTERNS
114
115 The following pattern names are recognised. They may be passed to the
116 constructor in the patterns hash, or provided as a class method under
117 the name pattern_name.
118
119 * ws
120
121 Pattern used to skip whitespace between tokens. Defaults to
122 /[\s\n\t]+/
123
124 * comment
125
126 Pattern used to skip comments between tokens. Undefined by default.
127
128 * int
129
130 Pattern used to parse an integer by token_int. Defaults to
131 /-?(?:0x[[:xdigit:]]+|[[:digit:]]+)/. If accept_0o_oct is given, then
132 this will be expanded to match /0o[0-7]+/ as well.
133
134 * float
135
136 Pattern used to parse a floating-point number by token_float.
137 Defaults to /-?(?:\d*\.\d+|\d+\.)(?:e-?\d+)?|-?\d+e-?\d+/i.
138
139 * ident
140
141 Pattern used to parse an identifier by token_ident. Defaults to
142 /[[:alpha:]_]\w*/
143
144 * string_delim
145
146 Pattern used to delimit a string by token_string. Defaults to /["']/.
147
148 SUBCLASSING METHODS
149
150 The following optional methods may be defined by subclasses, to
151 customise their parsing.
152
153 on_parse_start
154
155 $parser->on_parse_start;
156
157 Since version 0.21.
158
159 If defined, is invoked by the from_* method that begins a new parse
160 operation, just before invoking the toplevel structure method.
161
162 on_parse_end
163
164 $result = $parser->on_parse_end( $result );
165
166 Since version 0.21.
167
168 If defined, is invoked by the from_* method once it has finished the
169 toplevel structure method. This is passed the tentative result from the
170 structure method, and whatever it returns becomes the result of the
171 from_* method itself.
172
173 METHODS
174
175 from_string
176
177 $result = $parser->from_string( $str );
178
179 Parse the given literal string and return the result from the toplevel
180 method.
181
182 from_file
183
184 $result = $parser->from_file( $file, %opts );
185
186 Parse the given file, which may be a pathname in a string, or an opened
187 IO handle, and return the result from the toplevel method.
188
189 The following options are recognised:
190
191 binmode => STRING
192
193 If set, applies the given binmode to the filehandle before reading.
194 Typically this can be used to set the encoding of the file.
195
196 $parser->from_file( $file, binmode => ":encoding(UTF-8)" );
197
198 filename
199
200 $filename = $parser->filename;
201
202 Since version 0.20.
203
204 Returns the name of the file currently being parsed, if invoked from
205 within "from_file".
206
207 from_reader
208
209 $result = $parser->from_reader( \&reader );
210
211 Since version 0.05.
212
213 Parse the input which is read by the reader function. This function
214 will be called in scalar context to generate portions of string to
215 parse, being passed the $parser object. The function should return
216 undef when it has no more string to return.
217
218 $reader->( $parser );
219
220 Note that because it is not generally possible to detect exactly when
221 more input may be required due to failed regexp parsing, the reader
222 function is only invoked during searching for skippable whitespace.
223 This makes it suitable for reading lines of a file in the common case
224 where lines are considered as skippable whitespace, or for reading
225 lines of input interactively from a user. It cannot be used in all
226 cases (for example, reading fixed-size buffers from a file) because two
227 successive invocations may split a single token across the buffer
228 boundaries, and cause parse failures.
229
230 pos
231
232 $pos = $parser->pos;
233
234 Since version 0.09.
235
236 Returns the current parse position, as a character offset from the
237 beginning of the file or string.
238
239 take
240
241 $str = $parser->take( $len );
242
243 Since version 0.16.
244
245 Returns the next $len characters directly from the input, prior to any
246 whitespace or comment skipping. This does not take account of any
247 end-of-scope marker that may be pending. It is intended for use by
248 parsers of partially-binary protocols, or other situations in which it
249 would be incorrect for the end-of-scope marker to take effect at this
250 time.
251
252 where
253
254 ( $lineno, $col, $text ) = $parser->where;
255
256 Returns the current parse position, as a line and column number, and
257 the entire current line of text. The first line is numbered 1, and the
258 first column is numbered 0.
259
260 fail
261
262 fail_from
263
264 $parser->fail( $message );
265
266 $parser->fail_from( $pos, $message );
267
268 fail_from since version 0.09.
269
270 Aborts the current parse attempt with the given message string. The
271 failure message will include the line and column position, and the line
272 of input that failed at the current parse position (fail), or a
273 position earlier obtained using the pos method (fail_from).
274
275 This failure will propagate up to the inner-most structure parsing
276 method that has not been committed; or will cause the entire parser to
277 fail if there are no further options to take.
278
279 die
280
281 die_from
282
283 $parser->die( $message );
284
285 $parser->die_from( $pos, $message );
286
287 Since version 0.20.
288
289 Throws an exception that propagates as normal for die, entirely out of
290 the entire parser and to the caller of the toplevel from_* method that
291 invoked it, bypassing all of the back-tracking logic.
292
293 This is much like using core's die directly, except that the message
294 string will include the line and column position, and the line of input
295 that the parser was working on, as it does in the "fail" method.
296
297 This method is intended for reporting fatal errors where the parsed
298 input was correctly recognised at a grammar level, but is requesting
299 something that cannot be fulfilled semantically.
300
301 warn
302
303 warn_from
304
305 $parser->warn( $message );
306
307 $parser->warn_from( $pos, $message );
308
309 Since version 0.22.
310
311 Issues a warning as normal for the warn core Perl function, appending
312 information to the message string giving the current line and column
313 position and the line of input the parser was working on, as it does in
314 the "fail" method.
315
316 at_eos
317
318 $eos = $parser->at_eos;
319
320 Returns true if the input string is at the end of the string.
321
322 scope_level
323
324 $level = $parser->scope_level;
325
326 Since version 0.05.
327
328 Returns the number of nested scope_of calls that have been made.
329
330 include_string
331
332 $result = $parser->include_string( $str, %opts );
333
334 Since version 0.21.
335
336 Parses a given string into the existing parser object.
337
338 The current parser state is moved aside from the duration of this
339 method, and is replaced by the given string. Then the toplevel parser
340 method (or a different as specified) is invoked over it. Its result is
341 returned by this method.
342
343 This would typically be used to handle some sort of "include" or "macro
344 expansion" ability, by injecting new content in as if the current parse
345 location had encountered it. Other than the internal parser state,
346 other object fields are not altered, so whatever effects the invoked
347 parsing methods will have on it can continue to inspect and alter it as
348 required.
349
350 The following options are recognised:
351
352 filename => STRING
353
354 If set, provides a filename (or other descriptive text) to pretend
355 for the source of this string. It need not be a real file on the
356 filesystem; it could for example explain the source of the string in
357 some other way. It is the value reported by the "filename" method and
358 printed in failure messages.
359
360 toplevel => STRING | CODE
361
362 If set, provides the toplevel parser method to use within this
363 inclusion, overriding the object's defined default.
364
365 STRUCTURE-FORMING METHODS
366
367 The following methods may be used to build a grammatical structure out
368 of the defined basic token-parsing methods. Each takes at least one
369 code reference, which will be passed the actual $parser object as its
370 first argument.
371
372 Anywhere that a code reference is expected also permits a plain string
373 giving the name of a method to invoke. This is sufficient in many
374 simple cases, such as
375
376 $self->any_of(
377 'token_int',
378 'token_string',
379 ...
380 );
381
382 maybe
383
384 $ret = $parser->maybe( $code );
385
386 Attempts to execute the given $code in scalar context, and returns what
387 it returned, accepting that it might fail. $code may either be a CODE
388 reference or a method name given as a string.
389
390 $ret = $parser->maybe( $code, @args );
391
392 Since version 0.22 this method passes any additional arguments into the
393 invoked code. This is especially useful if the $code is a method name.
394
395 If the code fails (either by calling fail itself, or by propagating a
396 failure from another method it invoked) before it has invoked commit,
397 then none of the input string will be consumed; the current parsing
398 position will be restored. undef will be returned in this case.
399
400 If it calls commit then any subsequent failure will be propagated to
401 the caller, rather than returning undef.
402
403 This may be considered to be similar to the ? regexp qualifier.
404
405 sub parse_declaration
406 {
407 my $self = shift;
408
409 [ $self->parse_type,
410 $self->token_ident,
411 $self->maybe( sub {
412 $self->expect( "=" );
413 $self->parse_expression
414 } ),
415 ];
416 }
417
418 scope_of
419
420 $ret = $parser->scope_of( $start, $code, $stop );
421
422 Expects to find the $start pattern, then attempts to execute the given
423 $code, then expects to find the $stop pattern. Returns whatever the
424 code returned. $code may either be a CODE reference of a method name
425 given as a string.
426
427 While the code is being executed, the $stop pattern will be used by the
428 token parsing methods as an end-of-scope marker; causing them to raise
429 a failure if called at the end of a scope.
430
431 sub parse_block
432 {
433 my $self = shift;
434
435 $self->scope_of( "{", 'parse_statements', "}" );
436 }
437
438 If the $start pattern is undefined, it is presumed the caller has
439 already checked for this. This is useful when the stop pattern needs to
440 be calculated based on the start pattern.
441
442 sub parse_bracketed
443 {
444 my $self = shift;
445
446 my $delim = $self->expect( qr/[\(\[\<\{]/ );
447 $delim =~ tr/([<{/)]>}/;
448
449 $self->scope_of( undef, 'parse_body', $delim );
450 }
451
452 This method does not have any optional parts to it; any failures are
453 immediately propagated to the caller.
454
455 committed_scope_of
456
457 $ret = $parser->committed_scope_of( $start, $code, $stop );
458
459 Since version 0.16.
460
461 A variant of "scope_of" that calls "commit" after a successful match of
462 the start pattern. This is usually what you want if using scope_of from
463 within an any_of choice, if no other alternative following this one
464 could possibly match if the start pattern has.
465
466 list_of
467
468 $ret = $parser->list_of( $sep, $code );
469
470 Expects to find a list of instances of something parsed by $code,
471 separated by the $sep pattern. Returns an ARRAY ref containing a list
472 of the return values from the $code. A single trailing delimiter is
473 allowed, and does not affect the return value. $code may either be a
474 CODE reference or a method name given as a string. It is called in list
475 context, and whatever values it returns are appended to the eventual
476 result - similar to perl's map.
477
478 This method does not consider it an error if the returned list is
479 empty; that is, that the scope ended before any item instances were
480 parsed from it.
481
482 sub parse_numbers
483 {
484 my $self = shift;
485
486 $self->list_of( ",", 'token_int' );
487 }
488
489 If the code fails (either by invoking fail itself, or by propagating a
490 failure from another method it invoked) before it has invoked commit on
491 a particular item, then the item is aborted and the parsing position
492 will be restored to the beginning of that failed item. The list of
493 results from previous successful attempts will be returned.
494
495 If it calls commit within an item then any subsequent failure for that
496 item will cause the entire list_of to fail, propagating that to the
497 caller.
498
499 sequence_of
500
501 $ret = $parser->sequence_of( $code );
502
503 A shortcut for calling list_of with an empty string as separator;
504 expects to find at least one instance of something parsed by $code,
505 separated only by skipped whitespace.
506
507 This may be considered to be similar to the + or * regexp qualifiers.
508
509 sub parse_statements
510 {
511 my $self = shift;
512
513 $self->sequence_of( 'parse_statement' );
514 }
515
516 The interaction of failures in the code and the commit method is
517 identical to that of list_of.
518
519 any_of
520
521 $ret = $parser->any_of( @codes );
522
523 Since version 0.06.
524
525 Expects that one of the given code instances can parse something from
526 the input, returning what it returned. Each code instance may indicate
527 a failure to parse by calling the fail method or otherwise propagating
528 a failure. Each code instance may either be a CODE reference or a
529 method name given as a string.
530
531 This may be considered to be similar to the | regexp operator for
532 forming alternations of possible parse trees.
533
534 sub parse_statement
535 {
536 my $self = shift;
537
538 $self->any_of(
539 sub { $self->parse_declaration; $self->expect(";") },
540 sub { $self->parse_expression; $self->expect(";") },
541 sub { $self->parse_block },
542 );
543 }
544
545 If the code for a given choice fails (either by invoking fail itself,
546 or by propagating a failure from another method it invoked) before it
547 has invoked commit itself, then the parsing position restored and the
548 next choice will be attempted.
549
550 If it calls commit then any subsequent failure for that choice will
551 cause the entire any_of to fail, propagating that to the caller and no
552 further choices will be attempted.
553
554 If none of the choices match then a simple failure message is printed:
555
556 Found nothing parseable
557
558 As this is unlikely to be helpful to users, a better message can be
559 provided by the final choice instead. Don't forget to commit before
560 printing the failure message, or it won't count.
561
562 $self->any_of(
563 'token_int',
564 'token_string',
565 ...,
566
567 sub { $self->commit; $self->fail( "Expected an int or string" ) }
568 );
569
570 commit
571
572 $parser->commit;
573
574 Calling this method will cancel the backtracking behaviour of the
575 innermost maybe, list_of, sequence_of, or any_of structure forming
576 method. That is, if later code then calls fail, the exception will be
577 propagated out of maybe, no further list items will be attempted by
578 list_of or sequence_of, and no further code blocks will be attempted by
579 any_of.
580
581 Typically this will be called once the grammatical structure alter has
582 been determined, ensuring that any further failures are raised as real
583 exceptions, rather than by attempting other alternatives.
584
585 sub parse_statement
586 {
587 my $self = shift;
588
589 $self->any_of(
590 ...
591 sub {
592 $self->scope_of( "{",
593 sub { $self->commit; $self->parse_statements; },
594 "}" ),
595 },
596 );
597 }
598
599 Though in this common pattern, "committed_scope_of" may be used
600 instead.
601
602 TOKEN PARSING METHODS
603
604 The following methods attempt to consume some part of the input string,
605 to be used as part of the parsing process.
606
607 expect
608
609 $str = $parser->expect( $literal );
610
611 $str = $parser->expect( qr/pattern/ );
612
613 @groups = $parser->expect( qr/pattern/ );
614
615 Expects to find a literal string or regexp pattern match, and consumes
616 it. In scalar context, this method returns the string that was
617 captured. In list context it returns the matching substring and the
618 contents of any subgroups contained in the pattern.
619
620 This method will raise a parse error (by calling fail) if the regexp
621 fails to match. Note that if the pattern could match an empty string
622 (such as for example qr/\d*/), the pattern will always match, even if
623 it has to match an empty string. This method will not consider a
624 failure if the regexp matches with zero-width.
625
626 maybe_expect
627
628 $str = $parser->maybe_expect( ... );
629
630 @groups = $parser->maybe_expect( ... );
631
632 Since version 0.10.
633
634 A convenient shortcut equivalent to calling expect within maybe, but
635 implemented more efficiently, avoiding the exception-handling set up by
636 maybe. Returns undef or an empty list if the match fails.
637
638 substring_before
639
640 $str = $parser->substring_before( $literal );
641
642 $str = $parser->substring_before( qr/pattern/ );
643
644 Since version 0.06.
645
646 Expects to possibly find a literal string or regexp pattern match. If
647 it finds such, consume all the input text before but excluding this
648 match, and return it. If it fails to find a match before the end of the
649 current scope, consumes all the input text until the end of scope and
650 return it.
651
652 This method does not consume the part of input that matches, only the
653 text before it. It is not considered a failure if the substring before
654 this match is empty. If a non-empty match is required, use the fail
655 method:
656
657 sub token_nonempty_part
658 {
659 my $self = shift;
660
661 my $str = $parser->substring_before( "," );
662 length $str or $self->fail( "Expected a string fragment before ," );
663
664 return $str;
665 }
666
667 Note that unlike most of the other token parsing methods, this method
668 does not consume either leading or trailing whitespace around the
669 substring. It is expected that this method would be used as part a
670 parser to read quoted strings, or similar cases where whitespace should
671 be preserved.
672
673 nonempty_substring_before
674
675 $str = $parser->nonempty_substring_before( $literal );
676
677 $str = $parser->nonempty_substring_before( qr/pattern/ );
678
679 Since version 0.20.
680
681 A variant of "substring_before" which fails if the matched part is
682 empty.
683
684 The example above could have been written:
685
686 sub token_nonempty_part
687 {
688 my $self = shift;
689
690 return $parser->nonempty_substring_before( "," );
691 }
692
693 This is often useful for breaking out of repeating loops; e.g.
694
695 sub token_escaped_string
696 {
697 my $self = shift;
698 $self->expect( '"' );
699
700 my $ret = "";
701 1 while $self->any_of(
702 sub { $ret .= $self->nonempty_substring_before( qr/%|$/m ); 1 }
703 sub { my $escape = ( $self->expect( qr/%(.)/ ) )[1];
704 $ret .= _handle_escape( $escape );
705 1 },
706 sub { 0 },
707 )
708
709 return $ret;
710 }
711
712 generic_token
713
714 $val = $parser->generic_token( $name, $re, $convert );
715
716 Since version 0.08.
717
718 Expects to find a token matching the precompiled regexp $re. If
719 provided, the $convert CODE reference can be used to convert the string
720 into a more convenient form. $name is used in the failure message if
721 the pattern fails to match.
722
723 If provided, the $convert function will be passed the parser and the
724 matching substring; the value it returns is returned from
725 generic_token.
726
727 $convert->( $parser, $substr )
728
729 If not provided, the substring will be returned as it stands.
730
731 This method is mostly provided for subclasses to define their own token
732 types. For example:
733
734 sub token_hex
735 {
736 my $self = shift;
737 $self->generic_token( hex => qr/[0-9A-F]{2}h/, sub { hex $_[1] } );
738 }
739
740 token_int
741
742 $int = $parser->token_int;
743
744 Expects to find an integer in decimal, octal or hexadecimal notation,
745 and consumes it. Negative integers, preceded by -, are also recognised.
746
747 token_float
748
749 $float = $parser->token_float;
750
751 Since version 0.04.
752
753 Expects to find a number expressed in floating-point notation; a
754 sequence of digits possibly prefixed by -, possibly containing a
755 decimal point, possibly followed by an exponent specified by e followed
756 by an integer. The numerical value is then returned.
757
758 token_number
759
760 $number = $parser->token_number;
761
762 Since version 0.09.
763
764 Expects to find a number expressed in either of the above forms.
765
766 token_string
767
768 $str = $parser->token_string;
769
770 Expects to find a quoted string, and consumes it. The string should be
771 quoted using " or ' quote marks.
772
773 The content of the quoted string can contain character escapes similar
774 to those accepted by C or Perl. Specifically, the following forms are
775 recognised:
776
777 \a Bell ("alert")
778 \b Backspace
779 \e Escape
780 \f Form feed
781 \n Newline
782 \r Return
783 \t Horizontal Tab
784 \0, \012 Octal character
785 \x34, \x{5678} Hexadecimal character
786
787 C's \v for vertical tab is not supported as it is rarely used in
788 practice and it collides with Perl's \v regexp escape. Perl's \c for
789 forming other control characters is also not supported.
790
791 token_ident
792
793 $ident = $parser->token_ident;
794
795 Expects to find an identifier, and consumes it.
796
797 token_kw
798
799 $keyword = $parser->token_kw( @keywords );
800
801 Expects to find a keyword, and consumes it. A keyword is defined as an
802 identifier which is exactly one of the literal values passed in.
803
804 EXAMPLES
805
806 Accumulating Results Using Variables
807
808 Although the structure-forming methods all return a value, obtained
809 from their nested parsing code, it can sometimes be more convenient to
810 use a variable to accumulate a result in instead. For example, consider
811 the following parser method, designed to parse a set of name: "value"
812 assignments, such as might be found in a configuration file, or
813 YAML/JSON-style mapping value.
814
815 sub parse_dict
816 {
817 my $self = shift;
818
819 my %ret;
820 $self->list_of( ",", sub {
821 my $key = $self->token_ident;
822 exists $ret{$key} and $self->fail( "Already have a mapping for '$key'" );
823
824 $self->expect( ":" );
825
826 $ret{$key} = $self->parse_value;
827 } );
828
829 return \%ret
830 }
831
832 Instead of using the return value from list_of, this method accumulates
833 values in the %ret hash, eventually returning a reference to it as its
834 result. Because of this, it can perform some error checking while it
835 parses; namely, rejecting duplicate keys.
836
837 TODO
838
839 * Make unescaping of string constants more customisable. Possibly
840 consider instead a parse_string_generic using a loop over
841 substring_before.
842
843 * Easy ability for subclasses to define more token types as methods.
844 Perhaps provide a class method such as
845
846 __PACKAGE__->has_token( hex => qr/[0-9A-F]+/i, sub { hex $_[1] } );
847
848 * Investigate how well from_reader can cope with buffer splitting
849 across other tokens than simply skippable whitespace
850
851 AUTHOR
852
853 Paul Evans <[email protected]>
854