CS 3723
 Programming Languages 
   Bizarre Parsing  

The Most Ridiculous Parse Ever: Start with an arithmetic expression involving + - * / ^ with usual precedence rules. The scheme below was actually suggested in print at dawn of compilers. (Well, before then.)

The idea is that a fully parenthesized arithmetic expression can be handled without knowing about precedence. So this scheme translates a parenthesis-free expression to one with parentheses that enforce precedence correctly.

This scheme does not handle associativity correctly. It punts when given a sequence of operators with the same precedence. It also doesn't deal correctly with parentheses already in the expression.

Given the input arithmetic expression, make the following replacements for every occurrence of an operator:

Replacements
replace" + " with " ) ) ) + ( ( ( "
replace" - " with " ) ) ) - ( ( ( "
replace" * " with " ) ) * ( ( "
replace " / " with " ) ) / ( ( "
replace " ^ " with " ) ^ ( "
add " ( ( ( " at start
add " ) ) ) " at end

Thus

Replacement Example
    a    +    b   *   d    $
is replaced by:
((( a )))+((( b ))*(( d )))$
and simplified to:
((  a  ))+((  b  )*(  d  ))$
and further simplified to:
    a    + (  b   *   d  ) $
and finally transformed to:
A = b*d; B = a+A;$

The following table gives the example above, along with others:

Replacement Examples
a+b*d$
(((a)))+(((b))*((d)))$
A = b*d; B = a+A; $

a+b*c^d$
(((a)))+(((b))*((c)^(d)))$
A = c^d; B = b*A; C=a+B; $

a^b*c+d$
(((a)^(b))*((c)))+(((d)))$
A = a^b; B = A*c; C = B+d; $

a*b+d$
(((a))*((b)))+(((d)))$
A = a*b; B = A+d; $

a+b^c*d$
(((a)))+(((b)^(c))*((d)))$
A = b^c; B = A*d; C = a+B; $

a^b+c*d^e$
(((a)^(b)))+(((c))*((d)^(e)))$
A = a^b; B = d^e; C = c*B; D = A+C; $

Here is the program that does some of the processing above. (There were also hand edits.)

Prec.java
class Prec {
   private GetNext getChar = new GetNext();
   private char ch;
   private char temp = 'A';

   private String P() {
      String res = "";
      while ((ch =
            getChar.getNextChar()) != '$') {
         if (ch == '+') res += ")))+(((";
         else if (ch == '-') res += ")))-(((";
         else if (ch == '*') res += "))*((";
         else if (ch == '/') res += "))/((";
         else if (ch == '^') res += ")^(";
         else res += ch;
      }
      return "(((" + res + ")))$";
   }

   private String Q(String res) {
      String s = "";
      for (int i = 0; i < res.length(); i++)
          System.out.print(res.charAt(i));
      System.out.print("\n");
      int level = 0;
      for (int i = 0; i < res.length(); i++) {
          char c = res.charAt(i);
          if (c == '(') {
             level++;
             s = s + '(' + level;
          }
          else if (c == ')')  {
             level--;
             s = s + ')' + level;
          }
          else  s = s + c;
      }
      return s;
   }

   int maxLevel(String s) {
      int maxL = 0;
      int loc = -1;
      for(int i = s.length()-1; i >= 0;i--){
          char c = s.charAt(i);
          if (Character.isDigit(c)) {
             if ( (c-'0') >= maxL) {
                loc = i;
                maxL = c-'0';
             }
          }
      }
      return loc;
   }

   char nextTemp() {
      char ret = temp;
      temp++;
      return ret;
   }
      
   String reduce(String s) {
      for (int i = 0; i < 20; i++) {
         int loc = maxLevel(s);
         if (s.charAt(loc+2) == ')') {
            String s1 = s.substring(0, loc-1);
            String s2 = s.substring(loc+1,loc+2);
            String s3 = s.substring(loc+4);
            s = s1 + s2 + s3;
            System.out.println("step:" + i +
               ",s:" + s);
         }
         else if (s.charAt(loc+4) == ')') {
            String s1 = s.substring(0, loc-1);
            String s2 = s.substring(loc+1,loc+4);
            String s3 = s.substring(loc+6);
            char temp1 = nextTemp();
            System.out.println("Inst: " + temp1 +
               " = " + s2);
            s = s1 + temp1 + s3;
            System.out.println("step:" + i +
               ",s:" + s);
         }
      }
      return s;
   }

   public static void main(String[] args) {
      Prec prec = new Prec();
      String res = prec.P();
      System.out.println("res:" + res);
      String s = prec.Q(res);
      System.out.println("s:" + s);
      res = prec.reduce(s);
      System.out.println("res:" + res);
   }
}

Revision date: 2013-02-06. (Please use ISO 8601, the International Standard.)