You can turn a file into an on-demand sequence of results using a sequence builder:

open System.IO

let readEmployees (fileName : string) =
    seq {
        use reader = File.OpenText fileName
        while not reader.EndOfStream do
            yield reader.ReadLine() |> parseEmployee
    }

The following example takes the first three entries from an artificially generated file containing 10,000 copies of the same employee:

> File.WriteAllLines("employees.txt", Array.create 10000 line);;
val it : unit

> let firstThree = readEmployees("employees.txt") |> Seq.take 3;;
val firstThree : (string * string * System.DateTime * string) list

> for (last,first,startDate,title) in firstThree do
      printfn "%s %s started on %A" first last startDate;;
John Smith started on 20/01/1986 00:00:00
John Smith started on 20/01/1986 00:00:00
John Smith started on 20/01/1986 00:00:00

This technique is often used to do exploratory analysis of large data files. After the algorithm is refined using a prefix of the data, the analysis can then easily be run directly over the full data file.

Another technique that's frequently used to extract information from strings is to use regular expressions. The System.Text.RegularExpressions namespace provides convenient string-matching and -replacement functions. For example, let's say you have a log file containing a record of HTML GET requests. Here is a sample request:

GET /favicon.ico HTTP/1.1

The following code captures the name of the requested resource (favicon.ico) and the lower version number of the HTML protocol (1) used:

open System.Text.RegularExpressions

let parseHttpRequest line =
    let result = Regex.Match(line, @"GET (.*?) HTTP/1.([01])$")
    let file = result.Groups.[1].Value
    let version = result.Groups.[2].Value
    file, version

The relevant fields are extracted by using the Groups attribute of the regular expression match to access the matched strings for each parenthesized group in the regular expression.

You saw the basic structure of lexer files in the preceding example, which contained only a handful of rules. In general, fslex input files have the following simple structure:

// Preamble – any user code you need for the lexer, such as opening modules, etc.
{ [Code] }

// Definitions – named patterns that you can use in the rules or other definitions
let [Ident_1] = [Pattern]
let ...

// Rules – text patterns that trigger certain actions
rule [Rule_1] [arg1... argn] = parse
   | [Pattern] { [Action] }
   | ...
   | [Pattern] { [Action] }
and [Rule_2] [arg1... argn] = parse
    ...
rule [Rule_3] ...

// Epilogue – code that can call the lexer rules defined above
{ [Code] }

Each rule defined in the lexer becomes an F# function that can be accessed from other modules and the lexer itself. You can place comments between (* and *), and you can also use // comments in the actions just like in any other F# code. Patterns can be any of the forms listed in Table 16-2.

Lexical actions are pieces of F# code enclosed in braces; they're executed when a lexer match is made. You can put any logic here that you like; typically, you construct a token. Tokens are specified in the parser definition using the %token directive (you see this later in this chapter); if you don't have a parser, any user-defined type will do. If your lexer rules don't construct tokens, or if your lexer is simple enough, often you may want to put all driver code in the epilogue section to create a stand-alone lexer.

Listing 16-3 shows a lexer that constructs a list of tokens that then is printed. It can recognize integers, floats, identifiers, and the symbols ^, *, -, and +. Any other character causes a runtime exception.

{
module SimpleTokensLex

open System

type token =
    | INT    of int
    | FLOAT  of float
    | ID     of string
    | STRING of string
    | PLUS | MINUS | TIMES | HAT
    | EOF

let lexeme = Lexing.LexBuffer<_>.LexemeString
}

let num        = ['0'-'9']+
let intNum     = '-'? num
let floatNum   = '-'? num ('.' num)? (['e' 'E'] num)?
let ident      = ['a'-'z']+
let whitespace = ' ' | '	'
let newline    = '
' | '
' '
'

rule token = parse
    | intNum     { INT (Convert.ToInt32 (lexeme lexbuf)) }

