Frázové a abstraktní syntaktické stromy

Mluví se jen o jazycích odvozených z Fotranu, hádám? Nebo jsou obecně programovací jazyky podmnožinou formálních jazyků (ve Forthu, Common Lisp a i třeba TeX umožňují měnit co se jak lexikálně zpracuje)? Co je frázový a abstraktní strom třeba u Forthu? Je abstraktním stromem u Common Lispu míněn načtený sexp? Ten zdá se závisí na sémantice - např. hash-dot.

Když matení jazyků, tak pořádně! :)

hmmm, nerozumel som ani pol slova :-)

@1 Každý algoritmus lze vyjádřit formální gramatikou, jež definuje nějaký formální jazyk. Pro parsing prog. jazyků se obvykle používá bezkontextová gramatika. Forth bohužel moc neznám. U Lispu je situace velmi jednoduchá, AST je prostě seznam.

@2 Netvrdím, že problematika je triviální. Na studiích u zkoušky na tom spousta studentů vyletí :-)

Triviální to IMHO je. Akorát jsem nikdy neslyšel výraz "frázový syntaktický strom", já bych mu řekl "parsovací strom" :-)

@1 Ono to ani u jazyku odvozenych od Fortranu neni tak jednoduche. Uz treba s takovym c++ mate problem. Obecne se tomu rika "context sensitive lexer".
Nekde na netu muzete najit vyjadreni od Stroudapa proc nemuze v emacsu nikdy spravne fungovat auto-indent pro c++. Treba abyste mohl poznat co znamena "a " tak si musite behem parsovani urzovat nejakou symbol table a musite vedet jestli je "a" sablona, typ anebo promenna. Pokud lexer do parseru vrati, ze "a" je identifier tak to nestaci.

U DSL jazyku kde se hledi na zpetnou kompatibilitu je nejcastejsi problem, ze slovo muze mit specialni(reserved) vyznam, ale zaroven ale muze byt identifikatorem.

@6 v jiných editorech funguje celkem obstojně. Eclipse dokonce pozná, co je identifikátor, jakého typu a co je sablona a tak. Málokdy se v kódu nevyzná.

@1 Mluví se o jazycích, jenž mají oddělenu statickou a dynamickou fázi zpracování. A právě statická fáze se typicky skládá z parsování a typové kontroly.

@3: Mám na mysli třeba tohle v Common Lispu:

#.(compute-something-at-read-time) - ve fázi čtení (reader podle normy jazyka, odpovídá parseru podle terminologie blogu) výsledek závisí na tom, co aktuálně dělá funkce compute-something-at-read-time. Odpovídá příslušnému frázovému stromu pouze jeden abstraktní strom, když funkce vrací třeba aktuální čas?

