• Author / Uploaded
• Lupita Gómez Mercado

Citation preview

TECNOLOGICO DE ESTUDIOS SUPERIORES DE IXTAPALUCA

ING. EN SISTEMAS COMPUTACIONALES

ASIGNATURA: PROGRAMACION DE SISTEMAS

(ANALOGIA DE LOS TEMAS EN CLASE)

PROF.: GARCIA CORTES DAVID

ALUMNA: GOMEZ MERCADO GUADALUPE

GRUPO: 1502

MATRICULA: 200920834

FECHA DE ENTREGA: 30 DE ENERO DE 2012

INDICE 1

Introducción………………………………………………………………… ……………………………….6 Unidad I.- Introducción a la programación de Sistemas…………………………………7 1.1 ¿Qué es y que estudia la programación de sistemas? 1.2 Herramientas desarrolladas con la teoría de P.S. 1.3 Lenguajes 1.3.1 Lenguajes naturales 1.3.2 Lenguajes artificiales 1.3.3 Proceso de la comunicación 1.4 Traductor y su estructura 1.4.1 Ensambladores 1.4.2 Compiladores 1.5.3Interpretes 1.5 Generadores de código para compiladores (compilador de compilador) Unidad II Introducción al diseño de los lenguajes de programación…………..12 2.1 Visión del problema 2.2 Consideraciones preliminares 2.3 Objetivos y filosofías del diseño de los lenguajes de programación 2.4 Diseño detallado 2.5 Caso de estudio

2

Unidad III Análisis Léxico………………………………….. …………………………………………15 3.1 Introducción a los Autómatas finitos y expresiones regulares. 3.2 Analizador de léxico. 3.3 Manejo de localidades temporales de memoria (buffers). 3.4 Creación de tablas de símbolos. 3.6 Manejo de errores léxicos. 3.6 Generadores de código léxico: Lex y Flex. Unidad IV Análisis Sintáctico……………………………….. ……………………………………..23 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). 4.5 Administración de tablas de símbolos 4.6 Manejo de errores sintácticos y su recuperación 4.7 Generadores de código para analizadores sintácticos: Yacc, Bison.

3

Unidad V Análisis Semántico ………………………………………………………………………35 5.1 Analizador semántico 5.2 Verificación de tipos en expresiones. 5.3 Conversión de tipos. 5.4 Acciones agregadas en un analizador sintáctico descendente (top-down). 5.5 Pila semántica en un analizador sintáctico ascendente (bottom-up). 5.7 Administración de la tabla de símbolos. 5.7 Manejo de errores semánticos. Unidad VI Generación de Código Intermedio ……………………………………………41 6.1 Lenguajes intermedios. 6.2 Notaciones. 6.2.1 Infija. 6.2.2 Postfija. 6.2.3 Prefija. 6.3 Representación de código intermedio. 6.3.1 Notación Polaca. 6.3.2 Código P. 6.3.3 Triplos. 6.3.4 Cuádruplos. 6.4 Esquemas de generación. 4

6.4. Expresiones. 6.4. Declaración de variables, constantes 6.4. Estatuto de asignación. 6.4. Estatuto condicional. 6.4. Estatuto de ciclos 6.4. Arreglos. 6.4. Funciones. Unidad VII Optimización………………………………………………………………… ……………46 7.1 Tipos de optimización. 7.1.1 Locales. 7.1.2 Bucles. 7.1.3 Globales. 7.1.4 De mirilla. 7.2 Costos. 7.2.1 Costo de ejecución. 7.2.2 Criterios para mejorar el código. 7.2.3 Herramientas para el análisis del flujo de datos.

Unidad VIII Generación de código intermedio ……………………………………………49 8.1 Lenguaje máquina. 5

8.1.1 Características. 8.1.2 Direccionamiento. 8.2 Lenguaje ensamblador. 8.2.1 Características. 8.2.2 Almacenamiento. 8.3 Registros. 8.3.1 Distribución. 8.3.2 Asignación. 8.4 Administración de memoria. Bibliografía………………………………………………………………… ……………………………..53

