Dvojznačná gramatika - Ambiguous grammar

v počítačová věda, an nejednoznačná gramatika je bezkontextová gramatika pro které existuje a tětiva které mohou mít více než jednu derivace úplně vlevo nebo analyzovat strom,^[1] zatímco jednoznačná gramatika je bezkontextová gramatika, pro kterou má každý platný řetězec jedinečný derivační nebo parsovací strom zcela vlevo. Mnoho jazyků připouští dvojznačné i jednoznačné gramatiky, zatímco některé jazyky přijímají pouze nejednoznačné gramatiky. Jakýkoli neprázdný jazyk připouští nejednoznačnou gramatiku tím, že přebírá jednoznačnou gramatiku a zavádí duplicitní pravidlo nebo synonymum (jediný jazyk bez dvojznačných gramatik je prázdný jazyk). Jazyk, který připouští pouze nejednoznačné gramatiky, se nazývá neodmyslitelně nejednoznačný jazyk a jsou ze své podstaty nejednoznačné bezkontextové jazyky. Deterministické bezkontextové gramatiky jsou vždy jednoznačné a jsou důležitou podtřídou jednoznačných gramatik; existují však nedeterministické jednoznačné gramatiky.

Pro počítač programovací jazyky, referenční gramatika je často nejednoznačná kvůli problémům jako houpající se jinde problém. Pokud jsou tyto nejasnosti obecně vyřešeny přidáním pravidel priority nebo jiných kontextové pravidla syntaktické analýzy, takže celková gramatika fráze je jednoznačná.^{[Citace je zapotřebí ]} Některé algoritmy syntaktické analýzy (například (Earley^[2] nebo GLR analyzátory) mohou generovat sady analyzovaných stromů (nebo "analyzovat lesy") z řetězců, které jsou syntakticky nejednoznačné.^[3]

Příklady

Banální jazyk

Nejjednodušším příkladem je následující dvojznačná gramatika pro triviální jazyk, která se skládá pouze z prázdného řetězce:

A → A | ε

… Což znamená, že produkce může být buď sama sebou, nebo prázdným řetězcem. Prázdný řetězec tedy má nejvíce vlevo derivace délky 1, 2, 3 a skutečně libovolné délky, v závislosti na tom, kolikrát se použije pravidlo A → A.

Tento jazyk má také jednoznačnou gramatiku, která se skládá z jediné výrobní pravidlo:

A → ε

… Což znamená, že jedinečná produkce může vytvořit pouze prázdný řetězec, který je jedinečným řetězcem v jazyce.

Stejným způsobem lze libovolnou gramatiku pro neprázdný jazyk vytvořit dvojznačně přidáním duplikátů.

Unární řetězec

The běžný jazyk unárních řetězců dané postavy, řekněme 'A' (regulární výraz A*), má jednoznačnou gramatiku:

A → aA | ε

… Ale má také dvojznačnou gramatiku:

A → aA | Aa | ε

To odpovídá produkci a pravo-asociativní strom (pro jednoznačnou gramatiku) nebo umožňující asociaci vlevo i vpravo. Toto je rozpracováno níže.

Sčítání a odčítání

The bezkontextová gramatika

A → A + A | A - A | A

je nejednoznačný, protože pro řetězec a + a + a existují dvě derivace zcela vlevo:

Jako další příklad je gramatika nejednoznačná, protože existují dvě analyzovat stromy pro řetězec a + a - a:

Jazyk, který generuje, však není ve své podstatě nejednoznačný; toto je nejednoznačná gramatika generující stejný jazyk:

A → A + a | A - a | A

Visící jinde

Běžným příkladem nejednoznačnosti v programovacích jazycích počítačů je houpající se jinde problém. V mnoha jazycích jiný v Jestliže pak jinak) prohlášení je volitelné, což má za následek vnořené podmínky mít více způsobů uznání, pokud jde o bezkontextovou gramatiku.

Konkrétně lze v mnoha jazycích psát podmíněné výrazy ve dvou platných formách: forma if-then a forma if-then-else - ve skutečnosti je klauzule else volitelná:^{[poznámka 1]}

V gramatice obsahující pravidla

Prohlášení → -li Stav pak Prohlášení | -li Stav pak Prohlášení jiný Prohlášení | ... Stav → ...

mohou se objevit některé nejednoznačné struktury frází. Výraz

-li A pak -li b pak s jiný s2

lze analyzovat jako buď

-li A pak začít -li b pak s konec jiný s2

nebo jako

-li A pak začít -li b pak s jiný s2 konec

podle toho, zda jiný je spojen s prvním -li nebo druhý -li.

To se řeší různými způsoby v různých jazycích. Někdy je gramatika upravena tak, aby byla jednoznačná, například vyžadováním znaku endif prohlášení nebo tvorba jiný povinné. V ostatních případech je gramatika ponechána nejednoznačná, ale nejednoznačnost je vyřešena tím, že je celková fráze gramatická kontextově citlivá, například přidružením jiný s nejbližšími -li. V tomto druhém případě je gramatika jednoznačná, ale bezkontextová gramatika je nejednoznačná.^{[je zapotřebí objasnění ]}

