Analýza - Parsing

Rozebrat , syntaktická analýza , nebo syntaktická analýza je proces analyzování řetězce ve symbolů , a to buď v přirozeném jazyce , programovacích jazyků a datových struktur , které odpovídají pravidlům o formální gramatiky . Termín parsování pochází z latinského pars ( orationis ), což znamená část (řeči) .

Termín má v různých odvětvích lingvistiky a informatiky mírně odlišné významy . Tradiční analýza vět je často prováděna jako metoda porozumění přesnému významu věty nebo slova, někdy pomocí zařízení, jako jsou větné diagramy . Obvykle zdůrazňuje důležitost gramatických děl, jako je podmět a přísudek .

V rámci výpočetní lingvistiky se tento termín používá k označení formální analýzy věty nebo jiného řetězce slov počítačem na její složky, což má za následek, že analyzační strom ukazuje jejich vzájemný syntaktický vztah, který může také obsahovat sémantické a další informace ( p-hodnoty ). Některé algoritmy analýzy mohou generovat syntaktický les nebo seznam stromů analýzy pro syntakticky nejednoznačný vstup.

Termín je také používán v psycholingvistice při popisu porozumění jazyku. V této souvislosti analýza odkazuje na způsob, jakým lidské bytosti analyzují větu nebo frázi (v mluveném jazyce nebo textu) „z hlediska gramatických složek, identifikace částí řeči, syntaktických vztahů atd.“ Tento termín je obzvláště běžný při diskusích o tom, jaké jazykové narážky pomáhají reproduktorům interpretovat věty na zahradní cestě .

V rámci počítačové vědy se tento termín používá při analýze počítačových jazyků s odkazem na syntaktickou analýzu vstupního kódu do jeho jednotlivých částí, aby se usnadnilo psaní překladačů a tlumočníků . Termín může být také použit k popisu rozdělení nebo oddělení.

Lidské jazyky

Tradiční metody

Tradiční gramatické cvičení analýzy, někdy známé jako analýza klauzulí , zahrnuje rozdělení textu na jednotlivé části řeči s vysvětlením formy, funkce a syntaktického vztahu každé části. To je do značné míry určeno studiem konjugací a skloňování jazyka , což může být pro silně skloňované jazyky poměrně složité . Analyzovat frázi, jako je „člověk kousne psa“, vyžaduje poznamenat, že jednotné podstatné jméno „muž“ je předmětem věty, sloveso „kousne“ je třetí osoba jednotného čísla přítomného času slovesa „kousat“ a jednotné podstatné jméno 'pes' je předmětem věty. K označení vztahu mezi prvky ve větě se někdy používají techniky jako větné diagramy .

Analýza byla dříve ústředním bodem výuky gramatiky v celém anglicky mluvícím světě a byla široce považována za základní pro používání a porozumění spisovného jazyka. Obecná výuka těchto technik však již není aktuální.

Výpočtové metody

V některých systémech strojového překladu a zpracování přirozeného jazyka jsou psané texty v lidských jazycích analyzovány počítačovými programy. Lidské věty nejsou snadno analyzovány programy, protože existuje značná nejednoznačnost ve struktuře lidského jazyka, jehož použitím je zprostředkovat význam (nebo sémantiku ) mezi potenciálně neomezenou škálou možností, ale jen některé z nich jsou pro konkrétní případ klíčové. Takže výpověď „Člověk kouše psa“ versus „Pes kouše člověka“ je v jednom detailu jednoznačná, ale v jiném jazyce se může jevit jako „Člověk kouše psa“ se spoléháním na širší kontext k rozlišení mezi těmito dvěma možnostmi, pokud by ten rozdíl skutečně byl znepokojení. Je těžké připravit formální pravidla k popisu neformálního chování, i když je zřejmé, že některá pravidla jsou dodržována.

