Utilita YACC

Utilita YACC
« kdy: 20. 05. 2019, 10:14:14 »
Píšem si DSL pôvodne som parser chcel napísať ručne, ale jazyk už začína mať zložitú sémantiku a tým pádom je dosť zložitý aj parser. Takže som sa rozhodol že parser prepíšem a využijem nástroj Yacc resp (resp FsYacc) (lexer mám hotový takže nástroj lex nepotrebujem). S Yacc nemám s skúsenosti učím sa len so zdrojákov na githube  (vygooglil som si niekolko jazykov ktoré používajú Yacc a snažím sa nimi inšpirovať).

1.) Ale nejde mi do hlavy jedna vec, ako z takého malého zdrojáčika kde dokopy nič nie je si dokáže Yacc vygenerovať kompletný parser? Vyzerá to až príliš jednoducho.

2.) A vedeli by ste mi doporučiť najkú literatúru a tvorbe programovacích jazykov? Može byť v Angličtine, Slovenčine, alebo aj Češtine. Ale nech je to napísané zrozumiteľne aj pre laikov. Ideálne papierová kniha alebo ebook ale môže byť aj odkaz na web. Síce to zvládnem aj bez literatúry, ale možno je dobré mať aj teoretické základy nech tomu človek rozumie do hĺbky.
« Poslední změna: 20. 05. 2019, 10:15:51 od fortran1986 »


Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:Utilita YACC
« Odpověď #1 kdy: 20. 05. 2019, 12:21:35 »
Základní teorie zde (Knuth): https://www.csee.umbc.edu/courses/331/fall16/01/resources/papers/Knuth67AG.pdf

Jinak by to ale chtělo více informací o té DSL, takto se radí těžko.

Re:Utilita YACC
« Odpověď #2 kdy: 20. 05. 2019, 14:03:46 »
Niklaus Wirth: Algoritmy a štruktúry údajov

Re:Utilita YACC
« Odpověď #3 kdy: 20. 05. 2019, 15:53:23 »
S větším záběrem, ale stejně krásná - Michael Sipser: Introduction to the Theory of Computation.

Případně jestli chceš nějakou větší teorii tak nějaká skripta (v češtině třeba https://is.muni.cz/elportal/estud/fi/js06/ib005/Formalni_jazyky_a_automaty_I.pdf, ale opět je to asi obsáhlejší a ukecanější, než potřebuješ).

Re:Utilita YACC
« Odpověď #4 kdy: 20. 05. 2019, 18:50:46 »
Jedna praktictejsi publikace vedle druhe.

Co hledas se nejspis jmenuje Dragon Book, aka Aho, et al.: Compilers: Principles, Techniques, and Tools.

Jinak spis nez Yacc doporucuju pouzivat ANTLR a sousivejici materialy (maji je na webu).


Ravise

  • ***
  • 113
    • Zobrazit profil
    • E-mail
Re:Utilita YACC
« Odpověď #5 kdy: 20. 05. 2019, 21:32:29 »
Sice dělá interpret, ale http://craftinginterpreters.com/ stojí za přečtení.

Re:Utilita YACC
« Odpověď #6 kdy: 21. 05. 2019, 13:09:21 »
...
Jinak spis nez Yacc doporucuju pouzivat ANTLR a sousivejici materialy (maji je na webu).

U nás jsme na ANTLR přešli komplet před cca dvěma lety. Jsou tam tři chytáky:

1. Je to LL. Pokud tazatel už má hotovou gramatiku ve verzi pro YACC (který je LALR), tak bude muset investovat trochu času do přepsání pro ANTLR. Pokud se jedná o hodně jednoduchý DSL, tak by té práce nemělo být hodně.

2. ANTLR má vlastní lexer. A nám se moc nepodařilo ho přesvědčit, aby ho nechtěl. Vzdali jsme to zejména proto, že jeho lexer je vlastně hodně silný. Napsat pravidla pro něj nakonec bylo docela triviální.

3. ANTLR není určen k tomu, aby překládal. Do gramatiky se nepíší instrukce o tom, co se má zapsat na výstup. Styl práce je v tom, že vám ANTLR parsuje vstup a vytváří parse tree. To můžete ihned procházet přes visitora nebo později přes listener. Je to trochu jiný styl práce než YACC, protože si musíte přímo napsat kód, který bude řešit "vstoupil jsem do terminálu WHILE, co s tím?"

Přijde mi, že to je docela dost odlišností od YACC. S ohledem na původní dotaz nejspíš až příliš.

Já přechodu na ANTLR nelituji, ale jednoduché to nebylo. Používáme to třebas na parsování PL/SQL - generuje nám to komplet dokumentaci včetně referencí odkud je co voláno, kde co z čeho čte, co mění a co zapisuje, syntax highlighted převod do HTML apod. Času a práce je v tom utopeno hodně, ale ANTLR v tom pomohl.

Re:Utilita YACC
« Odpověď #7 kdy: 22. 05. 2019, 11:38:25 »
Citace
1. Je to LL.

Realne to neni problem, obzvlast, kdyz clovek dela vlastni gramatiku.

Citace
2. ANTLR má vlastní lexer. A nám se moc nepodařilo ho přesvědčit, aby ho nechtěl

Toto je fakt divna vyhrada, nevidim zadny duvod, proc nechtit lexer s ANTLR.

Citace
ANTLR není určen k tomu, aby překládal. Do gramatiky se nepíší instrukce o tom, co se má zapsat na výstup.

Kdyz si do pravidel napises instrukce, co se maji zapsat na vystup, vygenerovany parser ti to zapise.

Ale...

Citace
Styl práce je v tom, že vám ANTLR parsuje vstup a vytváří parse tree.

Tento styl prace je mnohem lepsi. Jednak oddeluje proces parsovani a generovani vystupni kodu, takze se v tom clovek neutopi. A pri tvorbe jakehokoliv prekladace nebo interpretu je to vyhodnejsi vzit AST a s tim dale pracovat, protoze driv nebo pozdeji clovek narazi na to, ze je potreba udelat nejaka pomocna transformace nebo optimalizace a delat to primo v gramatice muze byt docela peklo.