Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Automatas 1- Unidad 6

No description
by

snake pro

on 6 September 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Automatas 1- Unidad 6

Análisis
Sintáctico

GLC
Capturan la noción de constituyente sintáctico y la noción de orden.

Herramienta formal que puede ser vista tanto desde un punto de vista generador como estructurado.

Propiedades computacionales interesantes: se puede reconocer en tiempo polinómico.

Árboles de derivación.
Los árboles de derivación permiten hacer una clasificación jerárquica en las palabras de un lenguaje que es útil en aplicaciones como la compilación de lenguajes de programación. Los vértices de un árbol de derivación son etiquetados con terminales o variables de la gramática o posiblemente con ϵ si un vértice interior n es etiquetado con A, y los hijos de n son etiquetados con X₁, X₂,…, X_k por la izquierda, entonces A  X₁, X₂,…, X_k debe ser una producción.

Llamamos derivación a una secuencia de pasos de derivación que generan una palabra x  L(G) a partir del símbolo privilegiado S.

A cada derivación de una palabra producida por una gramática corresponde un árbol de la derivación, cuya raíz es la variable inicial. Los hijos de cada nodo son los elementos de la parte derecha de la regla de producción que se aplica en cada paso de la derivación.

Formas normales de Chomsky.
Teorema:
Si L es un lenguaje independiente del contexto que no contiene la cadena vacía, entonces existe una gramática G independiente del contexto tal que L(G)=L y del lado derecho de cualquier regla de reescritura en G consiste en un solo terminal o exactamente dos no terminales.

Diagramas de sintaxis
Diagramas de Sintaxis
Un diagrama sintáctico es una estructura representada por arboles binarios.
Ejemplo:
Tenemos la expresión a=b+c

Eliminación de la ambigüedad
¿Qué es la ambigüedad?
Si una gramática genera más de una estructura para la misma cadena, dicha estructura es ambigua.

Una gramática ambigua permite más de una derivación para la misma forma sentencial por lo que también habrá más de un [árbol de derivación] para la misma.

Eliminación de la ambigüedad

En general, no existe un algoritmo para eliminar la ambigüedad. Pero podemos forzar la precedencia para quedarnos con solo un árbol, de los dos que se formaron debido a la ambigüedad.

Tipos de analizadores
sintácticos
Manejo de errores
Generadores de analizadores sintácticos
De la forma de construir el árbol sintáctico se desprenden dos tipos o clases de analizadores sintácticos. Pueden ser descendentes o ascendentes.


Un buen compilador debe hacerse siempre teniendo también en mente los errores que se pueden producir; con ello se consigue:
• Simplificar la estructura del compilador.
• Mejorar la respuesta ante los errores.

Los errores en la programación pueden ser de los siguientes tipos:
• Léxicos, producidos al escribir mal un identificador, una palabra clave o un operador.
• Sintácticos, por una expresión aritmética o paréntesis no equilibrados.
• Semánticos, como un operador aplicado a un operando incompatible.
• Lógicos, puede ser una llamada infinitamente recursiva.


Tenemos varias estrategias para corregir errores, una vez detectados:

• Ignorar el problema (Panic mode ):

• Recuperación a nivel de frase: Intenta recuperar el error una vez descubierto.

• Corrección Global: Dada una secuencia completa de tokens a ser reconocida, si hay algún error por el que no se puede reconocer, consiste en encontrar la secuencia completa más parecida que sí se pueda reconocer.

Yacc
Sid
Bison
YaYacc
GOLD
Grammatica
Byacc/Java
COCO/R
SableCC
TP Lex/Yacc
AnaGram
Aflex/Ayacc
AntLR
LISA
JavaCC
CUP
Spirit
Oops
ParseView
Beaver
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. 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 accede a la tabla de símbolos, hace un chequeo de tipos y genera errores cuando se producen.

Realiza casi todas las operaciones de la compilación. Este método da lugar a los métodos de compilación dirigidos por sintaxis.

¿Qué es el analizador sintáctico?
GLC
Barrios Gonzalez Samuel
Marcos Cruz Edgar
Melchor Peña Ignacio
Perez de la Rosa Luis David
Rodriguez HernandeZ Maximo
Santiago Licona Ana Belen
Equipo 6
Ascendente:

En el Análisis Sintáctico Ascendente se parte de las hojas y se intenta construir el árbol hacia arriba hasta llegar al símbolo inicial de la gramática

Descendente:

En el Análisis Sintáctico Descendente se va recorriendo el árbol sintáctico desde la raíz hasta las hojas, llegando a generar la sentencia que se está analizando. La raíz representa el símbolo inicial de la gramática.

Generación de matriz predictiva
Full transcript