Az F# programozási nyelv

Scanner és parser generátorok

Bevezetés

Az F# saját lexer és parser generátorai: fslex és fsyacc.
Ezeket az eszközöket legtöbbször olyan esetben használjuk, amikor jól definiált szintakszisú felhasználói bementet szeretnénk saját szerkezetté, legtöbbször absztrakt szintakszis fává (AST) alakítani.
Ezeknek az eljárásoknak legtöbbször az a menete, hogy először egy lexikális elemzés során az input stringet tokenek sorozatává alakítjuk, ezután következik a szintaktikai elemzés, mely során pedig a nyelvtani szabályok alapján felépítjük a saját adatszerkezetünket.
A lexelés és parsolás folyamatát nem kell mindig szétválasztanunk, de néhány feladat során hasznos lehet.

A következő részek rövid tartalma:

Kis kiegészítés - szintaktikai, szemantikai analízis

A lexikális elemzés során egy adott inputon szeretnénk tokeneket azonosítani. Token: az input egy részlete, ami a lexerünk szempontjából egy különálló "szót" alkot. Ez lehet szám, azonosító, speciális kulcsszó, vagy karaktereknek akármilyen sorozata, amely önálló egységet alkot.
A szintaktikai analízis során azt vizsgáljuk, hogy az input megfelel-e a nyelvhez rendelt nyelvtani szabályoknak.Pl. F#-ban lehet a let a = b * 2 in ... kifejezés szintaktikailag helyes, de szemantikailag csak akkor fogadható el, ha b már rendelkezik értékkel ebben a hatásköri egységben.
A hatáskörök és a kötések a nyelv szemantikájától függnek, és a folyamatot, amellyel ezeket meghatározzuk, szemantikai analízisnek nevezzük.
Egy tipikus fordító a forrásprogramon a következő lépéseket hajtja végre: lexelés -> parsolás -> szemantikai analízis -> optimalizációk/transzformációk -> kód generálás.

Egyszerű, sor alapú input feldolgozása

A legegyszerűbb esete a parsolásnak és lexelésnek, amikor meghatározott input sorokkal dolgozunk. Ebben az esteben gyakran a parsolás csak annyiból áll, hogy szétvágjuk a sort a megfelelő határolók mentén, és a whitespace-eket figyelmen kívül hagyjuk:

> let line = "Smith, John, 20 January 1986, Software Developer";;
val line : string

> line.Split [| ',' |];;
val it : string [] = [|"Smith"; " John"; " 20 January 1986"; " Software Developer"|]

> line.Split [| ',' |] |> Array.map (fun s -> s.Trim());;
val it : string [] = [|"Smith"; "John"; "20 January 1986"; "Software Developer"|]

Minden sor feldolgozása függvénnyel:

let splitLine (line: string) =
line.Split [| ',' |] |> Array.map (fun s -> s.Trim())

let parseEmployee (line: string) =
    match splitLine line with
    | [| last; first; startDate; title |] ->
        last, first, System.DateTime.Parse(startDate), title
    | _ ->
    failwithf "invalid employee format: "%s"" line

Ezen függvények típusa:

val parseEmployee : string -> string * string * System.DateTime * string

> parseEmployee line;;
val it : string * string * System.DateTime * string
= ("Smith", "John", 20/01/1986 00:00:00, "Software Developer")

Sorfolytonos olvasás fájlból

A Seq-generate_using függvény segítségével egy sequence-ben tudjuk tárolni a soronkénti visszatérési értékeket:

open System.IO

let readEmployees (fileName : string) =
    Seq.generate_using
        (fun () -> File.OpenText(fileName))
        (fun reader ->
            if reader.EndOfStream then None
            else Some(parseEmployee(reader.ReadLine())) )

A következő példa az első három sorát veszi annak a fájlnak, ami 10000 ugyanolyan tartalmú sort tartalmaz:

> 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

Ezt a technikát gyakran nagy fájlok előzetes elemzésére használják. Ha az algoritmust az adatok egy prefixére már finomítottuk, az analízis hatékonyabban fog lefutni az egész adatfájlon.

Reguláris kifejezések használata

