FsYacc Overview

fsyacc is a LALR parser generator. It follows a similar specification to the OCamlYacc parser generator (especially when used with the ml compatibility switch)

Getting Started

Build the tool by cloning this project and running /build.sh or build.cmd

Add a reference in your project to FsLexYacc package via Nuget or paket.

You can run the parser generator directly: dotnet fsyacc.dll inputFile -o outputFile

Sample input

Parser generators typically produce numbers represented by values in an F# Union Type. For example:

type Expr = 
 | Val of string 
 | Int of int
 | Float of float
 | Decr of Expr


type Stmt = 
 | Assign of string * Expr
 | While of Expr * Stmt
 | Seq of Stmt list
 | IfThen of Expr * Stmt
 | IfThenElse of Expr * Stmt * Stmt
 | Print of Expr


type Prog = Prog of Stmt list

Given that, a typical parser specification is as follows:

%{
open Ast
%}

%start start
%token <string> ID
%token <System.Int32> INT
%token <System.Double> FLOAT
%token DECR LPAREN RPAREN WHILE DO END BEGIN IF THEN ELSE PRINT SEMI ASSIGN EOF
%type < Ast.Prog > start


%%


start: Prog {  $1 }


Prog: StmtList { Prog(List.rev($1)) }


Expr: ID { Val($1) }
    | INT {  Int($1)  }
    | FLOAT {  Float($1)  }
    | DECR LPAREN Expr RPAREN {  Decr($3)  }


Stmt: ID ASSIGN Expr { Assign($1,$3) }
    | WHILE Expr DO Stmt { While($2,$4) }
    | BEGIN StmtList END { Seq(List.rev($2)) }
    | IF Expr THEN Stmt { IfThen($2,$4) }
    | IF Expr THEN Stmt ELSE Stmt { IfThenElse($2,$4,$6) }
    | PRINT Expr { Print($2) }


StmtList: Stmt { [$1] }
       | StmtList SEMI Stmt { $3 :: $1  }

The above generates a datatype for tokens and a function for each start production. Parsers are typically combined with a lexer generated using FsLex.

The nuget package includes MSBuild support for FsLex and FsYacc. New MSBuild targets are added automatically by the nuget package.
But you must manually add FsLex andd FsYacc entries inside of an ItemGroup to your .fsproj file like this:

<FsYacc Include="..\LexAndYaccMiniProject\Parser.fsy">
  <OtherFlags>--module Parser</OtherFlags>
</FsYacc>
<FsLex Include="..\LexAndYaccMiniProject\Lexer.fsl">
  <OtherFlags>--unicode</OtherFlags>
</FsLex>

The generated .fs and .fsi files are written to the intermediate folder (obj/...), so they stay out of your source tree and dotnet clean removes them. Reference them through FsLexOutputFolder and FsYaccOutputFolder:

<ItemGroup>
  <FsYacc Include="Parser.fsy">
    <OtherFlags>--module Parser</OtherFlags>
  </FsYacc>
  <FsLex Include="Lexer.fsl">
    <OtherFlags>--unicode</OtherFlags>
  </FsLex>
  <Compile Include="$(FsYaccOutputFolder)Parser.fsi" />
  <Compile Include="$(FsYaccOutputFolder)Parser.fs" />
  <Compile Include="$(FsLexOutputFolder)Lexer.fs" />
</ItemGroup>

Setting FsLexOutputFolder or FsYaccOutputFolder yourself takes precedence. The default relies on FsLexYacc.targets being imported after the SDK targets, which is how the NuGet package imports it. If you import the targets file yourself from the project body, the build fails with an error telling you so.

To write the generated files next to the grammar instead, as FsLexYacc 12 and earlier did, set FsLexYaccOutputToIntermediate to false:

<PropertyGroup>
  <FsLexYaccOutputToIntermediate>false</FsLexYaccOutputToIntermediate>
</PropertyGroup>

When upgrading from FsLexYacc 12, a project that still compiles Parser.fs or Lexer.fs next to the grammar fails the build, because those copies are no longer regenerated. Change the Compile items as shown above and delete the old generated files, or opt out.

When the grammar has shift/reduce or reduce/reduce conflicts, FsYacc prints only how many there are. To see each conflict, with the state, the terminal and the two actions involved, add -v in the OtherFlags section. That writes a .fsyacc.output listing file next to the generated parser containing the conflicts and the LALR tables:

<FsYacc Include="..\LexAndYaccMiniProject\Parser.fsy">
  <OtherFlags>--module Parser -v</OtherFlags>
</FsYacc>

Command line options

fsyacc <filename> fsyacc <filename>

    -o <string> Name the output file.

    -v: Produce a listing file with the LALR tables and the detail of each conflict.

    --module <string> Define the F# module name to host the generated parser.

    --internal: Generate an internal module

    --open <string> Add the given module to the list of those to open in both the generated signature and implementation.

    --light: (ignored)

    --light-off: Add  to the top of the generated file

    --ml-compatibility: Support the use of the global state from the 'Parsing' module in FSharp.PowerPack.dll.

    --tokens: Simply tokenize the specification file itself.

    --lexlib <string> Specify the namespace for the implementation of the parser table interperter (default FSharp.Text.Parsing)

    --parslib <string> Specify the namespace for the implementation of the parser table interperter (default FSharp.Text.Parsing)

    --codepage <int> Assume input lexer specification file is encoded with the given codepage.

    --help: display this list of options

    -help: display this list of options

