Home > Fun, PL/SQL > PL/SQL RPN calculator – version 2

PL/SQL RPN calculator – version 2

November 24, 2014 Leave a comment Go to comments

This post presents a new version of my PL/SQL RPN calculator.
It now includes :

  • a regex-free tokenizer
  • a recursive-descent parser to validate the input expression
  • an improved evaluator based on a compiled “type-aware” RPN expression

Program and additional objects available here : rpn_util_v2.zip

Update 2016-08-07 : RPN_UTIL_v2 is now deprecated.
Please download and use PLCalc instead.

 

EBNF grammar

The parser is based on the following EBNF grammar that describes a valid expression :

    boolean_expr   ::= [ "not" ] boolean_term { "or" boolean_term }
    boolean_term   ::= boolean_factor { "and" boolean_factor }
    boolean_factor ::= expr [ relational_op expr ]
                     
    relational_op  ::= "=" | "<" | ">" | "!=" | "<=" | ">="

    expr           ::= [ "-" ] term { ( "+" | "-" ) term }
    term           ::= factor { ( "*" | "/" | "%" ) factor }
    factor         ::= base { "^" base }
    base           ::= number
                     | identifier
                     | constant
                     | function [ "(" expr_list ")" ]
                     | "(" boolean_expr ")"
                
    expr_list      ::= boolean_expr { "," boolean_expr }

    function       ::= "MIN" 
                     | "MAX"
                     | "IF"
                     # etc.
                     
    number         ::= \d+\.?\d*
    identifier     ::= [a-zA-Z]\w*
    constant       ::= "NULL" 
                     | "PI"

# note : identifiers, function names and constants are case-insensitive

 

Examples

a- Using the tokenizer

The previous version used a simple tokenizer based on a regular expression but since it was so slow on long expressions, I’ve decided to rewrite it without any regexp, using a character-wise scanner.
The tokenizer is typically not called directly but here’s an example of what it does :

SQL> select *
  2  from table(
  3         rpn_util.tokenize(
  4           upper('x + if(z=1 and x>=2, -x, cos(x)^2+sin(z)^2)')
  5         )
  6       )
  7  ;

      TYPE STRVAL                             NUMVAL   POSITION
---------- ------------------------------ ---------- ----------
        41 X                                                  1
         2 +                                                  3
        42 IF                                                 5
        30 (                                                  7
        41 Z                                                  8
         7 =                                                  9
        40 1                                1,0E+000         10
        13 AND                                               12
        41 X                                                 16
        11 >=                                                17
        40 2                                2,0E+000         19
        32 ,                                                 20
        16 -                                                 22
        41 X                                                 23
        32 ,                                                 24
        42 COS                                               26
        30 (                                                 29
        41 X                                                 30
        31 )                                                 31
         5 ^                                                 32
        40 2                                2,0E+000         33
         2 +                                                 34
        42 SIN                                               35
        30 (                                                 38
        41 Z                                                 39
        31 )                                                 40
         5 ^                                                 41
        40 2                                2,0E+000         42
        31 )                                                 43

29 rows selected.

SQL> select *
  2  from table(
  3         rpn_util.tokenize('X + ?')
  4       )
  5  ;
       rpn_util.tokenize('X + ?')
       *
ERROR at line 3:
ORA-20100: Lexical error at position 5 : invalid character '?'
ORA-06512: at "RPN.RPN_UTIL", line 159
ORA-06512: at "RPN.RPN_UTIL", line 295

 

b- Using the parser

SQL> exec rpn_util.parse(rpn_util.tokenize('IF(X > 0, 1)'))
BEGIN rpn_util.parse(rpn_util.tokenize('IF(X > 0, 1)')); END;

*
ERROR at line 1:
ORA-20100: Error at position 12 : function 'IF' expects 3 arguments
ORA-06512: at "RPN.RPN_UTIL", line 498
ORA-06512: at line 1