Egy másik gyakran használatos módszer, hogy egy stringből különböző információkat nyerjünk ki, a reguláris kifejezések használata.
A System.Text.RegularExpressions névtérben találhatunka reguláris kifejezések kezeléséhez (illesztés, helyettesítés) szükséges függvényeket.
Például vegyünk egy olyan fájlt, amely HTML GET request-ek rekordjait tartalmazza:

GET /favicon.ico HTTP/1.1

A fenti kód tartalmazza az igényelt forrást (favicon.ico) valamint használt HTML protocol alverziószámát (1).

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

A szükséges elemeket a Groups attribútum segítségével nyerhetjük ki. A reguláris kifejezésben minden bezárójelezett rész egy-egy csoport (group).

Tokenizálás FsLex-szel

Megvan a lehetőségünk, hogy kézzel készítsünk lexert, különböző ad hoc technikákat használjunk, vagy olyan függvényeket írjunk, amely explicit módon tudja manupilálni a karakterek listáját, de ilyenek készíteni gyakran unalmas és időt pazarló tevékenység.
Ehelyett könnyebb, ha ezt a munkát a lexer generátorra bízzuk. A következőkben az F# lexer generátorával, az fslex eszközzel fogunk megismerkedni.

Egy egyszerű példa: a lexer minden < és > karaktert a HTML-beli &lt és &gt megfelelőjére cseréli:
text2htmllex.fsl


rule convertHtml chan = parse
    | '<' { fprintf chan "&lt;";
        convertHtml chan lexbuf }
    | '>' { fprintf chan "&gt;";
        convertHtml chan lexbuf }
    | eof { () }
    | _ { fprintf chan "%s" (Lexing.lexeme lexbuf);
        convertHtml chan lexbuf }

A generált lexer használata:

text2html.fs

#light
open System.IO
open System.Text

let main() =
    let args = System.Environment.GetCommandLineArgs()
    if args.Length <= 2 then
        let base = Path.GetFileName(args[0])
        eprintfn "Usage: %s dir pattern" base
        exit 1
    let directory = args[1]
    let pattern = args[2]

for fileName in Directory.GetFiles(directory, pattern) do

    // egy file stream nyitása a fileName alapján
    use inputReader = File.OpenText(fileName)

    // Lex buffer létrehozása a generált lexer segítségével.
    // A lex buffer az inputReader streamet olvassa.
    let lexBuffer = Lexing.from_text_reader Encoding.ASCII inputReader

    // Kimeneti csatorna nyitása
    let outputFile = Path.ChangeExtension(fileName,"html")
    use outputWriter = (new StreamWriter(outputFile) :> TextWriter)

    // Header kiírása
    fprintfn outputWriter "<html>\<head></head>\n<pre>"

    // A generált lexer futtatása
    Text2htmllex.convertHtml outputWriter lexBuffer

    //footer kiírása
    fprintfn outputWriter "</pre>\n@lt;/html>\n"

do main()

Az F# forráskódot a fent definiált lexerből a következő parancs futtatásával lehet generálni:

fslex text2html.fsl

Ez az utasítás létrehoz egy text2htmllex.fs nevű fájlt, ami a convertHtml lexer implementációját tartalmazza. Ez a lexer imperatív, így nem tokenekkel tér vissza, hanem egy output stream-be ír ki.
A generált lexer szignatúrája:

val Text2htmllex.convertHtml: System.IO.TextWriter -> Lexing.lexbuf >> unit

A példaprogramot és lexert tudjuk együtt fordítani:

fsc text2htmllex.fs text2html.fs

Ezután az elkészült programot már tudjuk futtatni a megfelelő formátumú fájlokra megadva a könyvtárat és a fájl mintát:

text2html . *.txt

