Pratt parser extension for PetitParser

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
Advertisements

2 thoughts on “Pratt parser extension for PetitParser

  1. Alex says:

    Hey,

    Thank you for your work on this parser extension. I am new to Smalltalk and Pharo so perhaps I’m missing something trivial, but I’m having problems parsing basic arithmetic expressions using your exact code. For example, the exact expression from your sample code ‘2*3+4^(1/2)*3’ gives me an error MessageNotUnderstood: PPStream>>stream. It is strange, because some other expressions are evaluated correctly. It seems the length of the expression has something to do with causing the error. For example, ‘2+3’ works, but not ‘2+3+4’. Strangely ‘2+2^3^2’ works as well. I couldn’t find any information about this anywhere else on the internet so I’m posting about it here. I will try to learn and use PPExpressionParser for now. One more thing. I am learning to write a parser for a C-like language using Smalltalk. I was wondering, if there are some place where I could I find in depth tutorials on how to use PPPrattParser or PPExpressionParser, specifically in relation to producing ASTs using semantic actions and parsing expressions with both left and right associated infix operators, precedence levels and variable operands? So far the only resources I found are the comments section of PPExpressionParser class, and Chapter 18 about PetitParser in Deep Into Pharo book. As I do not know enough PEG parsing theory to implement all those features using PPCompositeParser on my own, I have to use something like PPExpressionParser. Anyway, thank you again and good luck.

  2. Ask the mailing-list. This blog is not a forum

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: