Kaksitasoinen kielioppi

Kaksitasoinen kielioppi on muodollinen kielioppi , jota käytetään luomaan toinen muodollinen kielioppi, esimerkiksi sellainen, jossa on ääretön määrä sääntöjä. Näin Algol-68 kielen määrittelyyn käytettiin van Wiingaardenin kielioppia . Kontekstiton kielioppi , joka määrittelee säännöt toiselle kieliopille, voi synnyttää olennaisesti äärettömän joukon johdettuja kielioppisääntöjä. Tämä tekee kaksitasoisista kieliopeista tehokkaampia kuin yksitasoiset yhteydettömät kieliopit, koska kaksitasoisten generatiivisten kielioppien on osoitettu olevan Turingin täydellisiä. [yksi]

Kaksitasoista kielioppia voidaan kutsua myös kaksitasoisen muodollisen kielen muodolliseksi kieliopiksi, toisin sanoen kieleksi, joka on määritelty kahdella tasolla, kuten sanatasolla ja lausetasolla.

Esimerkki

Tunnettu ei-kontekstiton kieli on

\{a^{n}b^{n}a^{n}|n\geq 1\}.

Sen kaksitasoinen kielioppi voi olla metakielioppi

N ::= 1 | N1 X ::= a | b | c

kieliopin kanssa

Aloita ::=

\langle a^{N}\rangle \langle b^{N}\rangle \langle c^{N}\rangle

\langle X^{N1}\rangle

::=

\langle X^{N}\rangle X

\langle X^{1}\rangle

::= X

Linkit

↑ Sintoff, M. "Van Wijngaardenin syntaksin olemassaolo jokaiselle rekursiivisesti numeroitavalle joukolle." Annales de la Société Scientifique de Bruxelles 2 (1967), 115-118.