Jednoznačná gramatika s více derivacemi

Existence více derivací stejného řetězce nestačí k označení nejednoznačnosti gramatiky; pouze několikanásobné úplně vlevo derivace (nebo ekvivalentně více analyzovaných stromů) označují nejednoznačnost.

Například jednoduchá gramatika

S → A + AA → 0 | 1

je jednoznačná gramatika pro jazyk {0 + 0, 0 + 1, 1 + 0, 1 + 1}. Zatímco každý z těchto čtyř řetězců má pouze jednu levou derivaci, má například dvě různé derivace

S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0

a

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

Pouze dřívější derivace je úplně vlevo.

Rozpoznávání nejednoznačných gramatik

The rozhodovací problém zda je libovolná gramatika nejednoznačná, je nerozhodnutelný protože lze prokázat, že je ekvivalentní s Problém s korespondencí.^[4] Přinejmenším existují nástroje, které některé implementují polorozhodovací postup pro detekci nejednoznačnosti bezkontextových gramatik.^[5]

Efektivitu bezkontextové syntaktické analýzy gramatiky určuje automat, který ji přijímá. Deterministické bezkontextové gramatiky jsou přijímány deterministické posunovací automaty a lze je analyzovat v lineárním čase, například pomocí Analyzátor LR.^[6] Toto je podmnožina souboru bezkontextové gramatiky které jsou přijímány zasunovací automat a lze je analyzovat v polynomiálním čase, například pomocí Algoritmus CYK. Jednoznačné bezkontextové gramatiky mohou být nedeterministické.

Například jazyk sudé délky palindromy na abecedě 0 a 1 má jednoznačnou bezkontextovou gramatiku S → 0S0 | 1S1 | ε. Libovolný řetězec tohoto jazyka nelze analyzovat, aniž byste nejdříve přečetli všechna jeho písmena, což znamená, že automat pro posun musí vyzkoušet alternativní přechody stavu, aby vyhověl různým možným délkám částečně rozebraného řetězce.^[7] Odebrání dvojznačnosti gramatiky však může způsobit deterministickou bezkontextovou gramatiku, a tak umožnit efektivnější analýzu. Generátory kompilátorů, jako jsou YACC zahrnout funkce pro řešení některých druhů nejednoznačnosti, například pomocí omezení priority a asociativity.

Vrozeně nejednoznačné jazyky

Existence inherentně dvojznačných jazyků byla prokázána Parikhova věta v roce 1961 Rohit Parikh ve výzkumné zprávě MIT.^[8]

Zatímco některé bezkontextové jazyky (sada řetězců, které lze generovat gramatikou) mají dvojznačné i jednoznačné gramatiky, existují bezkontextové jazyky, pro které nemůže existovat jednoznačná bezkontextová gramatika. Příkladem neodmyslitelně nejednoznačného jazyka je sjednocení ${ displaystyle {a ^ {n} b ^ {m} c ^ {m} d ^ {n} | n, m> 0 }}$ s ${ displaystyle {a ^ {n} b ^ {n} c ^ {m} d ^ {m} | n, m> 0 }}$. Tato sada je bezkontextová, protože spojení dvou bezkontextových jazyků je vždy bezkontextové. Ale Hopcroft & Ullman (1979) prokázat, že neexistuje způsob, jak jednoznačně analyzovat řetězce v (bezkontextové) společné podmnožině ${ displaystyle {a ^ {n} b ^ {n} c ^ {n} d ^ {n} | n> 0 }}$.^[9]

Viz také

• Analyzátor GLR, typ syntaktického analyzátoru pro nejednoznačné a nedeterministické gramatiky
• Analyzátor grafů, další typ syntaktického analyzátoru pro nejednoznačné gramatiky
• Syntaktická nejednoznačnost

Reference

• Gross, Maurice (září 1964). "Vrozená nejednoznačnost minimálních lineárních gramatik". Informace a kontrola. Informace a kontrola. 7 (3): 366–368. doi:10.1016 / S0019-9958 (64) 90422-X.
• Michael, Harrison (1978). Úvod do teorie formálního jazyka. Addison-Wesley. ISBN  0201029553.
• Hopcroft, John E .; Ullman, Jeffrey D. (1979). Úvod do teorie automatů, jazyků a výpočtu (1. vyd.). Addison-Wesley.CS1 maint: ref = harv (odkaz)
• Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Úvod do teorie automatů, jazyků a výpočtu (2. vyd.). Addison Wesley. str.217.CS1 maint: ref = harv (odkaz)
• Brabrand, Claus; Giegerich, Robert; Møller, Anders (březen 2010). „Analýza nejednoznačnosti bezkontextových gramatik“. Věda o počítačovém programování. Elsevier. 75 (3): 176–191. CiteSeerX  10.1.1.86.3118. doi:10.1016 / j.scico.2009.11.002.CS1 maint: ref = harv (odkaz)

Poznámky

externí odkazy

• dk.brics.grammar - analyzátor nejednoznačnosti gramatiky.
• CFGAnalyzer - nástroj pro analýzu bezkontextových gramatik s ohledem na univerzálnost jazyka, nejednoznačnost a podobné vlastnosti.