Managing and using position markers

Each action in an fsyacc parser has access to a parseState value through which you can access position information.

type IParseState =
    abstract InputStartPosition: int -> Position
    abstract InputEndPosition: int -> Position
    abstract InputRange: int -> Position * Position
    abstract ParserLocalStore: IDictionary<string,obj>
    abstract ResultRange  : Position * Position
    abstract RaiseError<'b> : unit -> 'b

Input relate to the indexes of the items on the right hand side of the current production, the Result relates to the entire range covered by the production. You shouldn't use GetData directly - these is called automatically by $1, $2 etc. You can call RaiseError if you like.

You must set the initial position when you create the lexbuf:

let setInitialPos (lexbuf:LexBuffer<_>) filename =
     lexbuf.EndPos <- { pos_bol = 0;
                        pos_fname=filename;
                        pos_cnum=0;
                        pos_lnum=1 }

You must also update the position recorded in the lex buffer each time you process what you consider to be a new line:

let newline (lexbuf:lexbuf) =
    lexbuf.EndPos <- lexbuf.EndPos.AsNewLinePos()

Likewise if your language includes the ability to mark source code locations, see custom essay (e.g. the #line directive in OCaml and F#) then you must similarly adjust the lexbuf.EndPos according to the information you grok from your input.

Notes on OCaml Compatibility

OCamlYacc accepts the following:

%type < context -> context > toplevel

For FsYacc you just add parentheses:

%type < (context -> context) > toplevel

type Expr =
  | Val of string
  | Int of int
  | Float of float
  | Decr of Expr

Multiple items
val string: value: 'T -> string

--------------------
type string = System.String

Multiple items
val int: value: 'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> =
int

Multiple items
val float: value: 'T -> float (requires member op_Explicit)

--------------------
type float = System.Double

--------------------
type float<'Measure> =
float

module Seq
from Microsoft.FSharp.Collections

type 'T list = List<'T>

Multiple items
union case Prog.Prog: Stmt list -> Prog

--------------------
type Prog = | Prog of Stmt list

type Prog = | Prog of Stmt list

namespace System

Represents a 32-bit signed integer.
type Int32 =
  member CompareTo: value: int -> int + 1 overload
  member Equals: obj: int -> bool + 1 overload
  member GetHashCode: unit -> int
  member GetTypeCode: unit -> TypeCode
  member ToString: unit -> string + 3 overloads
  member TryFormat: utf8Destination: Span<byte> * bytesWritten: byref<int> * ?format: ReadOnlySpan<char> * ?provider: IFormatProvider -> bool + 1 overload
  static member Abs: value: int -> int
  static member BigMul: left: int * right: int -> int64
  static member Clamp: value: int * min: int * max: int -> int
  static member CopySign: value: int * sign: int -> int
  ...

Represents a double-precision floating-point number.
type Double =
  member CompareTo: value: float -> int + 1 overload
  member Equals: obj: float -> bool + 1 overload
  member GetHashCode: unit -> int
  member GetTypeCode: unit -> TypeCode
  member ToString: unit -> string + 3 overloads
  member TryFormat: utf8Destination: Span<byte> * bytesWritten: byref<int> * ?format: ReadOnlySpan<char> * ?provider: IFormatProvider -> bool + 1 overload
  static member (<) : left: float * right: float -> bool
  static member (<=) : left: float * right: float -> bool
  static member (<>) : left: float * right: float -> bool
  static member (=) : left: float * right: float -> bool
  ...

Multiple items
module List
from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | op_Nil
  | op_ColonColon of Head: 'T * Tail: 'T list
  interface IReadOnlyList<'T>
  interface IReadOnlyCollection<'T>
  interface IEnumerable
  interface IEnumerable<'T>
  member GetReverseIndex: rank: int * offset: int -> int
  member GetSlice: startIndex: int option * endIndex: int option -> 'T list
  static member Cons: head: 'T * tail: 'T list -> 'T list
  member Head: 'T
  member IsEmpty: bool
  member Item: index: int -> 'T with get
  ...

val rev: list: 'T list -> 'T list

union case Expr.Val: string -> Expr

union case Expr.Int: int -> Expr

union case Expr.Float: float -> Expr

union case Expr.Decr: Expr -> Expr

union case Stmt.Assign: string * Expr -> Stmt

union case Stmt.While: Expr * Stmt -> Stmt

Multiple items
union case Stmt.Seq: Stmt list -> Stmt

--------------------
module Seq
from Microsoft.FSharp.Collections

union case Stmt.IfThen: Expr * Stmt -> Stmt

union case Stmt.IfThenElse: Expr * Stmt * Stmt -> Stmt

union case Stmt.Print: Expr -> Stmt

Multiple items
namespace FSharp

--------------------
namespace Microsoft.FSharp

type obj = System.Object

type unit = Unit