Aleš Šturala | Blog | česká verze

Parser je velice důležitá část kompilátoru. Jeho úkolem je sestavit abstract syntax tree (AST) z tokenů vygenerovaných scannerem. Jak na to si ukážeme v tomto díle.

Co důležitého na AST?

Scanner pouze vygeneruje list tokenů, které reprezentují kód tak jak byl napsán zleva doprava:

“x = 3 * 2 - 4 / 2″ => [IDENT(”x”), EQUAL, NUM(3), MUL, NUM(2), SUB, NUM(4), DIV, NUM(2)]

Oproti poli tokenů AST obsahuje jednu důležitou informaci navíc a to je jak má být daný kód vyhodnocen. Například kód “x = 3 * 2 - 4 / 2″ necheme vyhodnotit zleva doprava, ale nejdříve vypočítat “3 * 2″ a “4 / 2″, poté odečíst výsledky “6 - 2″ a následně přiřadit hodnotu do proměnné x. Parser tedy převede kód (tokeny) do stromové struktury podle toho, jak mají být jednotlivé operace provedeny:

[IDENT(”x”), EQUAL, NUM(3), MUL, NUM(2), SUB, NUM(4), DIV, NUM(2)]
=>

Ve srovnání se scannerem je implementace parseru obtížnější. I tak jednoduchý jazyk jakým je IPL1 má celkem mnoho parsovacích pravidel a není úplně jednoduché se na něm učit “základy parsování”. Proto pokud nemáte zkušenosti s parser generátory (jako například Yacc a jemu podobné) tak se můžete podívat na implementaci jednoduššího parseru aritmetických výrazů, který je ke stažení zde. Nicméně pojdmě se podívat na implementaci parseru jazyka IPL1.

Parser

Nejdříve musíme vytvořit datový typ pro generovaný strom. Pro tento účel můžeme použít tzv. discriminated unions v F#. Nepočítám, že každý je s tímto konceptem obeznámen, proto se pokusím discriminated unions vysvětlit.

Discriminated unions

Discriminated unions najdete obvykle ve funkcionálních jazycích jako například F# či Haskell. Jedná se o datový typ, který spojuje různé datové struktury.
Vezměme si například strukturu Person, která má uchovávat všechny důležíté informace o osobě, nicméně struktura uložených dat se liší pokud se jedná o dospělou osobu a pokud se jedná o dítě. V případě dítěte chceme uložit jeho jméno (string), věk (int), otec (Person), matka (Person), zatímco pokud se jedná o dospělou osobu pak uložené informace jsou jméno (string) a název firmy (string), ve které pracuje.

Zde je implementace typu Person za použití discriminated unions:

type Person =
  | Adult of string * string
  | Child of string * int * Person * Person

Pro každou strukturu je definován tzv. konstruktor - Adult a Child. Konstruktor se nazývá proto, že přes tento název se typ inicializuje:

let p1 = Adult("Andy", "Contoso")
let p2 = Adult("Maria", "Fabrikam")
let p3 = Child("John", 12, p1, p2)

Všechny tři proměnné jsou typu Person.

Použití discriminated union

Používat discriminated unions v F# nebudeme, protože s vygenerovaným AST budeme pracovat až v C#, nicméně pro zajímavost zde ukážu, jak se proměnná takovéhoto typu používá na funkci printPerson, která vytiskne jednotlivé hodnoty struktury do řetězce:

let printPerson = function
  | Adult(name, company) -> "Adult: " + name + ", " + company
  | Child(name, age, father, mother) -> "Child: " + name + " (" + age
                 + "), father - (" + printPerson father
                 + "), mother - (" + printPerson mother + ")"

Výsledkem volání printPerson p3 je řetězec:

“Child: John (12), father - (Adult: Andy, Contoso), mother - (Adult: Maria, Fabrikam)”

Datový typ pro AST

Zde je datový typ Tm pro parserem vygenerované AST:

// ast.fs

// Arithmetic operations
type ArithOp =
     | Add				// +
     | Sub				// -
     | Mul				// *
     | Div				// /

