1

I've got this code

type Exprs = 
    | Val of float
    | Mult of Exprs  * Exprs
    | Plus of Exprs  * Exprs

let pexpr, exprRef = createParserForwardedToRef<Exprs, unit>()
let pval = pfloat |>> Val
let binaryOp s = (ws >>. pexpr.>> ws) .>>. (ws >>. str s >>. ws >>. pexpr)
let pplus = binaryOp "+" |>> Plus 
let pmuil = binaryOp "*" |>> Mult

do exprRef := choice [ attempt pmuil
                       pplus
                       pval ]

let expression = ws >>. pexpr .>> ws

When it evaluated it throws StackoverflowExcpetion. So the question is how can i write it without infinitie recursion?

neftedollar
  • 1,108
  • 10
  • 14
  • 1
    Did you try it by hard coding the signatures? – Guy Coder May 06 '16 at 16:45
  • @guy-coder I've just try it. I've rewrite `let pplus = (ws >>. pval .>> ws) .>>. (ws >>. str "+" >>. ws >>. pval) |>> Plus` and it works! Why? – neftedollar May 06 '16 at 16:53
  • oh no! My code is wrong I'm using pval instead of pexpr! – neftedollar May 06 '16 at 16:59
  • question was updated – neftedollar May 06 '16 at 17:04
  • No, my problem not solved yet. it's look like same with http://stackoverflow.com/questions/6186230/recursive-grammars-in-fparsec and http://stackoverflow.com/questions/6763982/parsing-simple-types-in-fparsec – neftedollar May 06 '16 at 17:18
  • I haven't tested this and I don't normally use FParsec as my parser combinators, but try something like `Mult1 of Val` and `Mult2 of op * Exprs` With this you only look for another expression if you have an `op` and if you don't see the next `op` then you know you have reached the end of the expression. – Guy Coder May 06 '16 at 17:31
  • I am trying to run your example. For `(ws >>. str s >>. ws >>. pexpr) ` what is `str` defined as? – Guy Coder May 06 '16 at 17:42
  • it's `let str = pstring` and `let ws = unicodeSpaces` – neftedollar May 06 '16 at 17:52
  • Of interest: [Small Basic Parser](http://fssnip.net/le) with [Blog](http://trelford.com/blog/post/compiler.aspx) by Phillip Trelford – Guy Coder May 06 '16 at 18:23
  • 1
    Are you aware of [Chomsky hierarchy](https://en.wikipedia.org/wiki/Chomsky_hierarchy)? – Guy Coder May 06 '16 at 18:32
  • Normally I would point to a [Rosetta Code](http://rosettacode.org/wiki/Rosetta_Code) example for this, but the [F#](https://rosettacode.org/wiki/Arithmetic_evaluation#F.23) and [OCmal](https://rosettacode.org/wiki/Arithmetic_evaluation#OCaml) examples make use variations of [Lex/Yacc](https://en.wikipedia.org/wiki/Yacc) and would not be of use for an answer here. However the [ML](https://rosettacode.org/wiki/Arithmetic_evaluation#Standard_ML) version does NOT make use of Lexx/Yacc and is of interest. – Guy Coder May 06 '16 at 18:39
  • 1
    Of interest: `Grammar for arithmetic expressions` in [Parsing slides](http://www.cs.cornell.edu/courses/cs211/2004sp/handout/lecture05parsing.pdf) – Guy Coder May 06 '16 at 18:47
  • Thank you,@guy-coder, your comments realy helpfull. – neftedollar May 06 '16 at 22:06
  • FYI I am not working to solve this with FParsec and don't plan to do an FParsec answer. If you don't require FParsec then let me know and I will do a parser combinator answer. The reason I am not doing an FParsec answer is that with FParsec arithmetic expressions using precedence are done using `OperatorPrecedenceParser`. You should be able to do that one with the example provided in `Small Basic Parser` – Guy Coder May 07 '16 at 11:36
  • Also if you want a more indepth intro to parser combinators and one that leads toward the way FParsec works take a look at [The "Understanding Parser Combinators" series](https://fsharpforfunandprofit.com/series/understanding-parser-combinators.html) however that does not cover `OperatorPrecedenceParser` – Guy Coder May 07 '16 at 11:42
  • To understand `OperatorPrecedenceParser` requires talking about [operator associativity](https://en.wikipedia.org/wiki/Operator_associativity), [Operator precedence](https://en.wikipedia.org/wiki/Order_of_operations) and [shunting yard algorithm](http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm). Also an understanding what kind of language you have, e.g. `regular`, `context free`, which parsers/compilers e.g. `recursive descent`, `parser combinator`, `Lex/Yacc`, can handle those languages and how to construct/modifty the grammar for the parser. All of this is a bit more than a simple answer. – Guy Coder May 07 '16 at 11:48
  • 1
    Of interest: [Writing a MiniC-to-MSIL compiler in F# - Part 0 - Introduction](http://timjones.tw/blog/archive/2014/04/13/writing-a-minic-to-msil-compiler-in-fsharp-part-0-introduction) – Guy Coder May 16 '16 at 11:09
  • 1
    Of interest: [Constructing LR(0) parsing tables](https://en.wikipedia.org/wiki/LR_parser#Constructing_LR.280.29_parsing_tables) – Guy Coder May 19 '16 at 11:39
  • 1
    Of interest: [Haskell/GADT](https://en.wikibooks.org/wiki/Haskell/GADT) and F# request: [Add support for GADTs](https://fslang.uservoice.com/forums/245727-f-language/suggestions/5664643-add-support-for-gadts) – Guy Coder May 23 '16 at 11:33
  • 1
    Of interest: [LR to LL Grammer Conversion](https://www.andrews.edu/~bidwell/456/lr2llgram.html) – Guy Coder May 25 '16 at 14:29
  • 1
    Of interest: [Parsing “x y z” with the precedence of multiply](http://stackoverflow.com/a/29334253/1243762) – Guy Coder May 27 '16 at 10:48
  • 1
    Of interest: [Recursive parsers in FParsec](http://hestia.typepad.com/flatlander/2011/07/recursive-parsers-in-fparsec.html) – Guy Coder May 27 '16 at 11:06
  • 1
    Of interest: [Parsing: Lazy initialization and mutually recursive monads in F#](http://stackoverflow.com/questions/1084374/parsing-lazy-initialization-and-mutually-recursive-monads-in-f) – Guy Coder May 27 '16 at 11:15
  • 1
    Of interest: [Tail-recursion in FParsec](http://stackoverflow.com/questions/9251971/tail-recursion-in-fparsec) – Guy Coder May 27 '16 at 11:19
  • 1
    Of interest: [MicroCS](https://github.com/neildanson/MicroCS/tree/master/MicroCSharpCompiler) and [Building a C# compiler in F#](https://neildanson.wordpress.com/2014/02/11/building-a-c-compiler-in-f/) Noted because it covers a more complex language. – Guy Coder May 27 '16 at 11:26
  • 1
    Of interest: [Simple C# Parser](http://www.fssnip.net/lf) – Guy Coder May 27 '16 at 11:29
  • 1
    Of interest: [Snippets tagged FParsec](http://www.fssnip.net/tags/FParsec) – Guy Coder May 27 '16 at 11:31
  • 1
    Of interest: [Write Yourself a Scheme in 48 Hours in F# – Part I](https://lucabolognese.wordpress.com/2011/06/30/write-yourself-a-scheme-in-48-hours-in-f-part-i/) There are 7 (VII) parts. Also see [code drop](https://code.msdn.microsoft.com/windowsdesktop/Write-Yourself-a-Scheme-in-d50ae449#content) – Guy Coder May 27 '16 at 11:43
  • 1
    Of interest: [Adventure in parserland – parsing lambda expressions in F# – Part I](https://lucabolognese.wordpress.com/2011/08/19/adventure-in-parserland-parsing-lambda-expressions-in-f-part-i/) There are 5 (V) parts. – Guy Coder May 27 '16 at 11:49
  • 1
    Of interest: [How to convert an FParsec parser to parse whitespace](http://stackoverflow.com/q/8395139/1243762) Not specifically for this question but of use in general with FParsec. – Guy Coder May 27 '16 at 11:56
  • 1
    Of interest: [Improving the readability of a FParsec parser](http://stackoverflow.com/a/7501532/1243762) Read the comments. – Guy Coder May 27 '16 at 12:00
  • 1
    Of interest: [FParsec - Tracing a parser](http://www.quanttec.com/fparsec/users-guide/debugging-a-parser.html#tracing-a-parser) and [example](http://stackoverflow.com/a/37590147/1243762) – Guy Coder Jun 02 '16 at 11:39
  • 1
    Of interest: [Parsing expression grammar](https://en.wikipedia.org/wiki/Parsing_expression_grammar) Noted because it discusses removing left recursion. – Guy Coder Sep 19 '16 at 21:50
  • 1
    Of interest: [Notes on parsing](http://yz.mit.edu/notes/Compilers?revision=9a15a27b71a1a0475418b72c11973b134f1633d6) This gives an idea of what people who know many different parsers think about when presented with a new parser project. It should also help to understand why for many first time parser questions the answer is like, "it is not that simple" and "are you aware of ..." . – Guy Coder Sep 27 '16 at 14:17
  • 1
    Of interest: [Grammar Tutorial](http://marvin.cs.uidaho.edu/Teaching/CS445/grammar.html) – Guy Coder Nov 05 '16 at 17:11

0 Answers0