fparsec


Confusion as to how to integrate OperatorPrecedenceParser with mine


The only thing I have left for my parser is to successfully make operator precedence work and my parser will be done. But I don't know how I should integrate it with my current parser.
First, here is the language representation:
module MiniML
(* Structures de donnees a exporter *)
type Exp =
| C of Cst
| Id of Id
| Lam of Id * Exp
| App of Exp * Exp
| Let of Id * Exp * Exp
| Pair of Exp * Exp
| If of Exp * Exp * Exp
and Cst = I of int | B of bool | Unit | Nil
and Id = string;;
let op = ["+";
"-";
"*";
"/";
"=";
"<";
">";
"#";
"and";
"or";
",";
"::"
]
(* Fonction permettant de transformer une exp en string *)
let rec exp2str e = match e with
| C (I i) -> string i
| C (B b) -> string b
| C Unit -> "()"
| C Nil -> "nil"
| Id x -> x
| Lam(x,e) -> "lam " + x + "." + (exp2str e)
| App(Id x,Id y) -> x + " " + y
| App(Id x,((C _) as e')) -> x + " " + (exp2str e')
| App(Id x,Pair(e1,e2)) when List.contains x op -> (exp2str e1) + " " + x + " " + (exp2str e2)
| App(Id x,((Pair _) as e')) -> x + (exp2str e')
| App(Id x, e') -> x + " (" + (exp2str e') + ")"
| App(e, Id x) -> "(" + (exp2str e) + ") " + x
| App(e', ((C _) as e'')) -> "(" + (exp2str e') + ") " + (exp2str e'')
| App(e,e') -> "(" + (exp2str e) + ") (" + (exp2str e') + ")"
| Let(x,e,e') ->
"let " + x + " = " + (exp2str e) + " in " + (exp2str e') + " end"
(* entensions *)
| Pair(e1,e2) -> "(" + (exp2str e1) + "," + (exp2str e2) + ")"
| If(e,e1,e2) -> "if " + (exp2str e) + " then " + (exp2str e1) + " else " + (exp2str e2)
Here is the current state of the parser code (I've left the french comment for completness sake.):
module FPParse
open MiniML
open FParsec
(* Raccourcis pour spaces. ws veux dire whitespace *)
let ws = spaces
let operator : Parser<MiniML.Id,unit> = op |> List.map pstring |> choice
(* Liste des mots cles du langage *)
let keyword : Parser<string,unit> = ["false";"true";"let";"end";"in";"if";"then";"else";"lam"] |> List.map pstring |> choice
(* Parse la premiere lettre d'un identifiant *)
let fstId = asciiLetter <|> pchar '_'
(* Parse les lettres autres que la premiere d'un identifiant *)
let restId = fstId <|> digit <|> pchar '''
(* Genere un parseur pour des valeurs entre parenthese *)
let betweenPar p = between (pchar '(' .>> ws) (pchar ')' .>> ws) p
(* Parse une constante boolean *)
let cstB = (stringReturn "true" (B true)) <|> (stringReturn "false" (B false))
(* Parse une valeur entiere *)
let cstI = puint32 |>> (int >> I)
(*
Parse Unit
*)
let cstU = stringReturn "()" Unit
(*
Parse Nil
*)
let cstN = stringReturn "[]" Nil
(* Parse une expression constante *)
let expC : Parser<Exp,unit> = cstB <|> cstI <|> cstU <|> cstN |>> C
(* Parse un string d'identifiant avec un parseur qui lorsqu'il reussis indique la fin du parsing de l'identifiant *)
let expIdStr = notFollowedByL keyword "Cannot use keyword as variable" >>.
notFollowedByL operator "Cannot use operator as variable" >>.
many1CharsTill2 fstId restId (notFollowedBy restId)
(* Parse un identifiant *)
let expId : Parser<Exp,unit> = expIdStr |>> (MiniML.Exp.Id)
(* Comme exp est recursif on doit le declarer avec une valeur indefinie pour l'utiliser *)
let exp, expRef = createParserForwardedToRef<Exp, unit>()
(* Comme expApp est recursif on doit le declarer avec une valeur indefinie pour l'utiliser *)
let expApp, expAppRef = createParserForwardedToRef<Exp, unit>()
(*
Parse une expression lambda de la forme: lam( )*expId( )*.( )*exp
*)
let expLam : Parser<Exp,unit> = (pstring "lam" >>. ws >>. expIdStr .>> ws .>> pchar '.') .>> ws .>>. exp |>> Lam
(*
Parse une expression let de la forme: let( )*expId( )*=( )*exp( )*in( )*exp( )*end
*)
let expLet = tuple3 (pstring "let" >>. ws >>. expIdStr .>> ws .>> pchar '=' .>> ws) (exp .>> ws .>> pstring "in" .>> ws) (exp .>> ws .>> pstring "end") |>> Let
(*
Parse une expression if de la forme: if( )*exp( )*then( )*exp( )*else( )*exp
*)
let expIf = tuple3 (pstring "if" >>. ws >>. exp .>> ws) (pstring "then" >>. ws >>. exp .>> ws) (pstring "else" >>. ws >>. exp) |>> If
(* Comme closeEXP est recursif on doit le declarer avec une valeur indefinie pour l'utiliser *)
let closeEXP, closeEXPRef = createParserForwardedToRef<Exp, unit>()
(*
Parse un operateur ! de la forme: !exp
*)
let expBang = (pstring "!" >>% MiniML.Id "!") .>>. closeEXP |>> App
let buildList (el,ef) =
let rec go l = match l with
| (e::es) -> App(MiniML.Id "cons", Pair(e,go es))
| [] -> C Nil
go (el # [ef])
let expList = between (pchar '[' .>> ws) (pchar ']') (many (exp .>>? (ws .>> pchar ';' .>> ws)) .>>. exp .>> ws
|>> buildList )
let opOpp : InfixOperator<Exp,unit,unit> list =
[
InfixOperator("*", ws, 7, Associativity.Left, fun x y -> App(MiniML.Id "*",Pair(x,y)));
InfixOperator("/", ws, 7, Associativity.Left, fun x y -> App(MiniML.Id "/",Pair(x,y)));
InfixOperator("+", ws, 6, Associativity.Left, fun x y -> App(MiniML.Id "+",Pair(x,y)));
InfixOperator("-", ws, 6, Associativity.Left, fun x y -> App(MiniML.Id "-",Pair(x,y)));
InfixOperator("::", ws,5, Associativity.Right, fun x y -> App(MiniML.Id "cons",Pair(x,y)));
InfixOperator("=", ws, 4, Associativity.Left, fun x y -> App(MiniML.Id "=",Pair(x,y)));
InfixOperator("<", ws, 4, Associativity.Left, fun x y -> App(MiniML.Id "<",Pair(x,y)));
InfixOperator(">", ws, 4, Associativity.Left, fun x y -> App(MiniML.Id ">",Pair(x,y)));
InfixOperator("and", ws, 3, Associativity.Right, fun x y -> App(MiniML.Id "and",Pair(x,y)));
InfixOperator("or", ws, 2, Associativity.Right, fun x y -> App(MiniML.Id "or",Pair(x,y)));
InfixOperator(",", ws,1, Associativity.None, fun x y -> Pair(x,y) )
]
let opp = new OperatorPrecedenceParser<Exp,unit,unit>()
let expOp = opp.ExpressionParser
let term = exp <|> betweenPar expOp
opp.TermParser <- term
List.iter (fun x -> opp.AddOperator(x)) opOpp
(*
Parse une expression close de la forme: expC | expId | (exp)( )* | [exp]
*)
do closeEXPRef := choice [expC ; expId ; expBang ; betweenPar exp ; expList] .>> ws
(*
Assigne le parseur d'application en lambda-calcul. Le parseur parse autant d'expression close que possible.
Il est impossible que la liste soit vide, du a l'utilisation de many1 qui echoue et retourne s'il n'y a pas
au moins une valeur.
*)
do expAppRef := many1 closeEXP |>> (function (x::xs) -> List.fold (fun x y -> App(x,y)) x xs | [] -> failwith "Impossible")
(*
Assigne le parseur d'expression en lambda-calcul. L'ordre des expressions represente leur priorite
*)
do expRef := [expLam;expIf;expLet;expApp] |> choice
(*
Parse une expression lambda-calcul au complet. Le eof s'assure qu'il ne reste pas de caractere non parse
*)
let mainExp = expOp .>> eof
(*
Prends un string et retourne un Exp. Peut leve un message d'erreur en exception si le parsing echoue
*)
let str2exp s = match run mainExp s with
| Success(result, _, _) -> result
| Failure(errorMsg, _, _) -> failwith errorMsg
I've tried to add it in the list of choice after the expApp parser but it's just ignored. If I put it before the expApp on in the closedExp, it throws exception because, I think, of infinite recursion. I really don't know how to mix it in. I don't want to be just given the solution, I'd like to know why. Also, is there any non-trivial exemple of big language being parse by FParsec?

Related Links

Confusion as to how to integrate OperatorPrecedenceParser with mine
fparsec rfc2822 parsing multiple header lines
OperatorPrecedenceParser throw exception about negative priority wich I don't have
Why does FParsec use lists?

Categories

HOME
makefile
windows-7
firebase-app-indexing
webdav
quill
tumblr
netflix-feign
pjsip
jboss7.x
phoenix
equalizer
sign
rapidjson
mod-pagespeed
lenskit
pyephem
rails-activerecord
fop
hhvm
cocoa-touch
extractor
novnc
hanami
skmaps
mayavi
winscp
partial-application
gpib
smart-mobile-studio
oracle-xml-db
idl
lego
liquid-xml
es-shell
socketpair
mongoexport
jquery-multidatespicker
alchemy.js
wsadmin
stdclass
stereo-3d
dojox.mobile
powermta
upsert
rkt
email-parsing
amazon-clouddrive
production-environment
nuget-server
photography
c64
backstop.js
metalsmith
listadapter
fps
concur
multinomial
servlet-3.0
void
difference
sourcegear-vault
pyrocms
ipojo
robocode
sysctl
cpu-speed
tcpreplay
jstat
java-collections-api
dto
system.web
dvcs
svcutil.exe
android-json-rpc
facebook-chat
ftp4j
carddav
client-side-scripting
cgimageref
process-monitor
fieldset
css-tables
die
file-exists
signals2
userid
galaxy-tab
curljs
hibernate3-maven-plugin
jquery-ui-button
usability-testing
castle-validators

Resources

Mobile Apps Dev
Database Users
javascript
java
csharp
php
android
MS Developer
developer works
python
ios
c
html
jquery
RDBMS discuss
Cloud Virtualization
Database Dev&Adm
javascript
java
csharp
php
python
android
jquery
ruby
ios
html
Mobile App
Mobile App
Mobile App