Nejednoznačná gramatika

Nejednoznačná gramatika v teorii formálních jazyků je taková bezkontextová gramatika, která generuje (aspoň jednu) nejednoznačnou větu. Nejednoznačná věta je taková věta, pro kterou existují nejméně dva různé derivační stromy. Pokud každá z vět generovaných gramatikou má jediný derivační strom, je gramatika jednoznačná.

Nejednoznačný jazyk je jazyk, pro které neexistuje žádná jednoznačná gramatika.

Aby se předešlo problémům s porovnáváním derivačních stromů používá se také definice, že nejednoznačná gramatika je bezkontextová gramatika, v níž existuje věta, který má více než jednu levou derivaci, zatímco jednoznačná gramatika je bezkontextová gramatika, jejíž každá větu má jednoznačnou levou derivaci.

Problém zjišťování nejednoznačnosti gramatiky je pro obecné bezkontextové gramatiky algoritmicky nerozhodnutelný.

Vztah jednoznačných gramatik a jazyků

Pro mnoho jazyků existují nejednoznačné i jednoznačné gramatiky, ale pro některé jazyky existují pouze nejednoznačné gramatiky. Pro jakýkoli neprázdný jazyk lze sestrojit nejednoznačnou gramatiku z jednoznačné gramatiky přidáním duplicitních pravidel nebo synonym (jediný jazyk bez nejednoznačné gramatiky je prázdný jazyk). +more Jazyk, který připouští pouze nejednoznačné gramatiky, se nazývá #Jazyky z podstaty nejednoznačné|z podstaty nejednoznačný jazyk, a z podstaty nejednoznačný bezkontextové jazyky existují. Deterministické bezkontextové gramatiky jsou vždy jednoznačné a jsou důležitou podtřídou jednoznačných bezkontextových gramatik; existují však i nedeterministické jednoznačné bezkontextové gramatiky.

Pro skutečné programovací jazyky je referenční bezkontextová gramatika často nejednoznačná, kvůli problémům jako je #Nepovinné else|nepovinné else. Jsou-li takovéto nejednoznačnosti přítomny, jsou zpravidla řešeny přidáním precedenčních pravidel nebo jiných kontextových pravidel tak, aby výsledná frázová gramatika byla jednoznačná.

Příklady

Triviální jazyk

Nejjednodušším příkladem nejednoznačné gramatiky je následující gramatika triviálního jazyka, který sestává pouze z prázdného řetězce: :S → A | B :A → ε :B → ε …což znamená, že prázdný řetězec ε může být vytvořen libovolným ze dvou ekvivalentních pravidel a tedy má dvě levé derivace.

Další nejednoznačná gramatika pro triviální jazyk je: :A → A | ε …což znamená, že symbol A se přepíše buď na sebe sama nebo na prázdný řetězec. Pro prázdný řetězec tedy existují levé derivace délky 1, 2, 3, … Podle toho, kolikrát se použije pravidlo A → A, může mít derivace libovolnou délku.

Tento jazyk má i jednoznačnou gramatiku, obsahující pouze jedno přepisovací pravidlo: :A → ε …což znamená, že jednoznačné přepisovací pravidlo může produkovat pouze prázdný řetězec, což je jednoznačný řetězec v jazyce.

Stejným způsobem lze z libovolné gramatiky pro neprázdný jazyk vytvořit nejednoznačnou gramatiku přidáním duplikátů.

Unární řetězec

Regulární jazyk unárních řetězců určitého znaku, např. 'a' (popsaný regulárním výrazem a*), má jednoznačnou gramatiku: :A → aA | ε …ale má také nejednoznačnou gramatiku: :A → aA | Aa | ε První gramatika odpovídá vytváření zprava asociativního stromu (pro jednoznačnou gramatiku), druhá dovoluje levé- i pravé- spojení. +more Toto je rozebráno níže.

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

Bezkontextová gramatika :A → A + A | A − A | a je nejednoznačná, protože pro řetězec a + a + a existují dvě levé derivace:

Jako jiný příklad, gramatika je nejednoznačná, protože existují dva derivační stromy pro řetězec + −: :+moresvg'>400px.

Jazyk, který gramatika generuje, není nejednoznačný ze své podstaty; jednoznačná gramatika, která jej generuje, je: :A → A + a | A − a | a

Nepovinné else

Častým příkladem nejednoznačnosti ve skutečných programovacích jazycích je nepovinné else. V mnoha jazycích je část za else v podmíněném příkazu if-then-else nepovinná. +more Při vnoření dvou nebo více podmíněných příkazů do sebe není jednoznačné, ke kterém if dané else patří, přinejmenším při použití bezkontextových gramatik.