Nézzük meg közelebbről a fenti példát! A text2htmllex.fsl-nek a rule-szekciója definiálja lényegében a lexert, paraméterként kap egy kimeneti csatornát, és egy lex buffert. A szabályok szerint, ha < vagy > jelet találunk, akkor kiírjuk a kimenetre ennek a HTML-beli megfelelőjét, és rekurzívan meghívjuk a lexert a maradék inputra. Ha fájlvége jelet találunk, egyszerűen megállunk, akármilyen más karakter esetén pedig kiírjuk azt a kimeneti csatornára. A lexbuf nevű változó csak a szabályokon belül látható, típusa Lexing.lexbuf, amely a Microsoft.FSharp.Tools.FsLex.LexBuffer-ben található. Ezáltal a változó által különböző információkhoz juthatunk a lexelés állapotáról (ez a későbbiekben részletesebben).
A 'meghajtó' lehet akármilyen F# kód.Ellenőrizzük az argumentumokat, ahol megadjuk a könyvtárnevet és egy fájl mintát, amely alapján kiválogatjuka könyvtárból azokat a fájlokat, amire a minta illeszkedik, majd minden fájlt sorban megnyitunk, és példányosítjuk hozzá a generált lexert a következő sorokkal:

use inputReader = File.OpenText(fileName)
let lexBuffer = Lexing.from_text_reader Encoding.ASCII inputReader
...
Text2htmllex.convertHtml outputWriter lexBuffer

Ez a kód néhány fontos függvényt használ a Lexing modulból.

További fontosabb függvények és tulajdonságuk:

Az elemző számára elérhető lexbuf típust létrehozhatunk:

Az aktuális token pozíciói: LexBuffer.EndPos : Lexing.position, LexBuffer.StartPos : Lexing.position

További függvények:

Megjegyzés:
Az FsLex egy táblázat alapú véges automatával dolgozik, amely az input karakterek sorozatát egyenként, egymás után olvassa be, amíg egy tokennel vissza nem tér. Az automata felfüggeszti a működését, amíg nem érkezik újabb input. Az állapota a reguláris kifejezések segítségével leírt szabályoktől függ. Ha egykarakteres literálokkal dolgozunk, akkor egy új karakter új állapotba viszi az automatát, ismétlődő karakter esetén ugyanabban az állapotban marad.

A lexer használata Visual Studio-val

1. Nyissunk egy új Visual F# projectet.
2. Adjuk a referenciákhoz az FSharp.PowerPack és FSharp.Compiler hivatkozásokat.
3. Adjuk meg a Properties/Build event/Prebuild event-nél a fslex-et teljes elérési úttal.
4. Fordítsuk le a programot és az fslex.exe által készült fs fájl adjuk hozzá a projecthez. Ez a fájl legyen mindig előrébb, mint a főprogramunk.
5. Megadhatunk a Properties/Debug/Command line argument-nél parancsori argumentumokat.

Az fslex bemenete részletesen

Az fslex inputjának a következő szerkezettel kell rendelkeznie:

// Bevezető rész : bármilyen kód, ami e lexerhez szükséges, pl. modulok megnyitása
{ [Code] }

// Definíciók : minták megnevezése, amelyeket szabályokhoz, vagy egyéb
// definíciókhoz fogunk használni
let [Ident_1] = [Pattern]
let ...
// Szabályok : minták, és az illeszkedés esetén végrehajtandó szabályok rule [Rule_1] [arg1... argn] = parse
    | [Pattern] { [Action] }
    | ...
    | [Pattern] { [Action] }
and [Rule_2] [arg1... argn] = parse
...
rule [Rule_3] ...

// Lezáró rész : olyan kód, ami a lexer fentebb említett szabályait hívhatja
{ [Code] }

Minden szabályból egy F# függvény fog létrejönni, amit más modulokból, vagy a lexerből magából elérhetünk.
Kétféle komment létezik: (* és *) közötti többsoros és // utáni egysoros; mindkettőt ugyanúgy használhatjuk az akciókban, mint akármilyen más F# kódnál.
A szabályokban használható minták:

Az akciók azok az F# kódok, amelyek { és } között helyezkednek el, és lefutnak, amikor az előtte álló mintára illeszkedés történik. Eljárhatunk akármilyen logika szerint, de legtöbb esetben itt állítjuk össze a tokeneket.
A parser definíciójában a %token direktívát használjuk tokenek jelölésére, vagy ha nincs parserünk, akármilyen, a felhasználó által definiált típust használhatunk. (Ha a szabályokkal nem szeretnénk tokeneket lértehozni, akkor a lexer nagyon egyszerűvé válik).

Egyszerű token stream generálása

A következő példában tokenek listáját fogjuk generálni és kiíratni. A lexer fel tud ismerni integer, float típusú értékeket, azonoítókat, és a '^', '*', '-' és '+' jeleket. A többi egyéb karakter futási idejű hibát fog okozni.

