Analizador sintáctico (Parte I)
El analizador sintáctico recibe los tokens o palabras generadas por el analizador léxico y determina si la secuencia u orden que presentan es correcta y permitida por el lenguaje. La salida que generará será el árbol sintáctico.
Lo primero que tenemos que hacer es determinar la sintaxis del lenguaje y expresarla formalmente en notación BNF. Esta tarea es bastante sencilla.
Script ::= <Sentencias> FinFichero <Sentencias> ::= <Sentencia> . <Sentencias> | <Sentencia> <Sentencia> ::= <DeclaracionVariable> | <DeclaracionConstante> | <Asignacion> | <Condicional> | <Bucle> | <LlamadaAMetodo> <DeclaracionVariable> ::= Variable <Tipo> Identificador <Tipo> ::= Numerica | Cadena | Logica <DeclaracionConstante> ::= Constante Numerica Identificador = Cte_Numerica | Constante Cadena Identificador = Cte_Cadena | Constante Logica Identificador = Cte_Logica <Asignacion> ::= Identificador = <Expresion> <Condicional> ::= Si <Expresion> Entonces <Sentencias> <RestoCondicional> <RestoCondicional> ::= Sino <Sentencias> Fin Si | Fin Si <Bucle> ::= Mientras <Expresion> Hacer <Sentencias> Fin Mientras <LlamadaAMetodo> :: = Identificador <Parametros> <Parametros> ::= < UnoOMasParametros > | ε <UnoOMasParametros>::= <Expresion> , <UnoOMasParametros> | < Expresion > <Expresion> ::= <ExpresionSimple> <OperadorRelacional> <ExpresionSimple> | <ExpresionSimple> <OperadorRelacional> ::= < | > | <= | >= | = | != <ExpresionSimple> ::= < ExpresionSimple > <OperadorAditivo> < Termino> | <Termino> <OperadorAditivo> ::= + | - | O <Termino> ::= <Termino> <OperdoraMultiplicacion> <Operando> | <Operando> <OperadorMultiplicacion> ::= * | / | Y <Operando> ::= Identificador | Cte_Numerica | Cte_Cadena | Cte_Logica | ( <Expresion> )
Vamos a imponer que nuestra definición del lenguaje cumpla la condición LL(1), lo cual implica que a partir de un determinado símbolo no terminal solo existe una producción que se puede aplicar. Para lo cual hay que eliminar las ambigüedades, la recursividad inmediata por la izquierda y los prefijos comunes. Esto es algo más complicado y nos puede dar algún quebradero de cabeza.
1. <Sentencia> ::= <Asignacion>
2. <Sentencia> ::= <LLamadaAMetodo>
3. <Asignacion> ::= Identificador = <Expresion>
4. <LLamadaAMetodo> ::= Identificador <Parametros>
En este ejemplo el lenguaje no cumpliría la condición LL(1) ya que si el símbolo que leemos es un identificador se podrían aplicar tanto la producción uno como la dos.
Para comprobar que cumple la condición LL(1) hemos de calcular los símbolos directores, es decir aquellos símbolos terminales que nos guiarán para elegir una determinada producción entre todas aquellas que tengan la misma parte izquierda. De tal forma que cuando tengamos un determinado no terminal y leamos un símbolo por adelantado solo exista una producción que tenga el no terminal por parte izquierda y el símbolo por adelantado como símbolo director. En el ejemplo anterior tendríamos como símbolo director de todas las producciones el no terminal “Identificador”, por lo tanto si tenemos el no terminal <Sentencia> y leemos el símbolo “Identificador” no podríamos decantarnos por ninguna de las dos producciones (la uno o la dos).
El calculo de los directores es una tarea sumamente tediosa y es fácil cometer algún error. Numeramos las producciones para poder identificarlas más fácilmente.
1 <Script> ::= <Sentencias> FinFichero Dir = Inic(Sentencias) = Inic(Sentencia) = Inic(DeclaracionVariable) U Inic(DeclaracionConstante) U Inic(Asignacion_O_LlamadaAMetodo) U Inic(Condicional) U Inic(Bucle) = Variable Constante Identificador Si Mientras 2 <Sentencias> ::= <Sentencia> . <Resto_Sentencias> Dir = Inic(Sentencia) = Inic(DeclaracionVariable) U Inic(DeclaracionConstante) U Inic(Asignacion_O_LlamadaAMetodo) U Inic(Condicional) U Inic(Bucle) = Variable Constante Identificador Si Mientras 3 <Resto_Sentencias> ::= <Sentencias> Dir = Inic (sentencias) = Variable Constante Identificador Si Mientras 4 <Resto_Sentencias> ::= ε Dir = Seg(Resto_Sentencias) = Seg(Sentencias) = FinFichero U Fin U Sino U Seg(Resto_Sentencias) = FinFichero Fin Sino 5 <Sentencia> ::= <DeclaracionVariable> Dir = Variable 6 <Sentencia> ::= <DeclaracionConstante> Dir = Constante 7 <Sentencia> ::= <Asignacion_O_LlamadaAMetodo> Dir = Identificador 8 <Sentencia> ::= <Condicional> Dir = Si 9 <Sentencia> ::= <Bucle> Dir = Mientras 10 <DeclaracionVariable> ::= Variable <Tipo> Identificador Dir = Variable 11 <Tipo> ::= Numerica Dir = Numerica 12 <Tipo> ::= Cadena Dir = Cadena 13 <Tipo> ::= Logica Dir = Logica 14 <DeclaracionConstante> ::= Constante <Resto_Constante> Dir = Constante 15 <Resto_Constante> ::= Numerica Identificador = Cte_Numerica Dir = Numerica 16 <Resto_Constante> ::= Cadena Identificador = Cte_Cadena Dir = Cadena 17 <Resto_Constante> ::= Logica Identificador = Cte_Logica Dir = Logica 18 <Condicional> ::= Si <Expresion> Entonces <Sentencias> <Resto_Condicional> Dir = Si 19 <Resto_Condicional> ::= Sino <Sentencias> Fin Si Dir = Sino 20 <Resto_Condicional> ::= Fin Si Dir = Fin 21 <Bucle> ::= Mientras <Expresion> Hacer <Sentencias> Fin Mientras Dir = Mientras 22 <Asignacion_O_LlamadaAMetodo> ::= Identificador <Resto_Asignacion_O_LlamadaAMetodo> Dir = Identificador 23 <Resto_Asignacion_O_LlamadaAMetodo> ::= = <Expresion> Dir = = 24 <Resto_Asignacion_O_LlamadaAMetodo> ::= <Parametros> Dir = Inic(UnoOMasParametros) U Seg(Parametros) = Inic (Expresion) U Seg(Resto_Asignacion_O_LlamadaAMetodo) = Inic(ExpresionSimple) U Seg(Asignacion_O_LlamadaAMetodo) = Inic(Termino) U Seg(Sentencia) = Inic(Operando) U . = Identificador Cte_Numerica Cte_Cadena Cte_Logica ( . 25 <Parametros> ::= <UnoOMasParametros> Dir = Inic (UnoOMasParametros) = Inic(Expresion) = Inic(ExpresionSimple) = Inic(Termino) = Inic(Operando) = Identificador Cte_Numerica Cte_Cadena Cte_Logica ( 26 <Parametros> ::= ε Dir = Seg(Parametros) = Seg(Resto_Asignacion_O_LlamadaAMetodo) = Seg(Asignacion_O_LlamadaAMetodo) = Seg(Sentencia) = . 27 <UnoOMasParametros>::= <Expresion> <Resto_UnoOMasParametros> Dir = Inic(Expresion) = Inic(ExpresionSimple) = Inic(Termino) = Inic(Operando) = Identificador Cte_Numerica Cte_Cadena Cte_Logica ( 28 <Resto_UnoOMasParametros>::= , <UnoOMasParametros> Dir = , 29 <Resto_UnoOMasParametros>::= ε Dir = Seg(Resto_UnoOMasParametros) = Seg(UnoOMasParametros) = Seg(Parametros) = Seg (Resto_Asignacion_O_LlamadaAMetodo) = Seg(Asignacion_O_LlamadaAMetodo) = Seg(Sentencia) = . 30 <Expresion> ::= <ExpresionSimple> <Resto_Expresion> Dir = Inic(ExpresionSimple) = Inic(Termino) = Inic(Operando) = Identificador Cte_Numerica Cte_Cadena Cte_Logica ( 31 <Resto_Expresion> ::= <OperadorRelacional> <ExpresionSimple> Dir = Inic(OperadorRelacional) = < > <= >= = != 32 <Resto_Expresion> ::= ε Dir = Seg(Expresion) = Entonces U Hacer U ) U , U Seg(Resto_Asignacion_O_LlamadaAMetodo) = Entonces U Hacer U ) U Seg(Asignacion_O_LlamadaAMetodo) = Entonces U Hacer U ) U Seg(Sentencia) = Entonces Hacer ) , . 33 <OperadorRelacional> ::= < Dir = < 34 <OperadorRelacional> ::= > Dir = > 35 <OperadorRelacional> ::= <= Dir = <= 36 <OperadorRelacional> ::= >= Dir = >= 37 <OperadorRelacional> ::= = Dir = = 38 <OperadorRelacional> ::=!= Dir = != 39 <ExpresionSimple> ::= <Termino> <Resto_ExpresionSimple> Dir = Inic(Termino) = Inic(Operando) = Identificador Cte_Numerica Cte_Cadena Cte_Logica ( 40 <Resto_ExpresionSimple> ::= <OperadorAditivo> <ExpresionSimple> Dir = + - O 41 <Resto_ExpresionSimple> ::= ε Dir = Seg(Resto_ExpresionSimple) = Seg(ExpresionSimple) = Inic(Resto_Expresion) U Seg(Expresion) U Seg(Resto_Expresion) U Seg(Resto_ExpresionSimple) = Inic(OperadorRelacional) U Entonces U Hacer U ) U , U . U Seg(Resto_Asignacion_O_LlamadaAMetodo) U Seg(Expresion) = < > <= >= = != U Entonces U Hacer . U ) 42 <OperadorAditivo> ::= + Dir = + 43 <OperadorAditivo> ::= - Dir = - 44 <OperadorAditivo> ::= O Dir = O 45 <Termino> ::= <Operando> <Resto_Termino> Dir = Inic(Operando) = Identificador Cte_Numerica Cte_Cadena Cte_Logica ( 46 <Resto_Termino> ::= <OperadorMultiplicacion> <Termino> Dir = * / Y 47 <Resto_Termino> ::= ε Dir = Seg(Resto_Termino) = Seg(Termino) = Inic (Resto_ExpresionSimple) U Seg(ExpresionSimple) = Inic(OperadorAditivo) U Inic(Resto_Expresion) U Seg(Expresion) U Seg(Resto_Expresion) U Seg(Resto_ExpresionSimple) = + - O U Inic(OperadorRelacional) U Entonces U Hacer U . U , U Seg(Resto_Asignacion_O_LlamadaAMetodo) U Seg(Expresion) = + - O U < > <= >= = != U Entonces U Hacer U . U , U ) U Seg(Sentencia) = + - O U < > <= >= = != U Entonces U Hacer U . U ,U ) U Inic(Resto_Sentencias) = + - O U < > <= >= = != U Entonces U Hacer U . U , U ) 48 <OperadorMultiplicacion> ::= * Dir = * 49 <OperadorMultiplicacion> ::= / Dir = / 50 <OperadorMultiplicacion> ::= Y Dir = Y 51 <Operando> ::= Identificador Dir = Identificador 52 <Operando> ::= Cte_Numerica Dir = Cte_Numerica 53 <Operando> ::= Cte_Cadena Dir = Cte_Cadena 54 <Operando> ::= Cte_Logica Dir = Cte_Logica 55 <Operando> ::= ( <Expresion> ) Dir = (
Continuación
Analizador sintáctico (Parte II)
Septiembre 21st, 2006 at 12:22
Una sugerencia: ¿Por qué no hacer una producción ::= ε ?
Eso permitiria hacer bloques de sentencias vacios, por ejemplo dentro de un bucle, que a la hora de programar es bastante útil si aun no sabes lo que tienes que poner, y quieres dejar solo un comentario de momento.
Y otra cosa, ¿como van a funcionar los tipos? Porque viendo la gramática no me queda claro. Estoy suponiendo que el identificador es directamente un token (el nombre de la variable), por lo que no permites tipos construidos como arrays y similares, ¿me equivoco?
Un blog muy util, por cierto
Septiembre 21st, 2006 at 12:23
Vale, se ha comido la parte izquierda de la produccion al poner el comentario. Me estaba refieriendo a Sentencias ::= ε
Septiembre 21st, 2006 at 23:49
Si, las producciones vacías si las utilizo por ejemplo en las producciones 4, 26, 29, 32 y en alguna más.
Los arrays no están implementados y son necesarios. La razón de que no estén es muy tonta, se me pasó al implementarlo (un lapsus) y luego me dio pereza. De todas formas quiero implementarlo mas adelante.
Un saludo y gracias por los comentarios.
Junio 7th, 2007 at 22:41
Hola,
Bueno yo ya tengo realizado mi analizador lexico en visual basic .net, ahora necesito hacer un analizador sintactico, pero la verdad no entendi muy bien esto…
entiendo como determinar la sintaxis de mi lenguaje, lo q no entiendo es como implementarlo…
Mi analizador lexico me guarda un archivo .txt que contiene los tokes, ejemplo:
PalReservada, using
PalReservada, system
PuntoYComa, ;
etc…
Como puedo implementar una clase para el analizador sintactico..
Mas que nada es como usar en mi codigo la sintaxis del lenguaje…
Estoy extremadamente confundido, espero me puedan ayudar…
Gracias..
Junio 8th, 2007 at 16:36
Buenas
Echale un vistazo a la segunda parte de este artículo Analizador sintáctico (Parte II) está explicado como implementarlo.
Basicamente consiste en ir leyendo los tokens que ya tienes e ir aplicando las producciones. En el segundo articulo viene más detallado.
Saludos