Aby mohli vědci analyzovat data v přirozeném jazyce, musí se nejprve dohodnout na gramatice , kterou mají používat. Volba syntaxe je ovlivněna jak lingvistickými, tak výpočetními problémy; například některé systémy analýzy používají lexikální funkční gramatiku , ale obecně je známo, že analýza pro gramatiky tohoto typu je NP-úplná . Gramatika struktury frází řízená hlavou je dalším lingvistickým formalismem, který byl populární v komunitě analyzujících, ale další výzkumné úsilí se zaměřilo na méně složité formalismy, jako je ten, který se používá v Penn Treebank . Mělká analýza má za cíl najít pouze hranice hlavních složek, jako jsou fráze podstatných jmen. Další populární strategií, jak se vyhnout lingvistickým kontroverzím, je analýza gramatiky závislostí .

Většina moderních analyzátorů je alespoň částečně statistická ; to znamená, že se spoléhají na soubor tréninkových dat, který již byl anotován (analyzován ručně). Tento přístup umožňuje systému shromažďovat informace o frekvenci, s jakou se v konkrétních kontextech vyskytují různé konstrukce. (Viz strojové učení .) Přístupy, které byly použity, zahrnují přímočaré PCFG (pravděpodobnostní bezkontextové gramatiky), maximální entropii a neurální sítě . Většina úspěšnějších systémů používá lexikální statistiky (to znamená, že berou v úvahu identitu příslušných slov a také jejich část řeči ). Takové systémy jsou však náchylné k nadměrnému vybavení a vyžadují určitý druh vyhlazení, aby byly účinné.

Algoritmy analýzy pro přirozený jazyk se nemohou spoléhat na to, že gramatika má „pěkné“ vlastnosti jako u ručně navržených gramatik pro programovací jazyky. Jak již bylo zmíněno dříve, některé gramatické formalismy je velmi obtížné analyzovat výpočetně; obecně, i když požadovaná struktura není bezkontextová , k provedení prvního průchodu se používá nějaký druh bezkontextové aproximace gramatiky. Algoritmy, které používají bezkontextové gramatiky, se často spoléhají na nějakou variantu algoritmu CYK , obvykle s nějakou heuristikou, která odstraní nepravděpodobné analýzy, aby ušetřila čas. (Viz analýza grafu .) Některé systémy však obchodují s rychlostí kvůli přesnosti, například pomocí algoritmů pro redukci posunu v lineárním čase . Poněkud nedávným vývojem bylo opětovné vyhodnocení analýzy, ve kterém analyzátor navrhuje velké množství analýz a složitější systém vybere nejlepší možnost. Sémantické analyzátory převádějí texty na reprezentace jejich významů.

Psycholingvistika

V psycholingvistice analýza nezahrnuje pouze přiřazování slov do kategorií (vytváření ontologických vhledů), ale vyhodnocení významu věty podle pravidel syntaxe vyvozených závěry učiněnými z každého slova ve větě (známé jako konotace ) . K tomu obvykle dochází, když jsou slova slyšena nebo čtena. Psycholingvistické modely analýzy jsou tedy nutně inkrementální , což znamená, že při zpracování věty vytvářejí interpretaci, která je normálně vyjádřena jako částečná syntaktická struktura. Při interpretaci vět o zahradní cestě dochází k vytváření původně nesprávných struktur .

Analýza diskurzu

Analýza diskurzu zkoumá způsoby, jak analyzovat používání jazyka a sémiotické události. Přesvědčivý jazyk lze nazvat rétorikou .

Počítačové jazyky

Analyzátor

