Programacion de sistemas

Unidad IV Análisis Sintáctico
M.C. Juan Carlos Olivares Rojas

Agenda
4.1 Introducción a las Gramáticas libres de contexto y árboles de derivación. 4.2 Diagramas de sintaxis. 4.3 Precedencia de operadores. 4.4 Analizador sintáctico. 4.4.1 Analizador descendente (LL). 4.4.2 Analizador ascendente(LR, LALR).

Agenda
• 4.5 Administración de tablas de símbolos • 4.6 Manejo de erroressintácticos y su recuperación • 4.7 Generadores de código analizadores sintácticos: Yacc, Bison para

4.1 Introducción a las Gramáticas libres de contexto y árboles de derivación
• Todo lenguaje posee una serie de reglas para describir los programas fuentes (sintaxis). • Un analizador sintáctico implementa estas reglas haciendo uso de GICs

Gramáticas
• Son un formalismo matemático que permitedecidir si una cadena pertenece a un lenguaje dado. • Se define como la cuarteta G= (N, Σ, S, P), en donde N es el conjunto de símbolos terminales, Σ es conjunto de símbolos terminales, S es el símbolo inicial (S pertenece a N) y P es un cojunto de reglas de producción.

Gramáticas
• Los símbolos no terminales (N) son aquellos que pueden seguir derivando en otros; mientras que los terminales elproceso finaliza allí. • Las reglas de producción siguen el formato: α β donde α y β pertenecen a N y Σ en cualquier forma.

Reglas de producción
• Son las reglas que permiten decidir si la cadena pertenece a un lenguaje y la estructura que lleva: • S A|aB • A aA|bC • S B C ε ε

Genera cadenas del lenguaje a*b u a

Tipos de gramáticas
• Las gramáticas más sencillas son las gramáticasregulares, debido a que no presentan anomalías de ningún tipo. Desafortunadamente este tipo de gramáticas no permiten expresar todos los lenguajes posibles y en especial los humanos por lo que se necesitan otros tipos de gramáticas. Las más utilizadas en informáticas son las libres del contexto.

Gramáticas Regulares
• Son las que se forman a través de Autómatas Finitos Deterministas y Expresionesregulares. No presentan ambiguedades. • Sus reglas de producción son del tipo: α β donde α pertenece a N y β pertenece a (Σ)* N?

Gramáticas Independientes del Contexto
• Son aquellas G cuya reglas de producción son de la forma: α β, en donde α pertenece a N y β pertenece (N u Σ)* • Las ventajas de uso de GICs son: • Proporcionan una estructura precisa y fácil de comprender sintácticaGramáticas Independientes del Contexto
• Proporciona al lenguaje fuente una estructura adecuada para la generación del código. • Por medio de las GICs analizadores sintácticos es fácil construir

• Es sencillo añadir funcionalidades a un analizador sintáctico

GICs
• Hay que revisar que la gramática no sea inherentemente ambigua para poder eliminar esa ambigüedad o rediseñar la gramática sinanomalías. • Algunas formas de eliminar esa ambigüedad es utilizando técnicas como algoritmos CYK y las formas normales de Chomsky (FNCh) y Greibach (FNG).

Ejemplos de GICs
• Expresiones válidas en lenguajes C: Expr (expr) | - expr | expr op expr| VAR | NUM • Error sintáctico: cuando la secuencia de componentes léxicos no puede ser generada por la gramática del lenguaje fuente.

Ejemplos deGICs
• Declaración de variables en C: Decl TIPO listavar PYC var | var COMA listavar Listavar Var ID | ASTER var Dimension CI ENTERO CD |CI ENTERO CD dimension

Jerarquía de Chomsky
• Las otras dos gramáticas en las cuales clasificó Chomsky (GR tipo 3, GIC tipo 2) son las gramáticas sensible al contexto (tipo 1, donde |α| < |β|, donde α y β pertenecen a (Σ u N)* salvo ε) y las gramáticas deltipo 0 o sin restricciones, las cuales sus reglas de producción pueden ser de cualquier tipo.

Árboles de Derivación
• Es la representación gráfica de la derivación de una cadena. • Se crea utilizando el símbolo inicial como la raíz, los símbolos N representan nodos del árbol y los símbolos Σ las hojas del árbol. • A través de los árboles de derivación se puede verificar la sintaxis de un...