5.0 ANÁLISIS SINTÁCTICO

5.1.  Aspectos generales de un analizador sintáctico

¿Qué es el analizador sintáctico ?



 Es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce.

 En teoría, se supone que la salida del analizador sintáctico es alguna representación del árbol sintáctico que reconoce la secuencia de tokens suministrada por el analizador léxico. En la práctica, el analizador sintáctico también hace:

 • Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador semántico).

 • Chequeo de tipos ( del analizador semántico). • Generar código intermedio.

 • Generar errores cuando se producen. En definitiva, realiza casi todas las operaciones de la compilación. 

Este método de trabajo da lugar a los métodos de compilación dirigidos por sintaxis. 

5.2.  Gramáticas y diseño de un árbol gramatical

Nosotros nos centraremos en el análisis sintáctico para lenguajes basados en gramáticas formales, ya que de otra forma se hace muy difícil la comprensión del compilador, y se pueden corregir, quizás más fácilmente, errores de muy difícil localización, como es la ambigüedad en el reconocimiento de ciertas sentencias.


 La gramática que acepta el analizador sintáctico es una gramática de contexto libre: 

• Gramática : G (N, T, P, S) N = No terminales. T = Terminales.

 P = Reglas de Producción. S = Axioma Inicial. Ejemplo : Se considera la gramática que reconoce las operaciones aritméticas. 

Å E Ú E + T Æ | T Ç T Ú T * F È | F É F Ú ID Ê | NUM Ë | ( E ) En el que: N = {E, T, F} están a la izquierda de la regla. T = {ID, NUM, ( ,) ,+ ,*} P = Son las siete reglas de producción. 

 S = Axioma inicial. Podría ser cualquiera, en este caso es E.

 • Derivaciones : La idea central es que se considera una producción como una regla de reescritura, donde el no terminal de la izquierda es sustituido por la cadena del lado derecho de la producción. 


De un modo más formal: . _ con ., (N F T)* , si con A N; 1, 2, / (N F T)*; y D VG E VWG A { { ½ ¾ ¿ } regla de producción A 2



Árbol sintáctico de una sentencia de un lenguaje


Es una representación que se utiliza para describir el proceso de derivación de dicha sentencia. Como nodos internos del árbol, se sitúan los elementos no terminales de las reglas de producción que vayamos aplicando, y tantos hijos como símbolos existan en la parte derecha de dichas reglas.

 Veamos un ejemplo:

 Sea la gramática anterior. E Ú E + T | T T Ú T * F | F F Ú ( E ) | a | b Supongamos que hay que reconocer: ( a + b ) * a + b Si el árbol puede construirse, es que la sentencia es correcta:

Ambigüedad: Una gramática es ambigua si derivando de forma diferente con el mismo
tipo de derivación se llega al mismo resultado.

Ejemplo: Considérese la gramática

E E + E
E E * E
E ( E )
E id | num
si tenemos aux + cont + i

 <ID><+><ID><+><ID

5.3.  Verificación de sintaxis y aplicación de reglas sintácticas

De la forma de construir el árbol sintáctico se desprenden dos tipos o clases de analizadores sintácticos. Pueden ser descendentes o ascendente 


• Descendentes :


 Parten del axioma inicial, y van efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia. Pueden ser:

  Con retroceso. Con recursión. LL(1) 


• Ascendentes:


 Parten de la sentencia de entrada, y van aplicando reglas de producción hacia atrás (desde el consecuente hasta el antecedente), hasta llegar al axioma inicial. Pueden ser: 

Con retroceso. LR(1)


Análisis descendente con retroceso


. • Objetivo : 


El método parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda. • Ejemplo:

 Utilizaremos la siguiente gramática (No recursiva por la izquierda) ± E Ú T + E ² E Ú T ³ T Ú F * T ´ T Ú F µ F Ú a ¶ F Ú b · F Ú (E) para reconocer la cadena de entrada: (a + b) * a + b

5.4.  Elaboración del PARSER

Visión general del proceso


El siguiente caso demuestra un caso común de análisis de un lenguaje de programación con dos niveles de gramática, léxica y sintáctica.

El primer estado es la generación de tokens o análisis léxico, en este proceso la cadena de entrada se parte en símbolos con significado definidos por una gramática de expresiones regulares,

por ejemplo un programa calculadora con la siguiente entrada: "12*(3+4)^2", la dividiría en los siguientes tokens 12, *, (, 3, +, 4, ), ^ y 2, cada uno de estos símbolos tiene un significado en el contexto de la expresión aritmética.

El analizador contendrá reglas para indicar que los símbolos *, +, ^, ( y ) indican el comienzo de un nuevo token, de modo que otros tokens que no tendrían sentido como 12 o 13 no se generarán.

El siguiente estado es el análisis sintáctico lo que significa comprobar que los tokens forman una expresión válida, esto se hace usualmente usando una gramática libre de contexto que define recursivamente componentes que pueden aparecer en una expresión y el orden en que estos deben aparecer. Las reglas que definen un lenguaje de programación no siempre se pueden expresar usando únicamente una gramática libre de contexto, por ejemplo la validación de tipos y la declaración correcta de identificadores. Estas reglas pueden expresarse formalmente usando gramáticas de atributos.

La fase final es el análisis semántico, que trabaja en las implicaciones de la expresión ya validada y realiza las actuaciones pertinentes. En el caso de la calculadora, la acción es evaluar la expresión. Un compilador por el contrario generará código. Las gramáticas de atributos pueden ser usadas también para definir estas acciones.



Análisis de dependencias





Diferencia entre un árbol de dependencia y un árbol de constituyentes

Otro método para realizar análisis sintáctico o parsing es utilizando gramáticas de dependencias, que surgen como una alternativa a las estructuras de frases.



​ En términos generales estas gramáticas definen una relación de dependencia entre cada elemento de una construcción (por lo general son oraciones pero también pueden ser solo frases) y su "cabeza" (o head ) .



Estos elementos pueden ser palabras, tokens, lemmas o incluso signos de puntuación. Adicionalmente se denomina a un elemento 0 o "raíz"(root) a la cabeza del constituyente principal, generalmente el verbo principal de la oración. Es importante no confundir dependencias con constituyentes, ya que las relaciones de dependencia generan pares únicos y ordenados.



Los criterios para determinar la cabeza H de un dependiente D en una construcción C son los siguientes:





1. H determina la categoría sintáctica de C y H puede reemplazar a C.

2. H determina la categoría semántica de C; D especifica a H.

3. H es obligatoria; D puede ser opcional.

4. H selecciona a D y determina si D es obligatoria.

5. La forma de D depende d H (agreement or government).

6. La posición linear de D es especificada con respecto a H.




Sin embargo estos criterios pueden generar contradicciones o inconsistencias con criterios morfológicos o semánticos y no siempre es claro si los dependientes son opcionales o no.

Ejemplo de un análisis de dependencias en inglés


La tarea de los analizadores de dependencias es, dada una oración, determinar las cabezas y el tipo de dependencia de cada uno de los elementos. La ventaja de utilizar este tipo de análisis es que se pueden evitar ciertos problemas en lenguajes con orden de palabras poco estricto.


Existen muchas formas distintas de clasificar los tipos de dependencias pero CoNLL (Conference on Computational Natural Language Learning)​ ha creado un formato para uso universal en análisis sintácticos de dependencias: CoNLL-U




Los resultados de los últimos sistemas en diferentes pruebas de análisis sintáctico han sido compilados en el sitio de la tarea compartida (shared task), en el 2017 la tarea consistió en crear un analizador plurilingüe, es decir capaz de analizar diferentes idiomas.