Gramatyka dwupoziomowa

Gramatyka dwupoziomowa jest gramatyką formalną używaną do generowania innej gramatyki formalnej, na przykład z nieskończonym zestawem reguł. W ten sposób użyto gramatyki Van Wijngaardena do określenia Algol 68 . Gramatyka bezkontekstowa , która definiuje reguły dla drugiej gramatyki, może dać efektywnie nieskończony zestaw reguł dla gramatyki pochodnej. To sprawia, że takie gramatyki dwupoziomowe są potężniejsze niż pojedyncza warstwa gramatyki bezkontekstowej, ponieważ wykazano, że generatywne gramatyki dwupoziomowe są kompletne według Turinga .

Gramatyka dwupoziomowa może również odnosić się do gramatyki formalnej dla dwupoziomowego języka formalnego , który jest językiem formalnym określonym na dwóch poziomach, na przykład poziomów słów i zdań. ^{[ potrzebne źródło ]}

Przykład

Dobrze znanym językiem bezkontekstowym jest

{\ Displaystyle \ {a ^ {n} b ^ {n} a ^ {n} | n \ geq 1 \}.}

Dwupoziomową gramatyką dla tego języka jest metagramatyka

N ::= 1 | N1

X ::= a | B

wraz ze schematem gramatycznym

Start :: =

{\ Displaystyle \ langle a ^ {N} \ rangle \ langle b ^ {N} \ rangle \ langle a ^ {N} \ rangle}

{\ Displaystyle \ langle X ^ {N1} \ rangle}

:: =

{\ Displaystyle \ langle X ^ {N} \ rangle X}

{\ Displaystyle \ langle X ^ {1 }\rangle }

::= X

Zobacz też

^ Shutt, John N. „Gramatyka dwupoziomowa” .
^ Estes, Matthew Scott (maj 2005). „Właściwości nieskończonych języków i gramatyk” (PDF) . Teza przedstawiona na wydziale Graduate School Tennessee Technological University.
Bibliografia _ i in. (red.). „Poprawiony raport na temat języka algorytmicznego ALGOL 68” . Zarchiwizowane od oryginału w dniu 24 stycznia 2002 r.
^ Sintzoff, M. (1967). „Istnienie składni van Wijngaardena dla każdego zestawu przeliczalnego rekurencyjnie”. Annales de la Société Scientifique de Bruxelles . 2 : 115-118.

Linki zewnętrzne

Petersson, Kent (1990). „Składnia i semantyka języków programowania” (PDF) . Projekt notatek z wykładów . Zarchiwizowane od oryginału (PDF) w dniu 5 czerwca 2001 r.
Augusto, LM (2023). „Gramatyka dwupoziomowa: niektóre interesujące właściwości gramatyk van Wijngaardena” (PDF) . Omega - Journal of Formal Languages . 1 : 3–34.

[1] Shutt, John N. „Gramatyka dwupoziomowa” .

[2] Estes, Matthew Scott (maj 2005). „Właściwości nieskończonych języków i gramatyk” (PDF) . Teza przedstawiona na wydziale Graduate School Tennessee Technological University.

[3] Bibliografia _ i in. (red.). „Poprawiony raport na temat języka algorytmicznego ALGOL 68” . Zarchiwizowane od oryginału w dniu 24 stycznia 2002 r.

[4] Sintzoff, M. (1967). „Istnienie składni van Wijngaardena dla każdego zestawu przeliczalnego rekurencyjnie”. Annales de la Société Scientifique de Bruxelles . 2 : 115-118.