Si empieza con las reglas para construir una gramática libre de contexto y las amplía permitiendo que los no terminales de la izquierda sean funciones de uno o más argumentos, ¿va eso más allá de la definición de una gramática libre de contexto? Si es así (imagino que sí), ¿de qué clase de gramáticas se trata? ¿Sensible al contexto?
Para aclararnos, supongamos que tenemos la siguiente gramática:
$S \to F(a,b,c)$
$F(x,y,z) \to xyz$
La gramática anterior es equivalente a la siguiente porque x, y y z se sustituyen:
$S \to abc$
Supongamos ahora que aprovechamos la capacidad de la función con la siguiente gramática:
$S \to F(\epsilon)$
$F(x) \to x\ a\ |\ x\ a\ F(x\ b)$
( $\epsilon$ significa cadena vacía)
Esa gramática produce:
a
aba
ababba
ababbabbba
...Una aplicación práctica de las funciones en una gramática es expresar un lenguaje informático con formato de sangría. Un ejemplo trivial:
statement(indent)
: indent basic_statement
| indent header ':' newline statement_list(indent whitespace)
statement_list(indent)
: statement(indent)*Esto significa que una sentencia, dada una cadena de indentación, puede ser de una sola línea (por ejemplo, print 'hola') o puede ser un encabezado (por ejemplo, if (x == 5)) seguido de ':', una nueva línea y una o más sentencias hijas de un nivel de indentación mayor.
Tenga en cuenta que statement_list tiene que salir por sí mismo aquí, ya que statement(indent whitespace)* podría producir líneas hijas con sangrías inconsistentes si el espacio en blanco se expande a algo no constante. Llamando a statement_list una vez con la posible variable whitespace, obligamos a todas las sentencias hijas a tener exactamente la misma sangría. Una vez más, las funciones vienen al rescate.
Para ser más específico sobre las reglas del sistema gramatical del que hablo:
- La parte izquierda de cada regla es un terminal, un no terminal o una declaración de función para cero o más argumentos.
- Una función de argumentos cero equivale a un no terminal.
- Los argumentos de una declaración de función deben ser variables individuales (yo he utilizado $x$ , $y$ y $z$ en los ejemplos anteriores).
- Los argumentos de una "llamada a función" (utilizada en el lado derecho de una regla) pueden contener terminales, no terminales y llamadas a función anidadas.
- Los argumentos de una llamada a función se expanden antes de pasarlos. Por lo tanto, las funciones en este sistema gramatical no son superiores al primer orden (si estoy utilizando el término correctamente).
Entonces, añadiendo "funciones" a CFG, ¿qué obtengo?