SQL> exec rpn_util.parse(rpn_util.tokenize('(3+)/2'))
BEGIN rpn_util.parse(rpn_util.tokenize('(3+)/2')); END;

*
ERROR at line 1:
ORA-20100: Error at position 4 : unexpected symbol ')'
ORA-06512: at "RPN.RPN_UTIL", line 498
ORA-06512: at line 1

SQL> exec rpn_util.parse(rpn_util.tokenize('MIN(3+1,0'))
BEGIN rpn_util.parse(rpn_util.tokenize('MIN(3+1,0')); END;

*
ERROR at line 1:
ORA-20100: Error at position 10 : unexpected symbol '<eof>' instead of ')'
ORA-06512: at "RPN.RPN_UTIL", line 498
ORA-06512: at line 1

 

c- Compiling an expression

This is done with the compile() function :

/* ======================================================================================
    Compile the input expression in RPN form using the Shunting-yard algorithm.
    PARAMETERS
      p_expr   <VARCHAR2> : expression
      p_options  <NUMBER> : validation options (VALIDATE | NO_VALIDATE), 
                            VALIDATE (default) performs an internal call to the PARSE 
                            procedure
  ====================================================================================== */
  function compile (p_expr in varchar2, p_options in number default VALIDATE)
  return st_array deterministic ;

 

Example :

SQL> select type, strval, numval
  2  from table(
  3         rpn_util.compile(
  4           'x + if(z=1 and x>=2, -x, cos(x)^2+sin(z)^2)'
  5         )
  6       )
  7  ;

      TYPE STRVAL                             NUMVAL
---------- ------------------------------ ----------
        41 X
        41 Z
        40 1                                1,0E+000
         7 =
        41 X
        40 2                                2,0E+000
        11 >=
        13 AND
        41 X
        16 -
        41 X
        42 COS
        40 2                                2,0E+000
         5 ^
        41 Z
        42 SIN
        40 2                                2,0E+000
         5 ^
         2 +
        42 IF
         2 +

21 rows selected.

 

d- Evaluating a compiled expression

Not much difference compared to the previous version. The compiled expression may be evaluated directly or by passing a collection of bind variables :

SQL> select rpn_util.eval(
  2           rpn_util.compile('(1 + min(-1,3)*4^3)/2')
  3         ) as result
  4  from dual ;
 
    RESULT
----------
     -31.5
 
SQL> select rpn_util.eval(
  2           rpn_util.compile('cos(2*PI*x)^2 + sin(PI*y)^2')
  3         , kv_table(
  4             kv_obj('x', 1)
  5           , kv_obj('y', 1/2)
  6           )
  7         ) as result
  8  from dual ;
 
    RESULT
----------
         2
 

 

If used for intensive calculations, the package may benefit from native compilation :

ALTER PACKAGE rpn_util COMPILE PLSQL_CODE_TYPE=NATIVE PLSQL_OPTIMIZE_LEVEL=3;

 

Advertisements
Categories: Fun, PL/SQL Tags: ,
  1. January 12, 2015 at 19:25

    Any tips on how to open the .pck file included? i cannot open it

    • January 15, 2015 at 00:02

      Hard to believe you cannot open it.
      Don’t be abused by the .pck extension, it’s a simple text file, any text editor will do (Notepad etc.)

  2. Bob Iyer
    June 8, 2015 at 21:40

    Thank you for creating this wonderful package. I had a need to write one but I ran across yours and it does way more than what I would have written.

  3. December 8, 2015 at 14:58

    Nice piece of work! Will you be able to extend it by functions with variable number of arguments?

  4. Deependra
    May 12, 2016 at 03:24

    Hi, is there a postgresql version of this, unfortunately i have SAME requirement in postgre.

    • May 18, 2016 at 18:34

      Most of the code (parser + calculator) could probably be ported to PL/pgSQL without too much effort.

  5. Jairo Cortés
    July 27, 2016 at 15:30

    Congratulations! This is an excellent work.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

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: