2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I cannot find "()" parsing, if you have "... + - 3 * (5 - 5)" than you should expect a number (or expression) after +, but you find -, so it is unary, if it starts from - (like -3 * 5) then it is unary. Back to brackets, when there is bracket then you should execute what was inside first, the same with function call, treat it as unary operator expecting bracket. This are working techniques, but there might exist some better (proper) solution - I am not an expert, just handled something like this using "()" priority. $\endgroup$ – Evil Oct 22 '16 at 0:22
  • $\begingroup$ Take a look at the answer to stackoverflow.com/questions/16380234/… . That doesn't discuss AST construction, which is a separate question. StackExchange encourages asking only one question at a time and strongly discourages askinf the same question on multiple sites. How to Ask $\endgroup$ – rici Oct 22 '16 at 2:20
  • 1
    $\begingroup$ I'm not sure this question is particularly suited for Computer Science. While there may be a conceptual issue, you have hidden it behind huge chunks of source code; we don't do those here. In essence, you are asking us to debug your code, which is offtopic. Can you extract the underlying issue? $\endgroup$ – Raphael Oct 22 '16 at 7:56
  • 1
    $\begingroup$ "What is a guideline I should keep" -- don't write parsers by hand; use parser generators. $\endgroup$ – Raphael Oct 22 '16 at 7:56
1
$\begingroup$

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:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.