PB173 - Binární programování Linux
II. Parsery
Jiri Slabý
Fakulta informatiky Masarykova univerzita
23. 9. 2014
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23.9.2014      1 /21
Důležité informace
• Kolokvium za DÚ
• DÚ do příštího cvičení
• Login/heslo
• vyvoj/vyvoj
• GIT: http://github.com/jirislaby/pbl73-bin
• git pull --rebase
a Studijní materiály v ISu
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
2/21
Sekce 1
Parsery
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
3/21
Parsery
« Analyzátor jazyka
• Přirozeného, programovacího, ...
• Výstupem je nějaký lépe zpracovatelný popis jazyka
• Např. informace v grafu nebo stromu
• Několik mezifází, jak toho dosáhnout
• Projdeme si na dalších slidech
• Získané informace se dále využijí
• K překladu do jiného jazyka (např. strojového)
• K interpretaci «...
• Detailněji o jazycích a parserech např. v „Dragon Book"
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
4/21
Výroba parseru
• Ručně psané
• Rychlost parseru a explicita
• gcc (Demo)
• Generované nástroji
• Rychlost napsání parseru a přehlednost
• Lex+Yacc
• Flex+Bison
• Antlr a A další
Jiri Slabý (Fakulta informatiky, MU) PB173/03 23. 9. 2014      5121
Antlr
• Nástroj ke generování parserů
• Psaný v Javě
• Vstup je LL(*) gramatika (shora-dolů, čitelná)
• Generuje parsery do různých jazyků
• Java, C, C++, C#, ...
• Podpora pro C jen ve verzi 3 (pro 4 se připravuje)
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
6/21
Úkol
Stáhněte a zprovozněte si Antlr 3
http://www.antlr3.org/download.html
• Ukládejte do pbl73-bin/02/
• AntlrWorks: „Version 1.5"
• Antlr: „Complete Antlr 3.5.2 Java binaries jar"
O Knihovna pro C (libantlr3c a libantlr3c-devel)
• RPM:http://software.opensuse.org
• Zdroje:http://www.antlr3.org/download/C/
Q Vyzkoušejte generovat Parser.g Z pbl73-bin/02/test/
• make
O Pusťte jej
• ./parser test_input
• Změňte test_input a zkuste znovu
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
7/21
Struktura parseru
CFG
ŕ-\ Zdroj —>■	Lexikální analýza		f-^ Tokeny *_.		Syntaktická analýza	—>• AST ■
O Lexikální analýza
• Převod sekvence znaků na sekvenci „tokenů"
• Např. „int a" převede na „KEYWORD: int ID:a"
Q Syntaktická analýza
• Převod sekvence tokenů na strom...
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
8/21
Abstraktní syntaktický strom (AST)
void fun(int a) key:void id:fun LPAR key:int id:a RPAR
{/* comment */ LCUR intb = 0; key:int id:b EQ num:0 SEMIC
if (a) =4>      key:if LPAR id:a RPAR
b = 5; id:b EQ num:5 SEMIC
a = 3* b; id:a EQ num:3 MULT id:b SEMIC
} RCUR
void
	fun		
			
