Wiingaardenin kielioppi

Van Wiingaarden kielioppi (myös vB-kielioppi tai B-kielioppi ) on kaksitasoinen kielioppi , joka tarjoaa tavan määritellä mahdollisesti äärettömät kieliopit äärellisen määrän sääntöjä. Adrian van Wiingaarden keksi formalismin määrittelemään joitain syntaktisia rajoituksia, jotka aiemmin piti muotoilla luonnollisilla kielillä, huolimatta niiden pohjimmiltaan syntaktisesta luonteesta. Tyypillisiä sovelluksia ovat sukupuolen ja numeron käsittely luonnollisilla kielillä sekä ohjelmointikielien tunnisteiden oikea muotoilu.

Menetelmää käytettiin ja kehitettiin ohjelmointikielen ALGOL 68 määrittelyssä . Tämä on esimerkki laajemmasta liitekieliopista.

Yleiskatsaus

B-kielioppi koostuu äärellisestä määrästä metasääntöjä, joita käytetään johtamaan (mahdollisesti äärettömiä) päättelysääntöjä äärellisestä määrästä hypersääntöjä. Metasääntöjen määritelmä rajoittuu yhteydettömään kielioppiin. Hypersäännöt rajoittavat sallittuja konteksteja korkeammalla tasolla. Pohjimmiltaan päättelyprosessissa käytetty johdonmukainen substituutio vastaa yhdistämisprosessia, esimerkiksi Prolog-kielestä, kuten Alan Colmeroe totesi.

Esimerkkejä ALGOL 68:sta

Ennen ALGOL 68 -kieltä ALGOL 60 formalisoitiin kontekstittomilla Backus-Naur-lomakkeilla. Uusien tilannekohtaisten kaksitasoisten kielioppien ilmestyminen aiheutti vaikeuksia joillekin ALGOL 68 :n loppuraportin lukijoille vuonna 1968. Myöhemmin Weingaarden ja kollegat toimittivat loppuraportin, ja se julkaistiin "Muokattuna raporttina" ALGOL 68:sta vuonna 1973.

ALGOL 68 vuoden 1968 raportissa § 2.1

a) ohjelma: avoin symboli, tavallinen alkusoitto, kirjaston alkusoittovaihtoehto, tietty ohjelma, poistuminen, kirjaston jälkisoitto, tavallinen jälkisoitto, sulkemissymboli. b) vakioalkusoitto: julistusalkusoittosekvenssi. c) kirjaston alkusoitto: ilmoitusalkusekvenssi. d) tietty ohjelma: etikettijärjestysvaihtoehto, vahva CLOSED void lauseke. e) poistuminen: jatka symbolia , kirjain e kirjain x kirjain i kirjain t, etiketin symboli. f) kirjaston jälkisoitto: lauseen välisoitto. g) tavallinen jälkisoitto: vahva void lausekejuna

ALGOL 68 vuonna 1973 muokattu raportti § 2.2.1, § 10.1.1