simpleTokensLex.fsl:

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

let num = ["0"-"9"]+
let intNum = "-"? num
let floatNum = "-"? num ("." num)? (["e" "E"] num)?
let ident = ["a"-"z"]+
let whitespace = " " | "\t"
let newline = "\n" | "\r" "\n"

rule token = parse
    | intNum { INT (Int32.of_string (Lexing.lexeme lexbuf)) }
    | floatNum { FLOAT (Float.of_string (Lexing.lexeme lexbuf)) }
    | ident { ID (Lexing.lexeme lexbuf) }
    | "+" { PLUS }
    | "-" { MINUS }
    | "*" { TIMES }
    | "^" { HAT }
    | whitespace { token lexbuf }
    | newline { token lexbuf }
    | eof { EOF }
    | _ { failwithf "unrecognized input: "%s"" (Lexing.lexeme lexbuf) }

A lexert a következő módon generálhatjuk:

fslex simpleTokensLex.fsl

A generált generált lexer egy modult fog tartalmazni, a nevét a bement alapján kapja: SimpleTokensLex. Minden szabályhoz egy belépési pont van, ebben az esetben a függvény típusa a következő:

val token: Lexing.lexbuf -> SimpleTokensLex.token

A következőkben láthatjuk, hogyan tudunk imperatívan token stream-et generálni egy stringből, és az eredményt kiírni.

> #load "simpleTokensLex.fs";;
...
> let lexbuf = Lexing.from_string "3.4 x 34 xyx";;
val lexbuf : Lexing.lexbuf

> 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;;
Microsoft.FSharp.Core.FailureException: End of file on lexing stream

Pozíció információk helyes meghatározása

Az fslex által generált lexer mindig tartalmazza a legutóbb elfogadott tokan pozíció információit a bemeneti karakter stream alapján.
A LexBuffer StartPos és EndPos property-jeinek visszatérési értékei Lexing.Position típusúak.
A position típus szignatúrája:

type Position with
    // Az input steam-ként megadott fájlnév
    member FileName : string

    // Az aktuális pozíció sorának sorszáma.
    member Line : int

    // Az input stream-ben található karakterek száma
    member AbsoluteOffset : int

    // Az aktuális oszlop sorszáma
    member Column : int

    // A pozíciót a következő sor elejére állítja
    member NextLine : position
    ...
end

Néhány esetben a lexerek akcóinak néhány extra feladatot kell teljesíteniük. Különösképpen, amikor új sor karakter dolgozunk fel, hiszen ilyenkor mindig frissíteni kell a LexBuffer EndPos property-jét. (ez azért a lexer feladata, mert különböző lexerek esetén különbözhetnek az újsor karakterek). Az endOfLine szabályt megváltoztatva tehetjük ezt meg:

| newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine;
token lexbuf }
Most kísérletezzünk interaktívan ezzel az új lexerrel, és vizsgáljuk meg a StartPos és EndPos property-ket minden token feldolgozása után:
> let lexbuf = Lexing.from_string "3.4 \n 34 xyx";;
val lexbuf : Lexing.lexbuf

> 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)

Gyakran előfordul, hogy pozícióinformációt kell csatolni minden feldolgozott tokenhez. Azonban amikor a lexert együtt használjuk a fsyacc parser generátorral, a pozíció információkat minden feldolgozott token után automatikusan kiolvasásra kerülnek, és tárolódnak a parser állapotában.

Kommentek és stringek kezelése

Eddig csak olyan példákat láthattunk, ahol egy lexelési szabály elegendő volt. Ez azért volt, mert a főszabály elégséges volt minden tokenre, és nem kellett olyan inputot lexelnünk, ami nem lett volna leírható reguláris kifejezéssel.
Vegyünk most pélának a kommentezést! Egy komment "(*" és "*)" karakterek között helyezkedik el. Formálisan tehát van egy nyitó elválasztó, a komment törzse és a záró elválasztó.
Az első megközelítés:

"(*" _* "*)"

hibás, mert a középső minta mindenre illeszkedni fog, így nem jut el a csukó "*)" jelig.
A következő megoldás már jobbnak tűnik:

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