// Relation operations
type RelOp =
     | Lt				// <
     | Leq				// =<
     | Eq				// ==
     | Neq				// !=
     | Geq				// >=
     | Gt				// >

// AST
type Tm =
     | Num of int
     | String of string
     | Ident of string
     | True
     | False
     | AOp of ArithOp * Tm * Tm		// operation * left * right
     | ROp of RelOp * Tm * Tm		// operation * left * right
     | Lambda of List * Tm		// params * body
     | Call of Tm * List		// funName * [arg1..]
     | IfElse of Tm * Tm * Tm		// condition * body1 * body2
     | Let of List * Tm			// [declaration1, ..] * body
     | Decl of string * Tm		// ident * val …
                         // … declarations inside ‘let-in-end’ block

Každý konstruktor representuje uzel, případně list stromu.

Zde je příklad jednoduchého kódu:
if true then 5 else 7

a dopovídajícího AST:
IfElse( True, Num(5), Num(7) )

Parsovací pravidla

Zde přichází to nejdůležitější čímž jsou parsovací pravidla, která sestaví požadovaný AST (šedý kód byl již vysvětlen v předchozím článku):

// parser.fsy
%{
open Ast
%}


%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


// The start token becomes a parser function in the compiled code
%start start

// This is the type of the data produced by a successful reduction of the ’start’
%type  start

// Setting associativity
%left OpPLUS OpDASH
%left OpSTAR OpSLASH

%%

// These are the rules of the grammar along with the F# code of the
// actions executed as rules are reduced. In this case the actions
// produce data using F# data construction terms.
start:
		| tm EOF				{ $1 }

tm:
		| tmFunPrio				{ $1 }

tmFunPrio:
		| tmEqPrio				{ $1 }
		| KeyFUN tmParams OpEQUALGREATER tm	{ Lambda(List.rev($2), $4) }
		| KeyLET tmDecl KeyIN tm KeyEND		{ Let(List.rev($2), $4) }
		| KeyIF tmEqPrio KeyTHEN tm KeyELSE tm	{ IfElse($2, $4, $6) }

tmEqPrio:
		| tmAOpPrio				{ $1 }
		| tmAOpPrio OpLESS tmAOpPrio		{ ROp(Lt, $1, $3) }
		| tmAOpPrio OpEQUALLESS tmAOpPrio	{ ROp(Leq, $1, $3) }
		| tmAOpPrio OpEQUALEQUAL tmAOpPrio	{ ROp(Eq, $1, $3) }
		| tmAOpPrio OpEXCLAMATIONEQUAL tmAOpPrio{ ROp(Neq, $1, $3) }
		| tmAOpPrio OpGREATEREQUAL tmAOpPrio	{ ROp(Geq, $1, $3) }
		| tmAOpPrio OpGREATER tmAOpPrio		{ ROp(Gt, $1, $3) }

tmAOpPrio:
		| tmCallPrio				{ $1 }
		| tmAOpPrio OpPLUS tmAOpPrio		{ AOp(Add, $1, $3) }
		| tmAOpPrio OpDASH tmAOpPrio		{ AOp(Sub, $1, $3) }
		| tmAOpPrio OpSTAR tmAOpPrio		{ AOp(Mul, $1, $3) }
		| tmAOpPrio OpSLASH tmAOpPrio		{ AOp(Div, $1, $3) }

tmCallPrio:
		| tmAtom				{ $1 }
		| IDENT SpLEFTPAREN tmArgs SpRIGHTPAREN { Call(Ident($1), List.rev($3)) }

tmAtom:
		| NUM					{ Num($1) }
		| KeyFALSE				{ False }
		| KeyTRUE				{ True }
		| STRING				{ String($1) }
		| IDENT					{ Ident($1) }
		| SpLEFTPAREN tm SpRIGHTPAREN		{ $2 }

tmDecl:
		| 					{ [] }
		| tmDecl KeyVAL IDENT OpEQUAL tm	{ Decl($3, $5) :: $1 }
tmArgs:
		|					{ [] }		// no args
		| tmFunPrio				{ [$1] }	// one arg
		| tmArgs SpCOMMA tmFunPrio		{ $3 :: $1 }	// many args

