Kontekstiton kielioppi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 3. tammikuuta 2022 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Kontekstiton kielioppi ( CS-grammar , kontekstiton kielioppi ) on formaalisen kieliopin ( Chomsky-hierarkian tyyppi 2 ) erikoistapaus, jossa kaikkien tuotantojen vasemmat osat ovat yksittäisiä ei -päätteitä (objekteja, jotka ilmaisevat mitä tahansa olemusta kieli (esimerkiksi: kaava, aritmeettinen lauseke, komento) ja jolla ei ole erityistä symbolista merkitystä). Käsitteen "kontekstiton" merkitys on, että tuotantoa voidaan soveltaa ei-päätteeseen, ja lisäksi riippumatta tämän ei-terminaalin kontekstista (toisin kuin yleisesti, rajoittamaton Chomsky-kielioppi).

Kieltä , joka voidaan määrittää CFG:llä, kutsutaan kontekstivapaaksi kieleksi tai CFL:ksi.

Itse asiassa KS-kielioppi on toinen BNF :n muoto .

Sovellus

COP-kieliopilla on paljon käyttöä tietojenkäsittelytieteessä . Ne asettavat useimpien ohjelmointikielten kieliopin rakenteen , strukturoidun datan jne. (katso kielioppianalyysi )

COP-kieliopin jäsentämiseen riittää push-down- automaatti , ei-COP-kieliopin jäsentämiseen voidaan tarvita Turingin täydellinen kone .

CS-kielioppityypit

LL kielioppi
LALR-kielioppi (katso: LALR(1) )
LR kielioppi
SLR-kielioppi (katso: SLR(1) )

Tunnistajat

CF-kielillä on kaksi erilaista tunnistusluokkaa (tunnistusautomaatit). Niiden nimet liittyvät järjestykseen, jossa tulospuu rakennetaan. Pääsääntöisesti kaikki tunnistimet lukevat syötetyn merkkijonon vasemmalta oikealle, koska tällaista merkintää odotetaan ohjelmien lähdekoodia kirjoitettaessa.

Alavirran ratkaisijat

Ylhäältä alas -selvittimet, jotka luovat vasemmanpuoleisia tulosketjuja ja rakentavat tulospuun ylhäältä alas.

He käyttävät algoritmin muunnelmia vaihtoehtojen valinnassa. Niitä luotaessa käytetään menetelmää, jolla voit valita yksilöllisesti yhden ja vain yhden vaihtoehdon jokaisessa MP-automaatin vaiheessa (poistovaihe tässä automaatissa suoritetaan aina yksilöllisesti).

Nousevat tunnistimet

Alhaalta ylös -selvittimet, jotka luovat oikeakätisten tulosteiden ketjuja ja rakentavat tulospuun alhaalta ylös.

Ylävirran tunnistimet käyttävät muunnoksia shift-fold (tai shift-fold, joka on sama) algoritmiin. Niitä luotaessa käytetään menetelmiä, joiden avulla voit yksiselitteisesti valita, suoritetaanko "siirto" ("siirto") tai "konvoluutio" jokaisessa laajennetun MP-automaatin vaiheessa, ja kun konvoluutio suoritetaan, voit yksiselitteisesti valita säännön. jolla konvoluutio suoritetaan. Algoritmi "siirto-konvoluutio".

Esimerkkejä

Esimerkkejä SF-kieliopista ja niitä vastaavista SF-kielistä:

Käännä sana

Annettu kaavalla $L=\{w\in \Sigma ^{*}|w=w^{R}\}$

Päätteet: aakkosten kirjaimet ; $\Sigma$
Ei-pääte: ; $S$
Tuotteet: $S\rightarrow \alpha S\alpha \,|\,\alpha \,|\,\varepsilon ,\alpha \in \Sigma$
Alkuperäinen ei- pääte on . $S$

Sisäkkäiset sulut

Päätteet: ja ; $($ $)$
ei-päätelaite: ; $S$
tuotteet: ; $S\rightarrow (S)\mid \varepsilon$
alkuperäinen ei -pääte - . $S$

Tämä kielioppi määrittää sisäkkäisten hakasulkeiden kielen . $\{\left(^{n}\oikea)^{n}\mid n\geq 0\}$

Dickin kieli

Aritmeettinen lauseke

Päätteet: '+', '-', '*', '/', '(', ')', 'x'
nonterminaalit: <lauseke>, <termi>, <kerroin>
Tuotteet:

<lauseke> → <lauseke> + <termi>, <lauseke> → <lauseke> - <termi>, <lauseke> → <termi>, <termi> → <termi> * <kerroin>, <termi> → <termi> / <kerroin>, <termi> → <kerroin>, <kerroin> → ( <lauseke> ), <kerroin> → x,

alkuperäinen ei-pääte: <lauseke>.

Tämä kielioppi määrittelee aritmeettisen lausekkeen, joka sisältää yksinkertaisimmat aritmeettiset operaatiot muuttujalle x. Jos korvaamme terminaalin 'x' ei-päätteellä <numero>, saadaan kielioppi, joka määrittää aritmeettisen lausekkeen, joka koostuu kokonaislukujen yhteen-, vähennys-, kerto- ja jakolaskuoperaatioista.

COP-kieliopin rajoitukset

Kaikkia kieliä ei voida määritellä CF-kieliopin avulla. Helpoin tapa todistaa tämä on seuraava: COP-kieliopit muodostavat laskettavan joukon, kun taas kaikkien kielten joukon kardinaalisuus on jatkumo . Rakentava todiste samasta tosiasiasta voidaan saada esimerkiksi sillä perusteella, että kieli { a n b n c n | n ≥1} ei ole kontekstivapaa; Kuitenkaan jälkimmäiselle väitteelle ei näytä olevan lyhyttä todistetta: julkaistut todistukset perustuvat yhteydettömien kielten kasvulauseeseen.

Yleistykset

Puunlisäyskielioppi yleistää yhteydettömän kieliopin siten, että päättelysääntöjen perusyksikkö on puut, ei yksittäiset merkit.

Katso myös

Kirjallisuus

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
Belousov A. I., Tkachev S. B. Diskreetti matematiikka. — M .: MGTU , 2006. — 743 s. — ISBN 5-7038-2886-4 .

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