Epäselvä kielioppi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 30. marraskuuta 2014 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Tietojenkäsittelytieteessä moniselitteinen kielioppi on muodollinen kielioppi , joka voi luoda tietyn merkkijonon useammalla kuin yhdellä tavalla (eli merkkijonolle on useampi kuin yksi jäsennyspuu ). Kielen sanotaan olevan pohjimmiltaan moniselitteinen , jos se voidaan tuottaa vain moniselitteisten kielioppien avulla.

Joidenkin ohjelmointikielten kieliopit ovat moniselitteisiä. Tällaisia kieliä jäsennettäessä on otettava huomioon semanttiset tiedot oikean muunnelman valitsemiseksi. Esimerkiksi C-kielellä seuraava merkintä:

x*y;

voidaan tulkita seuraavasti:

ilmaisemalla tunnisteen y tyyppiä pointer -to- x, tai
lauseke , jossa xkerrotaan yja tulos jätetään huomiotta.

Valitakseen näiden tulkintojen välillä kääntäjän on tarkasteltava symbolitaulukkoaan nähdäkseen, oliko ilmoitus xtypedef-nimi tietyssä laajuudessa.

Esimerkki

Konteksti vapaa kielioppi

A → A + A | A − A | a

on moniselitteinen, koska merkkijonolle a + a + a on kaksi vasemmanpuoleista lähtöä:

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

Lisäksi kielioppi on moniselitteinen, koska merkkijonolle a + a − a on kaksi jäsennyspuuta:

Sen luoma kieli ei kuitenkaan ole olennaisesti moniselitteinen, koska seuraava yksiselitteinen kielioppi tuottaa saman kielen:

A → A + a | A − a | a

Epäselvän kieliopin tunnistaminen

Yleinen ongelma sen määrittämisessä, onko kielioppi moniselitteinen, on algoritmisesti ratkaisematon . Ei voi olla algoritmia, joka määrittää kieliopin moniselitteisyyden, koska Postin ratkaisematon vastaavuusongelma pelkistyy monitulkintaongelmaksi.

Moniselitteisen kieliopin jäsentäminen deterministisellä jäsentimellä on ilmeinen , mutta ei-deterministinen jäsentäminen johtaa merkittävään tehokkuuden heikkenemiseen. Useimmat jäsentämistä vaativat konstruktit voidaan tunnistaa yksiselitteisistä kieliopeista. Jotkut moniselitteiset kieliopit voidaan muuntaa yksiselitteisiksi kieliopeiksi, mutta tälle muunnokselle ei ole yleistä menettelytapaa, kuten ei ole algoritmia kieliopin moniselitteisyyden määrittämiseksi. Kääntäjägeneraattorit , kuten YACC , pystyvät yksiselitteistämään tietynlaisia, esimerkiksi käyttämällä etusija- ja assosiatiivisuusrajoituksia .

Merkittävästi moniselitteiset kielet

Vaikka joillakin kielillä (kieliopin luomilla merkkijonoilla) on sekä yksiselitteisiä että moniselitteisiä kielioppeja, on kieliä, joille ei ole yksiselitteistä kielioppia. Esimerkki olennaisesti moniselitteisestä kielestä on yhdistelmä ja . Se on yhteydetön kieli yhteydettömien kielten yhdistelmänä, mutta Johdatus automaatioteoriaan… sisältää todisteen siitä , että ei ole mahdollista jäsentää yksiselitteisesti merkkijonoja (ei-kontekstivapaassa) osajoukossa , joka on näiden kahden leikkauspiste. Kieli (kielet. ${\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\))$

Muodolliset kielet ja viralliset kieliopit
Yleiset käsitteet	Chomsky-hierarkia Aakkoset Sana
Tyyppi 0	Rajoittamaton kielioppi Turingin kone lueteltu kieli Ratkaiseva kieli
Tyyppi 1	Tilanneherkkä kielioppi Tilannekohtainen kieli Lineaarisesti rajattu automaatti
Tyyppi 2	Kontekstiton kielioppi Epäselvä kielioppi Kontekstiton kieli Työntöautomaatti ( deterministinen ) Kasvu Lemma Ogdenin Lemma Cookin lause
Tyyppi 3	Tavallinen kielioppi tavallinen kieli Tavallinen ilme Tilakone ( deterministinen , ei - deterministinen ) DFA-minimointi NFA:n määrittäminen Myhill-Neroden lause
jäsentäminen	LL analysaattori LR jäsentäjä Rekursiivinen laskeutumismenetelmä Kok-Younger-Kasami-algoritmi