Muodollinen kielioppi

Muodollinen kielioppi tai vain kielioppi muodollisten kielten teoriassa on tapa kuvata muodollista kieltä, eli valita tietty osajoukko jonkin äärellisen aakkoston kaikkien sanojen joukosta . On olemassa generatiivisia ja tunnistavia (tai analyyttisiä ) kielioppeja - ensimmäinen asettaa säännöt, joilla voit rakentaa minkä tahansa kielen sanan, ja toinen antaa sinun määrittää tietystä sanasta, sisältyykö se kieleen vai ei.

Ehdot

Terminaali (päätemerkki) on objekti, joka on suoraan läsnä kielioppia vastaavan kielen sanoissa ja jolla on erityinen, muuttumaton merkitys (yleistys käsitteestä "kirjaimet"). Tietokoneella käytetyillä muodollisilla kielillä kaikki tai osa standardeista ASCII-merkit - latinalaiset kirjaimet, numerot ja erikoismerkit - otetaan yleensä päätteinä .
Ei-pääte (ei-päätemerkki) on objekti, joka ilmaisee jotakin kielen entiteettiä (esimerkiksi: kaava, aritmeettinen lauseke, komento) ja jolla ei ole tiettyä symbolista arvoa.

Generatiiviset kieliopit

Kieliopin antamat kielen sanat ovat kaikki päätejonoja, jotka tulostetaan (generoidaan) alkuperäisestä ei-päätteestä lähtösääntöjen mukaisesti.

Asettaaksesi kieliopin, sinun on asetettava päätteiden ja ei-päätteiden aakkoset, joukko päättelysääntöjä ja valittava myös alkuperäinen ei-päätejoukosta.

Joten kielioppi määritellään seuraavilla ominaisuuksilla:

$\Sigma$ — päätemerkkien joukko ( aakkoset ).
N on joukko ( aakkoset ) ei-päätteisiä symboleja
P on joukko sääntöjä muodossa: "vasen puoli" "oikea puoli", jossa: $\nuoli oikealle$
- "vasen puoli" on ei-tyhjä terminaalien ja ei-päätteiden sarja, joka sisältää vähintään yhden ei-terminaalin
- "oikea puoli" - mikä tahansa terminaalien ja ei-päätteiden sarja
S on kieliopin alkusymboli (tai alkusymboli) ei-päätteisten joukosta.

Johtopäätös

Lähtö on rivijono, joka koostuu päätteistä ja ei-päätteistä, jossa ensimmäinen rivi on rivi, joka koostuu yhdestä aloittavasta ei-päätteestä, ja jokainen seuraava rivi saadaan edellisestä korvaamalla jokin alimerkkijono yhden (mikä tahansa) mukaan. säännöistä. Viimeinen merkkijono on merkkijono, joka koostuu kokonaan terminaaleista, ja on siksi kielen sana.

Tietyn sanan johdannaisen olemassaolo on kriteeri sen kuulumiselle tietyn kieliopin määrittelemään kieleen.

Kielioppityypit

Chomsky-hierarkian mukaan kieliopit on jaettu 4 tyyppiin, jokainen seuraava on rajoitetumpi osajoukko edellisestä (mutta myös helpompi analysoida):

tyyppi 0. rajoittamaton kielioppi - kaikki säännöt ovat mahdollisia
tyyppi 1. kontekstiherkät kieliopit - vasen osa voi sisältää yhden ei-terminaalin, jota ympäröi "konteksti" (merkkijonot, jotka ovat samassa muodossa oikeassa osassa); itse ei-pääte korvataan ei-tyhjällä merkkijonolla oikealla.
tyyppi 2. yhteydettömät kieliopit — vasen osa koostuu yhdestä ei-päätteestä.
tyyppi 3. säännölliset kieliopit ovat yksinkertaisempia, vastaavat äärellisiä automaatteja .

Lisäksi siellä on:

Ei-lyhennetty kielioppi . Jokaisella tällaisen kieliopin säännöllä on muoto , jossa . Säännön oikean puolen pituus ei ole pienempi kuin vasemman reunan pituus [1] . $\alpha \rightarrow \beta$ $|\alpha |\leqslant |\beta |$
Lineaariset kieliopit . Jokaisen tällaisen kieliopin säännön muoto on , eli säännön oikea puoli voi sisältää enintään yhden ei-päätteisen esiintymän [2] . $A\rightarrow uBv$ $A\rightarrow u$

Sovellus

Kontekstittomia kielioppeja käytetään laajasti kieliopin rakenteen määrittämiseen kielioppianalyysissä .
Säännöllisiä kielioppeja ( säännöllisten lausekkeiden muodossa ) käytetään laajalti tekstin haun, jaottelun ja korvaamisen malleina, myös leksikaalisessa analyysissä .

