Matthew Manela's Home Page

This lexer allows you to define your regular expression based rules in a very declarative way using F# computation expressions.

open Lexer
let definitions = 
    lexerDefinitions {
        do! addNextlineDefinition "NEWLINE" @"(\n\r)|\n|\r"
        do! addIgnoreDefinition "WS"        @"\s"
        do! addDefinition "LET"             "let"
        do! addDefinition "ID"              "(?i)[a-z][a-z0-9]*"
        do! addDefinition "FLOAT"           @"[0-9]+\.[0-9]+"
        do! addDefinition "INT"             "[0-9]+"
        do! addDefinition "OPERATOR"      @"[+*=!/&|<>\^\-]+"   
    }

With those defined you can execute the lexer with:

open Lexer
let lex input = 
    try    
        let y = Lexer.tokenize definitions input
        printfn "%A" y
    with e -> printf "%s" e.Message
lex "let a = 5"

Which will result in:

seq [{name = "LET";
      text = "let";
      pos = 0;
      column = 0;
      line = 0;}; {name = "ID";
                   text = "a";
                   pos = 4;
                   column = 4;
                   line = 0;}; {name = "OPERATOR";
                                text = "=";
                                pos = 6;
                                column = 6;
                                line = 0;}; {name = "INT";
                                             text = "5";
                                             pos = 8;
                                             column = 8;
                                             line = 0;}]

The lexer’s code is structured in three parts.  The first part is a state monad using the F# computation expressions.  This enables the declarative approach (seen above) to setup your lexer rules.

module StateMonad
type State<'s,'a> = State of ('s -> ('a *'s))
let runState (State f) = f
type StateBuilder() = 
    member b.Return(x) = State (fun s -> (x,s))
    member b.Delay(f) = f() : State<'s,'a>
    member b.Zero() = State (fun s -> ((),s))
    member b.Bind(State p,rest) = State (fun s -> let v,s2 = p s in  (runState (rest v)) s2)
    member b.Get () = State (fun s -> (s,s))
    member b.Put s = State (fun _ -> ((),s))

The second part are the combinators that are used to define your lexer rules.  There are three main combinators:  AddDefinition which lets you define a name / regex pair, AddIgnoreDefinition which lets you define characters which the lexer should ignore and AddNextlineDefinition which lets you define what characters determine a new line.

type LexDefinitions = 
  {regexes : string list;
   names : string list;
   nextlines : bool list;
   ignores : bool list; }
   
let buildDefinition name pattern nextLine ignore =
    state {
        let! x = state.Get()
        do! state.Put { regexes = x.regexes @  [sprintf @"(?<%s>%s)" name pattern];
                        names = x.names @ [name]; 
                        nextlines  = x.nextlines @ [nextLine];
                        ignores = x.ignores @ [ignore]}
    }
    
let addDefinition name pattern = buildDefinition name pattern false false
let addIgnoreDefinition name pattern = buildDefinition name pattern false true
let addNextlineDefinition name pattern = buildDefinition name pattern true true    

And the final part is the code that performs the tokenizing.  It uses the Seq.unfold method to create the list of tokens.  Unfold is a function which takes a single item and generates a list of new items from it.  It is the opposite of Seq.fold which takes a list of items and turns it into a single item.  The tokenize function used Seq.unfold to generate each token while keeping track of the current line number, position in that line and position in the input string.

type Token = 
    { name : string;
      text: string; 
      pos :int;
      column: int;
      line: int }
   
let createLexDefs pb =  (runState pb) {regexes = []; names = []; nextlines = []; ignores = []} |> snd
 
let tokenize lexerBuilder (str:string) = 
    let patterns = createLexDefs lexerBuilder
    let combinedRegex =  Regex(List.fold (fun acc reg -> acc + "|" + reg) (List.head patterns.regexes) (List.tail patterns.regexes))
    let nextlineMap = List.zip patterns.names patterns.nextlines |> Map.ofList
    let ignoreMap = List.zip patterns.names patterns.ignores |> Map.ofList
    let tokenizeStep (pos,line,lineStart) = 
        if pos >= str.Length then
            None
        else
            let getMatchedGroupName (grps:GroupCollection) names = List.find (fun (name:string) -> grps.[name].Length > 0) names
            match combinedRegex.Match(str, pos) with
                | mt when mt.Success && pos = mt.Index  -> 
                    let groupName = getMatchedGroupName mt.Groups patterns.names
                    let column = mt.Index - lineStart
                    let nextPos = pos + mt.Length
                    let (nextLine, nextLineStart) = if nextlineMap.Item groupName then (line + 1, nextPos) else (line,lineStart)
                    let token = if ignoreMap.Item groupName 
                                then None 
                                else Some {
                                        name = groupName; 
                                        text = mt.Value; 
                                        pos = pos; 
                                        line = line; 
                                        column = column; }
                    Some(token, (nextPos, nextLine, nextLineStart))
                    
                | otherwise -> 
                    let textAroundError = str.Substring(pos, min (pos + 5) str.Length)
                    raise (ArgumentException (sprintf "Lexing error occured at line:%d and column:%d near the text:%s" line (pos - lineStart) textAroundError))
    Seq.unfold tokenizeStep (0, 0, 0) |> Seq.filter (fun x -> x.IsSome) |> Seq.map (fun x -> x.Value)

Lastly, here are the unit tests written using XUnit.Net:

module LexerFacts
open Xunit
open Lexer
open System.Linq
let simpleDefs = 
    state {
        do! addNextlineDefinition "NextLine"           "/"
        do! addIgnoreDefinition "IgnoredSymbol"        "=+"
        do! addDefinition "String"                     "[a-zA-Z]+"
        do! addDefinition "Number"                     "\d+"
        do! addDefinition "Name"                       "Matt"
    }
[<Fact>]
let Will_return_no_tokens_for_empty_string() =
  
    let tokens = Lexer.tokenize simpleDefs ""
    
    Assert.Equal(0, tokens.Count())
[<Fact>]
let Will_throw_exception_for_invalid_token() =
  
    let tokens = Lexer.tokenize simpleDefs "-"
    let ex = Assert.ThrowsDelegateWithReturn(fun () -> upcast tokens.Count()) |> Record.Exception
    Assert.NotNull(ex)
    Assert.True(ex :? System.ArgumentException)
[<Fact>]
let Will_ignore_symbols_defined_as_ignore_symbols() =
  
    let tokens = Lexer.tokenize simpleDefs "========="
    
    Assert.Equal(0, tokens.Count())
[<Fact>]
let Will_get_token_with_correct_position_and_type() =
  
    let tokens = Lexer.tokenize simpleDefs "1one=2=two"
    
    Assert.Equal("Number",tokens.ElementAt(2).name)
    Assert.Equal("2",tokens.ElementAt(2).text)
    Assert.Equal(5,tokens.ElementAt(2).pos)
    Assert.Equal(5,tokens.ElementAt(2).column)
    Assert.Equal(0,tokens.ElementAt(2).line)
[<Fact>]
let Will_tokenize_string_with_alernating_numbers_and_strings() =
  
    let tokens = Lexer.tokenize simpleDefs "1one2two"
    
    Assert.Equal("1",tokens.ElementAt(0).text)
    Assert.Equal("one",tokens.ElementAt(1).text)
    Assert.Equal("2",tokens.ElementAt(2).text)
    Assert.Equal("two",tokens.ElementAt(3).text)
[<Fact>]
let Will_increment_line_with_newline_symbol() =
  
    let tokens = Lexer.tokenize simpleDefs "1one/2two"
    
    Assert.Equal("Number",tokens.ElementAt(2).name)
    Assert.Equal("2",tokens.ElementAt(2).text)
    Assert.Equal(5,tokens.ElementAt(2).pos)
    Assert.Equal(0,tokens.ElementAt(2).column)
    Assert.Equal(1,tokens.ElementAt(2).line)
[<Fact>]
let Will_give_priority_to_lexer_definitions_defined_earlier() =
  
    let tokens = Lexer.tokenize simpleDefs "Matt"
    
    Assert.Equal("String",tokens.ElementAt(0).name)

I attached a zip (Lexer.zip) containing all the code mentioned above.

I don’t know why I didn’t do this long ago, but I am done writing this:

var val = (SomeEnum)Enum.Parse(typeof(SomeEnum),”someString”);

I have typed this too many times and it annoys me. 

I wrote a small extension method on the string type to make this better:

public static class StringExtensions
{
    public static T ToEnum<T>(this string @string)
    {
        return (T)Enum.Parse(typeof (T), @string);
    }
}

With this I can now write the previous line as:

var val = "someString".ToEnum<SomeEnum>()

When reading source code, I sometimes come across unappealing code(sometimes even my own).  However, there is one kind of “bad code” I see quite frequently.  It is a set of unit tests which have had the DRY (Don't Repeat Yourself) principle unduly forced upon them.  DRY is the idea that you shouldn’t have to write the same code over and over; abstract it in a function or a class and just call the abstraction.  This is all well and good in most cases, but I find it misguided when applied to a test case. 

A test case should be like a simple short story.  The characters are introduced, action/conflict occurs and then resolution takes place (sometimes with a moral).  This (kind of) corresponds to the 3 steps of a unit test: arrange, act and assert.  You arrange and setup what you need for your test to run, you perform the action that you are trying to test and then you assert the results. The issue I find is that a coder, in attempting to apply DRY to his test cases, will abstract away all of the arrange step into a function often with a name like SetupExpectations or just Setup.  This goes against the point of a test case. A test case needs to be concise and tell me everything I need to know about how that one bit of functionality works. I don’t want to jump around the test class trying to read one test case. To me, this is like reading a book that says, “If you want to learn about the characters in this book please open this other book.”  This doesn’t stop you from understanding the test, but it slows you down…and is just annoying.

That is why I will come out and say do not apply DRY haphazardly to test cases.

When reading source code, I sometimes come across unappealing code(sometimes even my own).  However, there is one kind of “bad code” I see quite frequently.  It is a set of unit tests which have had the DRY (Don't Repeat Yourself) principle unduly forced upon them.  DRY is the idea that you shouldn’t have to write the same code over and over; abstract it in a function or a class and just call the abstraction.  This is all well and good in most cases, but I find it misguided when applied to a test case. 

A test case should be like a simple short story.  The characters are introduced, action/conflict occurs and then resolution takes place (sometimes with a moral).  This (kind of) corresponds to the 3 steps of a unit test: arrange, act and assert.  You arrange and setup what you need for your test to run, you perform the action that you are trying to test and then you assert the results. The issue I find is that a coder, in attempting to apply DRY to his test cases, will abstract away all of the arrange step into a function often with a name like SetupExpectations or just Setup.  This goes against the point of a test case. A test case needs to be concise and tell me everything I need to know about how that one bit of functionality works. I don’t want to jump around the test class trying to read one test case. To me, this is like reading a book that says, “If you want to learn about the characters in this book please open this other book.”  This doesn’t stop you from understanding the test, but it slows you down…and is just annoying.

That is why I will come out and say do not apply DRY haphazardly to test cases.

Often when learning a new technology I start with a simple console application in which the program is run in a loop it continues to prompt you for more input until you give some command like quit or exit or whatever you choose:

Enter input: someInput
someOutput
Enter input: otherInput
someoutPut
Enter input: quit
Thanks! Come again!

The code for this is in an imperative language is usually something like:

   1: while(true)

   2: {

   3:     Console.Write("\nEnter input:");

   4:     var line = Console.ReadLine();

   5:     if(line == "quit") break;

   6:     

   7:     doSomething(line);

   8: }

   9:  

  10: Console.WriteLine("Thanks! Come Again");

While reading some F# samples, I saw some code doing essentially the same thing which looked something like:

   1: Console.Write "\nEnter input:"

   2: let mutable input = Console.ReadLine()

   3: while input <> "quit"

   4:     do

   5:     

   6:     if input <> "quit" 

   7:     then

   8:         doSomething input

   9:         Console.Write "\nEnter input:" 

  10:         input <- Console.ReadLine()

Now this just feels dirty! In a functional language explicit loop constructs like a while loop feel wrong.  I different way of doing this which is more functional is to create an infinite list of actions.  Where each action represents one iteration of any of the above loops. Then you just execute each action until some condition is met (like seeing the input “quit”).

   1: let action = fun _ ->

   2:     Console.Write "\nEnter input: "

   3:     Console.ReadLine()

   4:  

   5: let readlines = Seq.init_infinite (fun _ -> action())

   6:     

   7: let run item = if item = "quit" 

   8:                 then Some(item) 

   9:                 else

  10:                     parse item 

  11:                     None

  12:  

  13: Seq.first run readlines |> ignore

  14: Console.WriteLine "Thanks! Come Again"

This code makes use of the Seq.init_infinite which create a infinite sequence and Seq.first which enumerates the sequence until the passed in function returns Some.

Often when learning a new technology I start with a simple console application in which the program is run in a loop it continues to prompt you for more input until you give some command like quit or exit or whatever you choose:

Enter input: someInput
someOutput
Enter input: otherInput
someoutPut
Enter input: quit
Thanks! Come again!

The code for this is in an imperative language is usually something like:

   1: while(true)

   2: {

   3:     Console.Write("\nEnter input:");

   4:     var line = Console.ReadLine();

   5:     if(line == "quit") break;

   6:     

   7:     doSomething(line);

   8: }

   9:  

  10: Console.WriteLine("Thanks! Come Again");

While reading some F# samples, I saw some code doing essentially the same thing which looked something like:

   1: Console.Write "\nEnter input:"

   2: let mutable input = Console.ReadLine()

   3: while input <> "quit"

   4:     do

   5:     

   6:     if input <> "quit" 

   7:     then

   8:         doSomething input

   9:         Console.Write "\nEnter input:" 

  10:         input <- Console.ReadLine()

Now this just feels dirty! In a functional language explicit loop constructs like a while loop feel wrong.  I different way of doing this which is more functional is to create an infinite list of actions.  Where each action represents one iteration of any of the above loops. Then you just execute each action until some condition is met (like seeing the input “quit”).

   1: let action = fun _ ->

   2:     Console.Write "\nEnter input: "

   3:     Console.ReadLine()

   4:  

   5: let readlines = Seq.init_infinite (fun _ -> action())

   6:     

   7: let run item = if item = "quit" 

   8:                 then Some(item) 

   9:                 else

  10:                     parse item 

  11:                     None

  12:  

  13: Seq.first run readlines |> ignore

  14: Console.WriteLine "Thanks! Come Again"

This code makes use of the Seq.init_infinite which create a infinite sequence and Seq.first which enumerates the sequence until the passed in function returns Some.

I just wrote this simple plugin for JQuery which lets you synchronize the scroll bars of any collection of elements.  This lets you move the scrollbar of one div it have the scrollbars’ of the rest of the divs move the same exact amount.

Here is the code:

   1: jQuery.fn.synchronizeScroll = function() {

   2:  

   3:            var elements = this;

   4:            if (elements.length <= 1) return;

   5:  

   6:            elements.scroll(

   7:            function() {

   8:                var left = $(this).scrollLeft();

   9:                var top = $(this).scrollTop();

  10:                elements.each(

  11:                function() {

  12:                    if ($(this).scrollLeft() != left) $(this).scrollLeft(left);

  13:                    if ($(this).scrollTop() != top) $(this).scrollTop(top);

  14:                }

  15:                );

  16:            });

  17:        }

Using this is SUPER simple.  Lets say you have several divs defined as:

<div class=”scrollDiv” style=”overflow:auto;”> .. some large content</div>

To synchronize the scrollbars’ on all divs with the class scrollDiv all you need to write is:

$(“.scrollDiv”).synchronizeScroll();

I just wrote this simple plugin for JQuery which lets you synchronize the scroll bars of any collection of elements.  This lets you move the scrollbar of one div it have the scrollbars’ of the rest of the divs move the same exact amount.

Here is the code:

   1: jQuery.fn.synchronizeScroll = function() {

   2:  

   3:            var elements = this;

   4:            if (elements.length <= 1) return;

   5:  

   6:            elements.scroll(

   7:            function() {

   8:                var left = $(this).scrollLeft();

   9:                var top = $(this).scrollTop();

  10:                elements.each(

  11:                function() {

  12:                    if ($(this).scrollLeft() != left) $(this).scrollLeft(left);

  13:                    if ($(this).scrollTop() != top) $(this).scrollTop(top);

  14:                }

  15:                );

  16:            });

  17:        }

Using this is SUPER simple.  Lets say you have several divs defined as:

<div class=”scrollDiv” style=”overflow:auto;”> .. some large content</div>

To synchronize the scrollbars’ on all divs with the class scrollDiv all you need to write is:

$(“.scrollDiv”).synchronizeScroll();

I randomly yesterday started thinking about the unfoldr function in Haskell while working out at the gym (how nerdy is that, I am lifting iron but thinking of functional programming). Unfoldr take a single and an unfolding function and turns it into a list (the opposite of fold).  At the gym I was thinking about an application where I can use this and I decided that when I got home I would use it to write a prime factorization function.  This is a method that when given a number returns the list of its prime factors.

It was easy to write the only part I am not pleased about is the code I used to deal with tuples.  It seems clumsy and I am still looking for a way to clean that up.

One note: The code below references a list of prime numbers called primes , which is not shown.

Here is the code:

   1: primeFactors x = unfoldr findFactor x

   2:                  where

   3:                    first (a,b,c) = a

   4:                    findFactor 1 = Nothing

   5:                    findFactor b = (\(_,d,p)-> Just (p, d))

   6:                                   $ head $ filter ((==0).first) 

   7:                                   $  map (\p -> (b `mod` p, b `div` p, p))  primes

This function will take any number which is greater than 1 and return a list of its prime factors.  But don’t take my word for it, I wrote a quickcheck property to ensure the prime factors multiply back to the original number:

   1: prop_factors num =  num > 1 ==> num == (foldr1 (*) $ primeFactors num)

When running quickcheck on this property you see the following: 

quickCheck prop_factors
OK, passed 100 tests.

I randomly yesterday started thinking about the unfoldr function in Haskell while working out at the gym (how nerdy is that, I am lifting iron but thinking of functional programming). Unfoldr take a single and an unfolding function and turns it into a list (the opposite of fold).  At the gym I was thinking about an application where I can use this and I decided that when I got home I would use it to write a prime factorization function.  This is a method that when given a number returns the list of its prime factors.

It was easy to write the only part I am not pleased about is the code I used to deal with tuples.  It seems clumsy and I am still looking for a way to clean that up.

One note: The code below references a list of prime numbers called primes , which is not shown.

Here is the code:

   1: primeFactors x = unfoldr findFactor x

   2:                  where

   3:                    first (a,b,c) = a

   4:                    findFactor 1 = Nothing

   5:                    findFactor b = (\(_,d,p)-> Just (p, d))

   6:                                   $ head $ filter ((==0).first) 

   7:                                   $  map (\p -> (b `mod` p, b `div` p, p))  primes

This function will take any number which is greater than 1 and return a list of its prime factors.  But don’t take my word for it, I wrote a quickcheck property to ensure the prime factors multiply back to the original number:

   1: prop_factors num =  num > 1 ==> num == (foldr1 (*) $ primeFactors num)

When running quickcheck on this property you see the following: 

quickCheck prop_factors
OK, passed 100 tests.