Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Parsing "x y z" with the precedence of multiply

Tags:

f#

fparsec

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?

like image 481
J D Avatar asked Mar 28 '15 21:03

J D


People also ask

What is precedence function in operator precedence parsing?

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.

What do you mean by operator precedence parsing explain with example?

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.

What is operator precedence parser for regular expression?

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.


1 Answers

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.

like image 105
J D Avatar answered Oct 16 '22 12:10

J D