Esimerkkinä ovat aritmeettiset lausekkeet

Harkitse yksinkertaista kieltä, joka määrittelee rajoitetun osajoukon aritmeettisia kaavoja, jotka koostuvat luonnollisista luvuista , suluista ja aritmeettisista merkeistä. On syytä huomata, että tässä jokaisessa säännössä nuolen vasemmalla puolella on vain yksi ei-päätesymboli. Tällaisia kielioppeja kutsutaan kontekstivapaiksi . $\nuoli oikealle$

Päätteen aakkoset:

\Sigma

= {'0','1','2','3','4','5','6','7','8','9','+','-', '*','/','(',')'}

Ei-pääteaakkoset:

{ KAAVA, TUNNUS, NUMERO, NUMERO }

Säännöt:

1. KAAVA KAAVA MERKKIKAAVA

\to

(kaavassa on kaksi kaavaa, jotka on yhdistetty merkillä) 2. KAAVAN NUMERO

\to

(kaava on numero) 3. KAAVA ( FORMULA )

\to

(kaava on suluissa oleva kaava) 4. SIGN + | - | * | /

\to

(merkki on plus tai miinus tai kerro tai jaa) 5. NUMERONUMERO ( luku

\to

on numero) 6. NUMERON NUMERO

\to

(luku on numero ja numero) 7. NUMERO 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

\to

(numero on 0 tai 1 tai ... 9)

Alkuperäinen ei-pääte:

KAAVA

Johtopäätös :

Johdetaan kaava (12+5) lueteltujen päättelysääntöjen avulla. Selvyyden vuoksi kunkin vaihdon sivut on esitetty pareittain, kussakin parissa vaihdettu osa on alleviivattu.

KAAVA (FORMULA)

{\stackrel {3}{\to ))

( FORMULA ) ( FORMULA SIGN FORMULA )

{\stackrel {1}{\to ))

(FORMULA SIGN FORMULA) (FORMULA + FORMULA)

{\stackrel {4}{\to ))

( FORMULA + KAAVA ) ( KAAVA + NUMERO )

{\stackrel {2}{\to ))

( KAAVA + NUMERO ) ( KAAVA + NUMERO )

{\stackrel {5}{\to ))

( KAAVA + NUMERO ) ( KAAVA + 5 )

{\stackrel {7}{\to ))

( KAAVA + 5) ( NUMERO + 5)

{\stackrel {2}{\to ))

( NUMERO + 5) ( NUMERO + 5)

{\stackrel {6}{\to ))

( NUMERO NUMERO + 5) ( NUMERO + 5)

{\stackrel {5}{\to ))

( NUMERO + 5) ( 1 NUMERO + 5)

{\stackrel {7}{\to ))

(1 NUMERO + 5) (1 2 + 5)

{\stackrel {7}{\to ))

Analyyttiset kieliopit

Generatiiviset kieliopit eivät ole ainoa kielioppityyppi, mutta ne ovat yleisimpiä ohjelmointisovelluksissa. Toisin kuin generatiiviset kieliopit, analyyttinen (tunnistava) kielioppi määrittelee algoritmin, jonka avulla voit määrittää, kuuluuko tietty sana kieleen. Esimerkiksi mikä tahansa säännöllinen kieli voidaan tunnistaa tilakoneen määrittämän kieliopin avulla , ja mikä tahansa yhteydetön kielioppi voidaan tunnistaa pinopohjaisella automaatilla . Jos sana kuuluu johonkin kieleen, niin tällainen automaatti rakentaa tulostensa eksplisiittiseen muotoon, mikä mahdollistaa tämän sanan semantiikan analysoinnin.

Katso myös

JFLAP - automaattien, Turingin koneiden, kielioppien simulaattori
jäsentäminen
Epäselvä kielioppi
Pienin kielioppiongelma
Kielioppi lauserakenteella

Kirjallisuus

Belousov A. I., Tkachev S. B. Diskreetti matematiikka. — M .: MGTU , 2006. — 743 s. — ISBN 5-7038-2886-4 .
Gladkiy A. V. Muodolliset kieliopit ja kielet. - M .: Nauka, 1973.
Kasyanov VN Luentoja muodollisten kielten teoriasta, automaateista ja laskennallisesta monimutkaisuudesta. - Novosibirsk: NGU, 1995. - 112 s.
Chomsky N., Miller J. Johdatus luonnollisten kielten muodolliseen analyysiin // Kyberneettinen kokoelma / Toim. A.A. Lyapunova ja O.B. Lupanova. - M .: Mir, 1965.
Gross M., Lanten A. Formaalisten kielioppien teoria. - M .: Mir, 1971. - 296 s.

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