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í
×
    dnes 00:11 | Nová verze

    Po 9 týdnech vývoje od vydání Linuxu 6.15 oznámil Linus Torvalds vydání Linuxu 6.16. Přehled novinek a vylepšení na LWN.net: první a druhá polovina začleňovacího okna a Linux Kernel Newbies.

    Ladislav Hagara | Komentářů: 0
    25.7. 19:55 | IT novinky

    Americký výrobce čipů Intel propustí 15 procent zaměstnanců (en), do konce roku by jich v podniku mělo pracovat zhruba 75.000. Firma se potýká s výrobními problémy a opouští také miliardový plán na výstavbu továrny v Německu a Polsku.

    Ladislav Hagara | Komentářů: 22
    25.7. 17:33 | Komunita

    MDN (Wikipedie), dnes MDN Web Docs, původně Mozilla Developer Network, slaví 20 let. V říjnu 2004 byl ukončen provoz serveru Netscape DevEdge, který byl hlavním zdrojem dokumentace k webovým prohlížečům Netscape a k webovým technologiím obecně. Mozille se po jednáních s AOL povedlo dokumenty z Netscape DevEdge zachránit a 23. července 2005 byl spuštěn MDC (Mozilla Developer Center). Ten byl v roce 2010 přejmenován na MDN.

    Ladislav Hagara | Komentářů: 0
    25.7. 14:55 | Nová verze

    Wayback byl vydán ve verzi 0.1. Wayback je "tak akorát Waylandu, aby fungoval Xwayland". Jedná se o kompatibilní vrstvu umožňující běh plnohodnotných X11 desktopových prostředí s využitím komponent z Waylandu. Cílem je nakonec nahradit klasický server X.Org, a tím snížit zátěž údržby aplikací X11.

    Ladislav Hagara | Komentářů: 0
    25.7. 13:33 | Nová verze

    Byla vydána nová verze 6.18 živé linuxové distribuce Tails (The Amnesic Incognito Live System), jež klade důraz na ochranu soukromí uživatelů a anonymitu. Nově se lze k síti Tor připojit pomocí mostu WebTunnel. Tor Browser byl povýšen na verzi 14.5.5. Thunderbird na verzi 128.12.0. Další změny v příslušném seznamu.

    Ladislav Hagara | Komentářů: 0
    24.7. 14:33 | IT novinky

    Meta představila prototyp náramku, který snímá elektrickou aktivity svalů (povrchová elektromyografie, EMG) a umožňuje jemnými gesty ruky a prstů ovládat počítač nebo různá zařízení. Získané datové sady emg2qwerty a emg2pose jsou open source.

    Ladislav Hagara | Komentářů: 1
    24.7. 14:22 | Nová verze

    Byla vydána (𝕏) nová verze 25.7 open source firewallové a routovací platformy OPNsense (Wikipedie). Jedná se o fork pfSense postavený na FreeBSD. Kódový název OPNsense 25.7 je Visionary Viper. Přehled novinek v příspěvku na fóru.

    Ladislav Hagara | Komentářů: 0
    24.7. 13:33 | IT novinky

    Před 40 lety, 23. července 1985, společnost Commodore představila první počítač Amiga. Jednalo se o počítač "Amiga od Commodore", jenž byl později pojmenován Amiga 1000. Mělo se jednat o přímou konkurenci počítače Apple Macintosh uvedeného na trh v lednu 1984.

    Ladislav Hagara | Komentářů: 2
    24.7. 06:00 | IT novinky

    T‑Mobile USA ve spolupráci se Starlinkem spustil službu T-Satellite. Uživatelé služby mohou v odlehlých oblastech bez mobilního signálu aktuálně využívat satelitní síť s více než 650 satelity pro posílání a příjem zpráv, sdílení polohy, posílání zpráv na 911 a příjem upozornění, posílání obrázků a krátkých hlasových zpráv pomocí aplikace Zprávy Google. V plánu jsou také satelitní data.

    Ladislav Hagara | Komentářů: 9
    23.7. 21:55 | Komunita

    Společnost Proxmox Server Solutions stojící za virtualizační platformou Proxmox Virtual Environment věnovala 10 000 eur nadaci The Perl and Raku Foundation (TPRF).

    Ladislav Hagara | Komentářů: 2
    Kolik tabů máte standardně otevřeno ve web prohlížeči?
     (29%)
     (26%)
     (6%)
     (5%)
     (4%)
     (1%)
     (3%)
     (26%)
    Celkem 143 hlasů
     Komentářů: 17, poslední 26.7. 20:08
    Rozcestník
    Alternativně viz také můj osobní blog (RSS pro anglické články, RSS pro české články), kde toho hlavně v angličtině vychází mnohem víc.

    Víte že můžete odebírat mé blogy pomocí RSS? (Co je to RSS?)


    A kdo neumí použít RSS, tak je tu twitter: @Bystroushaak.

    Od určité doby jsou všechny texty které zde publikuji verzované na Githubu.

    Jestliže najdete chybu, nepište mi do diskuze a rovnou jí opravte. Github má online editor, není to skoro žádná práce a podstatně mi tím usnadníte život. Taky vás čeká věčná sláva v commit logu :)

    Aktuální zápisy

    Jak se píše programovací jazyk 3: Parser a AST

    16.2.2019 21:09 | Přečteno: 2241× | Obecné IT | Výběrový blog | poslední úprava: 25.2.2019 00:01

    Ve třetím dílu seriálu Jak se píše programovací jazyk se podíváme na způsob, kterým se z jednorozměrného pole Token objektů udělá syntaktický strom, který pak následně můžeme dále zpracovávat a vyhodnocovat.

    Parser

    Jak bylo popsáno v minulém dílu, Lexer vám kód rozřeže na pole jednotlivých elementů. V mém případě z kódu jako:

    (| asd = 1 | ^asd.)

    udělá pole ve stylu:

    [
      Token("OBJ_START", "("),
      Token("SEPARATOR", "|"),
      Token("IDENTIFIER", "asd"),
      Token("ASSIGNMENT", "="),
      Token("NUMBER", "1"),
      Token("SEPARATOR", "|"),
      Token("RETURN", "^"),
      Token("IDENTIFIER", "asd"),
      Token("OBJ_END", ")")
    ]

    Jde o seznam Token objektů, kde v property .name je uložen název tokenu (například „IDENTIFIER“) a v .value jeho hodnota (například „asd“). Na parseru je poté kód vzít a udělat z něj AST (abstraktní syntaktický strom) ve stylu:

    Object(
      slots={"asd": Number(1)},
      params=[],
      parents={},
      code=[
        Return(
          Send(Self(), Message("asd"))
        )
      ],
    )

    Na to jak je tinySelf jednoduchý jazyk mi dal parser docela zabrat. Původně jsem ho začal psát v RPythonním rpython.rlib.parsing.ebnfparse, což vypadalo opticky dobře a jednoduše:

    IGNORE: " |\n";
    
    root: (expression ["\."])* expression;
    
    object: ["("] slots? sends* [")"];
    block: ["["] slots? sends* ["]"];
    
    return: ["^"] expression;
    expression: IDENTIFIER | value | object | block | send;
    
    #sends: (send ["\."])* send ["\."]?;
    sends: (expression ["\."])* expression ["\."]?;
    send: (receiver? keyword) | (receiver? message) | (receiver? receiver? operator receiver);
    receiver: IDENTIFIER | object | block;
    message: IDENTIFIER;
    keyword: FIRST_KW_IDENTIFIER >expression< (KEYWORD_IDENTIFIER >expression<)*;
    operator: operator_characters+;
    operator_characters: "!" | "@" | "#" | "$" | "%" | "&" | "*" | "-" | "+" | \
                         "=" | "~" | "/" | "?" | "<" | ">" | "," | ";";
    
    slots: ["|"] (>slot_definition< ["\."])* >slot_definition<? ["\."]? ["|"];
    slot_definition: IDENTIFIER | (FIRST_KW_IDENTIFIER >expression<) | ARGUMENT;
    
    value: <string> | <float> | <integer>;
    
    float: integer "\." POSINT;
    integer: "\-" POSINT | POSINT;
    
    POSINT: "0|[1-9][0-9]*";
    
    ARGUMENT: ":[a-z_][a-zA-Z0-9_\*]*";
    IDENTIFIER: "[a-z_][a-zA-Z0-9_\*]*";
    FIRST_KW_IDENTIFIER: "[a-z_][a-zA-Z0-9_]*:";
    KEYWORD_IDENTIFIER: "[A-Z][a-zA-Z0-9_]*:";
    
    string: SINGLE_QUOTED_STRING | DOUBLE_QUOTED_STRING;
    SINGLE_QUOTED_STRING: "'[^\\\']*'";
    DOUBLE_QUOTED_STRING: "\\"[^\\\\"]*\\"";

    Poměrně záhy jsem však narazil na nedostatek dokumentace a taky na chování, které mi vysloveně vadilo (všechny ty >< a <> kolem identifikátorů, divná rekurze s |, mixování s reguláry atd..). Od začátku jsem to pojal jako TDD development (psatní testů před kódem) a jen díky tomu jsem se z toho nezcvokl, neměl jsem k tomu však daleko.

    Bystřejší čtenáři si jistě všimli, že v kódu jsou použity jiné tokeny, než v předchozím díle. Je tomu tak proto, že ebnfparse umožňuje definovat tokeny zároveň s parserem, což rply neumožňuje a to co bylo uvedeno v minulém díle je má pozdější snaha.

    RPLY

    Chybějící dokumentace mě časem donutila od RPythonního ebnfparse odejít, speciálně když jsem si procházel ostatní projekty, které používaly jiné parsery. Časem jsem narazil na rply, což je port parseru ply přímo pro RPython. Funguje tak, že píšete dekorátory funkcím ve stylu:

    @pg.production('expression : NUMBER')
    def expression_number(p):
        return Number(int(p[0].getstr()))

    Dekorátor určuje pattern z tokenů. Dekorovaná funkce pak co se s tokeny provede. Všechny tokeny jsou předány v poli v proměnné ‚p‘.

    V kódu nahoře se vezme první token (index 0) a vratí se objekt Number s tokenem, jehož hodnota byla převedena na číslo.

    Number není žádný magický objekt, nadefinoval jsem si ho sám po vzoru ostatních parserů. Dohromady mám tyto objekty, ze kterých se sestavuje syntaktický strom:

    Jak je vidět, v tinySelfu existují pouze objekty, bloky, akt poslání zprávy, přeposlání zprávy, kaskáda zpráv (akt poslání několika zpráv jednomu objektu), návrat hodnoty, tři typy zpráv (unární, binární, keyword) a poté čtyři zkratky pro často používané objekty: čísla, stringy, Self a Nil. Self by existovat teoreticky nemusel, mohla by to být jen Message("self") poslaná nikomu, ale zpřehledňuje to kód i výsledný strom. Nil je jen zkratka pro singleton, který by mohl být uložený v globálním namespace.

    Složitější rekurzivní pravidla

    Zde je ukázka složitějšího transformačního pravidla:

    @pg.production('expression : IDENTIFIER')
    def unary_message(p):
        return Send(obj=Self(), msg=Message(p[0].getstr()))
    
    @pg.production('expression : expression IDENTIFIER')
    def unary_message_to_expression(p):
        return Send(obj=p[0], msg=Message(p[1].getstr()))

    Na ukázce je dobře vidět, jak vzniká poslání zpráv a jak je řešeno vkládání implicitního Selfu. Pokud je identifikátor poslán zdánlivě ničemu, je aktu poslání zprávy předán jako cíl Self(). Pokud je před identifikátorem nějaký výraz, je cíli poslání zprávy předán první token obsahující tento výraz (což už je naparsovaná expression, tedy prvek AST).

    Podobnými pravidly je složen celý jazyk. Zde je také hezky vidět rekurzivní povaha parseru, který definuje expression jako identifikátor a poté také jako expression následované identifikátorem. Parser takhle provede rekurzivní pattern matching na všechny odpovídající tokeny, v samotných funkcích se pak jen definuje, co se z toho má složit za AST.

    Tenhle přístup má svou výhodu, protože vám dovoluje skládat AST přímo tak jak ho chcete. Předtím používaný ebnf z RPythonu vypadal sice zapsán elegantněji jako jeden krásný string, ale neumožňoval žádné skoro žádné manipupace s AST a vyplivl vám strom z tokenů, který bylo dále třeba zpracovávat. I když to bylo na vyšší úrovni, než samotné pole tokenů, stejně to byl masivní opruz. Oproti tomu přímý přístup k datům v rply vám umožňuje vygenerovat rovnou hotový a upravený AST.

    Zde je zdrojový kód celého parseru:

    Nikdy dřív jsem nepsal takhle složitý EBNF parser a musím říct, že to pro mě byl docela záhul. Naučit se přemýšlet v rekurzivně skládaných definicích mi dalo zabrat, a to ani nemluvím o tom, že jsem pro Self nenašel žádnou EBNF definici, takže jsem si jí podle manuálu +- skládal sám.

    Nakonec se však povedlo a kód prošel všemi testy, které jsem pro něj napsal. Myslel jsem si, že tím to pro mě končí, ale jak se ukázalo, byl to jen začátek další parsovací bolesti, tentokrát spočívající ve snaze kód upravit pro překlad RPythonem.

    Pokračování

    Příští díl bude takovým mezidílem na téma RPythonu a některých praktických problémů, které jsem musel vyřešit, abych mohl parser a lexer pod ním zkompilovat.

           

    Hodnocení: 89 %

            špatnédobré        

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

    Komentáře

    Vložit další komentář

    17.2.2019 14:20 Odin1918 | skóre: 6 | blog: Valhalla
    Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 3: Parser a AST
    Kvuli takovym clankum ma stale smysl sem chodit. Dekuji moc za clanek. Mohu se prosim zeptat, jakym nastrojem je vygenerovan onen pekny diagram?
    Bystroushaak avatar 17.2.2019 16:15 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
    Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 3: Parser a AST
    Je to obyčejné plantuml. Dělá se to deklarativními zápisy. Třeba ten pro tenhle diagram vypadá takhle: ast.plantuml.

    Někdy okolo sedmého dílu se tomu budu věnovat víc, protože jsem ty diagramy dynamicky generoval, když jsem se snažil oddebugovat tail call optimizace.
    17.2.2019 20:28 Odin1918 | skóre: 6 | blog: Valhalla
    Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 3: Parser a AST
    To je moc pekne, toto jsem neznal. Pred lety jsem toto resil u pomerne komplexniho a velmi "kosateho" projektu, kde snaha byla doplnit dokumentaci i automaticky generovanymi UML diagramy klicovych komponent. Nakonec jsem zplacal programek, ktery prolezl vsechny zdrojaky, zmapoval tridy a vztahy mezi nimi a vygeneroval zadani pro graphviz. Toto ale vypada lepe a srozumitelne - rozhodne vystup je daleko lepsi nez u graphvizu pred lety. ;-)
    Bystroushaak avatar 17.2.2019 20:59 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
    Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 3: Parser a AST
    Nakonec jsem zplacal programek, ktery prolezl vsechny zdrojaky, zmapoval tridy a vztahy mezi nimi a vygeneroval zadani pro graphviz.
    Hehe, to jsem před pár lety napsal taky. Tenkrát jsem si zakládal na tom, že mám v dokumentaci vždycky i pár obrázků, ze kterých je možné letmým pohledem pochopit vztahy v kódu, jednak co je tam za struktury, ale taky jak je použít, kde jsem UML znásilňoval tak aby popisovalo tok programu.
    Toto ale vypada lepe a srozumitelne - rozhodne vystup je daleko lepsi nez u graphvizu pred lety. ;-)
    Pokud se nepletu, tak plantuml na graphvizu staví, akorát ho v podstatě omezuje na jím používané diagramy. Ale nejsem si tím jistý stoprocentně.
    17.2.2019 21:49 Pavel Křivánek | skóre: 29 | blog: Kvičet nezávaznou konverzaci
    Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 3: Parser a AST
    PlantText taky používám, jen je škoda, že není založen na nějaké solidní gramatice. Jeden kolega si moc pochvaloval velice přívětivý přístup autora, který jeho rozumné návrhy na vylepšení prakticky okamžitě to PlantTextu zapracoval a komunikuje velice přátelsky.
    I'm sure it crashed in the most type-safe way possible.
    21.2.2019 21:46 kvr
    Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 3: Parser a AST
    Bouml ( http://bouml.fr/ ) má pěkné diagramy taky (a editovatelné), a umí reverse engineering. Podporuje poměrně hodně jazyků (Java, C++, Python, Php atd.), u reverse engineering těch dynamicky typovaných si nejsem jistý limitacemi, s Java a C++ funguje dobře. Export na web ideálně do SVG.
    22.2.2019 16:27 Ivan
    Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 3: Parser a AST
    Myslel jsem si, že tím to pro mě končí, ale jak se ukázalo, byl to jen začátek další parsovací bolesti, tentokrát spočívající ve snaze kód upravit pro překlad RPythonem.

    To mi pripomelo "Life After Parsing"

    https://www.semanticdesigns.com/Products/DMS/LifeAfterParsing.html?Home=DMSToolkit

    Založit nové vláknoNahoru

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