tmParams:
		|					{ [] }		// no params
		| tmParams IDENT			{ $2 :: $1 }

• Kód mezi %{ a }% bude vložen přímo do vygenerovaného F# kódu
• %start definuje počáteční pravidlo, kterým parser začíná. Zároveň je podle názvu tohoto pravidla pojmenovaná funkce vygenerovaného parseru, tzn. že v tomto případě parser budeme volat Parser.start(…), protože “start“ se jmenuje počáteční pravidlo
• %type je datový typ vrácené hodnoty parserem. V našem případě je to je Tm reprezentující AST
• %% po těchto znacích jsou očekávána parsovací pravidla
• Konečné pravidlo je tmAtom, které (až na poslední konstruktor pro závorky) nelze dále redukovat

Stavění pravidel

Při sestavování pravidel parseru je vždy nejdůležitější, aby parser zachytil co nejvíce nepovolených konstrukcí, ale zároveň aby nebyl příliš restriktivní, tzn. aby byl schopen zpracovat jakýkoliv validní kód.
Například příliš restriktivním pravidlem pro if-then-else by byl:

| KeyIF tmAtom KeyTHEN tm KeyELSE tm { IfElse($2, $4, $6) }

Toto pravidlo očekává v podmínce tmAtom, takže například kód…

if true then 5 else 7

…by parser byl schopen zpracovat, protože parsování true je přímo v tmAtom, nicméně u kódu

if 2 < 3 then 5 else 7

..by již parser vrátil chybu, protože takovou konstrukci již tmAtom nepovoluje.

Naopak příkladem málo restriktivního pravidla je:

| KeyIF tm KeyTHEN tm KeyELSE tm { IfElse($2, $4, $6) }

Pravidlo tm v podmínce totiž povoluje víceméně jakoukoliv konstrukci, takže pro parser by byl validní kód i například:

if fun x,y => x + y then 5 else 7

Samozřejmě podmínka očekává boolean hodnotu, takže tento kód není validní a chyba by se projevila až za běhu aplikace. Nicměně měli bychom se snažit aby již parser objevil co nejvíce nepovolených konstrukcí, protože pokud chybu objeví parser, tak programátor bude varován už při kompilaci kódu zatímco v tomto případě by programátor na chybu přišel až za běhu aplikace a to pouze v případě, že by byla tato část kódu vykonána.

„Správným“ řešením je:

| KeyIF tmEqPrio KeyTHEN tm KeyELSE tm { IfElse($2, $4, $6) }

což je použito i v našem parseru jazyka IPL1. Označení „spravným“ v uvozovkách jsem použil záměrně, protože ani toto pravidlo není stoprocentní a to proto, že nyní sice definici funkce v podmínce již parser jako chybu nahlásí, nicméně například povolí kód

if 5 then 7 else 3

…což taktéž není správně. Pokud bychom se ale snažili parser zdokonalovat tak, aby objevil co nejvíce nepovolených konstrukcí tak budeme potřebovat více pravidel a implementace parseru se stane o mnoho komplikovanější, proto je lepší hledat určitou vyváženost mezi kvalitou parseru a jeho komplikovaností.

Generování

Jakmile je soubor s parsovacímy pravidly hotov, můžeme z něj vygenerovat F# kód pomocí nástroje fsyacc, který jsme již používali minulou kapitolu a který se nachází ve složce kde je nainstalován F#.

Použití je jednoduché:
fsyacc.exe parser.fsy

Volání parseru

Implementace funkce runParser volající parser a vracející AST:

// return  AST
let runParser code =
  let lexbuf = Lexing.from_string code                     // initialize
  try
    Parser.start Scanner.scan lexbuf
  with e ->
    let ex = Printf.sprintf "Parser excetion: %s \ncolumn %d" e.Message lexbuf.EndPos.Column
    failwith ex

Závěr

Zdrojové kódy můžete stáhnout na konci tohoto tutoriálu. Součástí projektu jsou i unit testy, kde můžete vidět jaké AST jsou pro různé kódy vygenerované.
V další kapitole se již dostaneme k DLR a náš kompilátor jazyka IPL1 dokončíme.

IPL1_02parser.zip