Provided by: libparser-mgc-perl_0.15-2_all bug

NAME

       "Parser::MGC::Examples::EvaluateExpression" - an example parser to evaluate simple
       numerical expressions

DESCRIPTION

       This evaluator-parser takes simple mathematical expressions involving the four basic
       arithmetic operators (+, -, *, /) applied to integers, and returns the numerical result.
       It handles operator precedence, with * and / having a higher level than + and -, and copes
       with parentheses.

       Operator precedence is implemented by using two different parsing functions to handle the
       two different precedence levels.

   Boilerplate
       We start off by declaring a package and subclassing Parser::MGC.

          package ExprParser;
          use base qw( Parser::MGC );

          use strict;
          use warnings;

   parse
       The topmost parsing function, "parse", handles the outermost level of operator precedence,
       the + and - operators. It first parses a single term from the input by callling
       "parse_term" to obtain its value.

       It then uses the "any_of" structure-forming method to look for either a + or - operator
       which would indicate another term will follow it. If it finds either of these, it parses
       the next term from after the operator by another call to "parse_term" and then adds or
       subtracts the value of it from the running total.

       The "any_of" call itself is used as the conditional expression of a "while" loop, to
       ensure it gets called multiple times. Whenever another term has been parsed, the body
       function returns a true value, to indicate that the while loop should be invoked again.
       Only when there are no more + or - operators, indicating no more terms, does the body
       return false, causing the while loop to stop.

       This continues until there are no more + or - operators, when the overall total value is
       returned to the caller.

          sub parse
          {
             my $self = shift;

             my $val = $self->parse_term

             1 while $self->any_of(
                sub { $self->expect( "+" ); $val += $self->parse_term; 1 },
                sub { $self->expect( "-" ); $val -= $self->parse_term; 1 },
                sub { 0 },
             );

             return $val;
          }

       This function recognises input matching the following EBNF grammar:

          EXPR = TERM { ( '+' | '-' ) TERM };

   parse_term
       Called by "parse", the next function is "parse_term" which has a similar structure. This
       function implements the next level of operator precedence, of the * and / operators. In a
       similar fashion to the previous function, this one parses a single factor from the input
       by calling "parse_factor", and then looks for * or / operators, multiplying or dividing
       the value by the next factor it expects to find after those. This continues until there
       are no more * or / operators, when the overall product is returned.

          sub parse_term
          {
             my $self = shift;

             my $val = $self->parse_factor;

             1 while $self->any_of(
                sub { $self->expect( "*" ); $val *= $self->parse_factor; 1 },
                sub { $self->expect( "/" ); $val /= $self->parse_factor; 1 },
                sub { 0 },
             );

             return $val;
          }

       This function recognises input matching the following EBNF grammar:

          TERM = FACTOR { ( '*' | '/' ) FACTOR };

   parse_factor
       Finally, the innermost "parse_factor" function is called by "parse_term" to parse out the
       actual numerical values. This is also the point at which the grammar can recurse,
       recognising a parenthesized expression. It uses an "any_of" with two alternative function
       bodies, to cover these two cases.

       The first case, to handle a parenthesized sub-expression, consists of a call to
       "scope_of". This call would expect to find a "(" symbol to indicate the parenthesized
       expression. If it finds one, it will recurse back to the toplevel "parse" method to obtain
       its value, then expects the final ")" symbol. The value of this factor is then the value
       of the sub-expression contained within the parentheses.

       If the first case fails, because it does not find that leading "(" symbol, the second case
       is attempted instead. This handles an actual integer constant.  This case is simply a call
       to the "token_int" method of the underlying class, which recognises various string forms
       of integer constants, returning their numerical value.

          sub parse_factor
          {
             my $self = shift;

             $self->any_of(
                sub { $self->scope_of( "(", sub { $self->parse }, ")" ) },
                sub { $self->token_int },
             );
          }

       This function recognises input matching the following EBNF grammar:

          FACTOR = '(' EXPR ')'
                 | integer

