Dvorazinska gramatika

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 s beskonačnim skupom produkcija[2] te gramatike poput Van Wijngaardenove gramatike korištene za specificiranje jezika ALGOL-68[3] Predložak:Webarchive. 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, jer je pokazano da su dvorazinske generativne gramatike Turing-potpune.

Primjer

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 ::= $⟨a^N⟩⟨b^N⟩⟨a^N⟩$

$⟨X^{N1}⟩$ ::= $⟨X^N⟩X$

$⟨X^1⟩$ ::= X

Vidjeti također

• Van Wijngaardenova gramatika

Vanjske poveznice

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