INDICE GENERAL
Introducción
..........................................................................................
2
Diagramas
sintácticos.........................................................................
4
INDICE DE TABLAS Y FIGURAS
Introducción
..........................................................................................
2
Ejemplo 1
..............................................................................................
2
Ejemplo 2 ..............................................................................................
2
Ejemplo 3
..............................................................................................
3
Figura 1
.................................................................................................
3
Diagramas
sintácticos..........................................................................
4
Figura 2a
...............................................................................................
4
Figura 2b
...............................................................................................
4
Figura 2c
...............................................................................................
5
Figura 2d
...............................................................................................
5
Figura 2e
...............................................................................................
6
Ejemplo 4
..............................................................................................
6
Figura 3a
...............................................................................................
6
Figura 3b
...............................................................................................
6
Ejemplo 5
..............................................................................................
7
Figura 4
.................................................................................................
7
Conclusiones
.......................................................................................
7
Glosario..............................................................
8
Referencias
........................................................ 8
Representaciones gramaticales
Notación BNF
Una alternativa usual para denotar
las producciones de las gramáticas del tipo 2 es la notación BNF (que viene de
Backus-Naur Form). Se sabe que los lados izquierdos de todas las producciones
en una gramática del tipo 2 son un solo símbolo no terminal. El símbolo w
permanecerá en la izquierda y todos los lados derechos asociados a w se
enlistarán juntos, separados por el símbolo “|”. El símbolo de la relación “®” se reemplaza
por el símbolo “::=”. Finalmente, los símbolos no terminales, siempre que
ocurran, se encerrarán entre llaves “< >”. Esto tiene la ventaja
adicional de permitir que los símbolos no terminales contengan espacios. Por
tanto,
Ejemplo 1.
En la notación BNF, las producciones gramaticales de una oración serán :
Ejemplo 2.
Obsérvese que el lado izquierdo
de una producción puede aparecer en una de las secuencias del lado derecho. Así
en la segunda línea ,
Ejemplo 3.
La
notación BNF a menudo se emplea para especificar los lenguajes de programación
reales. El ALGOL y el PASCAL tuvieron sus gramáticas en BNF, originalmente. En
el siguiente ejemplo se examina un pequeño subconjunto común de esas dos
gramáticas. Este subconjunto describe la sintaxis de los números decimales y
puede verse como una minigramática cuyo lenguaje correspondiente consta
precisamente de todos los números decimales formados adecuadamente.
Sea:
S ={0,1,2,3,4,5,6,7,8,9, . }. Sea V la unión de
s con el conjunto
N ={número-decimal, fracción-decimal, entero-sin
dígito, dígito}
Entonces sea G la gramática con
los conjuntos de símbolos de V y S, con el símbolo inicial “número-decimal” y
con las producciones dadas en la forma BNF como sigue:
1.
2.
3.
4.
Figura 1
Obsérvese que en el número 3 del
enunciado BNF es recursivo en la segunda parte de su lado derecho. La figura
siguiente muestra el árbol de derivación, en esta gramática, para el número
decimal 23.14 .
Diagramas Sintácticos.
Son una representación gráfica
que permiten al usuario ver a las situaciones dinámicamente, esto es, se pueden
ver como movimientos a través del diagrama. Un enunciado BNF que incluye sólo
una producción única como :
producirá un diagrama como el de la figura 2(a).
Los símbolos que integran el lado derecho de la producción se dibujan en
sucesión de izquierda a derecha. Las flechas indican la dirección del
movimiento. Los rectángulos que encierran a w1, w2 y w3
muestran el hecho de que éstos son símbolos no terminales. Si hubiera símbolos
terminales se encerrarían en círculos o elipses.
Figura 2a
La figura 2(b) es la
representación de la producción:
En
este ejemplo se ilustra la situación donde existen varias producciones con el
mismo lado izquierdo. Donde, por convención, a, b y c son símbolos terminales.
Figura 2b
Ahora examinemos la producción
BNF :
El diagrama sintáctico se muestra
en la figura 2(c) :
Figura 2c
Si se pasa a través del ciclo una
vez, se encontrará a a, luego b y entonces se devuelve al punto inicial
designado por w. Esto representa la sustitución recursiva de abw por w. Varios
recorridos del diagrama representan varias sustituciones sucesivas. Por tanto,
si se atraviesa el diagrama tres veces y se retorna al punto inicial, se ve que
w se reemplazará por abababw en tres sustituciones sucesivas. Esto caracteriza
la manera en que el movimiento a través de un diagrama sintáctico representa el
proceso de sustitución.
Lo anterior muestra cómo se
construye un diagrama sintáctico de una producción recursiva normal. Las
producciones recursivas no normales no producen los diagramas simples
explicados con anterioridad, pero algunas veces es posible reemplazar la
producción recursiva no normal por una producción recursiva normal y obtener
una gramática que produzca el mismo lenguaje. Ya que las producciones
recursivas en una gramática regular deberán ser normales, los diagramas
sintácticos pueden usarse siempre para representar gramáticas regulares.
Obsérvese además que los
diagramas sintácticos de un lenguaje no son en absoluto únicos. No sólo
cambiarán cuando se utilicen diferentes producciones equivalentes sino que
podrán combinarse y simplificarse en una gran cantidad de maneras.
Examínese ahora la siguiente
producción BNF :
Si se construye el diagrama
sintáctico para w, usando las reglas explicadas, se obtendrá el diagrama de la
siguiente figura:
Figura 2d
Esto muestra que es posible
“escapar” de w, esto es, eliminar a w por completo, sólo al pasar a través de
la trayectoria superior. Por otro lado, se podrá atravesar el ciclo inferior
cualquier número de veces. Por tanto, cualquier movimiento a través del
diagrama que logre a la postre la eliminación completa de w por sustituciones
sucesivas producirá una secuencia de
símbolos de la forma (ab)n, n ³ 1.
Figura 2e
Es fácil ver que el simple
diagrama de la figura siguiente, que se produce al combinar las trayectorias de
la figura anterior de una manera obvia, es un diagrama sintáctico totalmente
equivalente. Este tipo de simplificaciones se harán siempre que sea posible.
Ejemplo 4.
Los
diagramas sintácticos de la figura 3(a) representan los enunciados en BNF del
ejemplo 2 construidos con las reglas originales para dibujar diagramas
sintácticos. Una versión un poco más estética se muestra en la figura 3(b) :
Figura 3a Figura 3b
Ejemplo
5
Las producciones del ejemplo 3, para los números decimales bien
formados, se incluyen en el diagrama sintáctico de la figura siguiente:
Figura 4
CONCLUSIONES:
Al
representar las gramáticas con la notación BNF, se presenta una ventaja al
utilizar los signos < >
encerrando los símbolos no terminales, para que se permita espacios entre las
palabras que lo forman, y esto ayuda a una mejor comprensión por parte del
programador en general, y comúnmente es utilizado por los lenguajes de programación
reales. También maneja lo que son las producciones
recursivas, y esto consiste en que un símbolo no terminal que aparece del lado
derecho de la producción, pueda ser definido después, pasando del lado derecho
de la producción, lo que da más claridad a la definición del lenguaje. La notación BNF utiliza diagramas sintácticos
que consisten en una representación gráfica que permite ver los movimientos
realizados a través del diagrama.
La combinación
de todos sus características da como resultado una notación sencilla de
entender, para después aplicarla.
GLOSARIO:
Gramáticas tipo 2
Lenguaje: conjunto de símbolos
cuyo objetivo es la comunicación.
Lenguajes de programación reales: están definidos por reglas preestablecidas, a las cuales se ajustan con todo rigor.
Gramática: conjunto
de reglas que definen un lenguaje.
Notación
Producción recursiva: una
producción que se llama así misma para ser definida más delante.
Producciones gramaticales
Secuencia
Símbolo no terminal: cuando la producción tiene asociada
otra producción.
Símbolo terminal: la
producción ya es la última, ya no hay más producciones asociadas.
REFERENCIAS:
Teoría de la computación.
Lenguajes
formales, autómatas y complejidad.
J. Glenn Brookshear.
Edit. Prentice Hall.
***********************************************************************