abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
    dnes 10:49 | IT novinky
    Světem se valí vlna BSOD počítačů s operačním systémem Windows v kombinaci s bezpečnostním agentem CrowdStrike. Částečně jsou ochromeny letiště, banky, burzy, Microsoft Cloud apod. Zatím je znám jen workaround v podobě nabootování do recovery režimu a smazání jednoho souboru.
    karkar | Komentářů: 2
    včera 23:44 | Komunita

    Nezisková organizace Apache Software Foundation (ASF) oznámila, že se částečně přestane dopouštět kulturní apropriace a změní své logo a brand. Minimálně z loga odstraní indiánské pírko. Nové logo a brand představí na své konferenci Community Over Code v říjnu letošního roku. Ta byla ještě nedávno známá jako ApacheCon.

    Ladislav Hagara | Komentářů: 14
    včera 19:00 | Nová verze

    Sound Open Firmware, projekt Linux Foundation, open source audio DSP firmware a SDK, byl vydán ve verzi 2.10.0. Podrobný přehled novinek na GitHubu.

    Ladislav Hagara | Komentářů: 0
    včera 10:33 | Komunita

    Společnost Nvidia na svém technickém blogu informuje o přechodu na open source moduly jádra pro GPU (představila je v květnu 2022). Na nejnovějších platformách Grace Hopper nebo Blackwell lze používat pouze open source moduly. Pro Turing, Ampere, Ada Lovelace nebo Hopper se doporučuje přejít na open source moduly, v oficiálním instalátoru si lze vybrat mezi proprietárním a open source modulem. Nejstarší Maxwell, Pascal nebo Volta vyžadují proprietární ovladače.

    Ladislav Hagara | Komentářů: 0
    včera 00:11 | Zajímavý článek

    Příspěvek na blogu společnosti Wiz se podrobně věnuje dnes již opraveným zranitelnostem v SAP AI. Útočník si mohl změnit své UID na UID firewallu, tj. 1337, a tím obejít firewall, …

    Ladislav Hagara | Komentářů: 0
    17.7. 23:22 | IT novinky

    Vláda schválila Zprávu o stavu kybernetické bezpečnosti České republiky za rok 2023 (pdf). Dokument připravil Národní úřad pro kybernetickou a informační bezpečnost (NÚKIB) a vyplývá z něj, že v roce 2023 se v České republice meziročně zvýšil celkový počet kybernetických incidentů evidovaných NÚKIB ze 146 na 262. Policie ČR pak v roce 2023 evidovala přes 19 tisíc trestných činů v oblasti kybernetické kriminality, což činí 6% meziroční

    … více »
    Ladislav Hagara | Komentářů: 0
    17.7. 13:11 | Zajímavý článek

    Nikita Mazurov pro The Intercept popisuje, jak si zařídil anonymní účet v komunikátoru Signal, tedy aniž by použil své telefonní číslo. Využil telefonní budku. Poslední telefonní budka v Česku byla odstraněna v roce 2021.

    Fluttershy, yay! | Komentářů: 42
    17.7. 01:55 | Nová verze

    Svobodná webová platforma pro sdílení a přehrávání videí PeerTube (Wikipedie) byla vydána v nové verzi 6.2. Přehled novinek i s náhledy v oficiálním oznámení a na GitHubu.

    Ladislav Hagara | Komentářů: 0
    17.7. 01:33 | Nová verze

    Byla vydána nová stabilní verze 3.6 svobodného multiplatformního softwaru pro editování a nahrávání zvukových souborů Audacity (Wikipedie). Přehled novinek také na YouTube. Ke stažení je oficiální AppImage. Zatím starší verze Audacity lze instalovat také z Flathubu a Snapcraftu.

    Ladislav Hagara | Komentářů: 0
    17.7. 01:11 | Nová verze

    Po necelých 4 měsících vývoje od vydání verze 6.5 byla vydána nová verze 6.6 svobodného open source redakčního systému WordPress. Kódové jméno Dorsey bylo vybráno na počest amerického jazzového trombonisty, trumpetisty, skladatele a dirigenta big band éry Tommyho Dorseyho (YouTube).

    Ladislav Hagara | Komentářů: 0
    Rozcestník

    Jazyky a překladače - 5 (syntaxe 3)

    27. 9. 2006 | Michal Vyskočil | Programování | 9167×

    Implementace syntaktického analyzátoru není příliš snadná záležitost a konstrukce parsovací tabulky jakbysmet. Proto si představíme dva programy pro generování syntaktických analyzátorů.

    Obsah

    V předcházejícím díle jsme se seznámili se syntaktickou analýzou a s pojmy LR a LL parsery. Dnešní díl bude nadupaný kódem až po kou... koncovou kapitolu, proto asi nepotěším milovníky všeho formálního, jak tomu bylo v minulém díle.

    Bison

    link

    Stejně jako flex je GNU náhrada staršího POSIXového lexu, je i bison náhradou programu yacc. Pro vysvětlení hackerského humoru — bison je druh jaka a yacc znamená yet another compiler compiler. Jedná se o generátor LR syntaktických analyzátorů a ve spojitosti s programem flex tvoří část (frontendu) překladače.

    V minulém díle jsem ukazoval, že překladač jazyka C nepřeloží konstrukci printf("%s\n", n) if (n == 10);. Navíc jsem uvedl část gramatiky ve formátu EBNF, která se této části jazyka týká. Napíšeme si tedy jednoduchý analyzátor pro konstrukci if v jazyce C. Ovšem je nutné si uvědomit, že syntaxe jazyka C je velice složitá a náš příklad ukazuje pouze malou část (a to ještě ne zcela správně). To je také důvod, proč se v každém příkladu na yacc/bison, co jsem viděl, ukazuje gramatika Pascalu. Základem je tedy definiční soubor cselect.y, který obsahuje definici gramatiky.

    %{
    #include<stdio.h>
    %}
    
    %token IF ELSE
    %token IDENTIFIER CONSTANT STRING_LITERAL
    %token EQ_OP
    
    %start compound_statement
    
    %%
    

    První část obsahuje potřebné definice jazyka C. Dále tu vidíme seznam jednotlivých tokenů (terminálních symbolů gramatiky). Část start označuje startovací (nonterminální) symbol gramatiky. Navíc můžeme označit aritmetické operátory slovem left — například %left "+" (případně right pro ty s pravou asociativitou). Dva znaky procento ukončují danou část a objevuje se definice gramatiky.

    assignment_statement
    	: IDENTIFIER '=' expression
    	;
    
    selection_statement
    	: IF '(' expression ')' statement
    	| IF '(' expression ')' statement ELSE statement
    	;
    
    expression
    	: IDENTIFIER
    	| CONSTANT
    	| STRING_LITERAL
    	| '(' expression ')'
    	| expression EQ_OP expression
    	;
    
    statement
    	: compound_statement
    	| selection_statement
    	| assignment_statement
    	;
    
    statement_list
    	: statement
    	| statement_list ';' statement
    	;
    
    compound_statement
    	: '{' '}'
    	| '{' statement_list '}'
    	;
    %%
    

    Jak vidíte, i tato nepatrná část jazyka C potřebuje celkem 6 terminálních a 6 nonterminálních symbolů. Princip je zřejmý. Startovacím symbolem je compound_statement, který může být buďto prázdný, nebo obsahovat seznam příkazů statement_list. Seznam může obsahovat jeden nebo více příkazů, které jsou odděleny středníkem. A tak se pokračuje dále.

    int main()
    {
    	yyparse();
    }
    
    int yyerror(char* s)
    {
    	fprintf(stderr, "%s\n", s);
    	return 0;
    }
    
    int yylex()
    {
    	return 0;
    }
    

    Nakonec kód obsahuje C kód. Jak vidíme, tak hlavní parsovací funkce se nazývá yyparse. Navíc vidíme funkci yyerror, která slouží pro obsluhu chyb v průběhu parsování a potřebnou funkci lexikálního analyzátoru yylex. Zde tedy máme pouze syntaktický analyzátor, ale chybí nám lexikální. Využijeme nám známý program lex a napíšeme definici lexikálního analyzátoru.

    Protože na ní není vcelku nic zajímavého, uvedu sem pouze odkazy. Lexikální analyzátor cselect.l, zvýrazněná syntaxe cselect.l.html, syntaktický analyzátor cselect.y a zvýrazněná syntaxe cselect.y.html. Případně je k dispozici archív i s Makefile — cselect.tar.gz. Pokud se podíváte do definičního souboru pro parser, zjistíte, že je funkce yylex zakomentovaná a místo ní je v kódu #include "lex.yy.c", která zařídí vložení kódu lexikálního analyzátoru generovaného programem lex.

    Překlad toho celého provedeme takto:

    yacc -d cselect.y
    lex cselect.l
    gcc -o cselect y.tab.c -lfl
    

    Prvním příkazem vygenerujeme hlavičkový soubor y.tab.h, ve kterém jsou uvedeny makra pro jednotlivé tokeny. Navíc vygenerujeme zdrojový kód analyzátoru y.tab.c. Varování o shift/reduce konfliktech jsou způsobená nejednoznačnostmi v definici gramatiky. Při spuštění programu můžeme zadávat vstup:

    $ ./cselect
    { a = b }
    ^D
    $ ./cselect
    { if ( a == b ) { s = 1; gid = 0 }}
    ^D
    $ ./cselect
    a = b
    parse error
    $ ./cselect
    { a = b; }
    parse error
    

    Jak vidíme, parser skutečně provádí kontrolu podle zadané gramatiky. Například v ní není povoleno, aby poslední příkaz v seznamu končil středníkem. Rovněž není žádné zotavení se z chyb (což není nikterak jednoduchá věc a pro podrobnosti konzultujte dokumentaci), takže náš zárodek překladače je ekvivalentem jedné úpravy gcc, která vrací true, pokud je program dobře napsán a false, pokud špatně. Z reálně používaných programů dostávám stejně užitečná hlášení z MSIE — Na stránce se vyskytla chyba.

    Další možnosti

    link

    Zatím náš program nepředával žádné hodnoty mezi skenerem a parserem. K tomu slouží proměnná yyval, takže můžeme do definice skeneru napsat [0-9]+ {yyval = atoi(yytext); return CONSTANT;}. Jenže yyval je implicitně typu int. Naštěstí bison dovoluje definovat vlastní typ proměnné, takže do definice parseru přidáme

    %union {
    	int integer;
    	char* string;
    }
    ...
    %token <integer> CONSTANT
    %token <string> IDENTIFIER
    

    a definice parseru se změní na [0-9]+ {yyval.integer = atoi(yytext); return CONSTANT;}

    Při průchodu stromem potřebujeme při nalezení pravidla udělat nějakou akci. Například:

    expression
    	: IDENTIFIER {printf("nalezen identifikátor %s\n", $1);}
    	;
    

    Pokud vás zaráží $1, pak vězte, že jde o makro, které představuje odkaz na zásobník hodnot, které analyzátor spravuje. Například aritmetické operace se dají psát takto:

    expression:
    	: expression '+' expression { $$ = $1 + $3; }
    

    Konflikty

    link

    Gramatiky nebývají jednoznačné a nástroje jako yacc je odhalují. V našem případě se jedná mj. o problém volné klausule else, kterou trpí mnoho jazyků. Pokud zapíšeme kód

    if (a == b) if (b > c) do_anything else do_anything2
    

    Překladač neví, ke kterému z obou if patří klauzule else. Při zpracování totiž překladač může provést reduce a uzavřít pouze první if, anebo shift pokračovat ve čtení dalšího tokenu a zpracovat if-else. Implicitně yacc provádí přesuny tak dlouho, dokud nezíská nejdelší vstupní řetězec, takže klauzule else se přiřadí druhému if, což je stejné chování, jaké programátoři v C (Pascalu a podobných jazycích) očekávají. Pro jednoznačný zápis musí programátor napsat {}. Ovšem bison umožňuje přiřazovat některým větvím gramatiky prioritu. Například v jazyce Python tato situace nemůže nastat, protože tam jsou bloky přesně definovány odsazením.

    Antlr

    link

    Program s více než podivným názvem (znamená Another toolkit for language recognizer) způsobil menší pozdvižení v oblasti překladačů. Do té doby se všeobecně uznávalo, že není možné efektivně implementovat LL(n > 1) gramatiku (pro připomenutí, gramatiku, která potřebuje pro rozhodování více než jeden token). Ostatně, bez ohledu na snahy Niclause Wirtha dávali vývojáři přednost LR parserům, jejichž implementace byly považovány za efektivnější. Tento program, napsaný v Javě, mínění vývojářů změnil. Podotýkám, že název, který končí na LR, mnoho vývojářů mate, ale nemá to nic společného s LR parsery, program skutečně generuje LL(n) gramatiky. Nejsme tedy omezeni na C, nebo C++, jako je tomu v předchozím případě.

    Mezi jeho další výhody patří to, že generuje kód pro analýzu rekurzivním sestupem, který je čitelnější než výstup LR analýzy bisonu. Také dokáže generovat překladač pro čtyři prostředí — Java, v níž je napsán, C#, C++ a Python. Jeho Public Domain Licence navíc nikterak nebrání integraci do dalších produktů, jako je třeba Intelli Idea (viz seznam). Případně dokáže vygenerovat kód pro průchod syntaktickým stromem, obsahuje podporu i pro sémantické akce (ve skutečnosti jí trochu obsahuje i bison).

    Ukážeme si kousek analyzátoru (popravdě se jedná o upravený příklad ze stránek anltr.org):

    {
    	import java.io.*;
    
    	import antlr.CommonAST;
    	import antlr.DumpASTVisitor;
    }
    
    class P extends Parser;
    
    startRule
    	:   o:Constant
    	{System.out.println("Constant: "+o.getText());}
    	|   i:ID
    	{System.out.println("ID: "+i.getText());}
    	;
    
    {
    	import antlr.*;
    }
    
    class L extends Lexer;
    
    // one-or-more letters followed by a newline
    
    Constant
    	: '1'..'9' ( Digit )* NEWLINE
    	| '0' ( 'x' | 'X' ) ( 'a'..'f' | 'A'..'F' | Digit )+ NEWLINE
    	;
    
    ID:   ( Char ) ( Char | Digit |'_' )+ NEWLINE
    	;
    
    NEWLINE
    	:   '\r' '\n'   // DOS
    	|   '\n'        // UNIX
    	;
    
    protected Digit:    '0'..'9' ;
    protected Char:     'a'..'z' | 'A'..'Z' ;
    

    Jak vidíme, je možné prakticky kdekoliv v kódu psát kód v Javě. Ve výše zmíněném příkladu definujeme třídu pro parser i scanner v jednom souboru (na rozdíl od kombinace flex/bison). Dalším rozdílem je to, že je překladač objektový, takže máme třídu P pro parser a L pro lexikální analyzátor. Ovšem takový kód sám od sebe nedělá nic, je nutné objekty inicializovat a zavolat.

    import java.io.*;
    
    class Main {
    	public static void main(String[] args) {
    	try {
    		// vytvoreni scanneru
    		L lexer = new L(new DataInputStream(System.in));
    		// vytvoreni parseru
    		P parser = new P(lexer);
    		// zavolani startovaci podminky
    		parser.startRule();
    	} catch(Exception e) {
    		System.err.println("exception: "+e);
    	}
    	}
    }
    

    Po instalaci balíčku jsem ze skriptu /usr/bin/runantlr zjistil potřebnou CLASSPATH tak, abych mohl analyzátor přeložit.

    $ export CLASSPATH=$CLASSPATH:/usr/share/java/antlr.jar
    $ java antlr.Tool grammar.g
    ANTLR Parser Generator   Version 2.7.6 (20060511)   1989-2005
    $ javac *.java
    

    A používáme:

    $ java Main
    120
    Constant: 120
    $ java Main
    identifikator
    ID: identifikator
    $ java Main
    0112
    exception: line 1:2: unexpected char: '1'
    

    Závěr

    link

    V tomto díle jsme si představili dva nástroje pro tvorbu syntaktických analyzátorů. Je třeba si uvědomit, že oba dva generují parsery pro podmnožinu bezkontextových gramatik a proto, pokud vyžadujeme plnou sílu gramatiky, musíme využít jiné nástroje založené na jiných algoritmech. Přestože je kombinace yacc/bison součástí prakticky libovolného unixového systému, myslím, že program antlr stojí za pozornost.

    Existuje ovšem daleko větší řádka překladačů překladačů (jak se tyto nástroje nazývají).

    Essence Generátor LR parserů pro Scheme
    GOLD Parsing System Generátor LALR gramatik, který se pyšní největším počtem podporovaných cílových jazyků. Vedle C, Javy nebo Pythonu umí generovat kód pro x86 assembler nebo Visual Basic.NET.
    javaCC Další z řady LL(n) generátorů pro Javu.
    SableCC Generátor LALR parserů pro Javu (umí i C, C++, OCAML, Python a C#).
    SmaCC Generátor LR a LALR parserů pro Smalltalk.
    cl-yacc LR generátor pro Common Lisp.
    SPARK Implementace Earlyho parsovacího algoritmu v Pythonu.
    CYK Parser c C++ Implementace algoritmu CYK v C++

    Tímto vynecháme syntaxi a posuneme se dále. Velkou otázkou příštího dílu bude — co to vlastně znamená? V terminologii počítačových vědců sémantika. A s tím související otázku typů. Navíc si konečně ukážeme schéma překladače.

           

    Hodnocení: 92 %

            špatnédobré        

    Nástroje: Tisk bez diskuse

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    Komentáře

    Vložit další komentář

    27.9.2006 11:15 jan.xxx
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    Kdysi jsem přemýšlel, že bych tím projel jeden textový formát souborů a naparsoval bych to do nějakych tříd. Ale přijde mi to nějak složité. Asi ze mě programátor nikdy nebude :-(
    27.9.2006 12:00 Ladislav Thon
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    Implementace syntaktického analyzátoru není příliš snadná záležitost
    Implementace parseru (v ruce) je při použití rekurzivního sestupu velmi snadná záležitost. IMHO neexistuje důvod, proč navrhovat programovací jazyky jinak než jako LL(1), takže rekurzivní sestup je úplně v klidu. Z důvodu, který mi není známý, bohužel někdo s oblibou navrhuje LR prasárny typu C, které navíc obsahují příšerné množství konfliktů...
    yacc -d cselect.y
    lex cselect.l
    Já myslel, že používáme bison a flex :-)
    ANTLR ... program skutečně generuje LL(n)
    ANTLR používá predikátové LL(k) gramatiky, takže má dokonce větší vyjadřovací schopnosti než LALR. A to se vyplatí :-)
    Vašek Lorenc avatar 27.9.2006 12:17 Vašek Lorenc | skóre: 27
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    Implementace syntaktického analyzátoru není příliš snadná záležitost
    Implementace parseru (v ruce) je při použití rekurzivního sestupu velmi snadná záležitost.
    Ještě snazší je implementace parseru např. v Haskellu za pomoci monadických parserů. Nebo pomocí generátoru parserů Happy, nicméně to první řešení je mnohem elegantnější.
    ...včetně majestátného loosa
    27.9.2006 13:42 Ladislav Thon
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    Ještě snazší je implementace parseru např. v Haskellu za pomoci monadických parserů.
    To jsem neznal. A neznám. A věřím tomu, že při vysokoúrovňových funkcionálních orgiích mohou vzniknout nádherné parsery ;-) Nicméně z toho, co jsem tak za pár minut stihl najít, to vypadá, že v principu jde též o rekurzivní sestup. Wirthův přístup má ještě své zastánce! :-)
    27.9.2006 14:50 Tom.š Ze.le.in | skóre: 21 | blog: tz
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    yacc -d cselect.y
    lex cselect.l
    Já myslel, že používáme bison a flex :-)
    A proč by se binárka bisona neměla jmenovat yacc? :)
    27.9.2006 16:53 Ladislav Thon
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    A proč by se binárka bisona neměla jmenovat yacc? :)
    Uff, jestli se binárka bisona jmenuje yacc, tak jsem silně konsternován. Ještě že to nepoužívám, musel bych si začít klást otázky, proč se binárka Linuxového kernelu nejmenuje minix :-)
    27.9.2006 18:03 Michal Vyskočil | skóre: 60 | blog: miblog | Praha
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    # cd /usr/bin
    # ln bison yacc
    # rm bison
    
    Kontrolní otázka, jakže se teď jmenuje binárka bisonu :-D
    When your hammer is C++, everything begins to look like a thumb.
    27.9.2006 20:02 Michal Kubeček | skóre: 72 | Luštěnice
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    Jmenovat se tak může, stejně prakticky ve všech linuxových distribucích jsou lex a yacc jen linky na flex a bison (stejně jako třeba sh na bash a vi na vim). Pokud ji ale spouštíte jménem lex resp. yacc, neměl byste použít nic z rozšíření, která mají flex resp. bison navíc.
    27.9.2006 18:06 Michal Vyskočil | skóre: 60 | blog: miblog | Praha
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    No, v Linuxových distrech se stejně používá bison a flex. Ale tohle mi jelo i na prastaré Sunovské mašince :-)
    ANTLR používá predikátové LL(k) gramatiky, takže má dokonce větší vyjadřovací schopnosti než LALR. A to se vyplatí :-)
    Predikátové, to slovo mě vypadlo. Díky za upozornění.
    When your hammer is C++, everything begins to look like a thumb.
    3.7.2009 01:57 hypiz
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    jen drobna korekce, LL(k) a LALR(1) jsou neporovnatelne, .. nebo snad ne?
    27.9.2006 22:54 Pavel Kysilka
    Rozbalit Rozbalit vše Re: Jazyky a překladače - 5 (syntaxe 3)
    skvele, to jsem presne shanel. o bisonu vim, ale pro javu to je horsi.

    mnohokrate diky.

    gf
    18.1.2016 21:10 ehmmm
    Rozbalit Rozbalit vše Konflikty a Python
    Co se tyka konfliktu s if/else, tak v Python jde neco, co asi jde i v C.

    a if b else c if d else e

    Ma to byt?: a if b else (c if d else e)

    Nebo?: (a if b else c) if d else e

    Intuitivne si myslim, ze se to bude chovat jako ta prvni varianta.

    Ale uznavam, ze to nema na ceckovske if (a) if (b) {c;} else {d;}

    Založit nové vláknoNahoru

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.