Nebo, budu-li brutální,
(hello) ; -> (hello)
(eval-when (:compile-toplevel :load-toplevel)
(set-syntax-from-char #\l #\Space))
(hello)) ; -> (he o)

Jakou formální gramatikou bez včleněné sémantiky jazyka se popíše, kdy se l má brát jako mezera a kdy jako písmeno?

@3: "Forth bohužel moc neznám."

Chyba! (U nekoho, kdo se zabyva navrhem jazyku.) Vrele doporucuji http://sourceforge.net/projects/rpoku/files/jonesforth/

Zabere to 2 odpoledne precist a osviti to.

@9 Víc jak jeden AST frázovému stromu nikdy neodpovídá.

@11 Jednak nechápu proč by tohle mělo platit? A dále nechápu, jak to souvisí s @9?

@12 Plyne to přímo z definice a je to odpověď na otázku @9.

@8: To je ono, presne. Coz s jistou davkou nadsazky bych si dovolil nazvat "odvozene od Fortranu". Pokud se nekdo "zabývá vývojem kompilátorů a knihoven pro objektově-orientované programovací jazyky", mel by imho znat omezeni ktera implicitne prijima.

@14 Jak název napovídá, AST je syntaktická struktura, se sémantikou nemá nic společného, ani s konkrétním jazykem. Takže AST v Lispu je seznam seznamů atd. Doporučuju nastudovat si teorii grafů a formálních jazyků. O sémantice třeba někdy příště.

@15: Moje rypani se netyka AST samotneho, ale cesty od zdrojoveho textu k AST a jeji jednoznacnosti.

Dost mozna ze je problem v mem nechapani definic vyrazu (ktere zde explitne nevidim, a google na frazovy strom vcelku mlci).

Da se to ukazat co je co na dvou trivialnich prikladech v ramci stareho dobreho Ccka (s preprocesorem), treba se mi to pouzita termnilogie objasni?
Pokud je na vstupu 1+__LINE__, co je v tomto pripade frazovy strom (a zejmena obsahuje token __LINE__, nebo cislo radku?), a co je AST ke kompilaci? (u vyse uvadenych jazyku je rizeni preprocesoru soucasti jazyka, pokud je problem s tim ze by preprocesor a jazyk mely byt oddelene)

A pokud vstup nasledujici?
--
#define b +
a b c
--

@13 Můžete prosím ještě napsat definici AST, případně naznačit, jak funguje automatický převod z frázového stromu na abstraktní strom.

@17 Definice AST přímo plyne z toho převodu. Ten se definuje tak, že ve frázovém stromě dojde ke kontrakci hran mezi vrcholem reprezentovaným hlavou aplikovaného pravidla a výsledným neterminálem. Po kontrakci všech takových hran dostaneme AST a z postupu přímo plyne, že různé frázové stromy mohou dát stejný AST (u jednoznačné gramatiky to je ovšem 1:1). Ono se to asi lépe vysvětluje na přirozeném jazyce, klasický příklad Chomského s neterminály S, N, V, NP, VP, Det má např. pravidlo VP -> V NP, u kterého je hlavou V. Proto ve frázovém stromě kontrahujeme hranu mezi V a VP (V je preterminál a ten by se měl ještě kontrahovat s odpovídajícím listem). Podobně u pravidla S -> NP VP je hlavou VP a kontrahuje se tedy hrana mezi S a VP. Nakonec tedy dostaneme strom, jehož vrcholy jsou ohodnoceny původními listy a hrany mezi nimi představují závislosti (např. u prog. jazyka ve výrazu sčítání závisí operandy na vrcholu ohodnoceném operátorem, jenž je hlavou příslušného pravidla). Celý tento proces je nezávislý na konkrétním jazyce, k dalším transformacím už dochází s přihlédnutím k sémantice.

@16 Viz definice v @18. Prepocesor __LINE__ nahradí číslem, takže jak frázový strom, tak AST obsahují ono číslo. Jenže zatímco ve frázovém stromě jsou + a operand na stejné úrovni (ve stejné hloubce stromu), v AST je mezi + a operandem hrana.

Ok, asi vyjasneno - pokud je frazovym stromem mysleno neco uz takhle tesne pred AST, tak pak se jedna opravdu o trivialni operaci. Nepochopil jsem to nejspis proto, ze parsery ktere jsem videl snad ani frazovy strom v tomto smyslu explicitne netvori, pripadne je to jen jiny pohled na datovou strukturu reprezentujici AST. Pak opravdu asi plati vetsina veci v blogu, ale na druhou stranu cesta od vstupnich tokenu (a za vstupni token pro C pokladam v uvedenem pripade porad __LINE__) k nemu je potom obecne vyrazne zajimavejsi.

A pokud tedy prechazime k prirozenemu jazyku - tady mi zase tou vyrazne zajimavejsi casti parsovani prijdou viceznacnosti a jejich reseni at uz na urovni urceni typu literalu (time flies like an arrow) nebo na urovni "zavorkovani" - coz predpokladam v modelu vyse opet dela cast mezi tokenizaci a frazovym grafem (grafy?) zajimavejsi.

Za navrh nastudovat si teorii grafu a formalnich jazyku dekuji, ale kdysi jsem je uz zahledl, a jako mnoho jinych veci mi pripadaji jako sada nastroju, ze ktery je kazdy (napriklad context-free gramatiky) v nekterych pripadech uzitecny a v jinych mene, a je dobre vedet ktery pripad je ktery.

@18 Díky.

A když jazyk nemá smysluplnou bezkontextovou gramatiku, znamená to, že AST neexistuje (to je mj. případ i Common Lispu)?

@21 Úplně každý (rekurzivně spočetný) jazyk má gramatiku. I když není bezkontextová, vždy existuje AST.

@20 Ono to není těsně, pokud si nakreslíte ony stromy pro různé vstupy, dost se liší. Zajímavé je probrat si případy, kdy více frázových stromů produkuje jeden AST. Rozhodně nejsou jiným pohledem na AST, není tam relace 1:1.
Explicitní frázové stromy se používají v nástrojích (SableCC, ANTLR...) při treewalkingu. Stejně tak v podstatě každý transpiler používá frázový strom. Explicitně jsou vždy při parsingu v paměti, buď někde na zásobníku (u zásobníkového automatu), nebo v rámci chartu (když se použije chart parser).
Cesta od seznamu tokenů z lex. analýzy k frázovému stromu je triviální, je to jen jeden krok a dělá jej za nás plně automaticky gramatika - nic mimo samotnou gramatiku nelze parametrizovat, modifikovat apod. To se dělá až s AST.

U přirozených jazyků syntax víceznačnosti neřeší. Buď je někde WSD (word sense disambiguation), nebo nějaký jazykový model nad sémantikou. Také tam není žádný AST, buď se parsuje do závislostních stromů (většinou ne přes bezprostřední složky, ale jde to), nebo se používá bezkontextová gramatika a k ní paralelní datová struktura (pak je výsledkem parsingu frázový strom a odpovídající struktura, která např. v LFG dost připomíná AST, akorát to není strom, protože může obsahovat cykly).

@22 A jak vypadají frázové stromy u gramatik typu 0 - například by mě zajímal strom, kde se použije pravidlo A B C D -> X Y, kde A, B, C, D, X, Y jsou neterminály?

@24 Já jsem ale neřekl, že existuje frázový strom. Mluvil jsem o AST. U gramatik typu 0 máte chart (frázové stromy jsou speciálním případem chartu). Ten se dá reprezentovat dvourozměrnou maticí.

@25 AST jste definoval převodem z frázového stromu, tudíž AST není definováno, pokud nemáme frázový strom.

@26 Jistě, to jsme se bavili o bezkontextových gramatikách. Tak teď si jej odvoďte z chartu, postup se nemění.

@27 Teď ještě nevím, jak ten chart (doufám, že se bavíme o struktuře, jenž se používá v metodě chart parsing pro bezkontextové gramatiky?) použít pro zachycení derivace z gramatik typu 0. Jak se do toho zachytí pravidla s kontextem?

@28 Ano, a chart parsing není jen pro bezkontextové. Pravidla s kontextem (typ 1) se zachytí stejně jako bez kontextu, vlevo je jen jeden neterminál. U typu 0 je v chartu celá sekvence z levé strany pravidla. Proto tam taky není frázový strom, ale nějaký obecný graf s cykly.

@29 Díky za odpovědi, teď si to budu muset trochu promyslet.

@23: Taky diky za odpoved a budu se muset zamyslet. Mozna na to koukam moc z pozice prakticke realizace veci ktere jsem videl a me zajimaji a ne z pohledu abstrakce.

Pokud mam frazovy strom jako strukturu ulozenou v pameti, tak veci jako kontrakce hran mi prijdou ze se daji provadet ciste zmenou pohledu na tu strukturu, ve stejnem smyslu jako jedna struktura muze byt videna jako seznam, strom, binarni strom, cons, mnozina, property list nebo jine veci - a tudiz reprezentaci frazoveho stromu se mi zda ze je i reprezentace AST, byt nemusi byt optimalni ani unikatni.

Trivialita presunu od __LINE__ k cislu ve frazovem stromu v ramci gramatiky mi stale neni zrejma.

Predpokladam ze ani u programovacich jazyku se netrva na AST coby stromu - minimalne DAG, v nekterych pripadech i cykly (byt to nemusi byt platny program, ale interpretovat a nekdy kompilovat muze jit).

@31 >Trivialita presunu od __LINE__ k cislu ve frazovem stromu v ramci gramatiky mi stale neni zrejma.
To je jednoduchy ty gramatiky jsou dve. Preprocessor ma svou a kompilator ma taky svoji. Kazdy dela neco jineho. Zajimavejsi by byl priklad s __FUNCTION__

@31 Existují i jiné definice AST - viz třeba 1. kapitola Practical Foundations for Programming Languages od Roberta Harpera (http://www.cs.cmu.edu/~rwh/plbook/book.pdf) - uvedená definice vůbec nezávisí na syntaxi jazyka, což je pro některé aplikace výhodnější.

@31 Výsledkem aplikace generativní gramatiky nikdy nemůže být DAG, vždy je to strom. Asi myslíte nějakou strukturu po sémantických konverzích, která se interpretuje nebo dále kompiluje. Už se opakuju, ale tato fáze nemá se syntaxí nic společného.

@33 Ale vždyť ty definice jsou shodné, jen v té knize je zúžena na prog. jazyky. Jak jsem uvedl v článku, hlavou pravidla je zpravidla operátor (což je i volání funkce). Máte-li bezkontextovou gramatiku a postupujete, jak jsem popsal, dostanete přesně strom z knihy, kde kořenem podstromů je operátor a jeho syny argumenty (operandy). U listů se jejich ohodnocení v knize říká "variables", předpokládám, že jsou myšleny všechny atomické hodnoty.
Ta definice z knihy je snadnější na pochopení, ale neříká nic o vztahu mezi frázemi (a v takto definovaném stromě pochopitelně fráze explicitně zachyceny nejsou).
U Lispu je to krásně vidět, tam je operátor vždy první prvek seznamu, takže AST tam větví doprava (a u frázového stromu se vždy kontrahuje hrana k prvnímu synovi).

@33 P.S. Pokud vás zajímají různé přístupy k syntaxi a synt. stromům, doporučuji články Ronalda Kaplana z Palo Alto Research Center (Xerox). PARC nám nedal jen (skrz Jobse) myš, GUI apod., ale i velice inovativní přístup k tvorbě a aplikaci gramatik.

@35 Já myslím, že právě ta Harperova definice je obecnější:

1) Jednomu frázovému stromu mohu přiřadit libovolné množství AST
2) Sorty, jenž používám, nemusí být rekurzivně spočetné množiny

