Ing. Sistemas Computacionales

UNIDAD IV ANALISIS SINTACTICO

4.1 INTRODUCCIÓN A LAS GRAMÁTICAS LIBRES DE CONTEXTO Y ÁRBOLES DE DERIVACIÓN.
Gramática
_ Permite definir un lenguaje mediante reglas que nos permiten generar o producir cadenas de un lenguaje.
_ Estas gramáticas son similares a las gramáticas de los lenguajes naturales, pero mucho más restrictivas y sencillas.
_ Un ejemplo de regla de una gramática:
Oración_ Sujeto predicado
_ Estas reglas se suelen llamar reglas de reescritura: el símbolo Oración se puede reescribir por el símbolo Sujeto seguido del símbolo Predicado.
Autómata:
Al igual que con los lenguajes regulares podemos definir un autómata como una máquina reconocedora de cadenas (palabras) de un determinado lenguaje.
Los autómatas con los que trabajaremos en este tema son algo máscomplejos que los AF.
UN EJEMPLO
ORACIÓN  SUJETO PREDICADO | PREDICADO
SUJETO  ARTÍCULO NOMBRE
ARTICULO  el | la
NOMBRE  casa | niño
PREDICADO VERBO COMPLEMENTO
VERBO corre | es
COMPLEMENTO bien | obediente | bonita
ÁRBOLES DE DERIVACION
Derivaciones por la izquierda y derecha:
Existen básicamente dos formas de describir como en una cierta gramática una cadena puede ser derivada desdeel símbolo inicial. La forma más simple es listar las cadenas de símbolos consecutivas, comenzando por el símbolo inicial y finalizando con la cadena y las reglas que han sido aplicadas. Si introducimos estrategias como reemplazar siempre el no terminal de más a la izquierda primero, entonces la lista de reglas aplicadas es suficiente. A esto se le llama derivación por la izquierda. Por ejemplo,si tomamos la siguiente gramática:
(1) S → S + S
(2) S → 1
4.2 DIAGRAMAS DE SINTAXIS
Es otra forma (al igual que los árboles de derivación) de especificar gramáticas del tipo
La característica de este esquema es que permite ver las derivaciones al Instante de que ocurren.
Todo diagrama de sintaxis posee un origen y un destino, que no se suelen representar explícitamente, sino que se asumeque el origen se encuentra a la izquierda del diagrama y el destino a la derecha.
Cada arco con origen en " y destino en $ representa que el símbolo " puede ir seguido del $ (pudiendo ser " y $ tanto terminales como no terminales). De esta forma todos los posibles caminos desde el inicio del grafo hasta el final, representan formas sentenciales válidas.
Demostraremos que los diagramas desintaxis permiten representar las mismas gramáticas que la notación BNF, por inducción sobre las operaciones básicas de BNF:
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)
• 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.
4.4 ANALIZADOR SINTÁCTICO
Unanalizador 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...