Kielioppien esittämiseen käytettäviä metakieliä

(Alun perin kurssin TIEA241 Automaatit ja kieliopit syksy 2017 materiaaleista.)

Yleisessä käytössä on runsaasti erilaisia tapoja kirjoittaa kontekstiton kielioppi.

Backus–Naur Form (eli BNF) käyttää välikesymbolien niminä tavallisia sanoja tai ilmaisuja, jotka kirjoitetaan kulmasulkeiden sisään. Myös jotkin sellaiset päätesymbolit (kuten kokonaislukuvakiot), jotka edustavat monia eri merkkijonoja alkuperäisessä merkkijonossa, nimetään tähän tapaan. Muut päätesymbolit kirjoitetaan sellaisenaan. Produktion nuolen asemesta käytetään merkintää ::= ja saman välikesymbolin produktiot voidaan yhdistää erottamalla oikeat puolet pystyviivalla. Esimerkiksi aritmeettisten lausekkeiden kielioppi voitaisiin kirjoittaa BNF:llä näin:

Peter Naur ym.: Revised Report on the Algorithmic Language ALGOL 60. Communications of the ACM 6 (1), s. 1–17, 1963. doi:10.1145/366193.366201

Augmented BNF (eli ABNF) on käytössä Internetin standardointidokumenteissa (RFC:t). Idea on pääosin sama kuin BNF:ssä, mutta välikemerkkien (ja nimettyjen päätemerkkien) nimet kirjoitetaan sellaisenaan, ja muut päätesymbolit kirjoitetaan lainausmerkkeihin. Nuolen tilalla käytetään yhtäsuuruusmerkkiä. Valintaa merkitään kauttaviivalla, ja monia lyhennysmerkintöjä on käytetävissä.

expr = const / expr ( "+" / "-" / "*" / "/" ) expr / "(" expr ")"

D. Crocker (toim.): Augmented BNF for Syntax Specifications: ABNF. Internet Standard 68, RFC 5234, 2008. http://tools.ietf.org/html/rfc5234

Ritchien metakieli on käytössä C-sukuisten kielten syntaksikuvauksessa. En tiedä, kuka sen on alun perin keksinyt, mutta aikaisin lähde, johon olen törmännyt, on Dennis Ritchien C-kielimanuaali vuodelta 1974. Tällä metakielellä ei ole vakiintunutta nimeä, mutta nimeän sen tässä Ritchien mukaan. Välikesymbolit ja nimetyt päätesymbolit kirjoitetaan kursiivilla, ja muut päätesymbolit lihavoidulla tasavälisellä fontilla. Produktion vasen puoli kirjoitetaan rivin alkuun ja nuoli korvatan kaksoispisteellä. Saman välikesymbolin eri produktioiden oikeat puolet kirjoitetaan tämän alle sisennettynä, kukin omalle rivilleen. Jos oikeat puolet koostuvat vain nimeämättömistä päätesymboleista (kussakin produktiossa yksi symboli), voidaan kaksoispisteen perään kirjoittaa "one of" ja luetella oikeat puolet seuraavilla riveillä välilyönnillä erotettuna. Valinnaisuutta voidaan ilmaista laittamalla symbolin perään alaindeksi "opt".

expression:
constant
expression + expression
expression - expression
expression * expression
expression / expression
( expression )

Ratakiskokielioppi on graafinen notaaatio, josta voi lukea tarkemmin esim. Wikipediasta.