Aleš Šturala | Blog | česká verze

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í:

1. proměnné
2. hodnoty typu int a string
3. let-in-end bloky
4. if-else podmínky
5. 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 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.

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