PB173 - Binární programování Linux
II. Parsery
Jiri Slabý
ITI, Fakulta informatiky 24. 9. 2013
J. Slabý (ITI, Fl)
PB173/07
24.9.2013       1 / 17
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
• Studijní materiály v ISu
J. Slabý (ITI, Fl)
PB173/07
24.9.2013      2/ 17
Část I
Parsery
J. Slabý (ITI, Fl)
PB173/07
24.9.2013      3/ 17
Parsery
« Analyzátor jazyka
• Přirozeného, programovacího, ...
• Výstupem je nějaký lepší popis jazyka
• Např. informace v grafu nebo stromu
• Několik mezifází, jak toho dosáhnout
• Projdeme si na dalších slajdech
• Získané informace se dále využijí
9 K překladu do jiného jazyka (např. strojového)
• K interpretaci «...
• Detailněji o jazycích a parserech např. v „Dragon book"
J. Slabý (ITI, Fl)
PB173/07
24.9.2013      4/ 17
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ší
J. Slabý (ITI, Fl)
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)
J. Slabý (ITI, Fl)
PB173/07
24.9.2013      6/ 17
Úkol
Stáhněte a zprovozněte si Antlr 3
O http://www.antlr3.org/download.html
• Ukládejte do pbl73-bin/02/
• AntlrWorks: „Version 1.5"
• Antlr: „Complete Antlr 3.5 Java binaries jar"
O Knihovna pro C (libantlr3c a libantlr3c-devel)
• RPM: http://software.opensuse.org
• Zdroje:http://www. antlr3.org/download/C/
0 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
J. Slabý (ITI, Fl)
PB173/07
24.9.2013      7/ 17
Struktura parseru
Zdroj
Lexikální analýza
Tokeny
Syntaktická analýza
O Lexikální analýza
• Převod sekvence znaků na sekvenci „tokenů"
• Např. „int a" převede na „keyword : int id:e O Syntaktická analýza
• Převod sekvence tokenů na strom...
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
int		a		ded		if		=
int	var		a		=		a		*
	/\				A				A
	b 0			b		5		3	
J. Slabý (ITI, Fl)
PB173/07
24.9.2013      9/ 17
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'
J. Slabý (ITI, Fl)
Pravá strana pravidel
• I odděluje možnosti
9 Kombinace podčásti: zvirata :  Cpe' I 'ko') 's' ;
• Opakování pravidla: zvukHada : 's'+ ;
O pravidlo? - 0-1 krát
• pravidlo* - 0-°°krát
• pravidlo+ - 1-°okrát
• Speciální pravidlo pro konec souboru: EOF
• Donutí číst celý soubor
• Může obsahovat akce
» p : ID { x++; } ID { x++; } ID { puts("neco"); } ;
• Akce můžou referencovat předcházející části
• Implicitně (p : ID { $ID... } ;)
• Nebo pojmenováním (p : idl=lD { $idl... } ;)
J. Slabý (ITI, Fl)
PB173/07
24.9.2013       11 / 17
Formát Antlr
Formát celého souboru pro Antlr
grammar Jméno; // shoda s nazvem souboru options {
language = c; // výstupní jazyk parseru
}
tokens { STATEMENT; // uvidíme dale
}
@header{ #defineX10 // vlozi se na zacatek generovaného parseru
}
@members{ static void mojeJunkceO { ... } // vlozi se za hlavičku parseru
}
pravidlol : pravidlo2 I pravidlo3;
J. Slabý (ITI, Fl) PB173/07 24.9.2013       12/ 17
Úkol
Rozšíření gramatiky
O Prozkoumejte obsah 02/test/Parser.g O Přidejte do heiioWorid nová pravidla Pro anglický pozdrav • Možnost opakovaně zdravit „Hi" pomocí nového pravidla hi*
O Dopište akce pro všechna pravidla heiioWorid o Výpis nějakého textu
O Vyzkoušejte nově podporované vstupy
J. Slabý (ITI, Fl)
PB173/07
24.9.2013       13/ 17
Tvorba AST
• Do options
• ASTLabelType = pANTLR3_BASE_TREE;
• output = AST;
• Kořenem je uzel tvořený počátečním symbolem gramatiky
• Podstromy se připojují ve vnořených pravidlech
• Pomocí speciálních přepisovacích pravidel
• Explicitně: pravaStrana -> podstromAST
• ~(kořen pravaStrana)
• kořen musí být v token nebo v tokens
• Implicitně: pravaStrana (vytvoří podstrom pravaStrana)
• ~ - kořen (pod)stromu
• ! - nevkládat do stromu
statement : expression"';'! // implicitní strom
| e1=expression '+' e2=expression ';' -> "(BINARY.OP '+' e1 e2)
J. Slabý (ITI, Fl)
PB173/07
24.9.2013       14/ 17
Úkol
Dopište tvorbu stromu do gramatiky test/Parser .g O Nejprve přesuňte test/Parser. g do parser/Parser .g
• Je zde již podpora pro AST O Definujte token kořen
• V sekci tokens
O Explicitně vytvořte AST podstromy v helloWorld
• Např. ahoj svete přepište na "(kořen ahoj svete)
J. Slabý (ITI, Fl)
PB173/07
24.9.2013       15/ 17
Co s AST?
• Vypsat (viz main. c)
• puts((char *)parseTree.tree-> toStringTree(parseTree.tree)->chars);
• Vytvořit novou stromovou gramatiku
• Čte AST
• Nemusí se starat o původní jazyk
• Provádí akce na podstromech
• Interpretuje je
• Překládá
• Vytváří graf toku řízení
• ...
• tree grammar JmenoAST; V hlavičce
• tokenVocab = JmenoGramatiky; Voptions
• Pravidla podle generovaných: ~(binary_op ' + 'el e2)
• Na pravé straně může být akce:
{ printf("Y/„s + Y/„s\n", $el .text->chars, $e2.text->chars); }
J. Slabý (ITI, Fl)
PB173/07
24.9.2013       16/ 17
Úkol
Napište stromovou gramatiku pro Par ser. g O Vytvořte nový soubor ASTParser.g (nebo použijte ukázkový) 0 Zapište všechny možné AST stromy které generujete v Parser.g
• Můžete strukturovat za použití pravidel a rekurze
Q A vypište si ke každému pravidlu jeho jednotlivé části
• p : X { puts($X.text->chars); } ;
J. Slabý (ITI, Fl)
PB173/07
24.9.2013       17/ 17