Tvetydig grammatik

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 30 november 2014; kontroller kräver 5 redigeringar .

Inom datavetenskap är en tvetydig grammatik en formell grammatik som kan generera en given sträng på mer än ett sätt (det vill säga det finns mer än ett analysträd för en sträng). Ett språk sägs vara i huvudsak tvetydigt om det bara kan genereras av tvetydiga grammatiker.

Grammatiken för vissa programmeringsspråk är tvetydiga. Vid analys av sådana språk måste semantisk information beaktas för att välja rätt variant. Till exempel, i C-språk följande post:

x*y;

kan tolkas som antingen:

deklarera en identifierare y av typen pekare -till- x, eller
ett uttryck där xmultipliceras med yoch resultatet ignoreras.

För att välja mellan dessa tolkningar måste kompilatorn konsultera sin symboltabell för att se om deklarationen xvar ett typdef-namn i ett givet omfång.

Exempel

Sammanhangsfri grammatik

A → A + A | A − A | a

är tvetydig, eftersom det finns två vänsterhandsutgångar för strängen a + a + a:

A	→A+A	A	→A+A
	→ a+A		→A+A+A
	→ a+A+A		→ a+A+A
	→ a+a+A		→ a+a+A
	→ a + a + a		→ a + a + a

Dessutom är grammatiken tvetydig eftersom det finns två analysträd för strängen a + a − a:

Språket som det genererar är dock inte i huvudsak tvetydigt, eftersom följande entydiga grammatik genererar samma språk:

A → A + a | A − a | a

Erkännande av tvetydig grammatik

Det allmänna problemet med att avgöra om en grammatik är tvetydig är algoritmiskt oavgörbart . Det kan inte finnas en algoritm som bestämmer tvetydigheten i en grammatik, eftersom Posts olösliga korrespondensproblem reduceras till ett tvetydighetsproblem.

Det finns en uppenbar svårighet att tolka en tvetydig grammatik med en deterministisk tolk , men icke-deterministisk tolkning resulterar i en betydande förlust i effektivitet. De flesta konstruktioner som kräver analys kan kännas igen av entydiga grammatiker. Vissa tvetydiga grammatiker kan konverteras till entydiga grammatiker, men det finns ingen generell procedur för denna omvandling, precis som det inte finns någon algoritm för att bestämma en grammatiks tvetydighet. Kompilatorgeneratorer , såsom YACC , kan disambiguera vissa typer, till exempel genom att använda prioritets- och associativitetsbegränsningar .

Betydligt tvetydiga språk

Medan vissa språk (uppsättningar av strängar som genereras av en grammatik) har både entydiga och tvetydiga grammatiker, finns det språk för vilka det inte finns någon entydig grammatik. Ett exempel på ett i huvudsak tvetydigt språk är föreningen av och . Det är ett sammanhangsfritt språk som en sammanslagning av sammanhangsfria språk, men Introduction to Automata Theory... innehåller bevis på att det inte är möjligt att unikt tolka strängar i den (icke-kontextfria) delmängden som är skärningspunkten mellan de två språk. ${\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\))$ ${\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\))$ ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\))$

Formella språk och formella grammatiker
Allmänna begrepp	Chomsky hierarki Alfabet Ord
Typ 0	Obegränsad grammatik Turing maskin uppräknat språk Lösbart språk
Typ 1	Sammanhangskänslig grammatik Kontextkänsligt språk Linjärt begränsad automat
Typ 2	Kontextfri grammatik Tvetydig grammatik Kontextfritt språk Pushdown-automat ( deterministisk ) Tillväxt Lemma Ogdens Lemma Cooks teorem
Typ 3	Vanlig grammatik vanligt språk Vanligt uttryck Tillståndsmaskin ( deterministisk , icke- deterministisk ) DFA-minimering Bestämning av NFA Myhill-Nerodes sats
analysera	LL analysator LR-parser Rekursiv nedstigningsmetod Kok-Yngre-Kasami-algoritm