EXAMPLES OF OPERATION

   A single integer
       The simplest form of operation of this parser is when it is given a single integer value
       as its input; for example "15".

        INPUT:    15
        POSITION: ^

       The outermost call to "parse" will call "parse_term", which in turn calls "parse_factor".

        INPUT:    15
        POSITION  ^
        CALLS:    parse
                   => parse_term
                    => parse_factor

       The "any_of" inside "parse_factor" will first attempt to find a parenthesized sub-
       expression by using "scope_of", but this will fail because it does not start with an open
       parenthesis symbol. The "any_of" will then attempt the second case, calling "token_int"
       which will succeed at obtaining an integer value from the input stream, consuming it by
       advancing the stream position. The value of 15 is then returned by "parse_factor" back to
       "parse_term" where it is stored in the $val lexical.

        INPUT:    15
        POSITION:   ^
        CALLS:    parse
                   => parse_term -- $val = 15

       At this point, the "any_of" inside "parse_term" will attempt to find a * or / operator,
       but both will fail because there is none, causing the final alternative function to be
       invoked, which stops the "while" loop executing.  The value of 15 is then returned to the
       outer caller, "parse". A similar process happens there, where it fails to find a + or -
       operator, and thus the final value of 15 is returned as the result of the entire parsing
       operation.

        INPUT:    15
        OUTPUT:   15

   A simple sum of two integers
       Next lets consider a case that actually requires some real parsing, such as an expression
       requesting the sum of two values; "6 + 9".

        INPUT:    6 + 9
        POSITION: ^

       This parsing operation starts the same as the previous; with "parse" calling "parse_term"
       which in turn calls "parse_factor".

        INPUT:    6 + 9
        POSITION: ^
        CALLS:    parse
                   => parse_term
                    => parse_factor

       As before, the "any_of" inside "parse_factor" first attempts and fails to find a
       parenthesized sub-expression and so tries "token_int" instead. As before this obtains an
       integer value from the stream and advances the position. This value is again returned to
       "parse_term". As before, the "any_of" attempts but fails to find a * or / operator so the
       value gets returned to "parse" to be stored in $val.

        INPUT:    6 + 9
        POSITION:  ^
        CALLS:    parse -- $val = 6

       This time, the "any_of" in the outer "parse" method attempts to find a + operator and
       succeeds, because there is one at the next position in the stream. This causes the first
       case to continue, making another call to "parse_term".

        INPUT:    6 + 9
        POSITION:    ^
        CALLS:    parse -- $val = 6
                   => parse_term

       This call to "parse_term" proceeds much like the first, eventually returning the value 9
       by consuming it from the input stream. This value is added to $val by the code inside the
       "any_of" call.

        INPUT:    6 + 9
        POSITION:      ^
        CALLS:    parse -- $val = 15

       "parse" then calls "any_of" a second time, which attempts to find another operator. This
       time there is none, so it returns false, which stops the "while" loop and the value is
       returned as the final result of the operation.

        INPUT:    6 + 9
        OUTPUT:   15

   Operator precedence
       The two kinds of operators (+ and - vs * and /) are split across two different method
       calls to allow them to implement precedence; to say that some of the operators bind more
       tightly than others. Those operators that are implemented in more inwardly-nested
       functions bind tighter than the ones implemented further out.

       To see this in operation consider an expression that mixes the two kinds of operators,
       such as "15 - 2 * 3"

        INPUT:    15 - 2 * 3
        POSITION: ^

       The parsing operation starts by calling down from "parse" all the way to "token_int" which
       extracts the first integer, 15, from the stream and returns it all the way up to "parse"
       as before:

        INPUT:    15 - 2 * 3
        POSITION:   ^
        CALLS:    parse -- $val = 15

       As before, the "parse" function looks for a * or - operator by its "any_of" test, and
       finds this time the - operator, which then causes it to call "parse_term" to parse its
       value:

        INPUT:    15 - 2 * 3
        POSITION:     ^
        CALLS:    parse -- $val = 15
                   => parse_term

       Again, "parse_term" starts by calling "parse_factor" which extracts the next integer from
       the stream and returns it. "parse_factor" temporarily stores that in its own $val lexical
       (which remember, is a lexical variable local to that call, so is distinct from the one in
       "parse").

        INPUT:    15 - 2 * 3
        POSITION:       ^
        CALLS:    parse -- $val = 15
                   => parse_term -- $val = 2

       This time, when "parse_term" attempts its own "any_of" test to look for a * or / operator,
       it manages to find one. By a process similar to the way that the outer "parse" method
       forms a sum of terms, "parse_term" forms a product of factors by calling down to
       "parse_factor" and accumulating the result.  Here it will call "parse_factor" again, which
       returns the value 3. This gets multiplied into $var.

        INPUT:    15 - 2 * 3
        POSITION:           ^
        CALLS:    parse -- $val = 15
                   => parse_term -- $val = 6

       "parse_term" will try again to look for a * or / operator, but this time fails to find
       one, and so returns its final result, 6, back to "parse", which then subtracts it from its
       own $val.

        INPUT:    15 - 2 * 3
        POSITION:           ^
        CALLS:    parse -- $val = 9

       The outer "parse" call similarly fails to find any more + or - operators and so returns
       the final result of the parsing operation.

        INPUT:    15 - 2 * 3
        OUTPUT:   9

       By implementing the * and / operators separately in a different piece of logic inside the
       one that implements the + and - operators, we have ensured that they operate more
       greedily. That is, that they bind tighter, consuming their values first, before the outer
       + and - operators. This is the way that operator precedence is implemented.

   Parentheses
       This grammar, like many others, provides a way for expressions to override the usual
       operator precedence by supplying a sub-expression in parentheses. The expression inside
       those parentheses is parsed in the usual way, and then its result stands in place of the
       entire parenthesized part, overriding whatever rules might have governed the order between
       those operators inside it and those outside.

       In this parser we implement this as a recursive call, where one possibility of the
       innermost part (the "parse_factor" function or the "FACTOR" EBNF rule) is to recurse back
       to the outermost thing, inside parentheses. This example examines what happens to the
       input string "(15 - 2) * 3".

        INPUT:    (15 - 2) * 3
        POSITION: ^

       As with all the other examples the parsing operation starts by "parse" calling
       "parse_term" which calls "parse_factor". This time, the first case within the "any_of" in
       "parse_factor" does successfully manage to find an open parenthesis, so consumes it. It
       then stores the close parenthesis pattern as the end-of-scope marker, and makes a
       recursive call back to the parse method again.

        INPUT:    (15 - 2) * 3
        POSITION:  ^
        CALLS:    parse
                   => parse_term
                    => parse_factor
                     => parse                 EOS = ")"

       The operation of the inner call to "parse" proceeds much like the first few examples,
       calling down through "parse_term" to "parse_factor" to obtain the 15.

        INPUT:    (15 - 2) * 3
        POSITION:    ^
        CALLS:    parse
                   => parse_term
                    => parse_factor
                     => parse -- $val = 15    EOS = ")"

       Similar to previous examples, this then finds the - operator, and parses another term to
       subtract from it.

        INPUT:    (15 - 2) * 3
        POSITION:        ^
        CALLS:    parse
                   => parse_term
                    => parse_factor
                     => parse -- $val = 13    EOS = ")"

       At this point, the "any_of" test in the inner call to "parse" tries again to look for a +
       or - operator, and this time fails because it believes it is at the end of the input. It
       isn't really at the end of the string, of course, but it believes it to be at the end
       because of the "end-of-scope" pattern that the call to "scope_of" established. This
       pretends that the input has finished whenever the next part of the input matches the end-
       of-scope pattern.

       Because this inner call to "parse" now believes it has got to the end of its input, it
       returns its final answer back to the caller, which in this case was the "scope_of" call
       that "parse_factor" made. As the "scope_of" call returns, it consumes the input matching
       the end-of-scope pattern. This return value is then stored by "parse_term".

        INPUT:    (15 - 2) * 3
        POSITION:         ^
        CALLS:    parse
                   => parse_term -- $val = 13

       At this point, "parse_term" proceeds as before, finding and extracting the * operator and
       calling "parse_factor" a second time, multiplying them together and returning that to the
       outer "parse" call.

        INPUT:    (15 - 2) * 3
        POSITION:             ^
        CALLS:    parse -- $val = 39

       At this point "parse" fails to extract any more operators because it is at the (real) end
       of input, so returns the final answer.

        INPUT:    (15 - 2) * 3
        OUTPUT:   39

perl v5.26.0                                2017-08Parser::MGC::Examples::EvaluateExpression(3pm)