1

I'm writing a interpreter/compiler

I have encountered a problem which I have solved before, but not optimally perhaps.

The problem goes like this, expressions can express a lot of things like scopes, variable assignments and declarations.

When an expression is simple, for example:

a = 4 + 3

turning it into a Reverse Polish notation is easy enough, using the shunting yard algorithm I can turn it into:

4 3 + a =

executing this is easy enough, but with increasing complexity of expressions it seems infeasible.

for example:

Array<Class<T,U>> b = (x,y)=>{int x = k; return func1(k*y,2);}

Will I turn this complex expression into a reverse polish notation of only tokens?

Isn't the syntax too ambiguous for that?

I feel like while I Could Implement it with a raw token series, its probably unlikely that this is how compilers usually go at it because it seems unmaintainable.

On the other hand I could write subparsers for the expression making it an expression of subexpressions like:

{typeexpression} {identifiertoken} {operatortoken} {lambda expression}..

So the question arises, what is the most correct way to write an expression parser that is extensible but still true to compiler design.

As a side node: I did not study compiler design, therefor any resources or tips would help me out a lot, the current code for the interpeter (which is written in c#) is on GitHub. In case you want to see some code I've written I'll comment the repository.

  • Why not build tree structures for complex instructions, with leaf nodes are the simplest ones, and follow a recursive approach to build that tree – A.Rashad Aug 28 '17 at 10:55
  • i was planning on building a tree after i have an RPN representation of the expression, i need to read all of the tokens to get the order of operations correctly like in shunting yard dont I? – downrep_nation Aug 28 '17 at 11:17
  • You don't need an RPN expression to build a tree. – Robert Harvey Aug 28 '17 at 16:54
  • @RobertHarvey i would love documentation on that – downrep_nation Aug 28 '17 at 19:13
  • 2
    I have no idea how the C# compiler works internally, whether it uses the shunting yard algorithm or something else. I just know that you don't need an RPN conversion to create a tree from infix. Here is an example: cplusplus.kurttest.com/notes/stack.html#binary-expression-tree. It uses two stacks: one for the operators, and one for the operands. – Robert Harvey Aug 28 '17 at 19:27
2

The shunting yard algorithm is for a very specific parsing problem: parsing expressions with operator precedence. It can be used when all the productions in the grammar have the recursive form Expr → Expr op Expr, and the productions are ranked by priority. (Plus of course base cases of the form Expr → terminal, and productions for unary operators)

Most programming languages do not fit this simply structure. Even assignment = is not an ordinary operator because the left hand side may not be an arbitrary expression: 42 * 3 = a + 7 is invalid in most programming languages. As such, the assignment operator cannot be parsed by the shunting yard algorithm.

This restriction has nothing to do with RPN versus abstract syntax trees. RPN is exactly equivalent to a tree, the tree is just flattened out.

While the shunting yard algorithm is not powerful enough to parse “real” programming languages, it is a good stepping stone in order to understand more complex bottom-up parsing algorithms like LR. So because we will have to use a more powerful algorithm anyway, the shunting yard algorithm is not used in practice.

Many real programming language implementations use a parser generator (sometimes also called compiler-compiler). With a parser generator you write down the rules of your grammar in some kind of EBNF notation, and the tool generates a program that will parse this grammar. This is fairly maintainable and can use good parsing algorithms.

Alternatively, you can write a compiler by hand. This is actually quite common because this can potentially produce much better error messages or deal with ambiguities that a parser generator can't address. It is also much more difficult to get right.

Most hand-written parsers use a recursive descent strategy, which is basically your idea of sub-parsers: We implement each rule in our grammar as a function. The function takes parser state as input and returns a syntax tree fragment. For example a rule Assignment → Variable "=" Expr ";" might be implemented like this:

class Parser {
  ... // keep parser state as instance fields

  Assignment parseAssignment() {
    Variable variable = parseVariable();
    consumeLiteral("=");
    Expression expr = parseExpr();
    consumeLiteral(";");
    return new Assignment(variable, expr);
  }
}

The problem with recursive-descent parsers is that they have difficulty dealing with left-recursive productions (i.e. the left hand symbol of a production is the first symbol on the right hand side, like X → X ...). But these rules are common in mathematical expressions!

One legitimate possibility is using the shunting-yard algorithm for that, because it deals well specifically with those cases. Alternatively, this can be also solved by explicitly eliminating recursion. E.g. the rules Term -> Term "*" Factor; Term -> Factor might naively be implemented as

Expression parseTerm() {
  Expression left = parseTerm();  // FIXME infinite recursion
  if (!peekLiteral("*")) return left;
  consumeLiteral("*");
  Expression right = parseFactor();
  return new Multiplication(left, right);
}

Instead, the rule can be properly implemented without recursion but with a loop:

Expression parseTerm() {
  Expression expr = parseFactor();
  while (peekLiteral("*")) {
    consumeLiteral("*");
    Expression right = parseFactor();
    expr = new Multiplication(expr, right);
  }
  return expr;
}
  • Great insight, Indeed i use recursive descent to parse my language. Only one question , isnt dictionary["foo"] = 5-3; an expression where the left side is an expression too? – downrep_nation Aug 31 '17 at 4:12
  • @downrep_nation Yes, absolutely correct. There are some expressions to which we can assign, sometimes called Lvalues. In general we write a separate grammar rule for Lvalues and Rvalues. In practice, there often is some rule in the ordinary expression syntax that already describes legal Lvalues. Note that in C# the parser can't know whether syntax like x.Foo is an Lvalue because the Foo might be a read-only property. That decision is left to a later phase (semantic analysis/ type checking). – amon Aug 31 '17 at 5:37
  • so i could theoretically treat = as an operator? – downrep_nation Aug 31 '17 at 6:12
  • @downrep_nation Yes you can treat = as an expression level operator. There are some languages that do this, and later check whether the left side is a legal assignment target (e.g. Perl). In some languages, the = is both an assignment operator and part of the variable declaration statement syntax (e.g. C, C#, Java). In other languages like Python, the = is a fixed part of the assignment statement syntax, and not a legal operator inside expressions. So this depends entirely on the language you are implementing. – amon Aug 31 '17 at 9:20

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.