| floatNum   { FLOAT (Convert.ToDouble (lexeme lexbuf))  }
    | ident      { ID (lexeme lexbuf)  }
    | '+'        { PLUS }
    | '-'        { MINUS }
    | '*'        { TIMES }
    | '^'        { HAT }
    | whitespace { token lexbuf }
    | newline    { token lexbuf }
    | eof        { EOF }
    | _          { failwithf "unrecognized input: '%s'" (lexeme lexbuf) }

You can generate the lexer using this:

fslex simpleTokensLex.fsl --unicode

The generated lexer contains a single module SimpleTokensLex with one entry-point function for each rule. In this case, the type of this function is as follows:

val token: Lexing.LexBuffer<char> -> SimpleTokensLex.token

The following indicates how you can imperatively generate a simple token stream from a string and print the results in F# Interactive:

> #r "FSharp.PowerPack.dll";;
...
> #load "SimpleTokensLex.fs";;
> let lexbuf = Lexing.LexBuffer<_>.FromString "3.4 x 34 xyx";;
val lexbuf : Lexing.LexBuffer<char>

> SimpleTokensLex.token lexbuf;;
val it : SimpleTokensLex.token = FLOAT 3.4

> SimpleTokensLex.token lexbuf;;
val it : SimpleTokensLex.token = ID "x"

> SimpleTokensLex.token lexbuf;;
val it : SimpleTokensLex.token = INT 34

> SimpleTokensLex.token lexbuf;;
val it : SimpleTokensLex.token = ID "xyx"

> SimpleTokensLex.token lexbuf;;
val it : SimpleTokensLex.token = EOF

> SimpleTokensLex.token lexbuf;;
System.Exception: End of file on lexing stream

Lexers generated by fslex keep track of partial information about the position of the most recently accepted token within the source stream of characters. In particular, the StartPos and EndPos properties on the LexBuffer type return Lexing.Position values. A partial signature of this position type is as follows:

type Position with
     // The file name associated with the input stream.
     member FileName : string

     // The line number in the input stream, assuming fresh
     // positions have been updated modifying the
     // EndPos property of the LexBuffer.
     member Line : int

     // The character number in the input stream
     member AbsoluteOffset : int

     // Return the column number marked by the position, e.g. the
     // difference between the AbsoluteOffset and the StartOfLineAbsoluteOffset.
     member Column : int

     // Convert a position just beyond the end of a line to a
     // position at the start of the next line.
     member NextLine : Position
     ...
end

In some cases, certain lexer actions must perform extra bookkeeping. In particular, the lexer should update the EndPos property of the LexBuffer each time a newline marker is processed (this is left up to the lexer because the interpretation of newline characters can differ between various lexers). In particular, you can change the endOfLine rule in the lexer in Listing 16-3 to make this update:

| newline    { lexbuf.EndPos <- lexbuf.EndPos.NextLine;
               token lexbuf }

You can now experiment with this updated lexer in F# Interactive and examine the StartPos and EndPos properties after fetching each token:

> let lexbuf = Lexing.LexBuffer<_>.FromString "3.4 
 34 xyx";;
val lexbuf : Lexing.LexBuffer<char>

> SimpleTokensLex.token lexbuf;;
val it : SimpleTokensLex.token = FLOAT 3.4

> (lexbuf.StartPos.Line, lexbuf.StartPos.Column);;
val it : int * int = (0,0)

> (lexbuf.EndPos.Line, lexbuf.EndPos.Column);;

val it : int * int = (0,3)

> SimpleTokensLex.token lexbuf;;
val it : SimpleTokensLex.token = INT 34

> (lexbuf.StartPos.Line, lexbuf.StartPos.Column);;
val it : int * int = (1,1)

Often, you may need to attach position information to each lexer token. However, when you use lexers in conjunction with fsyacc parser generators, the position information is automatically read after each token is processed and then stored in the parser's state. We return to this topic later in this chapter.

So far, you've seen examples with one lexing rule only. This is because the main lexer rule was sufficient for all tokens and you haven't yet come across the need to lex input that can't be described by a regular expression. To illustrate this point, for instance, say you want to lex comments enclosed by (* and *). Formally, you have an opening delimiter, followed by the body of the comment, and finally enclosed by the closing delimiter. The first attempt, shown here

