Construcción de analizadores sintácticos

Analizadores sintácticos

Concepto

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.

Su función es tomar el programa fuente en forma de tokens, que recibe del analizador léxico, y determinar la estructura de las sentencias del programa. Este proceso es similar a determinar la estructura de una frase en Castellano, determinando quien es el sujeto, predicado, el verbo y los complementos. El análisis sintáctico agrupa a los tokens en clases sintácticas (denominadas no terminales en la definición de la gramática), tales como expresiones, procedimientos, etc. El analizador sintáctico o parser obtiene un árbol sintáctico (u otra estructura equivalente) en la cual las hojas son los tokens, y cualquier nodo que no sea una hoja, representa un tipo de clase sintáctica (operaciones).

Características

• Lee componentes léxicos (tokens)

• Comprueba que el orden de estos corresponde a la sintaxis predeterminada

• Genera errores en caso de que el flujo de tokens no responda a la sintaxis

• Genera árboles de análisis sintáctico

• Se suele conocer como “Parser”

• El análisis sintáctico desarrolla el esqueleto de toda la fase de análisis

• Utiliza el analizador léxico como una rutina dentro del análisis sintáctico ( getNextToken() )

• Integra el análisis semántico como un conjunto de rutinas a ejecutar durante la comprobación de la sintaxis

• Aunque el objetivo teórico es construir un árbol de análisis sintáctico, este raramente se construye como tal, sino que las rutinas semánticas integradas van generando el árbol de sintaxis abstracta.

• El análisis sintáctico se especifica mediante una gramática libre de contexto

• El análisis sintáctico se implementa mediante un autómata de pila

Ventajas

Ventajas de los analizadores sintácticos LR Los analizadores sintácticos son construidos por tablas, similar a los analizadores sintácticos LL no recursivos. El análisis sintáctico LR es atractivo por varias razones:

Pueden construirse analizadores sintácticos LR para reconocer prácticamente todas las construcciones de lenguajes de programación para las cuales puedan escribirse gramáticas libres de contexto.

El método de análisis sintáctico LR es el método de análisis sintáctico de desplazamiento reducción sin rastreo hacia atrás más general que se conoce a la fecha.

Un AS LR puede detectar un error sintáctico tan pronto como sea posible en una exploración de izquierda a derecha en la entrada.

La clase de gramáticas que pueden analizarse mediante los métodos LR es un superconjunto propio de la clase de gramáticas que pueden analizarse con métodos predictivos o LL.

Desventajas

Su principal desventaja es que es demasiado trabajo construir un analizador sintáctico LR en forma manual para una gramática común de un lenguaje de programación. 

Aplicabilidad

Analizador de oraciones
Ayuda a mejorar la estructura y redacción de oraciones
Complemento y apoyo para la enseñanza de partes de una oración

Completo análisis de las relaciones sintácticas que se establecen entre los pares de palabras que la componen: su tipo de relación de dependencia, qué palabra es nuclear y cuál dependiente, su categoría gramatical y su posición en la frase.

*Que son las gramáticas ambiguas

Es un gramática libre del contexto para la que existe una cadena que puede tener más de una derivación a la izquierda, mientras una gramática no ambigua es una Gramática libre del contexto para la que cada cadena válida tiene una única derivación a la izquierda. Muchos lenguajes admiten tanto gramáticas ambiguas como no ambiguas, mientras otros lenguajes admiten solo gramáticas ambiguas. Cualquier lenguaje no vacío admite una gramática ambigua al tomar una gramática no ambigua e introducir una regla duplicada (el único lenguaje sin gramáticas ambiguas es el lenguaje vacío). Un lenguaje que solo admite gramáticas ambiguas se conoce como un Lenguaje Inherentemente Ambiguo, y existen lenguajes libres del contexto inherentemente ambiguos. Las gramáticas libres del contexto deterministas son siempre no-ambiguas, y son una subclase importante de GLCs no-ambiguas; existen GLCs no-deterministas y no-ambiguas simultáneamente.

*Eliminación de recursión izquierda en las gramáticas, arboles de sintaxis