Building an RPN to Equation Parser

Posted by

In the final part of the examination of lex and yacc, here are the rules for building a parser that translates RPN into equation input (the reverse of the Equation to RPN parser.Translating RPN into standard equation format is a lot more difficult. Although the fundamentals are similar to the RPN parser (we still use a stack for values that are popped off when we see an operand), it is the recording of that process is much more difficult. In the RPN calculator, we can place the result of the calculation back onto the stack so that the value can be used. To resolve something into the equation format we need to record the equivalent expression, not the value. For that, we use a temporary string, and then check if the temporary string has a value and append further expressions to that string. Also, to help precedence in the final calculation (a process handled automatically by the sequence of numbers an operands in RPN) we also enclose each stage of the calculation in parentheses. The resulting rules are shown below. Note that for the example, only the basic operands (+ – * /) are supported, but the principles are valid for any combination.

%%list:   /* nothing */        | list EOLN        | list expr EOLN        { printf( "%sn",exprstring); }        ;expr:   primary        | expr primary MUL          {            if (strlen(exprstring) > 0)              {                sprintf(tmpstring,"(%s * %g)",exprstring, pop());              }            else              {                sprintf(tmpstring,"( %g * %g )",pop(),pop());              }            strcpy(exprstring,tmpstring);          }        | expr primary DIV          {            temp=pop();            if (strlen(exprstring) > 0)              {                sprintf(tmpstring,"(%s / %g)",exprstring, temp);              }            else              {                sprintf(tmpstring,"( %g / %g )",pop(),temp);              }            strcpy(exprstring,tmpstring);          }        | expr primary PLUS          {            if (strlen(exprstring) > 0)              {                sprintf(tmpstring,"(%s + %g)",exprstring, pop());              }            else              {                sprintf(tmpstring,"( %g + %g )",pop(),pop());              }            strcpy(exprstring,tmpstring);          }        | expr primary MINUS          {            temp=pop();            if (strlen(exprstring) > 0)              {                sprintf(tmpstring,"(%s - %g)",exprstring, temp);              }            else              {                sprintf(tmpstring,"( %g - %g )",pop(),temp);              }            strcpy(exprstring,tmpstring);          }        ;primary: NUMBER { push($1); }        ;%%

You can see the resulting output below:

4 5 + 6 *(( 4 + 5 ) * 6)

As mentioned in the original IBM article, we can pipe sequences together to show the parsing and calculation of an expression from different formats. For example:

$ rpntoequ|calc    4 5 + 6 *54

And even rpntoequ and equtorpn:

$ rpntoequ|equtorpn  4 5 + 6 *4 5 + 6 *

The current RPN translator as shown here is not as advanced as the main RPN system, and so it doesn’t support all the options, or expression formats, but you can get the general idea. You can download the code for this example: rpntoequ.tar.gz (Unix).