10 Jun
2015
10 Jun
'15
6:36 p.m.
Hello Pharoers and Moosers,
I did a Pratt parser extension for PetitParser.
A Pratt parser (a.k.a top-down operator precedence parser) handles left-recursion and
operator precedence.
It handles grouping, prefix, postfix, infix (right- or left-associative) and
"multifix” operators (e.g. "if ... then ... else ...", "... ? ... :
...", Smalltalk keyword messages).
Normally Pratt Parsing needs a tokenization phase but here tokenization is done on the fly
with other PP parsers.
Apart from tokenization, no backtracking is needed so parsing is quite fast
(approximatively 2 times faster than PPExpressionParser).
Here is an exemple of a calculator:
parser := PPPrattParser new.
"Numbers"
parser terminal: #digit asParser plus do: [ :token | token inputValue asNumber ].
parser skip: #space asParser plus.
"Parentheses"
parser groupLeft: $( asParser right: $) asParser.
"Addition, substraction, multiplication, division: all left infix, * and / have
higher precedence than + and -"
parser leftInfix: $+ asParser precedence: 1 do: [ :left :op :right | left + right ].
parser leftInfix: $- asParser precedence: 1 do: [ :left :op :right | left - right ].
parser leftInfix: $* asParser precedence: 2 do: [ :left :op :right | left * right ].
parser leftInfix: $/ asParser precedence: 2 do: [ :left :op :right | left / right ].
"Power: right infix with higher precedence than multiplication and
division"
parser rightInfix: $^ asParser precedence: 3 do: [ :left :op :right | left raisedTo:
right ].
"Unary minus: prefix with highest precedence"
parser prefix: $- asParser precedence: 4 do: [ :op :right | right negated ].
parser parse: '2*3 + 4^(1/2)*3' ----> 12
To try it:
Gofer it
smalltalkhubUser: 'CamilleTeruel' project: 'PetitPratt';
package: 'PetitPratt';
load
Note that it is in beta stage so it might still change drastically.
@PP Devs:
I had trouble with the PPContext furthestFailure that is taken into account instead of the
failures I return, so I had to redefine #parseWithContext: to return the failures I want.
The results given by furthestFailure were not very meaningful in my case (the same is true
for PPExpressionParser btw).
But I guess it was introduced because it gives good results in other cases.
So would it be possible to change this behavior to let the parser decide if it returns the
furthestFailure or the original failure?
Cheers,
Camille