V tomto díle se podíváme na první část kompilátoru, kterou je scanner. K implementaci scanneru jsem se rozhodl použít lexer a parser generátory, které značně celou implementaci zjednoduší.
reklama
Na konci první kapitoly byla zběžně popsána běžná architektura kompilátorů. Ta se většinou skládá ze tří částí - scanner, parser a generátor CILu v případě .NET jazyka. Nicméně kompilátor postavený na DLR se částečně liší, namísto CILu je generován DLR abstract syntax tree (DLR AST).
Zde můžete vidět jak v jednotlivých krocích kompilátor zpracovává kód:
Zatímco první AST je vytvořena „na míru“ danému jazyku (tzn. uzly a listy jsou nadefinovány programátorem jazyka), tak DLR AST je již sestaven z uzlů a listů z DLR frameworku a tak DLR umí takový strom interpretovat. DLR AST by také bylo možné vygenerovat přímo z tokenů a přeskočit tedy generátor, nicméně tím bychom žádnému zjevnému zrychlení kompilace nedosáhli a pouze by se implementace parseru stala velice nepřehledná, protože generátor nemá na starost pouze transformaci IPL AST na DLR AST, ale také má na starost mnoho dalších věcí jako jsou například proměnné a jejich rozsah platnosti (scoping), nahrávání potřebných assembly a pod.
Vyvíjený jazyk
V tomto tutoriálu se budeme zabývat implementací nového jazyka pro .NET, který jsem pojmenoval IPL (podle Implementation of Programming Language). IPL je jedoduchý jazyk podobný ToyScriptu, což je taktéž velice jednoduchý jazyk postavený na DLR. Stejně jako IPL je i ToyScript určený zejména pro studijní účely a ukázkou toho, jak implementovat jazyk na DLR, bohužel ale postrádá jakoukoliv dokumentaci či okomentovaný kód.
První verze jazyka IPL (nazývejme ji IPL1) bude podporovat pouze několik základních funkcí:
- proměnné
- hodnoty typu int a string
- let-in-end bloky
- if-else podmínky
- lambda funkce
Lambda funkce
Lambda funkce jsou obdobný koncept jako lambda expressions ze C# 3.0. Jedná se o jednoduchou funkci, kde tělo je výraz, který je při volání funkce vyhodnocen a hodnota vrácena.
Příklad:
add = fun x y => x + y // add(5,6) je 11
Let-in-end blok
Let-in-end bloky umožňují deklarovat proměnné. Každý blok má vlastní rozsah proměnných (scope) a bloky je možné “vkládat" do sebe. Koncept let-in-end bloků v jazyce IPL1 demonstruje jak implementovat rozsah platnosti proměnných (scoping) v DLR a jak pracovat s proměnnými.
Použití let-in-end:
Jazyk IPL1 zatím nebude obsahovat příkazy (statements), bude se jednat pouze výraz, který DLR vyhodnotí v jednu hodnotu. V dalších kapitolách pak jazyk obohatíme o další vlastnosti jako jsou zmiňované příkazy (statements), funkce, integrace s .NETem (volání a používání .NET knihoven) atd.
Ukázka implementace faktoriálu v IPL1:
let val x = 4
val fac = fun n => if n > 1 then n * self(n - 1)
else 1
in fac(x) end
Implementace jazyka IPL
Scanner a parser
Implementovat scanner nebo parser vlastními silami není vůbec jednoduché a vyžaduje to již nějaké zkušenosti. Nicméně existuje o mnoho jednodušší způsob a to použít některý z dostupných scanner a parser generátorů. Jedná se o úzce specializované nástroje zaměřené zejména na parsování zdrojových kódů. Protože kompilátor vyvíjíme v .NETu, musíme si vybrat některý z .NET generátorů. Já jsem se rozhodl pro generátory fslex (scanner generátor) a fsyacc (parser generátor), které jsou součástí F# a protože F# je víceméně dnes již standartním .NET jazykem, nebude problém propojit scanner a parser v F# s generátorem napsaným v C#.
Nemusíte se ničeho obávat pokud nemáte s F# zkušenosti, fslex a fsyacc soubory mají vlastní formát a tak F# kódu prakticky nenapíšeme více než 20 řádků.
Scanner
Fslex (stejně tak i fsyacc) je součástí distribuce F#. Ten můžete stáhnout na http://research.microsoft.com/fsharp/release.aspx ^.
Pokud nemáte zkušenosti s F# tak doporučuji nainstalovat verzi 1.9.4.x, kterou používám při psaní tohoto tutoriálu. Nová verze F# (September 2008 CTP a novější) obsahuje podstatné změny a screenshoty či kód se můžou lišit.
Pokud máte F# nainstalovaný, vytvořte nový C# projekt (Class library) a do vytvořeného solution přidejte nový F# projekt. Poté do vytvořeného F# projektu přidejte F# Lex soubor, ve kterém nadefinujeme pravidla scanneru pro parsování kódu.
Zde je implementace scanneru jazyka IPL1:
// scanner.fsl
{
open System
open Parser
open Lexing
}
let digit = ['0'-'9']
let char = ['a'-'z' 'A'-'Z']
let string = '"'([^'"'])*'"'
let whitespace = [' ' '\t' '\r' '\n']
rule scan = parse
// Keywords
| "else" { KeyELSE }
| "end" { KeyEND }
| "false" { KeyFALSE }
| "fun" { KeyFUN }
| "if" { KeyIF }
| "in" { KeyIN }
| "let" { KeyLET }
| "then" { KeyTHEN }
| "true" { KeyTRUE }
| "val" { KeyVAL }
// Operators
| "<" { OpLESS }
| "*" { OpSTAR }
| "-" { OpDASH }
| "+" { OpPLUS }
| "=" { OpEQUAL }
| "==" { OpEQUALEQUAL }
| "=<" { OpEQUALLESS }
| "=>" { OpEQUALGREATER }
| ">" { OpGREATER }
| ">=" { OpGREATEREQUAL }
| "/" { OpSLASH }
| "!=" { OpEXCLAMATIONEQUAL }
// Special
| "(" { SpLEFTPAREN }
| ")" { SpRIGHTPAREN }
| "," { SpCOMMA }
// others| digit+ { NUM (Int32.Parse(lexeme lexbuf)) }
| string { STRING ((lexeme lexbuf).Trim([|'\"'|])) }
| char(char | digit)* { IDENT (lexeme lexbuf) }
| whitespace { scan lexbuf }
| eof { EOF }
Scanner je tvořen pravidly. Pro každé klíčové slovo, operátor či speciální znak jazyka má scanner vždy jedno pravidlo. Pravidla začínají znakem ‘|’, následuje regulární výraz, který odpovídá parsovanému stringu a pak ve složených závorkách vygenerovaný odpovídající token. Token může taktéž uchovávat hodnotu, což je důležité například u parsování hodnot (string, int,...), kde nestačí pouze vygenerovat odpovídající token, ale zároveň je důležité uchovat parsovanou hodnotu (tu vrací funkce lexeme lexbuf).
Zde je ukázka kódu rozparsovaného scannerem do tokenů:
[IDENT(“x”), OpEQUAL, NUM (5), OpADD, NUM(3), OpMUL, NUM(6)]
Parser
I přesto, že v této kapitole se zabýváme pouze scannerem, i tak musíme vytvořit soubor pro parser, ve kterém se vedle pravidel pro parser definují taktéž používané tokeny (bez této definice by scanner nebyl kompletní).
Soubor parser.fsy:
// parser.fsy
%token NUM
%token STRING
%token IDENT
// Keywords
%token KeyELSE KeyEND KeyFALSE KeyFUN KeyIF KeyIN KeyLET KeyTHEN KeyTRUE
KeyVAL
// Operators
%token OpLESS OpSTAR OpDASH OpPLUS OpEQUAL OpEQUALEQUAL
OpEQUALLESS OpEQUALGREATER OpGREATER OpGREATEREQUAL OpSLASH
OpEXCLAMATIONEQUAL
// Special
%token SpLEFTPAREN SpRIGHTPAREN SpCOMMA
// others
%token EOF
// ** ignore rest of this file for now
%start start
%type start
%%
start: { "" }
Nyní když implementace je hotová, můžou být oba dva soubory zkompilované do F#. K tomu slouží nástroje fslex.exe a fsyacc.exe, které se nachází v C:\Program Files\FSharp-[version]\bin\.
Kompilace scanner.fsl a parser.fsy:
fslex.exe scanner.fsl
fsyacc.exe parser.fsy
Vygenerovány jsou 2 soubory - scanner.fs a parser.fs, které musíme přidat do projektu.
Pozor, na pozici souborů v projektu záleží! V F# jsou jednotlivé soubory interpretovány sekvenčně podle jejich pozice v projektu. A protože scanner.fsl používá tokeny, které jsou nadefinované v parser.fsy, musí být parser.fsy umístěn v projektu před souborem scanner.fsl. Pokud jsou soubory v jiném pořadí než potřebujete, jsou dva způsoby jak pozici souboru změnit - ve Visual Studiu přejmenování souboru ho automaticky přesune na poslední pozici. Nebo druhý způsob je otevřít soubor projektu (*.fsharpp) a v editoru a změnit pozici manuálně.
Volání scanneru
Zde se poprvé setkáváme s F# kódem, ve kterém naimplementujeme funkci volající vygenerovaný scanner a která vrací tokeny:
// main.fs
#light
open System
// returns list of tokens
let runScanner code =
let mutable cont = true // continue scanning?
let mutable tokens = [] // empty list of tokens
let lexbuf = Lexing.from_string code // initialize lexer
while cont = true do
let token = Scanner.scan lexbuf // parse one token
tokens <- tokens @ [token] // store token
// end of the string?
if token = Parser.token.EOF then
cont <- false
tokens
Zdrojové kódy
Odkaz na zdrojové kódy ke stažení jsou na konci tohoto dílu. Součástí projektu jsou i unit testy (ScannerTest.cs).
Závěr
Pokud je Vám implementace scanneru stále nejasná, zkuste se podívat na implementaci velice jednoduchého kompilátoru početních výrazů, který je ke stažení zde.
Další kapitola bude zaměřená na implementaci parseru, který v porovnání se scannerem je o něco obtížnější implementovat.
IPL1_01scanner.zip