It’s a lovely evening here in
Anyway I have been neglecting my blog lately, there is a reason for this, but nether the less I thought I should try and do something to correct this.
This sample was inspired by my current programming project. We are building a performance management system for a large Belgian bank; it’s all based found a SQL Server OLAP database/cube. We want to be able to offer our users, the banks performance managers who have a statically finance rather than technical back ground, the opportunity input formulas and have them transformed into MDX to query the cube.
To do this we need to write a parser, it is not yet clear how we will do this, but obviously F# would be a good choice. So in this sample I’ll demonstrate how to build a parser for a simple mathematical language. It’s beyond the scope of the sample to generate MDX, merely of the because there is no practical way I could distribute a OLAP database with the sample. So we’ll generate some MSIL instead as if you are interested in F# you will already have the means to run MSIL.
The parser comes in 3 parts a lexer to generate tokens from the text, the parser definition itself written in fslex and the abstract syntax tree (ast) that will be the result of the parser.
The lexer looks like this:
let digit = ['0'-'9']
let whitespace = [' ' '\t' ]
let newline = ('\n' | '\r' '\n')
rule token = parse
| whitespace { token lexbuf }
| newline { token lexbuf }
| "(" { LPAREN }
| ")" { RPAREN }
| "*" { MULTI }
| "/" { DIV }
| "+" { PLUS }
| "-" { MINUS }
| '['[^']']+']' { ID(lexeme lexbuf) }
| ['-']?digit+('.'digit+)?(['e''E']digit+)? { FLOAT (Double.Parse(lexeme lexbuf)) }
| eof { EOF }
The parser looks like this:
Expr: ID { Val($1) }
| FLOAT { Float($1) }
| LPAREN Expr RPAREN { $2 }
| Expr MULTI Expr{ Multi($1, $3) }
| Expr DIV Expr{ Div($1, $3) }
| Expr PLUS Expr{ Plus($1, $3) }
| Expr MINUS Expr{ Minus($1, $3) }
The ast looks like this:
type expr =
| Val of string
| Float of System.Double
| Multi of expr * expr
| Div of expr * expr
| Plus of expr * expr
| Minus of expr * expr
All in all just 62 lines of code. The interping the ast to make IL, takes just another 11 lines of code.
let generate_il e il =
let param_count = ref 0 in
let rec generate_il_inner e (il : ILGenerator) =
match e with
| Val name -> il.Emit(OpCodes.Ldarg, !param_count); inc param_count
| Multi (e1 , e2) -> generate_il_inner e1 il; generate_il_inner e2 il; il.Emit(OpCodes.Mul)
| Div (e1 , e2) -> generate_il_inner e1 il; generate_il_inner e2 il; il.Emit(OpCodes.Div)
| Plus (e1 , e2) -> generate_il_inner e1 il; generate_il_inner e2 il; il.Emit(OpCodes.Add)
| Minus (e1 , e2) -> generate_il_inner e1 il; generate_il_inner e2 il; il.Emit(OpCodes.Sub)
| Float x -> il.Emit(OpCodes.Ldc_R8, x) in
generate_il_inner e il;
il.Emit(OpCodes.Ret)
There a further 100 or so lines of F# in the sample, but this is just dealing with creating a form to expose the parser and its results.
The sample also demonstrates using F# with form written in C#. Thing that is sightly unsual about this is we compile the C# form into a library and then use it from F#, a lot of of people would do this the other way round. There are a couple of advantages to this, one that you can use F# lambdas with the form’s events, and secondly you can easily use the ast discimiating union type, which do not work well in C#.
Theres quite a bit more to the sample, and I’ll dig into the details in another post (maybe …). But for now you can download the full sample here.
Feedback:
Feedback was imported from my only blog engine, it's no longer possible to post feedback here.
re: A simple parser in F# - Dmitri
This is cool! It would be nice to see an MDX generator, though :)