CODEWITHSUNDEEP
f#type-providers
sdgfsdh
sdgfsdh

Reputation: 37045

Can an F# Type Provider be designed to generate an AST type and parser?

My understanding of F# Type Providers is that they are effectively a compile-time functions from strings to types. The type can also have static methods attached, so they can be used for code generation too.

At a high-level, this is the same as parser generator tools such as ANTLR, which take a grammar file and generate code for a target language.

So I am imaging an F# type provider that takes a grammar string and provides a type for the AST and parsing function as a static member.

It might look like this:

[<Literal>]
let Grammar = "
program
   : statement +
   ;

statement
   : 'if' paren_expr statement
   | 'if' paren_expr statement 'else' statement
   | 'while' paren_expr statement
   | 'do' statement 'while' paren_expr ';'
   | '{' statement* '}'
   | expr ';'
   | ';'
   ;

paren_expr
   : '(' expr ')'
   ;

expr
   : test
   | id '=' expr
   ;

test
   : sum
   | sum '<' sum
   ;

sum
   : term
   | sum '+' term
   | sum '-' term
   ;

term
   : id
   | integer
   | paren_expr
   ;

id
   : STRING
   ;

integer
   : INT
   ;


STRING
   : [a-z]+
   ;


INT
   : [0-9] +
   ;

WS
   : [ \r\n\t] -> skip
   ;
"

type MyAst = AstProvider<Grammar>

let myAst = MyAst.TryParse("int x = 1;")

Questions:

  1. Is this actually possible with Type Providers as they stand now?
  2. Are there any examples of this being implemented?

Upvotes: 2

Views: 350

Answers (2)

Andrew Stevenson
Andrew Stevenson

Reputation: 51

I built such a library 4 years ago, which you can peruse at https://github.com/aastevenson/FSharp.Text.Experimental.Transform

The documentation is fairly extensive and complete, including tutorials, examples, API reference, etc. If you're just interested in a parser, see Parsing with FSharp.Text.Experimental.Transform, which demonstrates with a comparison to FParsec.

The library additionally can do transformations on the resulting AST by defining functions that transform subtrees. Here's is a very simple Hello World example from the documentation

open FSharp.Text.Experimental.Transform

// specify the grammar
[<Literal>]
let grammar = """
    Program     :   Greeting 'world';
    Greeting    :   'welcome' | 'hello';
    """ 

// pass the grammar to the type provider
type HW = GrammarProvider<grammar>

let welcomeToHello (inp: HW.Greeting) =
    match inp.TryMatch<"welcome">() with
    | Some _ -> HW.Greeting.Construct<"hello">()
    | None   -> inp

HW.ParseString "welcome world"                  // parse input string
|> HW.Program.ApplyOnePass welcomeToHello       // apply transformation function
|> HW.Pretty                                    // unparse to a string
|> printfn "%s"                                 // prints "hello world"

But if you're just interested in the parser then you can ignore the transformation part of the library. It's still very easy to extract different AST elements of a parsed string.

Note that I haven't touched this project in a long time.

Upvotes: 4

Phillip Carter
Phillip Carter

Reputation: 5005

This is certainly possible to build, since all you need to do is "fill in the types" in accordance with how the SDK works. The Type Provider itself would implement the parser for your grammar, much like how FSharp.Data type providers implement parsers for JSON, XML, etc.

A pretty fun (and funny!) example of something like this is the Mixin Type Provider, which accepts F# source as input, generates an assembly, reads that assembly, and uses the type provider infrastructure to read the assembly and provided the types from the generated code. So you can really do a whole lot, though I can't say I'd recommend following what the Mixin Type Provider does.

Upvotes: 2

Related Questions