Shunting Yard Algorithm extension and AST generation

Question

Let me introduce you to my current project (that obviously yields the problem I face hence I post here). I am writing a so-called "compiler" for a simplistic language. I have already built a VM to run the produced bytecode, the associated Lexer (all this project is an optional assignment). My problem lies in the Expression parsing bit. I use the Shunting Yard Algorithm by Dijkstra to convert my postfix expressions into the corresponding AST structure, and I am incapable of adjusting the algorithm correctly to generate the correct AST if -and only if- I try to implement function calls and array subscript.

Here a sample of the algorithm implementation (everything is pretty self-explanatory I believe)

func (p *parser) shuntingyard(input token.TQueue) *ast.Node {
    var operands ast.NStack
    var operators *token.TStack

    operands = make(ast.NStack, 0)
    operators = token.TokenStack()

    for tok := input.Dequeue(); tok.Sym != "EOF"; tok = input.Dequeue() {
        switch tok.Kind {
        case "LParen":
            operators.Push(tok)
        case "RParen":
            for {
                // pop item ("(" or operator) from stack
                if operators.Empty() {
                    p.errorf("Unmatched parenthesis on line %d, expected '(' to match closing parenthesis in expression", p.lno)
                }

                op := operators.Pop()
                if op.Sym == "(" {
                    break // discard "("
                }

                if isUnary(op.Sym) {
                    node := ast.MakeNode(*op)
                    node.AddChild(operands.Pop())
                    operands.Push(node)
                    break
                }

                RHS := operands.Pop()
                LHS := operands.Pop()
                operands.Push(ast.MakeParentNode(*op, RHS, LHS))
            }
        default:
            if o1, isOp := prOps[tok.Sym]; isOp {
                // token is an operator
                for !operators.Empty() {
                    // consider top item on stack
                    op := operators.PeekTop()
                    if o2, isOp := prOps[op.Sym]; !isOp || o1.prec > o2.prec || o1.prec == o2.prec && o1.rAssoc {
                        break
                    }

                    // top item is an operator that needs to come off
                    op = operators.Pop()
                    if isUnary(op.Sym) {
                        node := ast.MakeNode(*op)
                        node.AddChild(operands.Pop())
                        operands.Push(node)
                        break
                    }
                    RHS := operands.Pop()
                    LHS := operands.Pop()
                    operands.Push(ast.MakeParentNode(*op, RHS, LHS))
                }
                // push operator (the new one) to stack
                operators.Push(tok)
            } else {
                operands.Push(ast.MakeNode(*tok))
            }
        }
    }

    // drain stack to result
    for !operators.Empty() {
        if operators.PeekTop().Sym == "(" {
            p.errorf("Unmatched parenthesis on line %d, expected ')' to match previous parenthesis in expression", p.lno)
        }

        RHS := operands.Pop()
        LHS := operands.Pop()
        operands.Push(ast.MakeParentNode(*operators.Pop(), RHS, LHS))
    }

    result := operands.Pop()
    for !operands.Empty() {
        result.AddSibling(operands.Pop())
    }

    return result
}

The idea is pretty straightforward when you encounter a binary operator from the operator stack, you pop off of the operand stack two nodes that you set as children of the operator encountered (or one if the operator is unary). And you push the resulting node on the operands stack.

For instance, this input:

c = 0;
a = 1 << 3 + 2;

results in the (valid) AST:

┣━ Assign           =
┃   ┣━ Identifier       'a'
┃   ┗━ Lshift           <<
┃       ┣━ Number           1
┃       ┗━ Plus             +
┃           ┣━ Number           3
┃           ┗━ Number           2
┗━ Assign           =
    ┣━ Identifier       'c'
    ┗━ Number           0

However, the output is being wrong whenever I try to nest function calls:

 foo(bar(0))

the result is (obviously) not correct:

┣━ Number           0
┣━ Function         bar
┗━ Function         foo

when I should have had:

┗━ Function         foo
    ┗━ Function         bar
        ┗━ Number        0

My first question is: What modification do I have to bring to my implementation to support AST generation for function calls ? Since all I have found on the Internet regarding the SY Algorithm is always generating an RPN string ...

Another thing is that an input such as:

-i++;

generates the valid output:

┗━ UnaryMinus       -u
    ┗━ PlusPlus         ++
        ┗━ Identifier       'i'

but (-i++); reports and unbalanced parenthesised expression ?

The map used to work with operators is:

var prOps = map[string]struct {
    prec   int
    rAssoc bool
}{
    "++" : {50, false}, "--" : {50, false},

    "."  : {40, false}, "["  : {40, false},

    "!"  : {30, true}, "~"   : {30, true},
    "-u" : {29, true}, "--u" : {29, true}, "++u": {29, true},
    "**" : {28, true},

    "*"  : {27, false}, "/"  : {27, false}, "%" : {27, false},
    "+"  : {26, false}, "-"  : {26, false},
    ">>" : {25, false}, "<<" : {25, false},
    ">"  : {24, false}, ">=" : {24, false}, "<" : {24, false}, "<=" : {24, false},
    "==" : {23, false}, "!=" : {23, false},
    "&"  : {22, false},
    "^"  : {21, false},
    "|"  : {20, false},
    "&&" : {19, false},
    "||" : {18, false},

    "="  : {10, true}, "+="  : {10, true}, "-=" : {10, true}, "*="  : {10, true},
    "/=" : {10, true}, "**=" : {10, true}, "^=" : {10, true}, "~="  : {10, true},
    "|=" : {10, true}, "&="  : {10, true}, "%=" : {10, true}, "<<=" : {10, true},
    ">>=": {10, true},
    ","  : {9, false},
}

Where -u, ++u, --u are the instances of the meant operator, but unarily.

On the other note, is the Shunting Yard Algorithm what I truly need ? I mean, if parsing an object-oriented expression with this algorithm is feasable, is that my best choice ?

I also read (a lot) on parsers in a larger sense. I believe, from what I read, that writing a Recursive Descent parser is my best chance to achieve my goal within reasonable amount of time. I read some source codes, but parsers tend not to be reader-friendly. What is a guideline I should keep for this project regarding the parser and AST generation ?

Please tell me if I did anything wrong with this thread :) And do ask if I missed to link/give any ressources needed !

In the hope of having some helpful answers.

Answer 1

I would recommend using a hybrid recursive descent parser that uses your existing shunting yard to parse expressions. For the examples you have shown, very little would change, but you would add a function to parse an atom that could be a number, an identifier, or a function call.

Something like this:

def parse_atom():
  tok = next_token()
  if tok is number:
    return AST.Number(value = tok.value)
  if tok is symbol:
    if peek_token() is '(': # look ahead at the next token but leave it on the stream
      <parse arguments here by calling shunting_yard>
      return AST.FunCall(function = tok.value, arguments)
    else: # variable
      return AST.Variable(name = tok.value)

Using a pure recursive descent parser to parse infix expressions is a pain, but mixing in something like shunting yard or precedence climbing works very well.

I have used a similar method to this (with precedence climbing instead of shunting yard) in several projects and had a good time with it. See, for example here and here.

I'd be happy to answer any questions you may have.

Some resources:

• Eli Bendersky on Hybrid Recursive Descent/Shunting Yard
• Eli Bendersky on Precedence Climbing in a Recursive Descent Parser