"(*" _* "*)"

fails because the middle pattern matches everything and you never reach the closing *). So, the best compromise could be as follows

"(*" [^ '*']* "*)"

where you match the inside of the comment as long as you don't see an asterisk, and then you try to match the closing *). This of course fails on any comment that contains an asterisk. You can play with this regular expression a little more. The inside of the comment is either anything but an asterisk or all asterisks that aren't followed by another asterisk or right parenthesis:

"(*" ([^ '*'] | ('*'+ ([^ '*' ')'])))* '*'+ ')'

This is about as close as you can get, and yet even this pattern has a problem: it can't match nested comments; it always stops at the first closing delimiter, ignoring all nested comment openers.

You can handle this problem by using a multirule lexer. The following rules show the additions you can make to the SimpleTokensLex.fsl lexer from Listing 16-3 in order to properly handle comments and strings:

rule token =
    ...
    | "(*"       { comment lexbuf; token lexbuf }
    | """       { STRING (string lexbuf.StartPos "" lexbuf) }
    | _          { failwith "unrecognized input: '%s'" (lexeme lexbuf) }

and comment = parse
    | "(*"       { comment lexbuf; comment lexbuf  }
    | "*)"       { () }
    | "
"       { lexbuf.EndPos <- lexbuf.EndPos.NextLine

comment lexbuf }
    | eof        { failwith "Unterminated comment" }
    | _          { comment lexbuf }

and string pos s = parse
    | "\" ('"' | 'n' | 'r' | 't')
                  { let s' = s + (match lexeme lexbuf with
                         | "\"" -> """
                         | "\n" ->  "
"
                         | "\r" ->  "
