Gramática de dos niveles

Una gramática de dos niveles es una gramática formal que se utiliza para generar otra gramática formal, como una con un conjunto infinito de reglas. Así es como se utilizó la gramática de van Wiingaarden para definir el lenguaje Algol-68 . Una gramática independiente del contexto que define reglas para otra gramática puede dar lugar a un conjunto esencialmente infinito de reglas gramaticales derivadas. Esto hace que las gramáticas de dos niveles sean más poderosas que las gramáticas libres de contexto de un solo nivel, ya que se ha demostrado que las gramáticas generativas de dos niveles son completas de Turing. [una]

Una gramática de dos niveles también se puede denominar una gramática formal para un lenguaje formal de dos niveles, es decir, un lenguaje definido en dos niveles, como un nivel de palabra y un nivel de oración.

Ejemplo

Un lenguaje bien conocido que no está libre de contexto es

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

La gramática de dos niveles puede ser la metagramática

N ::= 1 | N1 X ::= un | segundo | C

junto con la gramática

Inicio ::=

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

\langle X^{N1}\rangle

::=

{\ estilo de visualización \ ángulo X^{N} \ ángulo X}

\langle X^{1}\rangle

::= X

Enlaces

↑ Sintoff, M. "Existencia de la sintaxis de Van Wijngaarden para cada conjunto recursivamente enumerable". Annales de la Société Scientifique de Bruxelles 2 (1967), 115-118.