CODEWITHSUNDEEP
javaalgorithmcompiler-constructionevaluationoperator-precedence
Clashsoft
Clashsoft

Reputation: 11882

Operator Precedence Algorithm

I am currently writing a compiler for a custom programming language. The compiler converts every single operator or call to an object of the form

Call : Value
{
  Value instance
  String name
  Value[] arguments
}

For example, the expression 3 + 4 (= 3.+(4)) becomes

Call : Value
{
  instance = Value(3)
  name = "+"
  arguments = [ Value(4) ]
}

The expression 3 + 4 * 5 would be evaluated by the parser as 3.+(4).*(5).

Call : Value
{
  instance = Call
             {
               instance = Value(3)
               name = "+"
               arguments = Value(4)
             }
  name = "*"
  arguments = [ Value(5) ]
}

I know have a function that creates a list of the calls in this structure and sorts them by operator precedence, and the result would look like this:

[ 3.+(4).*(5), 3.+(4) ] (in the above form)

What I need now is an algorithm that sorts them so that the first expression is 3.+(4.*(5)). The problem about this is that the result from above can have any length. My current implementation (which relies on it being 2 or less infix operators) does it like this:

(go through all elements)
{
  current.arguments = [ prev ]
  prev.instance = current.arguments[0]
}

I know that operator precedence is usually achieved with special constructs in BNF files for parser generation, but since I am using a custom parser that will always evaluate this left-to-right, I cannot use such solutions.

Upvotes: 2

Views: 1695

Answers (1)

david.pfx
david.pfx

Reputation: 10863

A common solution is an algorithm sometimes called the "shunting yard", which uses an operator stack.

  • push mark on stack at lowest priority
  • get a primary
  • get an operator
  • if the precedence is lower or no more operators, pop the stack and generate code
  • push the operator on the stack
  • loop until the mark is all that is left

I'm sure you'll find a better explanation, but that's how I do it.

Upvotes: 5

Related Questions