itt addig illesztjük a kommentet, amíg el nem érünk egy csillagig, utána próbáljuk illeszteni a csukó "*)" jelet. Természetesen hibás eredményt kapunk minden olyan kommentnél, amely tartalmaz csillag jelet.
Ezzel a reguláris kifejezéssel még egy kicsit tovább játszhatunk. A komment törzse lehet bármi, kivéve a csillagot, de olyan csillag viszont lehet, amit nem követ ")" kerek záró zárójel:

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

Ezt a reguláris kifejezést már nem tudjuk tovább fejleszteni, de még ennek is van egy hibája: nem tudja kezelni az egymásba ágyazott kommenteket, hiszen az első kommentzárónál megáll, figyelmen kívül hagyva a többi eddig megnyitott kommentet.
A probléma kezelése érdekében használjunk multirule lexert. A következőkben leírtak megmutatják, hogyan kell kiegészíteni a simpleTokensLex.fsl lexert, hogy tudja kezelni a kommenteket:

rule token =
    ...
    | "(*" { comment lexbuf; token lexbuf }
    | "\"" { STRING (string lexbuf.StartPos "" lexbuf) }

and comment = parse
    | "(*" { comment lexbuf; comment lexbuf }
    | "*)" { () }
    | "\n" { 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 Lexing.lexeme lexbuf with
            | "\\\"" -> "\""
            | "\\n" -> "\n"
            | "\\r" -> "\r"
            | "\\t" -> "\t"
            | "\\\\" -> "\\"
            | _ -> "") in
        string pos s" lexbuf }
    | "\"" { s }
    | "\n" { lexbuf.EndPos <- lexbuf.EndPos.NextLine;
            string pos (s + "\n") lexbuf }
    | eof { failwithf "end of file in string started at or near %A" pos }
    | _ { string pos (s + (Lexing.lexeme lexbuf)) lexbuf }

A kommentek kezelését végző folyamat akkor indul, amikor elértünk egy kommentnyitót a token szabályban. Amikor egy kommentzárót találunk, egy comment szabály hívásból kilépünk. Az elképzelésünk szerint úgy kezeljük a beágyazott kommenteket, hogy rekurzívan alkalmazzuk a lexert.

Parsolás FsYacc-al

Az fcyacc eszköz LALR(1) parsert generál, amely egy olyan speciális részhalmaza az LR(1) parseroknak, ahol az állapottáblát úgy csökkentjük, hogy összevonjuk a hasonló állapotokat. Ez a gyakorlatban nem szűkíti a parsolható nyelvek számát, de jelentősen csökkentheti a parsolási tábla méretét.
A generált parser automata négy különböző műveletet tud végrehajtani bármely állapoton az előreolvasott token alapján, és ezeket fontos megérteni akkor, ha különféle nyelvtani konfliktusaink vannak, amiket fel kell oldani:

Először azt vizsgáljuk meg. hogyan tudunk parsert generálni egy egyszerű programozási nyelvhez.
Egy példa részlet egy BASIC-hez hasonló nyelvből, amelyet parsolni szeretnénk:

b := 0;
a := 1;
if a then d := 20 + 20;
if b then d := 40 * 20 + 20;
print d
while d do
    begin
        d := d + 1;
        print d
    end
print d

Az egyszerűség kedvéért a nyelvet nevezzük Kitty-nek. Ahogy az előző példában láthattuk, a Kitty tartalmaz változó deklarációkat, változók értékének kiiratását, alapvető aritmetikai operátorokat, while, valamint feltételes szerkezeteket.
Az Ast modulban definiáljuk a Kitty programok szerkezetét.

kittyAst.fs:

type expr =
    | Val of string
    | Int of int
    | Plus of expr * expr
    | Minus of expr * expr
    | Times of expr * 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

Lexer a Kitty-hez

