Dvorazinska gramatika

Izvor: Wikipedija
Skoči na: orijentacija, traži

Dvorazinska gramatika je jedna od dvije sljedeće formalne strukture:

  1. Formalna gramatika za dvorazinski formalni jezik, koji je formalni jezik specificiran na dvije razine - npr. na razini riječi i rečenica.
  2. Formalna gramatika korištena za generiranje druge formalne gramatike[1], poput one sa beskonačnim skupom produkcija[2] te gramatike poput Van Wijngaardenove gramatike korištene za specificiranje jezika ALGOL-68[3]. Kontekstno neovisna gramatika koja definira produkcije za drugu gramatiku može dati beskonačan skup produkcijskih pravila za izvedenu gramatiku. Dvorazinske gramatike koje generiraju drugu kontekstno neovisnu gramatiku su moćnije od jednorazinske kontekstno neovisne gramatike, budući da je pokazano da su dvorazinske generativne gramatike Turing-potpune.

Primjer[uredi VE | uredi]

Dobro poznat kontekstno neovisni jezik jest

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

Dvorazinska gramatika za ovaj jezik jest metagramatika

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

zajedno sa shemom gramatike

Start ::=  \langle a^N \rangle\langle b^N \rangle\langle a^N \rangle
 \langle X^{N1} \rangle ::= \langle X^N \rangle X
 \langle X^1 \rangle ::= X

Vidjeti također[uredi VE | uredi]

Vanjske poveznice[uredi VE | uredi]

  • Petersson, Kent (1990), "Syntax and Semantics of Programming Languages", Draft Lecture Notes, PDF text.


Computer-aj aj ashton 01.svg Nedovršeni članak Dvorazinska gramatika koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.