"
                         | "\t" ->  "	"
                         | "\\" -> "\"
                         | _ ->      "")
                    string pos s' lexbuf }
    | """         { s }
    | "
"         { lexbuf.EndPos <- lexbuf.EndPos.NextLine
                     string pos (s + "
") lexbuf }
    | eof          { failwithf "end of file in string started at or near %A" pos }
    | _            { string pos (s + (lexeme lexbuf)) lexbuf }

Comment processing begins when you encounter (* in the token rule. When the closing *) is encountered, you exit one invocation of the comment rule. The idea is that you deal with nested comments by recursively applying the lexer when a nested comment is reached. Note the double invocation of comment lexbuf for nested comment delimiters: once to tokenize the comment that belongs to the opener and again to tokenize the rest of the enclosing comment. There are also two further matches within the comment rule. If you hit the end of the source stream, you have an unterminated comment, and you raise an exception; in every other case, you move forward inside the comment.

In the example, strings are also handled by a separate lexer rule string that is invoked by the token lexer when you encounter the double-quote character. This rule takes two parameters: the string consumed so far and the start position of the string. The latter is used to report a nicer error for an unterminated string (you could also use this technique for the matching case for comments). You can also check whether you have an escaped character in the input. If so, you append the appropriate escape sequence to the string already accumulated and advance the current position. Upon encountering the closing character, you return the overall string. An imperative System.Text.StringBuffer object can also be used to accumulate the string, which is more efficient if strings get very long.

There are various limitations that you can't handle with recursive-descent parsers. For instance, if you translate a left-recursive production into code, you get an infinite recursion, like so:

<polynomial> ::= <polynomial> '+' <term> | <term>

This corresponds to the following:

let rec parsePolynomial src =
    let poly, src = parsePolynomial src
    ...

Another common problem with LL(k) parsing for some k>=1 is that the grammar rules for a given nonterminal can't start with the same symbols, or else there is no easy way to decide which rule to apply (because each is determined to be applicable upon checking k number of symbols). In such cases, left-factoring can be applied. For example, you can move the symbols after the common part into another production, as shown here:

<polynomial> ::= <term> | <term> '+' <polynomial>
can be refactored as
<polynomial> ::= <term> <polymomialTail>
<polynomialTail> ::= EPSILON  | '+' <polynomial>

Here, EPSILON is the empty symbol, so the function that parses polynomialTail both checks for a plus symbol and issues a call to parse a polynomial or exit in the absence of an initial plus symbol, leaving the input unchanged. Although this case is relatively simple (you can parse terms until they're followed by a plus sign iteratively), coding such grammar rules in the general case is cumbersome.

Problems such as these arise because you have to make parsing decisions early on (such as deciding which grammar rule you're pursuing if there are multiple choices for a given nonterminal), because they construct the parse tree from the top and proceed downward. LR parsers, on the other hand, postpone these decisions as much as possible and construct the parse tree bottom-up, resulting in much more flexibility both in terms of how naturally grammar rules can be expressed and how they can be mapped into code.

Listing 16-6 shows a lexer for the language in the file KittyLexer.fsl. It's similar to lexers developed earlier in this chapter. The one exception is that you use a keyword table. Matching against lexemes to identify tokens is a sensible solution only if there are relatively few cases. Tokenizing a large set of keywords and operators using explicit rules can lead to large lexers. This situation is often handled using tables that contain the possible lexeme matches and the tokens to be returned. Listing 16-6 uses simple dictionaries (maps).

{
module KittyLexer

open System
open KittyParser
open Microsoft.FSharp.Text.Lexing

let lexeme = LexBuffer<_>.LexemeString

let ids = [ ("while",   WHILE);
            ("begin",   BEGIN);
            ("end",     END);
            ("do",      DO);
            ("if",      IF);
            ("then",    THEN);
            ("else",    ELSE);
            ("print",   PRINT);]

let idsMap = Map.ofList ids

let ident lexbuf tokenText =
   if Map.containsKey tokenText idsMap then Map.find tokenText idsMap
   else ID tokenText
}

let num        = ['0'-'9']+
let alpha      = ['a'-'z' 'A'-'Z']
let ident      = alpha+ (alpha | ['_' '$'])*
let integer    = '-'? num
let whitespace = ' ' | '	'
let newline    = '
' | '
' '
'

rule token = parse
    | whitespace { token lexbuf }
    | newline    { lexbuf.EndPos <- lexbuf.EndPos.NextLine; token lexbuf }
    | "("        { LPAREN }
    | ")"        { RPAREN }
    | "+"        { PLUS }
    | "-"        { MINUS }
    | "*"        { TIMES }
    | ";"        { SEMI }
    | ":="       { ASSIGN }
    | ident      { ident lexbuf (lexeme lexbuf) }
    | integer    { INT (Int32.Parse(lexeme lexbuf)) }
    | eof        { EOF }

Note that at compilation time, the lexer depends on the parser defined later in Listing 16-7. This is because the lexer must return the type of tokens required by the parser.

You can generate the lexer by calling fslex:

fslex KittyLexer.fsl --unicode

This produces KittyLexer.fs, which contains the implementation of the lexer.

Listing 16-7 shows the parser specification for the Kitty language in the file KittyParser.fsy.

%{
open Ast
%}

// The start token becomes a parser function in the compiled code.
%start start

// These are the terminal tokens of the grammar along with the types of
// the data carried by each token:
%token <string> ID
%token <int> INT
%token PLUS MINUS TIMES LPAREN RPAREN IF THEN ELSE
%token WHILE DO BEGIN END PRINT SEMI ASSIGN EOF

// Associativity and Precedences - Lowest precedence comes first
%left PLUS MINUS
%left TIMES

// This is the type of the data produced by a successful reduction
// of the 'start' symbol:
%type <prog> start

%%

start: Prog                   { $1 }

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

Expr: ID                      { Val $1 }
    | INT                     { Int $1 }
    | Expr PLUS Expr          { Plus ($1, $3) }
    | Expr MINUS Expr         { Minus ($1, $3) }
    | Expr TIMES Expr         { Times ($1, $3) }
    | LPAREN Expr RPAREN      { $2 }


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  }

You can generate the parser by calling fsyacc:

fsyacc KittyParser.fsy --module KittyParser

This produces KittyParser.fs, which contains the implementations of the parser, along with a signature file KittyParser.fsi. The generated parser has one entry point for each %start symbol (here there is only one). The type of this entry point is as follows:

val start : (LexBuffer<'a> -> token) -> LexBuffer<'a> -> Ast.prog

You see how to use this function a little later in this chapter. In a roundabout way, the type says, "If you give me a lexing function that generates tokens and give me a LexBuffer to supply to that lexing function, then I'll generate you an Ast.prog." The generic type variable indicates that the parser is independent of the characters manipulated by the LexBuffer.

We now cover in more detail the different aspects of fsyacc parsing illustrated by this example.

// Preamble – any code you need for the parser, such as opening modules, etc.
%{ [Code] %}

// Tokens and their types – each line may contain several tokens
%token <[Type]> [TokenName] ... [TokenName]
...
// Associativity and precedences – where tokens associate (left, right,
// nonassoc) and how strongly they bind (in the order of their declaration)
%left     [TokenName]
%right    [TokenName]
%nonassoc [TokenName]
...


// Start symbols and their types
%start [StartSymbol]
%type <[Type]> [StartSymbol]
%%

// Productions – defining how non-terminals are derived
[Symbol] : [Symbols_1] { [Code_1] }

| [Symbols_2] { [Code_2] }
...

In Kitty, statements can be separated by semicolons. This is handled in the StmtList grammar production, whose semantic extract is a list of statements. Note that you could have written this rule in a head-recursive way:

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

Unlike in recursive-descent or any other LL parsing technique, the previous rule doesn't pose a problem for fsyacc, and thus no left-factoring is needed. However, it does create a copy of the statement list each time a new expression is appended to it. You eliminate this by using the following productions

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

combined with a List.rev where the rule is used. This rule consumes all statements and inserts them, one by one, into the singleton list that contains the first statement. As a result, the return list is in reverse order, which is why you need to apply List.rev. You may want to define a separate rule to perform this operation. Another feature that is often needed is the ability to parse empty or optional lists. This can be easily accomplished using an empty (epsilon) symbol, as in the following example:

StmtListOpt:
               { [] }
    | StmtList { $1 }

This rule matches an optional list of statements and returns an empty list if no statements can be parsed.

As usual with arithmetic operators, division and multiplication should take precedence over addition and subtraction: 1+2*3 should be parsed as 1+(2*3). With fsyacc, this can be expressed easily using the associativity directives—or, to be more precise, their ordering:

// Associativity and Precedences - Lowest precedence comes first
%left PLUS MINUS
%left TIMES

By specifying what tokens associate and where (how strongly they bind), you can control how parse derivations are performed. For instance, giving left-associativity to the addition operator (PLUS), given an input 1+2+3, the parser automatically generates a nonambiguous derivation in the form of (1+2)+3. The basic arithmetic operators are left-associative and should be listed from the lowest precedence to the highest; in the example, the addition and subtraction operators have lower precedence than multiplication—the way it should be. Other associativity specifications include %nonassoc and %right, which are used to denote that a given symbol doesn't associate or associates to the right, respectively. The former is useful for relational and equality operators such as <, >, or !=, where the operator isn't applicable if applied multiple times: 1 > 2 > 3 yields a syntax error.

You can also give precedence to a rule by using %prec at the end of the rule and giving a token whose precedence is to be applied. You can list arbitrary tokens in the associativity and precedence declarations, even if they haven't been declared as tokens, and use them in such situations. You can find more details about specifying precedence at www.expert-fsharp.com/Topics/FsYacc.

Each state in this extract corresponds to one or more items, which are productions that indicate what has been seen while parsing them. This current position with respect to a rule is marked with a period (.). Furthermore, to each state belong various actions that are triggered by certain look-ahead symbols. For instance, the action in some state as follows

action 'ID' (noprec):   shift 7

indicates that if the ID token, which has no defined precedence, is encountered as look-ahead, the parser pushes this token to the parsing stack and shifts to state 7. For reduce actions, the rule that is reduced is shown. An error (reject) or accept action is shown for tokens that trigger a syntax error or acceptance, respectively.

The parser state extract also provides useful information about conflicts in your grammar. Conflicts arise when your grammar is ambiguous (which translates to having more than one choice for a parser action at any time), ultimately meaning more than one derivation can accept a given input. You can do a number of things to disambiguate your grammar. You can apply precedence to various tokens or rules, or rewrite your rules to be consistent and unambiguous. There are two main sources of grammar conflicts: reduce-reduce and shift-reduce conflicts. Reduce-reduce conflicts are considered really bad because there are multiple rules to reduce by at a given situation. Although fsyacc applies a disambiguation strategy (reducing by the grammar rule that was defined earlier), you should avoid reduce-reduce conflicts as much as possible.

Shift-reduce conflicts arise when the parser has the choice to shift a token or reduce by a rule. Unless you fix this conflict, fsyacc favors the shift action and defers the reduction to a later point. In some situations (for instance, the dangling-else problem), this yields the expected behavior; but in general, any such conflict is also considered a serious problem.

You can generate the parsers and lexers by calling fslex and fsyacc:

fslex KittyLexer.fsl --unicode
fsyacc KittyParser.fsy --module KittyParser

This produces KittyLexer.fs and KittyParser.fs, which contain the implementations of the parser and lexer. You can test these using F# Interactive by loading the files directly using the #load directive. The following code creates a LexBuffer called lexbuf. It then calls the KittyParser.start entry point for the parser, passing KittyLexer.token as the lexical analysis engine and lexbuf as the LexBuffer. This connects the parser and the lexer:

open Ast
open KittyParser
open KittyLexer

let parseText text =
    let lexbuf = Lexing.LexBuffer<_>.FromString text
    try
        KittyParser.start KittyLexer.token lexbuf
    with e ->
        let pos = lexbuf.EndPos
        failwithf "Error near line %d, character %d
" pos.Line pos.Column

You can now test this function interactively:

> let sample = "counter := 100; accum := 0; 

                while counter do 

                begin 

                    counter := counter - 1; 

                    accum := accum + counter 

                end; 

                print accum";;
val sample : string = "..."

> parseText sample;;
val it : Ast.prog
= Prog
   [Assign ("counter",Int 100); Assign ("accum",Int 0);
    While
     (Val "counter",
      Seq
       [Assign ("counter",Minus (Val "counter",Int 1));
        Assign ("accum",Plus (Val "accum",Val "counter"))]); Print Val "accum"]

Writing an evaluator for Kitty is straightforward. Here, you use an environment that maps variable names to the integer values they store. As expected, assignments in the source language add a binding for a given variable, and evaluating variables reads a value from this environment. Because of the lack of other types in Kitty, you use a nonzero value for the Boolean true and zero for false and wire the logic of the conditional and looping construct accordingly:

let rec evalE (env: Map<string, int>) = function
    | Val v          -> if env.ContainsKey v then env.[v]
                        else failwith ("unbound variable: " + v)
    | Int i          -> i
    | Plus  (e1, e2) -> evalE env e1 + evalE env e2
    | Minus (e1, e2) -> evalE env e1 - evalE env e2

| Times (e1, e2) -> evalE env e1 * evalE env e2

and eval (env: Map<string, int>) = function
    | Assign (v, e) ->
         env.Add(v, evalE env e)
    | While (e, body) ->
         let rec loop env e body =
             if evalE env e <> 0 then
                 loop (eval env body) e body
             else env
         loop env e body
    | Seq stmts ->
         List.fold eval env stmts
    | IfThen (e, stmt) ->
         if evalE env e <> 0 then eval env stmt else env
    | IfThenElse (e, stmt1, stmt2) ->
         if evalE env e <> 0 then eval env stmt1 else eval env stmt2
    | Print e ->
         printf "%d" (evalE env e); env

With these at hand, continuing the same interactive session, you can now evaluate the sample Kitty program:

> match parseText sample with
    | Prog stmts ->
        eval Map.empty (Seq stmts) |> ignore;;
4950
val it : unit = ()