PB173 - Binární programování Linux II. Parse ry Jiri Slabý Fakulta informatiky Masarykova univerzita 27. 9. 2016 Jiri Slabý (Fakulta informatiky, MU) PB173/05 27.9.2016 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 o Studijní materiály v isu Jiri Slabý (Fakulta informatiky, MU) PB173/05 27.9.2016 2/21 Sekce 1 Parsery Jiri Slabý (Fakulta informatiky, MU) PB173/05 27. 9. 2016 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 9 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/05 27. 9. 2016 4/21 Výroba parseru O Ručně psané • Rychlost parseru a explicita • gcc (Demo) Q Generované nástroji • Rychlost napsání parseru a přehlednost kódu • Lex+Yacc • Flex+Bison • Antlr • A další Jiri Slabý (Fakulta informatiky, MU) PB173/05 27.9.2016 5/21 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/05 27.9.2016 6/21 Ú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.2 Java binaries jar" O Knihovna pro C (libantlr3c a antlr3c-devel) RPM:http://software.opensuse.org • Zdroje: http://www.antlr3.org/download/C/ O Vyzkoušejte generovat Parser .g Z pbl73-bin/02/test/ • make • Spousty varování ignorujte O Pusťte jej • ./parser test_input • Změňte test_input a zkuste znovu Jiri Slabý (Fakulta informatiky MU) PB173/05 27. 9. 2016 7/21 Části parseru c CFG Zdroj Lexikální analýza Tokenyj—► Syntaktická analýza AST 'a r 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 • Dává sekvence tokenů smysl? • Ano sémantická analýza • Přímá interpretace, tvorba AST, ... Jiri Slabý (Fakulta informatiky, MU) PB173/05 27.9.2016 8/21 Vnitřní struktury parseru void fun(int a) {/* comment */ int b = 0; if (a) b = 5; a = 3 * b; } key:void ickfun LPAR key:int id:a RPAR LCUR key:int id:b EQ num:0 SEMIC key:if LPAR id:a RPAR id:b EQ num:5 SEMIC id:a EQ num:3 MULT id:b SEMIC RCUR Za 0 ZT int a ded if = A int var a = a * 71 Jiri Slabý (Fakulta informatiky MU) PB173/05 27. 9. 2016 9/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) PB173/05 27.9.2016 10/21 Části parseru 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á o ; odděluje pravidla • : odděluje levou a pravou stranu pravidla Příklad /* syntaktická analýza */ helloWorld : AHOJ SVETE | SVETE AHOJ { puts("Nepise se to obracené?");} /* lexikálni analýza */ AHOJ : 'Ahoj' ; SVETE : 'Svete' ; Jiri Slabý (Fakulta informatiky, MU) PB173/05 27.9.2016 11 /21 Pravá strana pravidel • I odděluje možnosti • Více možností: zvirata : savci | obojživelníci o Také kombinace podčástí: strunatci : (JpeJ I JkoJ) • Opakování pravidla • pravidlo? - 0-1 krát, např. nicNeboX : JxJ? ; • pravidlo* - 0-ookrát, např. kolonaAut : JautoJ* ; • pravidlo+- 1-ookrát, např. zvukHada : JsJ+ ; 9 Rozsahy • JAJ.. Jzj - celá velká ASCII abeceda • Speciální pravidlo pro konec souboru: EOF Donutí číst celý soubor Jiri Slabý (Fakulta informatiky MU) PB173/05 27.9.2016 12/21 Úkol Rozšíření gramatiky O Prozkoumejte Obsah 02/test/Parser .g O Vytvořte si token number pro čísla • (J0J..J9J)+ O Vytvořte si tokeny pro + a - O Vytvořte si nové pravidlo expr pro tyto 2 operace • Bude obsahovat 2 možnosti (oddělené I) • Pro sčítání např. number plus number O Přidejte do transiationUnit novou možnost • Bude odpovídat 1-oo opakováním expr O Vyzkoušejte nově podporované vstupy • 1+2, íoo-io, apod. Jiri Slabý (Fakulta informatiky, MU) PB173/05 27.9.2016 13/21 Sekce 2 Akce pravidel Jiri Slabý (Fakulta informatiky, MU) PB173/05 27.9.2016 14/21 Akce pravidel Pravidla mohou obsahovat akce o Kód spouštěný při určitých událostech a { C code } za pravostrannými tokeny • Vykoná se ihned, když token odpovídá vstupu Příklad p:ID{ putsffound an ID"); }ID{ putsffound second ID"); }ID{ putsfwow, 3 IDs"); } Jiri Slabý (Fakulta informatiky, MU) PB 173/05 27.9.2016 15/21 Úkol Akce pravidel o Dopište akce na konec obou možností expr o Vypište nějaký text • Ale různý pro každou možnost O Vyzkoušejte Jiri Slabý (Fakulta informatiky MU) PB173/05 27.9.2016 16/21 Vlastnosti tokenů Každý token má vlastnosti • line - zdrojový řádek • pos - zdrojový sloupec o text - tokenizovaný řetězec („Ahoj" pro AHOJ) • Jak pro tokeny (pravé strany), tak pro pravidla (levé strany) o Typ: pANTLR3_string, obsahuje char *chars o Akce můžou odkazovat předcházející tokeny • Implicitně jménem tokenu/pravidla: p : number { $number.line; } ; • Nebo pojmenováním: p : nl=number plus n2=number { $n2.pos; } ; Příklad helloWorld : x=AHOJ y=SVETE { printf("line=\%d col=\%d\n", $x.line, $x.pos); printf("x=\%s y=\%s whole=\%s\n", $x.text->chars, $y.text->chars, $helloWorld.text->chars); Jiri Slabý (Fakulta informatiky, MU) PB173/05 27.9.2016 17/21 Úkol Vlastnosti pravidel o Pro každou operaci sčítání/odčítání o Vypište číslo řádku a sloupce pro obě čísla ($number.line a $number.pos) • Vypište obě čísla jako řetězec ($number.text->chars) O Vyzkoušejte roztroušením textu po testovacím vstupu Jiri Slabý (Fakulta informatiky MU) PB173/05 27.9.2016 18/21 Předávání hodnot Každé pravidlo muže akceptovat/vracet hodnotu • Stejně jako funkce • levaStrana[typel parami, ...] returns [typeR ret] : pravaStrana • Pak lze v akcích odkazovat na Spárami typu typei • Akce musí nastavovat $ret typu typeR Příklad translationUnit : expr[5] EOF { printf(Tm 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 { $ret = 0;} Jiri Slabý (Fakulta informatiky MU) PB173/05 27.9.2016 19/21 Úkol Vlastnosti pravidel O Vytvořte si pravidlo pro čísla • number : NUMBER ; O Z něj a z expr si vracejte (smysluplnou) hodnotu • Tj. počítejte o V transiationUnit vypište výsledek • Pro každé expr Jiri Slabý (Fakulta informatiky, MU) PB173/05 27.9.2016 20/21 Inicializace/ukončení Každé pravidlo muže mít inicializace/ukončení • Na konci levé strany pravidla (před dvojtečkou) • Před aplikováním pravidla: @init{ ... } • Např. inicializovat proměnné Po aplikování pravidla: @af ter{ ... } • Např. počítání Příklad expr[int par] returns [int ret] @init{ $ret = 0;} @after{ $ret—;} : n1=NUMBER PLUS n2=NUMBER { $ret = $par * atoi($n1 .text->chars) + atoi($n2.text->chars); } Jiri Slabý (Fakulta informatiky MU) PB173/05 27.9.2016 21 /21