Konkrétně v mnoha jazycích lze psát podmíněný příkaz dvěma způsoby: ve tvaru if-then a ve tvaru if-then-else:

V gramatice obsahující pravidla

Příkaz = if Podmínka then Příkaz | if Podmínka then Příkaz else Příkaz | … Podmínka = …

se mohou objevit některé nejednoznačné frázové struktury. Výraz if a then if b then s else s2 může být analyzován jako if a then (if b then s) else s2 nebo jako if a then (if b then s else s2) podle toho, zda else má patřit k prvnímu nebo druhému if.

Tento problém se v různých jazycích řeší různě. Je možné navrhnout syntaxi programovacího jazyka tak, aby byla jednoznačná, například zakončením podmíněného příkazu klíčovým slovem endif, nebo nepovolením nepovinného else. +more Nebo je možné nechat bezkontextovou gramatiku nejednoznačnou, a přidat kontextové pravidlo, například že else patří k nejbližšímu if. Výsledná gramatika je pak jednoznačná, ale není bezkontextová.

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

Rozhodnutí, zda obecná bezkontextová gramatika je jednoznačná, je algoritmicky nerozhodnutelný problém, protože lze ukázat, že je ekvivalentní s Postovým korespondenčním problémem. Existují však nástroje, které implementují různé postupy umožňující detekovat některé případy nejednoznačnosti bezkontextových gramatik.

Efektivita syntaktické analýzy bezkontextové gramatiky je určena automatem, který ji přijímá. Deterministické bezkontextové gramatiky jsou přijímány deterministickými zásobníkovými automaty a mohou být analyzovány v lineárním čase, například LR analyzátorem. +more Je to vlastní podmnožina bezkontextových gramatik, které jsou přijímány zásobníkovým automatem a mohou být analyzovány v polynomiálním čase, například CYK algoritmem. Jednoznačné bezkontextové gramatiky mohou být nedeterministické. Například jazyk palindromů sudé délky nad abecedou 0 a 1 má jednoznačnou bezkontextovou gramatiku S → 0S0 | 1S1 | ε. Libovolný řetězec tohoto jazyka nemůže být analyzován bez načtení celého řetězce, což znamená, že zásobníkový automat musí zkusit alternativní přechody mezi stavy, aby podporoval různé možné délky částečně analyzovaného řetězce. Odstranění nejednoznačností gramatiky může produkovat deterministickou bezkontextovou gramatiku a tedy umožnit efektivnější syntaktickou analýzu. Generátory překladačů, jako například Yacc, obsahují prostředky pro řešení některých druhů nejednoznačnosti například pomocí precedence a omezení asociativity.

Jazyky z podstaty nejednoznačné

Existenci jazyků z podstaty nejednoznačných dokázal Rohit Parikh v roce 1961 ve výzkumné zprávě MIT (Parikhova věta).

Zatímco některé bezkontextové jazyky (množiny řetězců, které lze generovat gramatikou) mají nejednoznačné i jednoznačné gramatiky, existují bezkontextové jazyky, pro které jednoznačná bezkontextová gramatika neexistuje. Příkladem ze podstaty nejednoznačného jazyka je sjednocení množin \{a^n b^m c^m d^n | n, m > 0\} a \{a^n b^n c^m d^m | n, m > 0\}. +more Výsledný jazyk je bezkontextový, protože sjednocení dvou bezkontextových jazyků je vždy bezkontextový jazyk. Ale #CITEREFHopcroft|Ullman 1979 podal důkaz, že nelze jednoznačně analyzovat řetězce v (nebezkontextové) podmnožině \{a^n b^n c^n d^n | n > 0\}, která je průnikem těchto dvou jazyků.

Odkazy

Reference

Související články

Syntaktická nejednoznačnost

Analyzátory pro nejednoznačné a nedeterministické gramatiky:

* GLR analyzátor * Earleyův analyzátor * Tabulkový analyzátor

Externí odkazy

[url=http://www. brics. +moredk/grammar]dk. brics. gramatika[/url] - analyzátor nejednoznačnosti gramatik. * [url=https://web. archive. org/web/20110719055512/http://www2. tcs. ifi. lmu. de/~mlange/cfganalyzer/index. html]CFGAnalyzer[/url] - nástroj pro analýzu bezkontextových gramatik vzhledem k algoritmicky nerozhodnutelným problémům univerzalitě, nejednoznačnosti a podobným vlastnostem jazyka (analyzátor nemusí vydat rozhodnutí v omezeném čase).

Kategorie:Formální jazyky Kategorie:Nejednoznačnost