6

INTRODUCCION En esta antología tenemos un resumen de todo lo visto durante la asignatura de programación de sistemas. Esta asignatura es muy importante para la carrera de ing. En sistemas computacionales ya que tocan temas fundamentales de ella. La programación es un sistema es un conjunto de componentes que se relacionan entre si, para lograr un objetivo común. Las personas se comunican en un lenguaje que es un sistema formado por palabras y símbolos que tienen un significado para quien lo habla y quien loe escucha, lo mismo es para las computadoras. La programación consta de convertir las especificaciones de los sistemas en instrucciones de máquina que producen resultados deseados.

7

Unidad I Introducción a la programación de Sistemas 1.1 ¿Qué es y qué estudia la programación de sistemas? • Programa: conjunto de instrucciones que ejecuta una computadora para realizar una actividad. • Sistema: conjunto de elementos autónomos que trabajan en armonía para alcanzar un objetivo en común. Tipos de sistemas • Sistemas físicos: reales, Hardware

equipo,

maquinaria,

objetos

• Sistemas abstractos: ideas, hipótesis, conceptos, planes, Software • Sistemas abiertos y cerrados dependiendo del ambiente en que se ejecutan. Características de un sistema • Un sistema puede interactuar con su medio ambiente a través de una interfaz de entradas y salidas que recibe el nombre de parámetros del sistema. • Un sistema puede ser componente de otro sistema 1.2 Herramientas desarrolladas con la teoría de programación de sistemas

8

El caso más sencillo de programación de sistemas es la construcción de compiladores para ejecutar lenguajes de programación. Pero no sólo se aplica en lenguajes de programación, sino también se aplica en cualquier programa que se tenga que hacer un análisis o extracción de información Software de sistemas Editores de texto inteligentes (IDEs con autocompletar, revisores ortográficos, etc) Impresoras estéticas (impresión de gran calidad sin un editor visual, Latex, etc.) Intérpretes (Shells de sistemas operativos o de alguna aplicación como un SMBD) Búsqueda de información que no es tan común en base a patrones, etc. 1.3 Lenguajes Conjunto de palabras y reglas que permiten comunicar información entre dos entidades. El lenguaje que entienden las máquinas (lenguaje formal) es muy diferente del lenguaje que entendemos los humanos • Lenguaje: Son las cadenas que pueden generarse a través de una gramática Repaso de lenguajes y autómatas • Símbolo: representación abstracta de alguna entidad •

Alfabeto: conjunto finito de símbolos

• Cadena: yuxtaposición de símbolos de un alfabeto que representan a un objeto 9

• Lenguaje: conjunto de cadenas válidas que se pueden formar a través de un alfabeto 1.3.1 Lenguajes naturales El lenguaje natural es inherentemente ambiguo, por lo que se necesita crear un lenguaje que permita eliminar esas ambigüedades, es mejor crear otro lenguaje, denominado de alto nivel que es el encargado de mediar entre la abstracción humana y la abstracción de lenguaje de máquina 1.3.2 Lenguajes artificiales Los lenguajes artificiales son aquellos que los humanos hemos creado para comunicarnos • Las computadoras sólo saben 0 y 1 • Un lenguaje artificial permite implementar un algoritmo en una computadora para resolver un problema. Lenguajes de bajo nivel • Una abstracción más entendible del lenguaje máquina es el uso de lenguajes ensambladores en donde cada instrucción o mnemónico es traducido a una instrucción máquina. • ADD AX, 5 • LOAD A, 5

10