A következőkben bemutatjuk a Kitty nyevtanához készítendő lexert. Hasonló lesz az előző részben bemutatott lexerhezm azzal a különbséggel, hogy itt kulcsszó táblázatot használunk.
A tokeneket lexémmákkal való illesztéssel kapjuk meg, ez jó megoldás akkor, ha nem túl sok esetet kell megvizsgálnunk. Túl nagy lexert eredményezhet, ha explicit szabályokkal szerentnénk tokenizálni kulcsszavak és operátorok viszonylag nagy halmazát. Ezt a problémát úgy tudjuk kezeleni, hogy egy táblázatot használnuk, amely tartalmazza a lehetséges illeszkedő lexémákat, és hogy milyen tokent kell visszaadni az egyes esetekben. Egy egyszerű dictionary adatszerkezetet, a Map-et használjuk:

{ open System
open KittyParser
open Lexing
let ids = [ ("while", WHILE);
            ("begin", BEGIN);
            ("end", END);
            ("do", DO);
        ("if", IF);
            ("then", THEN);
            ("else", ELSE);
            ("print", PRINT);]
let idsMap = Map.of_list ids
let ident lexbuf tokenText =
if Map.mem 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 = " " | "\t"
let newline = "\n" | "\r" "\n"

rule token = parse
    | whitespace { token lexbuf }
    | newline { (lexbuf: 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 }

Megyjegyzés: lexer fordítási ideje a később definiálandó parsertől fog függeni. Ez azért van, mert a lexernek olyan típusú tokenekkel kell visszatérenie, amelyet a parser vár.

A lexert fslex futtatásával generálhatjuk:

fslex kittyLexer.fsl

Ennek eredményeképpen létrejön a lexer implementációját tartalmazó fájl, a kittyLexer.fs.

Parser a Kitty-hez

%{
open KittyAst
%}
%{ [Code] %} %start start
%token <string> ID
%token <int> INT
%token PLUS MINUS TIMES LPAREN RPAREN IF THEN ELSE
%token WHILE DO BEGIN END PRINT SEMI ASSIGN EOF
%left PLUS MINUS
%left TIMES
%left [TokenName]
%right [TokenName]
%nonassoc [TokenName]

%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 }
[Symbol] : [Symbols_1] { [Code_1] }
| [Symbols_2] { [Code_2] }

Listák parsolása

Kittyben a ;-vel elválasztott utasításokat az StmtList-ben utasítások listájaként tároljuk.
Ezt a szabály le tudjuk írni fej-rekurzív módon: 

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

Hátrány: mindig, amikor egy új kifejezést fűzünk az utasításlistához, egy másolat készül róla.

Másik megoldás:

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

A hozzáfűzés egyenként történik meg egy egy elemű listához, ami az első utasítás. Eredményként egy fordított sorrendű listát kapunk, ez szükségessé teszi a List.rev használatát.

Üres vagy tetszőleges lista parsolása: üres lista szimbólum használata a következő példának megfelelően:

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

Ez a szabály illeszkedi fog akármilyen listára, és üres listával tér vissza, ha nincs már parsolható utasítás.

Operátor precedencia, asszociativitás

Mint általában, az aritmetikai operátoroknál a osztás vagy szorzás magasabb precedenciájúak, mint az összeadás vagy kivonás, így az 1+2*3-at a következő zárójelezésnek megfelelően pasolhatjuk: 1+(2*3). Fsyacc-al ezt könnyedén kifejezhetjük az asszociativitás irányával, vagy ha még pontosabbak akarunk lenni, akkor rendezéssel is:

// Assziciativitás és precedencia - A legkisebb precedenciájú van felül

%left PLUS MINUS
%left TIMES

Ha megadjuk tokenekhez az asszociativitást és precedenciát (milyen erősen kötnek), akkor szabályozhatjuk a parsolást. Például adott egy bal-asszociatív összeadás: 1+2+3. A parser már ezt egy egyértelmű, nem felcserélhető műveletként dolgozza fel, ami a következő formájú: (1+2)+3. Az alapvető aritmetikai operátorok bal-asszociatívak, és egy olyan listában helyezkednek el, ahol sorba jönnek a különböző precedenciájú műveletek a legalacsonyabbtól a legmagasabb felé. Egyéb asszociativitás kifejező specifikációk még a %right és a %nonassoc, ami azt fejezi ki, hogy az adott szimbólum jobb-asszociatív, vagy nincsen asszociativitása. Az utóbbi akkor használandó, hogyha az operátor nem applikatív, ilyenek például a <, >, != jelek, így pl. az 1 > 2 > 3 szintaktikai hibát fog eredményezni.