Ad 1) Např. jeden operátor v AST mohu použít pro více operátorů v konkrétní syntaxi - operátor implikace v AST mohu použít i pro operátor implikace a operátor obrácené implikace v konkrétní syntaxi. Nebo do AST stromu mohu přidat další uzly. Ten Harperův AST může více abstrahovat od syntaxe.

Ad 2) Reálná čísla.

@35 Ještě k těm proměnným. Nepochopil jsem, co přesně myslíte tím všechny atomické hodnoty.

Proměnnou Harper myslí pojmenované volné místo, které má nějakou sortu a lze tam substituovat jiný AST. Například jazyk pro sčítání reálných čísel bude mít nulární operátor pro každé reálné číslo a jeden binární operátor pro sčítání. Bude tam jediná sorta výraz. Zápisem plus(1, x) rozumím příslušný AST a mohu například za x substituovat AST 3.5. Tím dostanu AST plus(1, 3.5), a pokud tomu jazyku přiřadím standardní dynamiku tak to redukuji na AST 4.5.

"Ten Harperův AST může více abstrahovat od syntaxe." AST je Abstract SYNTAX Tree. Jak může syntax abstrahovat od syntaxe? Jeho definice se sice nevztahuje explicitně ke gramatice, ale to co říkáte Vy, např. o konverzi operátorů, je další fáze zpracování za syntaxí. Jednomu frázovému stromu nikdy nemůže odpovídat více AST. Jistě, můžeme se bavit o stromech (nebo DAG), jež vzniknou nějakou sémantickou konverzí z AST, asi je to zajímavější, není to jen suchá teorie jako formální syntax. Jako téma k další diskuzi navrhuji např. rozdíl mezi povrchovou (surface) a hloubkovou syntaxí.