Parser je softwarová komponenta, která má vstupní data (často text) a vytvoří strukturu dat - často nějaký derivační strom , syntaktický strom nebo jiné hierarchické struktury, čímž strukturální reprezentaci vstupu, zatímco kontrola správnosti syntaxe. Analýze může předcházet další kroky nebo za ní mohou následovat, nebo je lze spojit do jednoho kroku. Analyzátoru často předchází samostatný lexikální analyzátor , který vytváří tokeny ze sekvence vstupních znaků; alternativně je lze kombinovat při analýze bez skeneru . Analyzátory mohou být naprogramovány ručně nebo mohou být generovány analyzátorem automaticky nebo poloautomaticky . Analýza je komplementární k šablonování , které produkuje formátovaný výstup. Ty mohou být použity na různé domény, ale často se objevují společně, jako například pár scanf / printf , nebo fáze (analyzování front -endu) a output (generování kódu back -endu) kompilátoru.

Vstupem do analyzátoru je často text v nějakém počítačovém jazyce , ale může to být také text v přirozeném jazyce nebo méně strukturovaná textová data. V takovém případě se obecně extrahují pouze určité části textu, a nikoli se sestavuje strom analýzy. Analyzátory sahají od velmi jednoduchých funkcí, jako je scanf , až po složité programy, jako je frontend kompilátoru C ++ nebo analyzátor HTML webového prohlížeče . Důležitá třída jednoduché analýzy se provádí pomocí regulárních výrazů , ve kterých skupina regulárních výrazů definuje regulární jazyk a modul regulárních výrazů automaticky generuje analyzátor pro tento jazyk, což umožňuje porovnávání vzorů a extrakci textu. V jiných kontextech jsou namísto analýzy použity regulární výrazy jako krok lexingu, jehož výstup pak použije analyzátor.

Použití analyzátorů se liší podle vstupu. V případě datových jazyků se analyzátor často nachází jako nástroj pro čtení souborů v programu, jako je čtení v textu HTML nebo XML ; tyto příklady jsou značkovací jazyky . V případě programovacích jazyků , je parser je složkou kompilátor nebo interpret , který analyzuje zdrojový kód o programovací jazyk vytvořit nějakou formu vnitřní reprezentace; analyzátor je klíčovým krokem ve frontendu kompilátoru . Programovací jazyky bývají specifikovány pomocí deterministické bezkontextové gramatiky, protože pro ně lze psát rychlé a efektivní analyzátory. U kompilátorů lze samotnou analýzu provést v jednom průchodu nebo ve více průchodech-viz jednoprůchodový kompilátor a víceprůchodový kompilátor .

Implicitní nevýhody jednoprůchodového kompilátoru lze do značné míry překonat přidáním oprav , kdy je zajištěno přemístění kódu během dopředného průchodu a opravy jsou aplikovány zpět, když byl aktuální programový segment rozpoznán jako dokončeno. Příkladem, kde by byl takový fixační mechanismus užitečný, by bylo dopředné prohlášení GOTO, kde je cíl GOTO neznámý, dokud není dokončen programový segment. V tomto případě bude aplikace opravy zpožděna, dokud nebude rozpoznán cíl GOTO. Naopak zpětné GOTO nevyžaduje opravu, protože umístění již bude známé.

Gramatiky bez kontextu jsou omezené v rozsahu, v jakém mohou vyjadřovat všechny požadavky jazyka. Neformálně je důvodem to, že paměť takového jazyka je omezená. Gramatika si nepamatuje přítomnost konstruktu přes libovolně dlouhý vstup; to je nezbytné pro jazyk, ve kterém musí být například jméno deklarováno, než na něj bude možné odkazovat. Výkonnější gramatiky, které mohou toto omezení vyjádřit, však nelze efektivně analyzovat. Je tedy běžnou strategií vytvořit uvolněný analyzátor bezkontextové gramatiky, který přijímá nadmnožinu požadovaných jazykových konstrukcí (to znamená, že přijímá některé neplatné konstrukty); později lze nežádoucí konstrukce odfiltrovat v kroku sémantické analýzy (kontextuální analýzy).

Například v Pythonu je syntakticky platný kód následující:

x = 1
print(x)

