To-niveau grammatik
En grammatik på to niveauer er en formel grammatik , der bruges til at generere en anden formel grammatik, såsom en med et uendeligt sæt regler. Sådan blev van Wiingaardens grammatik brugt til at definere Algol-68- sproget . En kontekstfri grammatik , der definerer regler for en anden grammatik, kan give anledning til et i det væsentlige uendeligt sæt af afledte grammatikregler. Dette gør bilevel grammatik mere kraftfuld end enkelt-niveau kontekstfri grammatik, da bilevel generative grammatikker har vist sig at være Turing-komplet. [en]
En to-niveaus grammatik kan også omtales som en formel grammatik for et to-niveau formelt sprog, det vil sige et sprog defineret på to niveauer, såsom et ordniveau og et sætningsniveau.
Eksempel
Et velkendt ikke-kontekstfrit sprog er
Den to-niveau grammatik for det kan være metagrammatikken
N ::= 1 | N1 X ::= a | b | csammen med grammatik
Start ::= ::= ::= X
Links
- ↑ Sintoff, M. "Eksistensen af Van Wijngaardens syntaks for hvert rekursivt optællingssæt." Annales de la Société Scientifique de Bruxelles 2 (1967), 115-118.