I'm trying to write a parser for the Mathematica language in F# using FParsec.
I have written one for a MiniML that supports the syntax f x y = (f(x))(y)
with high precedence for function application. Now I need to use the same syntax to mean f*x*y
and, therefore, have the same precedence as multiply. In particular, x y + 2 = x*y + 2
whereas x y ^ 2 = x * y^2
.
How can this be accomplished?
Operator precedence parsers use precedence functions that map terminal symbols to integers, and the precedence relations between the symbols are implemented by numerical comparison. The parsing table can be encoded by two precedence functions f and g that map terminal symbols to integers.
Operator precedence grammar is kinds of shift reduce parsing method. It is applied to a small class of operator grammars. A grammar is said to be operator precedence grammar if it has two properties: No R.H.S. of any production has a∈. No two non-terminals are adjacent.
An operator-precedence parser is a simple shift-reduce parser that is capable of parsing a subset of LR(1) grammars. More precisely, the operator-precedence parser can parse all LR(1) grammars where two consecutive nonterminals and epsilon never appear in the right-hand side of any rule.
As Stephan pointed out in a comment you can split the operator parser into two separate parsers and put your own parser in the middle for space-separated expressions. The following code demonstrates this:
#I "../packages/FParsec.1.0.1/lib/net40-client"
#r "FParsec"
#r "FParsecCS"
open FParsec
open System.Numerics
type Expr =
| Int of BigInteger
| Add of Expr * Expr
| Mul of Expr * Expr
| Pow of Expr * Expr
let str s = pstring s >>. spaces
let pInt : Parser<_, unit> = many1Satisfy isDigit |>> BigInteger.Parse .>> spaces
let high = OperatorPrecedenceParser<Expr,unit,unit>()
let low = OperatorPrecedenceParser<Expr,unit,unit>()
let pHighExpr = high.ExpressionParser .>> spaces
let pLowExpr = low.ExpressionParser .>> spaces
high.TermParser <-
choice
[ pInt |>> Int
between (str "(") (str ")") pLowExpr ]
low.TermParser <-
many1 pHighExpr |>> (function [f] -> f | fs -> List.reduce (fun f g -> Mul(f, g)) fs) .>> spaces
low.AddOperator(InfixOperator("+", spaces, 10, Associativity.Left, fun f g -> Add(f, g)))
high.AddOperator(InfixOperator("^", spaces, 20, Associativity.Right, fun f g -> Pow(f, g)))
run (spaces >>. pLowExpr .>> eof) "1 2 + 3 4 ^ 5 6"
The output is:
Add (Mul (Int 1,Int 2),Mul (Mul (Int 3,Pow (Int 4,Int 5)),Int 6))
which represents 1 * 2 + 3 * 4^5 * 6
as expected.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With