ohjelma : vahva tyhjä uusi suljettu lauseke A) ULKOINEN :: vakio ; kirjasto; järjestelmä; tietty. B) STOP :: etiketti kirjain s kirjain t kirjain o kirjain p. a) Ohjelmateksti: STYLE-aloitusmerkki, uudet LAYER1-alkuäänet, rinnakkaistunnus, uusi LAYER1-tehtäväpaketti, STYLE-päätetunnus. b) NEST1-alkusoitto: NEST1-standardin alkusoitto DECS1:n kanssa, NEST1-kirjaston alkusoitto DECSETY2:lla, NEST1-järjestelmän alkusoitto DECSETY3:lla, missä (NEST1) on (uusi TYHJÄ uusi DECS1 DECSETY2 DECSETY3). c) NEST1 EXTERNAL alkusoitto DECSETY1:n kanssa: vahva tyhjä NEST1-sarja DECSETY1:n kanssa, mene tokeniin ; missä (DECSETY1) on (TYHJÄ), TYHJÄ. d) NEST1-tehtävät: NEST1-järjestelmän tehtäväluettelo ja myös tunnus, NEST1-käyttäjätehtävä PACK-luettelo. e) NEST1-järjestelmätehtävä: vahva tyhjä NEST1-yksikkö. f) NEST1-käyttäjätehtävä : NEST2:n erityinen alkusoitto DECS:n kanssa, NEST2 tietty ohjelma PACK, siirry tokeniin, nest2 erityinen jälkisoitto, missä (PES2) on (PES11 uusi DECS STOP). g) NEST2-ohjelma: NEST2 uusi LABETY3 liittyi tarran määritelmään of LABSETY3, vahva tyhjyys NEST2 uusi LABSETY3 LIITETTY lauseke. h) LABSETYn NESTin liitetyn etiketin määritelmä: missä (LABSETY) on (TYHJÄ), TYHJÄ ; missä (LABSETY) on (LAB1 LABSETY1), LAB1:n NEST-tunnisteen määritelmä, NEST liittyi tunnisteen $LABSETY1 määritelmään. i) NEST2:n erityinen jälkisoitto: vahva tyhjä NEST2-sarja, jossa on STOP.

Historia

B-kieliopit perustuvat ajatukseen täydentää COP-kieliopin ei-terminaalisia symboleja attribuuteilla (tai liitteillä ), jotka välittävät tietoa jäsennyspuun solmujen välillä ja joita käytetään rajoittamaan syntaksia ja määrittämään semantiikkaa. Tämä ajatus oli tuolloin hyvin tiedossa, erityisesti Donald Knuth vieraili ALGOL 68 -kehityskomiteassa oman versionsa kehittämisen aikana. [1] Mielenkiintoinen B-kieliopin piirre on niiden tiukka suhde CF-kieliopin antamiin merkkijonoattribuutteihin, joissa ketjuttaminen on ainoa mahdollinen operaatio. Attribuuttien kielioppien attribuutit voivat olla mitä tahansa tyyppiä ja niihin voidaan soveltaa mitä tahansa toimintoa.

Algol 68 -raportissa esittelyn jälkeen B-kielioppeja pidettiin liian tehokkaina ja rajoittamattomina käytännön käyttöön. Algol 68:n muokattu raportti, joka vaikutti osittain niiden soveltamiseen, sisälsi paljon luettavamman kieliopin, mutta säilytti B-kieliopin oikean formalismin.

Tällä kertaa kävi selväksi, että B-kieliopit olivat todellakin liian voimakkaita. Ne ovat Turing-täydellisiä, mikä tekee niiden jäsentämisen mahdottomaksi: ongelmaa tarkistaa, voidaanko tietty merkkijono tuottaa tietyllä B-kieliopilla, on algoritmisesti ratkaisematon. Niiden käyttöä olisi rajoitettava ankarasti automaattisessa analysoinnissa tai kääntämisessä. Erityisesti tämän ongelman ratkaisemiseksi on kehitetty rajoitettuja ja muokattuja versioita B-kieliopista

Muut sovellukset kuin ALGOL 68

Anthony Fisher kirjoitti jäsentimen suurelle B-kielioppiluokalle [1] Arkistoitu 14. joulukuuta 2007 Wayback Machineen .

Dick Grune on luonut C-ohjelman, joka luo kaikenlaisia ​​päättelysääntöjä kaksitasoiseen kielioppiin [2] .

Edellä mainittuja laajennettujen liitekielioppien sovelluksia voidaan pitää B-kielioppien sovelluksina, koska PA-kieliopit ovat melko lähellä niitä.

B-kielioppeja on myös ehdotettu käytettäväksi kuvaamaan monimutkaisia ​​ihmisen toimintoja ergonomiassa.

Linkit

  1. ↑ [DE Knuth: Attribuuttien kielioppien genesis Arkistoitu 15. heinäkuuta 2010 Wayback Machinessa . Attribuuttien kielioppia ja niiden sovelluksia käsittelevän kansainvälisen konferenssin aineistoa (1990), 1-12.]