abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
    11.7. 16:44 | Komunita

    Dnes v 17:30 bude oficiálně vydána open source počítačová hra DOGWALK vytvořena v 3D softwaru Blender a herním enginu Godot. Release party proběhne na YouTube od 17:00.

    Ladislav Hagara | Komentářů: 3
    11.7. 14:55 | Humor

    McDonald's se spojil se společností Paradox a pracovníky nabírá také pomocí AI řešení s virtuální asistentkou Olivii běžící na webu McHire. Ian Carroll a Sam Curry se na toto AI řešení blíže podívali a opravdu je překvapilo, že se mohli přihlásit pomocí jména 123456 a hesla 123456 a získat přístup k údajům o 64 milionech uchazečů o práci.

    Ladislav Hagara | Komentářů: 14
    11.7. 00:11 | Nová verze

    Byla vydána (𝕏) červnová aktualizace aneb nová verze 1.102 editoru zdrojových kódů Visual Studio Code (Wikipedie). Přehled novinek i s náhledy a videi v poznámkách k vydání. Ve verzi 1.102 vyjde také VSCodium, tj. komunitní sestavení Visual Studia Code bez telemetrie a licenčních podmínek Microsoftu.

    Ladislav Hagara | Komentářů: 0
    10.7. 21:00 | Bezpečnostní upozornění

    Byla vydána nová verze 2.4.64 svobodného multiplatformního webového serveru Apache (httpd). Řešeno je mimo jiné 8 bezpečnostních chyb.

    Ladislav Hagara | Komentářů: 4
    10.7. 15:22 | Nová verze

    Společnost xAI na síti 𝕏 představila Grok 4, tj. novou verzi svého AI LLM modelu Grok.

    Ladislav Hagara | Komentářů: 12
    10.7. 12:55 | Bezpečnostní upozornění

    Ministerstvo vnitra odhalilo závažný kyberincident v IT systému resortu. Systém, do kterého se dostal útočník bez oprávnění, byl odpojen a nedošlo k odcizení dat [𝕏].

    Ladislav Hagara | Komentářů: 16
    10.7. 11:55 | Humor

    Před rokem byla streamovací služba HBO Max přejmenována na Max. Dle managementu slovo HBO v názvu nebylo důležité. Včera byl Max přejmenován zpět na HBO Max. Kolik milionů dolarů to stálo? 😂

    Ladislav Hagara | Komentářů: 15
    10.7. 02:11 | Nová verze

    Byla vydána nová major verze 8.0.0 svobodného systému pro detekci a prevenci průniků a monitorování bezpečnosti počítačových sítí Suricata (Wikipedie). Přehled novinek v oficiálním oznámení a v aktualizované dokumentaci.

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

    Mastodon (Wikipedie) - sociální síť, která není na prodej - byl vydán ve verzi 4.4. Přehled novinek s náhledy a videi v oznámení na blogu.

    Ladislav Hagara | Komentářů: 1
    10.7. 00:11 | IT novinky

    Instituce státní správy nebudou smět využívat produkty, aplikace, řešení, webové stránky a webové služby poskytované čínskou společností DeepSeek. Na doporučení Národního úřadu pro kybernetickou a informační bezpečnost rozhodla o jejich zákazu vláda Petra Fialy na jednání ve středu 9. července 2025.

    Ladislav Hagara | Komentářů: 8
    Jaký je váš oblíbený skriptovací jazyk?
     (59%)
     (27%)
     (7%)
     (3%)
     (1%)
     (1%)
     (4%)
    Celkem 389 hlasů
     Komentářů: 16, poslední 8.6. 21:05
    Rozcestník

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

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

    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.