Tvetydig grammatik

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 30. november 2014; checks kræver 5 redigeringer .

I datalogi er en tvetydig grammatik en formel grammatik , der kan generere en given streng på mere end én måde (det vil sige, at der er mere end ét parsetræ for en streng). Et sprog siges at være i det væsentlige tvetydigt , hvis det kun kan genereres af tvetydige grammatikker.

Grammatikken for nogle programmeringssprog er tvetydig. Når man analyserer sådanne sprog, skal der tages hensyn til semantisk information for at vælge den korrekte variant. For eksempel i C-sprog følgende post:

x*y;

kan tolkes som enten:

erklære en identifikator y af typen pointer -to- x, eller
et udtryk , hvori xganges med, yog resultatet ignoreres.

For at vælge mellem disse fortolkninger skal compileren konsultere sin symboltabel for at se, om erklæringen xvar et typedef-navn i et givet omfang.

Eksempel

Gratis kontekst grammatik

A → A + A | A − A | -en

er tvetydig, da der er to venstrehåndsudgange for strengen a + a + a:

EN	→A+A	EN	→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

Grammatikken er også tvetydig, fordi der er to parsetræer for strengen a + a − a:

Men det sprog, det genererer, er ikke væsentligt tvetydigt, da følgende utvetydige grammatik genererer det samme sprog:

A → A + a | A − a | -en

Anerkendelse af tvetydig grammatik

Det generelle problem med at afgøre, om en grammatik er tvetydig, er algoritmisk uafgørligt . Der kan ikke være en algoritme, der bestemmer tvetydigheden af en grammatik, da Posts uløselige korrespondanceproblem reduceres til et tvetydighedsproblem.

Der er en åbenlys vanskelighed ved at parse en tvetydig grammatik med en deterministisk parser , men ikke-deterministisk parsing resulterer i et betydeligt tab i effektivitet. De fleste konstruktioner, der kræver parsing, kan genkendes af utvetydige grammatikker. Nogle flertydige grammatikker kan konverteres til entydige grammatikker, men der er ingen generel procedure for denne konvertering, ligesom der ikke er en algoritme til at bestemme en grammatiks flertydighed. Compiler -generatorer , såsom YACC , er i stand til at disambiguere visse typer, for eksempel ved at bruge præcedens og associativitetsbegrænsninger .

Betydeligt tvetydige sprog

Mens nogle sprog (sæt af strenge genereret af en grammatik) har både entydige og tvetydige grammatikker, er der sprog, som der ikke er nogen entydig grammatik for. Et eksempel på et i det væsentlige tvetydigt sprog er foreningen af og . Det er et kontekstfrit sprog som en sammenlægning af kontekstfri sprog, men Introduktion til automatteori... indeholder bevis på , at det ikke er muligt entydigt at parse strenge i den (ikke-kontekstfrie) delmængde , der er skæringspunktet mellem de to Sprog. ${\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\))$

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme