Back to Questions
4.6k
views8
comments
Need help with FParsec calculator example
f#parsing

Hello,

I'm trying to learn how to use the FParsec library but I can't seem to get it to work. What I tried to do was to modify the Calculator example to also allow function calls - that is, to be able to parse strings such as "10.5 + 4*my_fun(5+2, 4)". I modified the example into the code below which runs into a stack overflow error. I (think I) kinda get why it fails (the recursive definition of the term parser) but I have no idea how to solve it.

Any input would be very helpful.

Thank you,

Rickard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

 

// AST definition
////////////////////////

type expr = 
    | Pow of expr*expr
    | Mul of expr*expr
    | Div of expr*expr
    | Add of expr*expr
    | Sub of expr*expr
    | Unary of expr
    | Val of float
    | Func of string*expr list

// the parser definition
////////////////////////

open FParsec.Primitives
open FParsec.CharParsers
open FParsec.OperatorPrecedenceParser

let ws = spaces // skips any whitespace

let ch c = skipChar c >>. ws
let str s = skipString s >>. ws

let number: Parser<expr, unit> = pfloat .>> ws |>> (fun x -> Val(x))

let inner_term_p, pRef = createParserForwardedToRef()

let arg_list = sepBy inner_term_p (ch ',')

let idStr = many1Satisfy isLower

let args = between (ch '(') arg_list (ch ')') 

// function call
let fcall_p = pipe2 idStr arg_list (fun fname fargs -> Func(fname, fargs))

// we set up an operator precedence parser for parsing the arithmetic expressions
let opp = new OperatorPrecedenceParser<_,_>()
let expr = opp.ExpressionParser
opp.TermParser <- inner_term_p <|> between (ch '(') (ch ')') expr

// operator definitions follow the schema
// operator type, string, trailing whitespace parser, precedence, associativity, function to apply

opp.AddOperator(InfixOp("+", ws, 1, Assoc.Left, fun x y -> Add(x, y)))
opp.AddOperator(InfixOp("-", ws, 1, Assoc.Left, fun x y -> Sub(x, y)))

opp.AddOperator(InfixOp("*", ws, 2, Assoc.Left, fun x y -> Mul(x, y)))
opp.AddOperator(InfixOp("/", ws, 2, Assoc.Left, fun x y -> Div(x, y)))

opp.AddOperator(InfixOp("^", ws, 3, Assoc.Right, fun x y -> Pow(x, y)))

opp.AddOperator(PrefixOp("-", ws, 4, true, fun x -> Unary(x)))

pRef := expr

let completeExpression = ws >>. expr .>> eof // we append the eof parser to make
                                            // sure all input is consumed
.

Hi Rickard,

The problem is indeed that you define an inner_term to be an expression ("pref := expr") and then an expression term to be an inner_term or an expression between parentheses ("opp.TermParser <- inner_term_p <|> between (ch '(') (ch ')') expr"). You get the stack overflow when the expression parser tries to parse a term, the term parser tries to parse an inner_term, the inner_term tries to parse an expression, ...

You can easily fix the parser definition by removing the inner_term and modifying the TermParser definition as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13

let opp = new OperatorPrecedenceParser<_,_>()

let expr = opp.ExpressionParser

let arg_list = sepBy expr (ch ',')

let args = between (ch '(') (ch ')') arg_list

let fcall_p = pipe2 idStr args (fun fname fargs -> Func(fname, fargs))

opp.TermParser <- choice [number; fcall_p; between (ch '(') (ch ')') expr]

let completeExpression = ws >>. expr .>> eof

Once you see the solution it's probably obvious to you :-)

Please ask, if you have any further questions.

Regards,
Stephan

By on 9/30/2009 1:29 PM ()

Hello,

I have a problem with a similar example. Let's say I'd like to have function calls, where the function can be any expression (not only an identifier). Ideally, I'd write this:

1

let fcall_p = pipe2 expr args (fun fname fargs -> Func(fname, fargs))

but it doesn't work for obvious reasons (left recursion, leading to a stack overflow). How could I do this?

Thanks,
Laurent.

By on 4/27/2010 10:40 AM ()

Hi Laurent,

Recursive descent parsers can't parse left-recursive grammars directly. So you'll have to refactor the grammar to avoid the left-recursion. If you post (part of) your grammar, I'll try to help you. Usually this isn't difficult.

- Stephan

By on 4/28/2010 6:29 AM ()

Hi,

I'm writing a parser for GLSL (a C-like language). I have used the OperatorPrecedenceParser to parse expressions.

Here is a part of my code, based on the calculator sample:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

let opp = new OperatorPrecedenceParser<_,_>()
let expr = opp.ExpressionParser

// add the operators here [...]
let subscript =
  let inner = between (ch '[') (ch ']') expr
  pipe2 ident inner (fun x y -> x)  // I'd like to have an expr, instead of ident

let argList = sepBy expr (ch ',')
let args = between (ch '(') (ch ')') argList
let fcall = pipe2 ident args (fun x y -> x) // I'd like to have an expr, instead of ident
let simpleExpr = between (ch '(') (ch ')') expr <|> (attempt fcall)
  <|> (attempt subscript) <|> ident
  <|> constant
opp.TermParser <- (simpleExpr .>> ws)

I have no idea how to rewrite this code, without throwing the OperatorPrecedenceParser.

Thanks,
Laurent.

By on 4/28/2010 7:16 AM ()

You'll have to factor out the common part of the productions. In this case you could, for example, structure the grammar similar to this C grammar for ANTLR (see postfix_expression and primary_expression):

1
2
3
4
5
6
7
8
9
10

let subscript = between (ch '[') (ch ']')
                        (expr |>> Subscript)

let fcall = between (ch '(') (ch ')')
                    (sepBy expr (ch ',') |>> FCall)

let prim = ident <|> constant
let post = subscript <|> fcall
let expr = pipe2 prim (many post)
                 (fun prim posts -> (* ... *))

If you prefer a recursive structure of the AST for subscript and fcall expressions, you could of course build such AST nodes in the function argument to pipe2 in the definition of expr.

Does this help?

By on 4/28/2010 9:17 AM ()

Yes, it helps! Thank you very much, it works. :-)
My grammar is not complete yet, but it should be straight-forward now.

Thanks again, FParsec is a great tool!

Laurent.

By on 4/28/2010 9:55 AM ()

I'm glad I could help. If you have any further questions, don't hesitate to ask here again.

BTW: A new version of FParsec with several new features, various performance improvements and a new tutorial is in the works. It still needs a some polishing, but I'm optimistic that I can make a new public release in the coming weeks.

By on 4/28/2010 10:38 AM ()

Thank you very much for your answer - it now makes perfect sense :-)

I must say that the library is a fantastic piece of functionality. Even the practical matter of not having to include a parser generation step in the build process is a very, very nice thing I think.
And I think the basic idea of chaining/piping/combining building blocks into a complex parser is quite intuitive.

I wish I knew about parser combinator libraries before, having handrolled parsers for small tools at work using regexes and heuristics.

Cheers,
Rickard

By on 9/30/2009 10:57 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper