FSharpCompiler.Analyzing 1.0.4

FSharpCompiler.Analyzing is the runtime for lexical analyzers.

How to write a lexical analyzer, see this solution xp44mm/PolynomialExpressions, We just extract the usage of the runtime library.

first, Install runtime NuGet:

install-package fsharpcompiler.analyzing

You should have written by hand a DFA or automatically generate a DFA by Lex. The DFA is as follows.

module PolynomialExpressions.TermDFA
let dtran = set [ ... ]
let finalLexemes:(Set<uint32>*Set<uint32>) list = [ ... ]

dtran is state transition table. finalLexemes is a list, an element of which is final state and trailing context state of the pattern.

build lexical analyzer using DFA:

open FSharpCompiler.Analyzing
let analyzer = LexicalAnalyzer(TermDFA.dtran, TermDFA.finalLexemes)
let split (tokens:seq<Token>) = analyzer.split(tokens,getTag)

split will return a steam of matched info, which consists of the index of matched pattern, and its occurrence of tokens.

We can now test the split on some sample inputs:

let tokens = [INT 2;ID "x";HAT;INT 2;PLUS;INT 3;ID "x";PLUS;INT 5]
let y = tokens |> Driver.split |> Seq.toList
Should.equal y 
<| [1,[INT 2;ID "x";HAT;INT 2];1,[PLUS;INT 3;ID "x"];0,[PLUS;INT 5]]

The result is a sequence of binary tuples, the type of which is seq<int*token seq>, which consists of an int and an groupings of tokens. The former is the matched pattern, and latter is the matched occurrence.

The results of parsing are a generic data structure, and we translate it into more semantic data. for example:

let mapper = function
| 0, [      INT n] 
| 0, [PLUS ;INT n] ->  Const n
| 0, [MINUS;INT n] ->  Const -n

| 1, [      ID x] 
| 1, [PLUS ;ID x] -> Term(1,x,1)
| 1, [MINUS;ID x] -> Term(-1,x,1)
| 1, [      ID x;HAT;INT i] 
| 1, [PLUS ;ID x;HAT;INT i] -> Term(1,x,i)
| 1, [MINUS;ID x;HAT;INT i] -> Term(-1,x,i)

| 1, [      INT n;ID x] 
| 1, [PLUS ;INT n;ID x] -> Term(n,x,1)
| 1, [MINUS;INT n;ID x] -> Term(-n,x,1)
| 1, [      INT n;ID x;HAT;INT i] 
| 1, [PLUS ;INT n;ID x;HAT;INT i] -> Term(n,x,i)
| 1, [MINUS;INT n;ID x;HAT;INT i] -> Term(-n,x,i)

| _ -> failwith ""

let parse (tokens:seq<Token>) =
    tokens
    |> Driver.split
    |> Seq.map mapper
    |> Seq.toList

In the example above, parse combines all the functions together.