Následující kód je však syntakticky platný z hlediska bezkontextové gramatiky a poskytuje syntaktický strom se stejnou strukturou jako předchozí, ale je syntakticky neplatný z hlediska kontextově citlivé gramatiky , která vyžaduje, aby byly proměnné inicializovány před použití:

x = 1
print(y)

Spíše než aby byly analyzovány ve fázi analýzy, je to zachyceno kontrolou hodnot ve stromu syntaxe, tedy jako součást sémantické analýzy: kontextová syntaxe je v praxi často snadněji analyzována jako sémantika.

Přehled procesu

Následující příklad ukazuje běžný případ analýzy počítačového jazyka se dvěma úrovněmi gramatiky: lexikální a syntaktickou.

První fází je generování tokenů neboli lexikální analýza , pomocí které je tok vstupních znaků rozdělen na smysluplné symboly definované gramatikou regulárních výrazů . Například, kalkulačka program by se podívat na vstupu, jako například „ 12 * (3 + 4)^2“ a rozdělit ji do žetony 12, *, (, 3, +, 4, ), ^, 2, z nichž každá je smysluplný symbol v rámci aritmetického výrazu. Lexer by obsahoval pravidla říci to, že znaky *, +, ^, (a )označit začátek nového tokenu, takže nesmyslné žetonů jako „ 12*“ nebo „ (3“ nebude generován.

Další fází je analýza nebo syntaktická analýza, která kontroluje, zda tokeny tvoří přípustný výraz. To se obvykle provádí s odkazem na bezkontextovou gramatiku, která rekurzivně definuje komponenty, které mohou tvořit výraz, a pořadí, ve kterém se musí objevit. Ne všechna pravidla definující programovací jazyky však lze vyjádřit pouze bezkontextovými gramatikami, například platností typu a řádnou deklarací identifikátorů. Tato pravidla lze formálně vyjádřit pomocí atributových gramatik .

Poslední fází je sémantická analýza nebo analýza, která řeší důsledky právě validovaného výrazu a provede příslušnou akci. V případě kalkulačky nebo tlumočníka je úkolem vyhodnotit výraz nebo program; překladač by naopak generoval nějaký druh kódu. K definování těchto akcí lze také použít gramatiky atributů.

Typy analyzátorů

Úkolem parseru je v podstatě zjistit, zda a jak se vstup může být odvozena od symbolu zahájení gramatiky. To lze provést v zásadě dvěma způsoby:

• Analýza shora dolů -Analýzu shora dolů lze považovat za pokus o nalezení nejlevnějších derivací vstupního proudu vyhledáním stromů analýzy pomocí rozšíření shora dolů daných formálních gramatických pravidel. Žetony se spotřebovávají zleva doprava. Inkluzivní volba slouží k vyrovnání nejednoznačnosti rozšířením všech alternativních pravých stran gramatických pravidel. Toto je známé jako prvotní polévkový přístup. Prvotní polévka je velmi podobná větnému diagramu a rozděluje obvody vět.
• Analýza zdola nahoru - Analyzátor může začít se vstupem a pokusit se jej přepsat na počáteční symbol. Analyzátor se intuitivně pokusí vyhledat nejzákladnější prvky, pak prvky, které je obsahují, atd. Analyzátory LR jsou příklady analyzátorů zdola nahoru. Další termín používaný pro tento typ analyzátoru je Shift-Reduce parsing.

Analyzátory LL a analyzátor rekurzivního sestupu jsou příklady analyzátorů shora dolů, které nemohou vyhovět pravidlům rekurzivní produkce vlevo . Ačkoli se věřilo, že jednoduché implementace analýzy shora dolů nemohou pojmout přímou a nepřímou levou rekurzi a mohou vyžadovat exponenciální časovou a prostorovou složitost při analýze nejednoznačných bezkontextových gramatik , Frost vytvořil sofistikovanější algoritmy pro analýzu shora dolů , Hafiz a Callaghan, které pojímají nejednoznačnost a levou rekurzi v polynomiálním čase a které generují reprezentace potenciálně exponenciálního počtu parse stromů v polynomiální velikosti. Jejich algoritmus je schopen produkovat jak levou, tak pravou derivaci vstupu s ohledem na danou bezkontextovou gramatiku .

Důležitým rozdílem s ohledem na analyzátory je, zda analyzátor generuje derivaci úplně vlevo nebo derivaci zcela vpravo (viz gramatika bez kontextu ). Analyzátory LL generují derivaci zcela vlevo a analyzátory LR generují derivaci zcela vpravo (i když obvykle obráceně).

Nějaký algoritmy grafické analýzy byly navrženy provizuální programovací jazyky. Analyzátory vizuálních jazyků jsou někdy založeny nagrafických gramatikách.

Algoritmy adaptivní analýzy byly použity ke konstrukci "samorozšiřujících" uživatelských rozhraní v přirozeném jazyce .

Software pro vývoj analyzátoru

Některé z dobře známých nástrojů pro vývoj analyzátoru zahrnují následující:

Dívat se dopředu

Program C, který nelze analyzovat na méně než 2 vyhledávací hlavy tokenů. Nahoru: Výňatek z gramatiky C. Dole: parser se rozštěpí tokeny „ “ a je asi zvolit pravidlo odvodit stmt . Když se podíváme pouze na první token „lookahead“ „ “, nemůže se rozhodnout, kterou z obou alternativ pro Stmt zvolit; ten druhý vyžaduje nahlédnutí do druhého tokenu.int v;main(){v

Lookahead stanoví maximální počet příchozích tokenů, které může analyzátor použít k rozhodnutí, které pravidlo by měl použít. Lookahead je zvláště relevantní pro analyzátory LL , LR a LALR , kde je často výslovně označen připojením hledací hlavy k názvu algoritmu v závorkách, jako je LALR (1).

Většina programovacích jazyků , primární cíl analyzátorů, je pečlivě definována takovým způsobem, že je může analyzovat analyzátor s omezeným hledáním, obvykle jeden, protože analyzátory s omezeným hledáním jsou často efektivnější. Jedna důležitá změna tohoto trendu přišla v roce 1990, kdy Terence Parr vytvořil ANTLR pro své Ph.D. práce, generátor analyzátoru pro efektivní analyzátory LL ( k ), kde k je jakákoli pevná hodnota.

Analyzátory LR obvykle mají po zobrazení každého tokenu jen několik akcí. Jsou to shift (přidejte tento token do zásobníku pro pozdější redukci), snížení (pop tokeny ze zásobníku a vytvoří syntaktický konstrukt), konec, chyba (neplatí žádné známé pravidlo) nebo konflikt (neví, zda se má posunout nebo zmenšit) .

Lookahead má dvě výhody.

• Pomáhá analyzátoru provést správnou akci v případě konfliktů. Například rozebrání příkazu if v případě klauzule else.
• Eliminuje mnoho duplicitních stavů a ​​snižuje zátěž dalšího zásobníku. Analyzátor non-lookahead jazyka AC bude mít přibližně 10 000 států. Analyzátor hledáčku bude mít přibližně 300 států.

Příklad: Analýza výrazu 1 + 2 * 3

Většina programovacích jazyků (kromě několika takových, jako je APL a Smalltalk) a algebraické vzorce dávají větší přednost násobení než sčítání, v takovém případě je správná interpretace výše uvedeného příkladu 1 + (2 * 3) . Všimněte si, že pravidlo 4 výše je sémantické pravidlo. Je možné přepsat gramatiku a začlenit ji do syntaxe. Ne všechna taková pravidla však lze přeložit do syntaxe.

Jednoduché akce analyzátoru bez vyhledávání

Původně vstup = [1, +, 2, *, 3]

1. Posuňte „1“ na zásobník ze vstupu (v očekávání pravidla 3). Vstup = [+, 2, *, 3] Zásobník = [1]
2. Redukuje "1" na výraz "E" na základě pravidla3. Zásobník = [E]
3. Shift "+" na zásobník ze vstupu (v očekávání pravidla1). Vstup = [2, *, 3] Zásobník = [E, +]
4. Shift "2" na stack ze vstupu (v očekávání pravidla3). Vstup = [*, 3] Zásobník = [E, +, 2]
5. Zmenšete prvek zásobníku „2“ na výraz „E“ na základě pravidla 3. Zásobník = [E, +, E]
6. Snižte položky zásobníku [E, +, E] a nový vstup "E" na "E" na základě pravidla1. Zásobník = [E]
7. Shift "*" do zásobníku ze vstupu (v očekávání pravidla2). Vstup = [3] Zásobník = [E,*]
8. Shift "3" na stack ze vstupu (v očekávání pravidla3). Vstup = [] (prázdný) Zásobník = [E, *, 3]
9. Zmenšete prvek zásobníku „3“ na výraz „E“ na základě pravidla3. Zásobník = [E, *, E]
10. Snižte položky zásobníku [E, *, E] a nový vstup "E" na "E" na základě pravidla2. Zásobník = [E]

Analyzovat strom a výsledný kód z něj není správný podle sémantiky jazyka.

Chcete -li správně analyzovat bez vyhledávání, existují tři řešení:

• Uživatel musí uzavřít výrazy do závorek. Toto často není schůdné řešení.
• Analyzátor musí mít více logiky pro zpětné sledování a opakování, kdykoli je pravidlo porušeno nebo není dokončeno. Podobná metoda se používá v analyzátorech LL.
• Alternativně musí analyzátor nebo gramatika mít dodatečnou logiku pro zpoždění redukce a redukce pouze tehdy, když si je naprosto jistý, které pravidlo redukovat jako první. Tato metoda se používá v analyzátorech LR. To správně analyzuje výraz, ale s mnoha dalšími stavy a zvýšenou hloubkou zásobníku.

Akce analyzátoru Lookahead

1. Posuňte 1 na zásobník na vstupu 1 v očekávání pravidla 3. Nesnižuje se okamžitě.
2. Snižte položku zásobníku 1 na jednoduchý výraz na vstupu + na základě pravidla3. Lookahead je +, takže jsme na cestě k E +, takže můžeme zmenšit stack na E.
3. Shift + na stack na vstupu + v očekávání pravidla1.
4. Posuňte 2 na zásobník na vstupu 2 v očekávání pravidla 3.
5. Snižte položku zásobníku 2 na výraz na vstupu * na základě pravidla3. Lookahead * očekává pouze E před ním.
6. Nyní má zásobník E + E a stále je vstup *. Nyní má dvě možnosti, buď k posunu na základě pravidla2, nebo snížení na základě pravidla1. Protože * má vyšší prioritu než + na základě pravidla4, přesouváme * na zásobník v očekávání pravidla2.
7. Posuňte 3 na zásobník na vstupu 3 v očekávání pravidla 3.
8. Poté, co uvidíte konec vstupu na základě pravidla 3, zredukujte položku zásobníku 3 na výraz.
9. Zmenšete hromádkové položky E * E na E na základě pravidla2.
10. Zmenšete položky zásobníku E + E na E podle pravidla 1.

Generovaný strom analýzy je správný a jednoduše efektivnější než analyzátory bez vyhledávání. Toto je strategie používaná v analyzátorech LALR .

Viz také

Reference

21. HTML kódy zdarma analyzovat [1]

Další čtení

externí odkazy

• Generátor analyzátoru Lemon LALR
• Stanfordský analyzátor Stanfordský analyzátor
• Analyzátor Turínské univerzity Analyzátor přirozeného jazyka pro italštinu, otevřený zdroj, vyvinutý v Common Lisp Leonardem Lesmem, University of Torino, Itálie.
• Krátká historie konstrukce analyzátoru