@39 "Jednomu frázovému stromu nikdy nemůže odpovídat více AST." Podle té Harperovy definice může - nic mi nebrání zvolit si libovolné zobrazení, kterým převedu frázový strom na AST. Myslím, že nejsem sám, kdo to takhle chápe - viz třeba slajd 122 v následující prezentaci http://www.par.univie.ac.at/~mehofer/teach/CC/semantic.pdf

Tou podivnou větou jsem chtěl říct, že ta Vaše definice AST v podstatě vůbec neabstrahuje od konkrétní syntaxe na rozdíl od té Harperovy definice. U Harpera můžu měnit konkrétní syntax a nechat si AST, což podle mě odpovídá významu slova "abstraktní".

@39 Když o tom tak přemýšlím, tak pokud mám gramatiku

Vyraz -> '(' Vyraz '+' Vyraz ')' | cislo

a zvolím hlavu '+' tak mi v AST, jak jste ho definoval, zůstanou i závorky, ne?

@1 Konkretne u Forthu by se ten strom obecne mohl menit s kazdym nove nadefinovanym slovem, takze to je z praktickeho hlediska nepouzitelne. Soucasne to je v praxi i zbytecne (postacuje rozsekat slova na zaklade bilych znaku a poslat je dat), teorie AST atd. se hodi spis na jazyky s nemennou syntaxi: Fortran->Algol->C(++)->Java atd.

(http://www.root.cz/serialy/programovaci-jazyk-forth/)