Operation Parser

[nicolas-zozol]

Creating a simple operation parser mainly for educational purposes

[nicolas-zozol]

This works :

function expression() {
    return P.try(
      number().thenLeft(plus()).then(P.lazy(expression))
                 .map(values => values[0]+values[1])
    ).or(number().debug('found single number'));
}

But this one produces a StackOverflow (changing the fisrt number() by lazy(expression)) :

function expression() {
    return P.try(
        P.lazy(expression).thenLeft(plus()).then(P.lazy(expression))
                 .map(values => values[0]+values[1])
    ).or(number().debug('found single number'));
}

It will probably works as long as I don't test (2+2)+3

exp = exp + exp is common in Bison. I have seen on Haskell forums that they usually use subexpressions. I might look at that.

[d-plaindoux]

Parsec lets you define predictive LL(1) parsers. Such parsers can't be left recursive by definition. Nevertheless exp can be designed using two parsers as shown in the next example:

exp   = sexp (op exp)?
sexp = number | '(' exp ')'

[nicolas-zozol]

I found a general solution that works with two precedences. I use * and +. It should work with no problem with -and /.

Implementing general solution :

// grammar terms 
E -> T E'
 E' -> + TE'  |  eps
 T -> F T'
 T' -> * FT'  |  eps
 F -> NUMBER | ( E )

 E== expr
 T == subExpr
 E'== optPlusExpr
 T' == optMultExpr
 F == terminal

// pseudo masala
 expr -> subExpr optPlusExpr'
 optPlusExpr -> ( + then subExpr then F.lazy(optPlusExpr) ).opt()
 subExpr -> terminal then optMultExpr
 optMultExpr -> ( * then terminal then F.lazy(optMultExpr) ).opt()
 F -> F.try( '(' then expr then ')' ).or(N.litteral)