parám			
int		a		ded		if		=
int		var		a		=		a		*
	/\					A				A
	b 0				b		5		3	
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
9/21
Analýzy v Antlr
Antlr obsahuje obě části v jednom souboru
• 2 typy pravidel
• Počáteční velké písmeno - lexikální Počáteční malé písmeno - syntaktická
/* syntaktická analýza */ helloWorld
: AHOJ SVETE // 2 tokeny v jednom syntaktickém pravidle | SVETE AHOJ { puts("Nepise se to obracené?");}
/* lexikálni analýza */ AHOJ
: 'Ahoj' // vytvori token AHOJ z řetězce "Ahoj"
SVETE
: 'Svete'
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
10/21
Pravá strana pravidel
• I odděluje možnosti
• VÍC6 možností: zvirata : savci I obojživelníci ;
• Kombinace podčásti: zvirata :  Cpe' I 'ko') 's';
• Opakování pravidla
pravidlo? - 0-1 krát (nicNeboX :   'x'? ;)
• pravidlo* - 0-°°krát (kolonaAut :   'auto'* ;)
• pravidlo+- 1-ookrát (zvukHada :   's'+ ;)
• Speciální pravidlo pro konec souboru: EOF
• Donutí číst celý soubor
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23.9.2014      11 /21
Úkol
Rozšíření gramatiky
O Prozkoumejte obsah 02/test/Parser.g
O Vytvořte si token number pro čísla ((' o >.. > 9 >) +)
O Vytvořte si tokeny + a - pro operace
O Vytvořte si nové pravidlo expr pro tyto 2 operace
• Bude obsahovat 2 řádky
• Pro sčítání např. number plus number
O Přidejte do transiationUnit novou pravou stranu expr+ O Vyzkoušejte nově podporované vstupy
• 1+2,100-10, apod.
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
12/21
Formát Antlr
Formát celého souboru pro Antlr
grammar Jméno; // shoda s nazvem souboru options {
language = C; // výstupní jazyk parseru
}
@header { #defineX10 // vlozi se na zacatek generovaného parseru
}
@members { static void moje_funkce() {...} // vlozi se za hlavičku parseru
}
pravidlol : pravidlo2 I pravidlo3;
Jiri Slabý (Fakulta informatiky, MU)
Sekce 2
Akce pravidel
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
14/21
Akce pravidel
Pravidla mohou obsahovat akce
a Kód spouštěný při určitých událostech
• p :  ID { x++; } ID { x++; } ID { puts("něco"); } ;
• Akce můžou referencovat předcházející části
• Implicitně jménem tokenu/pravidla
(p : NUMBER { $NUMBER...  } ;)
• Nebo pojmenováním
(p : nl=NUMBER PLUS n2=NUMBER { $nl ... $n2 ... } ;)
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
15/21
Úkol
Akce pravidel
O Dopište akce na konec jednotlivých pravidel expr O Vypište nějaký text O Vyzkoušejte
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
16/21
Vlastnosti tokenů
Každý token má vlastnosti
a text - tokenizovaný řetězec („Ahoj" pro AHOJ)
• Typ: pANTLR3_STRING, obsahuje char *chars
• Pravidla jej mají také
• line - zdrojový řádek
• pos - zdrojový sloupec
helloWorld : x=AHOJ y=SVETE{ printf("line=\%d col=\%d x=\%s y=\%s whole=\%s\n", $x.line, $x.pos, $x.text->chars, $y.text->chars, $helloWorld.text->chars);
}
| SVETE AHOJ { puts("Nepise se to obracené?");}
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
17/21
Úkol
Vlastnosti pravidel
O Pro každou operaci sčítání/odčítání
• Vypište číslo řádku a sloupce pro obě čísla ($number. line a
$number.pos)
• Vypište Obě Čísla ($number.text->chars)
Q Vyzkoušejte roztroušením textu po testovacím vstupu
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
18/21
Předávání hodnot
Každé pravidlo muže akceptovat/vracet hodnotu
• pravidlo [type1 parami,  ...] returns [type2 name] pravaStrana;
• Pak lze v akcích odkazovat na $paraml typu typel » Akce musí nastavovat $name typu type2
translationUnit
: expr[5] EOF { printffľm done \%d\n", $expr.ret);}
expr[int par] returns [int ret] : n1=NUMBER PLUS n2=NUMBER { $ret = $par * atoi($n1 .text->chars) + atoi($n2.text->chars);
}
| SVETE AHOJ { puts("Nepise se to obracené?"); $ret = 0;}
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
19/21
Úkol
Vlastnosti pravidel
O Vytvořte si pravidlo pro čísla
9 number : NUMBER ;
Q Z něj a z expr si vracejte (smysluplnou) hodnotu
9 Tj. počítejte 0 V transiationUnit vypište výsledek
• Pro každé expr
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23. 9. 2014
20/21
Inicializace/ukončení
Každé pravidlo muže mít inicializace/ukončení
• Za jménem pravidla a parametry
• Před středníkem
• Inicializace: @init{ ... }
• Např. inicializovat proměnné
• Ukončení: @after{ ... }
• Např. počítání
expr[int par] returns [int ret] @init{ $ret = 0;} @after{ $par—;} : n1=NUMBER PLUS n2=NUMBER { $ret = $par * atoi($n1 .text->chars) + atoi($n2.text->chars);
}
Jiri Slabý (Fakulta informatiky, MU)
PB173/03
23.9.2014       21 /21