in reply to Operator Precedence Parser
would show up as:a + b.c - 1.3 * 2 + 3
As I am parsing I also create a hash of found operators and I note their precedence which I get from a table (it is possible to add any amount of other operators to the table). This hash for this example would look like@tree = qw(a + b.c - 1.3 * 2 + 3);
I then call a method called "apply_precedence" passing it the tree and the %found hash. Apply precedence takes the highest precedence operator and splits the @tree array into sub trees whenever it finds an operator. Each of those sub trees recursively calls "apply_precedence" until each sub tree only has one element. The returned elements are placed in an execution optree that looks like '+', 'a', 'b.c'. The previous example would parse down to something like (but with a little bit different syntax for encoding the parsed variables, operators and arguments to expressions:%found = ('+' => 85, '-' => 85, '*' => 90)
['*', ['+', 'a', ['-', 'b.c', 1.3]], ['+', 2, 3]]
=head1 VARIABLE PARSE TREE CGI::Ex::Template parses templates into an tree of operations. Even variable access is parsed into a tree. This is done in a manner somewhat similar to the way that TT operates except that nested variables such as foo.bar|baz contain the '.' or '|' in between each name level. Operators are parsed and stored as part of the variable ( +it may be more appropriate to say we are parsing a term or an expression) +. The following table shows a variable or expression and the correspondi +ng parsed tree (this is what the parse_variable method would return). one [ 'one', 0 ] one() [ 'one', [] ] one.two [ 'one', 0, '.', 'two', 0 ] one|two [ 'one', 0, '|', 'two', 0 ] one.$two [ 'one', 0, '.', ['two', 0 ], 0 ] one(two) [ 'one', [ ['two', 0] ] ] one.${two().three} [ 'one', 0, '.', ['two', [], '.', 'three', 0], + 0] 2.34 2.34 "one" "one" "one"|length [ \"one", 0, '|', 'length', 0 ] "one $a two" [ \ [ '~', 'one ', ['a', 0], ' two' ], 0 ] [0, 1, 2] [ \ [ 'array', 0, 1, 2 ], 0 ] [0, 1, 2].size [ \ [ 'array', 0, 1, 2 ], 0, '.', 'size', 0 ] ['a', a, $a ] [ \ [ 'array', 'a', ['a', 0], [['a', 0], 0] ], +0] {a => 'b'} [ \ [ 'hash', 'a', 'b' ], 0 ] {a => 'b'}.size [ \ [ 'hash', 'a', 'b' ], 0, '.', 'size', 0 ] {$a => b} [ \ [ 'hash', ['a', 0], ['b', 0] ], 0 ] 1 + 2 [ \ [ '+', 1, 2 ], 0] a + b [ \ [ '+', ['a', 0], ['b', 0] ], 0 ] a * (b + c) [ \ [ '*', ['a', 0], [ \ ['+', ['b', 0], ['c', +0]], 0 ]], 0 ] (a + b) [ \ [ '+', ['a', 0], ['b', 0] ]], 0 ] (a + b) * c [ \ [ '*', [ \ [ '+', ['a', 0], ['b', 0] ], 0 ] +, ['c', 0] ], 0 ] a ? b : c [ \ [ '?', ['a', 0], ['b', 0], ['c', 0] ], 0 ] a || b || c [ \ [ '||', ['a', 0], [ \ [ '||', ['b', 0], ['c +', 0] ], 0 ] ], 0 ] ! a [ \ [ '!', ['a', 0] ], 0 ] Some notes on the parsing. Operators are parsed as part of the variable and become part of th +e variable tree. Operators are stored in the variable tree using a reference to the + arrayref - which allows for quickly descending the parsed variable tree and determi +ning that the next node is an operator. Parenthesis () can be used at any point in an expression to disamb +iguate precedence. "Variables" that appear to be literal strings or literal numbers are returned as the literal (no operator tree). The following perl can be typed at the command line to view the parsed + variable tree: perl -e 'use CGI::Ex::Template; print CGI::Ex::Template::dump_pars +e("foo.bar + 2")."\n"' Also the following can be included in a template to view the output in + a template: [% USE cet = CGI::Ex::Template %] [%~ cet.dump_parse('foo.bar + 2').replace('\s+', ' ') %]
Again - it is sort of funny to see the same ideas discovered and rediscovered over and over.$OPERATORS = [ # type precedence symbols action (undef means pl +ay_operator will handle) ['prefix', 98, ['++'], undef + ], ['prefix', 98, ['--'], undef + ], ['postfix', 98, ['++'], undef + ], ['postfix', 98, ['--'], undef + ], ['infix', 96, ['**', 'pow'], sub { $_[0] ** $_[ +1] } ], ['prefix', 93, ['!'], sub { ! $_[0] + } ], ['prefix', 93, ['-'], sub { @_ == 1 ? 0 - $_ +[0] : $_[0] - $_[1] } ], ['infix', 90, ['*'], sub { $_[0] * $_[ +1] } ], ['infix', 90, ['/'], sub { $_[0] / $_[ +1] } ], ['infix', 90, ['div', 'DIV'], sub { int($_[0] / $_[ +1]) } ], ['infix', 90, ['%', 'mod', 'MOD'], sub { $_[0] % $_[ +1] } ], ['infix', 85, ['+'], sub { $_[0] + $_[ +1] } ], ['infix', 85, ['-'], sub { @_ == 1 ? 0 - $_ +[0] : $_[0] - $_[1] } ], ['infix', 85, ['~', '_'], sub { join "", @_ + } ], ['infix', 80, ['<'], sub { $_[0] < $_[ +1] } ], ['infix', 80, ['>'], sub { $_[0] > $_[ +1] } ], ['infix', 80, ['<='], sub { $_[0] <= $_[ +1] } ], ['infix', 80, ['>='], sub { $_[0] >= $_[ +1] } ], ['infix', 80, ['lt'], sub { $_[0] lt $_[ +1] } ], ['infix', 80, ['gt'], sub { $_[0] gt $_[ +1] } ], ['infix', 80, ['le'], sub { $_[0] le $_[ +1] } ], ['infix', 80, ['ge'], sub { $_[0] ge $_[ +1] } ], ['infix', 75, ['==', 'eq'], sub { $_[0] eq $_[ +1] } ], ['infix', 75, ['!=', 'ne'], sub { $_[0] ne $_[ +1] } ], ['infix', 70, ['&&'], undef + ], ['infix', 65, ['||'], undef + ], ['infix', 60, ['..'], sub { $_[0] .. $_[ +1] } ], ['ternary', 55, ['?', ':'], undef + ], ['assign', 53, ['+='], sub { $_[0] + $_[ +1] } ], ['assign', 53, ['-='], sub { $_[0] - $_[ +1] } ], ['assign', 53, ['*='], sub { $_[0] * $_[ +1] } ], ['assign', 53, ['/='], sub { $_[0] / $_[ +1] } ], ['assign', 53, ['%='], sub { $_[0] % $_[ +1] } ], ['assign', 53, ['**='], sub { $_[0]** $_[ +1] } ], ['assign', 53, ['~=', '_='], sub { $_[0] . $_[ +1] } ], ['assign', 52, ['='], undef + ], ['prefix', 50, ['not', 'NOT'], sub { ! $_[0] + } ], ['infix', 45, ['and', 'AND'], undef + ], ['infix', 40, ['or', 'OR'], undef + ], ];
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re^2: Operator Precedence Parser
by ikegami (Patriarch) on Jun 09, 2006 at 21:14 UTC | |
by Rhandom (Curate) on Jun 09, 2006 at 22:27 UTC | |
by Rhandom (Curate) on Jun 12, 2006 at 12:52 UTC |