Lenguajes máquina El lenguaje máquina es dependiente de cada tipo de arquitectura de computadoras por lo que el código no es fácilmente portable a otras arquitecturas. Los lenguajes de alto nivel son más portables en lo que respecta al código fuente pudiendo llevarse a otras arquitecturas de computadoras sin mayor problema. Clasificación de Chomsky • Lenguajes sin restricciones (gramática 0) • Lenguajes dependientes del contexto (tipo 1) • Lenguajes independientes del contexto (tipo 1.3.3 Proceso de la comunicación Para entablar una comunicación se necesita que tanto el emisor como el receptor conozcan el mismo lenguaje o en su defecto tengan un traductor. En este sentido, los humanos escribimos algoritmos en un lenguaje formal que una computadora pueda transformar a un lenguaje entendible por ella. 1.4 Traductor y su estructura Un traductor es un mediador entre dos entidades: emisoras y receptoras, los mediadores enmascaran la complejidad y heterogeneidad de los lenguajes, un traductor convierte un lenguaje de entrada (código fuente) a uno de salida (código objeto). La traducción puede ser sencilla (literal) o compleja (revisar el contexto) dependiendo del tipo de lenguaje de entrada y salida.

11

Traducción español a inglés si se hace de manera literal es una mala traducción, se necesita de al menos otra revisión (pasada) para hacer una buena traducción. 1.4.1 Ensambladores Ensamblador es el traductor que se encarga de convertir instrucciones de bajo nivel a instrucciones de una máquina en general. //Encabezados 00 MOV AX, 58d 4F0188 03 CMP 0 3A00 05 JMP etiqueta 9918 … Etiqueta: 18 MUL AX, FF 4401FF 1.4.2 Compiladores Es el traductor que se encarga de convertir un lenguaje de alto nivel a código máquina. La característica de este traductor radica en el hecho de que necesita revisar todo el código fuente para poder realizar la traducción. Ejemplo: la traducción de un libro, discurso, o artículo técnico o de investigación Ejemplos de compiladores: C, C++, Pascal, etc. Entre más pasadas se de a un código fuente mayor es la optimización que se puede hacer. El problema radica en el tiempo y en los recursos para hacerlo 12

Antes de compilar un programa fuente se sigue una etapa de Pre procesamiento. Preprocesadores: Macros (expansión de funciones) Inclusión de archivos (bibliotecas) Procesadores racionales Extensiones al leguaje (inclusión de ensamblador en C) 1.4.3 Intérpretes Se ejecutan línea por línea, instrucción por instrucción. Lenguajes interpretados: PHP, PERL, BASIC En algunas ocasiones se necesita de una traducción rápida de algunas instrucciones, como en el Shell, instrucciones SQL, etc. ¿Java es compilado o interpretado? Java al igual que otros lenguajes como C# son lenguajes híbridos. Por una parte se compila un programa fuente para generar código objeto para una máquina virtual (bytecode o MSIL) para posteriormente ejecutarse de manera interpretada en las diferentes máquinas virtuales de cada plataforma. A este compilador se les llama jitter de JIT (Just in Time).

1.5 Generadores de código para compiladores (compilador de compilador)

13

Los dos primeros lenguajes de alto nivel desarrollado fueron FORTRAN y COBOL. Desarrollar FORTRAN tardó alrededor de 14 años. Desarrollar nuestro compilador tardará menos de 6 meses Son herramientas que auxilian algún aspecto del proceso de traducción Herramientas auxiliares para programación de sistemas • Cargadores y editores de enlace • Generadores de analizadores léxico • Generadores de Analizadores sintácticos • Traductores dirigidos por sintaxis • Generadores automáticos de código • Dispositivos para el análisis de flujo de datos

14

Unidad II Introducción programación

al

diseño

de

los

lenguajes

de

2.1 Visión del problema ¿Cuál es el propósito de un lenguaje? Los lenguajes de computación pueden ser de propósito general o específicos. C, C++, Java, Pascal, etc. Son lenguajes de programación de propósito general SQL, PROMELA, Actionscripts son lenguajes específicos ¿Por qué tal diversidad de lenguajes? Los lenguajes de programación son como los carros, existen para todos los gustos y/o usos. ¿Quién cargaría una tonelada de papas en un auto deportivo? Los lenguajes de propósito general son como los autos sedán, sirven para casi todo Se debe identificar que es lo que se piensa hacer con el lenguaje, ya que puede ser sólo la estructuración de contenido Web, visualizar información o bien realizar la conversión de un documento. HTML es lenguaje de representación visual OWL es lenguaje de descripción de elementos

15

C es un lenguaje programación 2.2 Consideraciones preliminares Debemos tomar en cuenta las palabras reservadas del lenguaje, los operadores, los tipos de datos. Debemos considerar el objetivo del lenguaje, si es un lenguaje de enseñanza, si es un lenguaje para profesionales, si el código desarrollado va a ser mejor. 2.3 Objetivos y filosofías del diseño de los lenguajes de programación Algunos usos de los lenguajes de programación son: – Comunicación humana – Prevención y Detección de errores – Usabilidad – Portabilidad – Independencia de la máquina Filosofías Es más importante que un programa sea leíble que escribible, ya que un programa generalmente se escribe una vez y se lee muchas veces (documentación, mantenimiento, etc.) La tendencia actual implementación es separa la interfaz de la Tratar de hacer lenguajes para múltiples arquitecturas de computadoras (máquinas virtuales) Control de apuntadores Control de tipo de datos robustos

16

Simplicidad por eficiencia 2.4 Diseño detallado • Considerar características como: – Patrones de diseño – Paquetes (bibliotecas, APIs, componentes) – Excepciones – Validaciones – Marco de trabajo – Utilerías auxiliares (preprocesador, enlazador) – Inclusión de otros lenguajes 2.5 Caso de estudio Explicar el lenguaje que se va a desarrollar en el curso: – ¿Por qué se va a desarrollar (problemática)? – Vocabulario del lenguaje (léxico palabras clases que hacen) – Reglas de estructura (gramática, sintaxis) – Semántica – Si existe código intermedio – Si se mejora ese código – El código objeto final

17

Unidad III Análisis Léxico 3.1 Introducción a los Autómatas finitos y expresiones regulares ¿Qué es un autómata? Es un modelo matemático que sirve para determinar si una cadena pertenece a un lenguaje no. 18

M=(Q, , &, F) – Q = conjunto de estados = alfabeto de entrada – & = funciones de transición – F = conjunto de estados de aceptación Autómatas finitos La característica que tienen los autómatas finitos es que solo existe una función de transición definida para un símbolo de entrada. Esto elimina ambigüedades • Una expresión regular representar lenguajes:

es

una

forma

abreviada

de

• a Representa el lenguaje de las letras a • a* Representa el lenguaje que tiene 0 hasta n a’s Autómatas • Oprel

|=|=|

• Un solo autómata varios sub_autómatas • Programar un autómata: • Identificador

letra (letra|digito|gb)*

Expresión Regular Generar la expresión electrónicos válidos.

regular

Formato: 19

para

identificar

correos

[email protected] id@dominio Expresiones Regulares y una gramática Una gramática sirve para generar cadenas de un determinado lenguaje pero también sirve para generarla. Existente una relación uno a uno entre Lenguajes, Autómatas, Expresiones regulares y gramáticas. Gramática de un if prop _ if expr then prop | if expr then prop else prop |_ expr _ termino oprel termino | termino termino _ id | num oprel _ < |>|=|=| id _ letra (letra | digito)* num _ digito+ (.digito+)?(E(+|-)?digito+)? eb _ delim+ delim _ blanco | tab | linenueva 3.2 Analizador Léxico • Primera fase de la compilación • Leer caracteres de entrada y generar como salida una secuencia de componentes léxicos • Eliminar espacios en blanco • Eliminar comentarios • Proporcionar información acerca de errores léxicos

20

Análisis Léxico El análisis lineal, se llama léxico o exploración. Posicion := inicial + velocidad * 60 Posicion: identificador := símbolo de asignación Inicial: identificador +: signo de suma Velocidad: identificador *: signo de multiplicación 60: numero Se elimina todos los espacios en blancos (espacios, tabuladores, salto de línea, etc. Reconocedores de identificadores y palabras clave. La tabla de símbolo debe insertar y buscar componentes léxicos. La tabla de símbolos es utilizada por el analizador sintáctico y por otras fases del proceso de traducción Un patrón es una regla que describe el conjunto de lexemas que puede representar a un conjunto léxico. Los componentes léxicos se tratan como terminales de la gramática del lenguaje fuente. La devolución de un componente léxico se hace a través de un número entero. Especificación de componentes léxicos Expresiones regulares (patrón). Cada patrón concuerda con una serie de cadenas. Las expresiones regulares dan el nombre al conjunto de cadenas con que concuerdan. Expresiones regulares 21

Se construyen a partir de otras expresiones regulares más simples, cada expresión regular r, representa un lenguaje L(r) • Letraaubucu…uz • Dígito1u2u3u…u0 • Identificador letra(letra u dígito)* Abreviaturas • * cero o más casos • + uno o más casos • [a-zA-Z] mayúsculas y minúsculas • [0-9] dígitos • ? Cero o un caso 3.3 Manejo de localidades temporales de memoria (buffers) • La forma más fácil de leer un programa es carácter por carácter pero es ineficiente. • La forma más eficiente es realizar una copia a la memoria de todo el código fuente. Pero esto en la gran mayoría de las ocasiones es impráctico por las dimensiones de los programas. Para solucionar este problema se sugiere utilizar buffers Manejo de buffers Existen muchas formas de dividir el trabajo, pero siempre se deberá llevar dos punteros, uno al carácter actual y otro al inicial del lexema. El manejo de buffers es esencial para realizar el análisis de grandes programas de mejor manera 3.4 Creación de tablas de símbolos

22

En general el proceso de análisis léxico puede describirse simplemente como el reconocimiento de caracteres de un lenguaje para generar una tabla de símbolos. El primer paso consiste en crear un escáner, el cual se encarga de verificar que no existan caracteres no presentes en el lenguaje. Tabla de símbolos La tabla de símbolos va a guardar cada palabra analizada, la va identificar como un lexema y le va asociar un identificador numérico para posteriormente utilizarlo. La tabla de símbolos debe estar en memoria para realizar un análisis rápido. 3.5 Manejo de errores léxicos • Son pocos los errores que se pueden detectar al hacer análisis léxico • fi (a == f(x)) //Error de sintaxis • Pero puede existir algún error si ninguno de los patrones con cuerda con el prefijo de entrada Técnicas de recuperación de errores • Borrar un carácter extraño • Insertar un carácter que falta • Reemplazar un carácter incorrecto por otro correcto • Intercambiar dos caracteres adyacentes Técnicas para realizar analizadores léxicos

23

• Utilizar un analizador léxico como FLEX. El generador se encarga de manejar buffers • Escribir el analizador en un lenguaje de alto nivel haciendo uso de la E/S del lenguaje • Escribir el lenguaje ensamblador y manejar explícitamente la E/S Análisis Léxico en XML • El análisis léxico en documentos XML lo realiza cualquier herramienta o API que utilice XML, ya que debemos cerciorarnos que el lenguaje esté bien formado. • Si el lenguaje no cumple con las reglas de construcción de documentos XML, falla el proceso. • Realizar análisis léxico de XML en Java o C# 3.6 Generadores de código léxico: Lex y Flex FLEX es la versión de software libre del popular generador de analizadores léxicos LEX para sistemas *NIX, genera código C aunque existen otras herramientas que generan código en otros lenguajes • Analizador.lex

flex

lex.yy.c

Programa ejecutable analizador • $gcc lex.yy.c –o analizador –lfl

Programa Lex %{ Definiciones globales ‘C’ 24

gcc

}% Definiciones flex %% Acciones %% Código ‘C’ auxiliar Definiciones regulares en flex %% Separadores de secciones Def

expresión

Acciones {def} {código ‘C’ asociado} “@” {código ‘C’ asociado} Programa que reconoce flotantes % { #include Int ocurrencias; }% Digito[0-9] Punto [\.] Exp [eE] Signo[\+\-] Digitos {digito}+ 25

Decimal {punto} {digitos}({exp}{signo}{digitos})? Flotante {digitos}{decimal}? Programa que reconoce flotantes % % {flotante} { printf(“flotante encontrado\n”) ocurrenicas++; } “@” { printf(“Arroba\n”); } . { printf(“Inválido: %s\n”, yytext); } %% main(int argc, char *argv[]) { FILE *f; F = fopen(argv[1], “r”); yyin = f; while(yylex()); printf(“%d flotantes encontrados\n”, ocurrencias); fclose(f); } Programa para reconocer direcciones IP Digito [0-9] Punto [\. ] 26

IP {digito}+{punto}{digito}+{punto}+{digito} {punto}{digito}+ %% {IP} { strcpy(aux, yytext); strcat(aux, “.”); for(i =0 ; i255) { printf(“Error\n”); break; } if(i==4) printf(“Dirección IP: %s\n”, yytext); }

27

Unidad IV Análisis Sintáctico 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 permite decidir 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, S 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. Los símbolos no terminales (N) son aquellos que pueden seguir derivando en otros; mientras que los terminales el proceso finaliza allí. 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

B

e

•A aA|bC

C

e

•S

Genera cadenas del lenguaje a*b u a 28

Tipos de gramáticas Las gramáticas más sencillas son las gramáticas regulares, 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 Expresiones regulares. No presentan ambiguedades. Gramáticas Independientes del Contexto Son aquellas G cuya reglas de producción son de la forma: , en donde a pertenece aNy ß pertenece (N u )* Las ventajas de uso de GICs son: •Proporcionan una estructura sintáctica precisa y fácil de comprender • Proporciona al lenguaje fuente una estructura adecuada para la generación del código. • Por medio de las GICs es fácil construir analizadores sintácticos • Es sencillo añadir funcionalidades a un analizador sintáctico GICs 29

• Hay que revisar que la gramática no sea inherentemente ambigua para poder eliminar esa ambigüedad o rediseñar la gramática sin anomalí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.

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 || sirven para indicar los símbolos no terminales. • La barra vertical | para representar O • La doble flecha • ::= indica

indica las derivaciones las producciones

• [] indican elementos opcionales • {} indican términos repetitivos

4.2 Diagramas de sintaxis 31

• Es otra forma (al igual que los árboles de derivación) de especificar gramáticas del tipo 2. • La característica de este esquema es que permite ver las derivaciones al instante de que ocurren.

::= < W2>

::=ab

::=< W1> < W2> | a | ab

4.3 Precedencia de operadores • La precedencia de operadores es de vital importancia en el proceso de análisis sintáctico ya que nos representará la forma en que debe construirse el árbol de derivación. • En aritmética existen prioridades, por ejemplo: * y / tienen preferencia sobre + y -. () indican la máxima prioridad. Prioridad de operadores • La instrucción a = b + c / 2 en la mayoría de los lenguajes no se evalúa de la forma a = (b + c) /2, sino de la forma a = b + (c/2) 32

• La forma de evaluación depende de cómo se construyan los operadores, ya sea en infijo, postfijo o prefijo. • Las operaciones se realizan de abajo hacia arriba.

33

4.4 Analizador sintáctico Un analizador sintáctico (Parser) es un programa que reconoce si una o varias cadenas de caracteres forman parte de un determinado lenguaje. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Los analizadores sintácticos fueron extensivamente estudiados durante los años 70 del siglo XX, detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la creación de programas generadores de analizadores sintácticos a partir de una especificación de la sintaxis del lenguaje, tales y como YACC, GNU bison y javacc. Es el proceso de determinar si una cadena dada puede ser generada por una gramática. Los analizadores sintácticos de lenguajes de programación suele hacerse de izquierda a derecha, viendo un componente léxico a la vez Los analizadores pueden clasificarse dependiendo de la forma en como se construyen los nodos del árbol de derivación sintáctico: ascendentes y descendentes Tipos de analizadores sintácticos • LL (left to left) leen la cadena de izquierda a derecha y derivan por la izquierda • LR (left to right) •S •A

aA aBbC

•B

b

•C

c

4.4.1 Analizador descendente (LL) 34

Existen diferentes métodos de análisis sintáctico. La mayoría caen en una de dos categorías: ascendentes y descendentes. Los ascendentes construyen el árbol desde las hojas hacia la raíz. Los descendentes lo hacen en modo inverso. Un analizador ampliamente utilizado se denomina método de análisis predictivo descendente recursivo que es muy sencillo.

4.4.2 Analizador ascendente (LR, LALR) Algunos problemas no se pueden resolver de forma descendente ya que no están fácil quitar la ambigüedad. En algunos casos es más fácil demostrar algo ya existente. Generalmente los analizadores sintácticos LR(k) son del tipo “bottom-up”. El analizador trata de reducir la cadena de entrada w al símbolo inicial S. En un proceso que recorre el árbol de derivación en sentido inverso que se llama reducción. No sólo es necesaria una gramática que no presente ambigüedades sino que también tenga el valor de k más pequeño. 4.5 Administración de tablas de símbolos La tabla de símbolos se crea durante la fase de análisis léxico a través de los componentes léxicos, pero en el proceso de análisis sintáctico sufren algunas modificaciones. Generalmente se agregan valores de tipo y significado para el análisis sintáctico. 4.6 Manejo de errores sintácticos y su recuperación. Si los traductores tuvieran que procesar programas correctos el proceso de implantación se simplificaría mucho. 35

¿Cómo debe de responder un compilador de pascal a un código Fortran? Ningún método de recuperación de errores resuelve todos los problemas Tipos de errores • Léxicos: como escribir mal un identificador, palabra clave u operador. • Sintácticos: como una expresión aritmética con paréntesis no equilibrados. • Semánticos: como un operador aplicado a un operando incompatible. • Lógicos: como una llamada infinitamente recursiva • La mayoría de los errores se centra en la fase de análisis sintáctico. • El manejador de errores debe: Informar la presencia de errores con claridad y exactitud.

Administrador de errores • Recuperar de cada error con la suficiente rapidez como para detectar errores posibles. • No debe retrasar de manera significativa procesamiento de programas correctos. • Debe indicar informativo

la

línea

del

error

Estrategias de recuperación de errores 36

y

algún

el

mensaje

• Modo Pánico • Nivel de Frase • Producciones de error • Corrección global Recuperación en modo pánico Es el más sencillo de implantar. El analizador sintáctico desecha componentes léxicos hasta encontrar un carácter de sincronización. Estos caracteres son el punto y como (;) entre otros. int a.b,c; struct c { … . } main( ) { int a; }

Recuperación a nivel de frase

37

Esta técnica utiliza una corrección de caracteres adyacentes, ya sea por inserción, eliminación o intercambio. Esta técnica permite sustituir , por ;, etc. Son traductores que corrigen errores. Desafortunadamente para muchos casos no aplican por lo que no se utilizan demasiados. Producciones de error Se pueden generar gramáticas para generar producciones de error y así de esta forma seguir con el proceso. La dificultad radica en el sentido de encontrar esas reglas gramaticales para generar error. En algunos casos sería inclusiva más extensa que la gramática del propio lenguaje. For (i