Analisis sintáctico

50 %
50 %
Information about Analisis sintáctico

Published on August 27, 2013

Author: osced

Source: slideshare.net

Análisis Sintáctico Analizadores Descendentes Método Predictivo Rercursivo

¿Que es un análisis descendente? Es una técnica que intenta comprobar si una cadena x pertenece al lenguaje definido por una gramática aplicando los siguientes criterios: • Partir del axioma de la gramática • Escoger reglas gramaticales estratégicamente • Hacer derivaciones por la izquierda (Left Most Derivation) • Procesar la entrada de izquierda a derecha • Obtener el árbol de análisis sintáctico o error

Analizadores predictivos • Se determina qué regla aplicar a partir de un análisis de los primeros tokens a la entrada • Son capaces de decidir qué regla de producción aplicar a cada paso en función de los elementos terminales que se encuentran en la sentencia de entrada • Como consecuencia se consigue un proceso de análisis con complejidad lineal O (n) con respecto al tamaño del problema • Estos analizadores son llamados analizadores LL (K)

Método Predictivo Recursivo Analizadores predictivos LL (1) • Determinan que regla de producción aplicar encada paso en función del token que se encuentra en cada momento en la cabeza de lectura. Analizadores predictivos LL (k) • Determinan que regla de producción aplicar en cada paso en función de los k primeros tokens que se encuentra en cada momento en la cabeza de lectura.

Analizadores LL (K)

Analizadores LL (1) • Para aplicar el análisis descendente predictivo LL(1) se asocia a cada regla de producción un conjunto de predicción. • El conjunto de predicción de una regla está formado por la colección de todos los posibles símbolos terminales que es necesario encontrar en la sentencia de entrada para poder aplicar dicha regla • De todas las reglas candidatas para el no terminal en curso se escoge aquella que contiene en su conjunto de predicción el terminal a la entrada.

Análisis predictivo LL (1) • Para aplicar el análisis predictivo LL (1) es necesario que los conjuntos de predicción de todas las reglas con un mismo símbolo terminal sean disjuntas entre sí.

Condiciones LL (1) • Para cumplir la condición LL (1) la gramática debe satisfacer necesariamente 3 requisitos: › No ambigua › Factorizada por la izquierda › No recursiva por la izquierda

Analizadores LL (1)

Implementación Analizadores LL (1) • En cada paso del proceso de derivación de la sentencia de entrada se realiza una predicción de la posible producción a aplicar • Se comprueba si existe una concordancia entre el símbolo actual en la entrada con el primer terminal que se puede generar a partir de esa regla de producción • Si existe esta concordancia se avanza en la entrada y en el árbol de derivación, en caso contrario se vuelve hacia atrás y se elige una nueva regla de derivación

Implementación Analizadores LL (1) • Nos restringimos al caso de métodos deterministas (no hay vuelta atrás) teniendo en cuenta un solo símbolo de pre análisis (componente léxico que se está analizando en la cadena de entrada en ese momento) • Conocemos exactamente en todo momento que producción aplicar. El símbolo de pre análisis se actualiza cada vez que se produce una concordancia.

Implementación Analizadores LL (1) Procedimiento Parea(terminal) Inicio si pre análisis == terminal entonces pre análisis=siguiente token sino error sintáctico fin

Implementación Analizadores LL (1) Procedimiento A() inicio según pre análisis está en: PRIMEROS(a1): {proceder según alternativa a1 } PRIMEROS(a2): {proceder según alternativa a2 } ... PRIMEROS(an): {proceder según alternativa an } fin según si pre análisis no pertenece a ningún PRIMEROS(ai) entonces error sintáctico, excepto si existe la alternativa A -> € en cuyo caso no se hace nada fin

Implementación Analizadores LL (1) • Gramática que se va a implementar: E --> T E’ E’--> + T E’ | - T E’ | € T --> F T’ T’--> * F T’ | / F T’ | € F --> (E) | num | id

Implementación Analizadores LL (1) Procedimiento S() { Expresion(); Parea(TKN #); } Procedimiento Expresion() { Termino(); Expresion_Prima(); } Procedimiento Expresion_Prima() { según pre análisis está en: {TKN MAS}: Parea(TKN MAS); Termino(); Expresion_Prima(); {TKN MENOS}: Parea(TKN MENOS); Termino(); Expresion_Prima(); si no está en ninguno de los anteriores entonces no hacer nada fin según }

Implementación Analizadores LL (1) Procedimiento Termino() { Factor(); Termino_Prima(); } Procedimiento Termino_Prima(){ según pre análisis está en: {TKN POR}: Parea(TKN POR); Factor(); Termino_Prima(); {TKN DIV}: Parea(TKN DIV); Factor(); Termino_Prima(); si no está en ninguno de los anteriores entonces no hacer nada fin según }

Implementación Analizadores LL (1) Procedimiento Factor() { según pre análisis está en: {TKN ABREPAR}: Parea(TKN ABREPAR); Expresion(); Parea(TKN CIERRAPAR); {TKN NUM}: Parea(TKN NUM); {TKN ID}: Parea(TKN ID); si no está en ninguno de los anteriores entonces error(); fin según }

Add a comment

Related presentations

Related pages

Análisis Sintáctico

Análisis Sintáctico. Practica tu sintaxis con EdAS, un editor web para realizar análisis sintáctico y morfológico. Ejercicios y exámenes de sintaxis ...
Read more

Análisis sintáctico - Scribd

ANÁLISIS SINTÁCTICO La lengua es el código ... El Analisis sintáctico. Rubén Darío. Esquema Literatura Siglo XX. Esquema Romanticismo Realismo y ...
Read more

1a6 Análisis sintáctico de oraciones simples ejercicios ...

Análisis sintáctico de oraciones simples: En estas oraciones simples analizadas hay ejemplos de todas las funciones sintácticas: sujeto, CD, CI ...
Read more

Análisis Sintáctico. Ejemplos y ejercicios de sintaxis

Ejemplos y ejercicios de sintaxis. Oraciones simples, compuestas y complejas resueltas.
Read more

Análisis Sintáctico Resueltos o Simple - scribd.com

Análisis Sintáctico Resueltos o Simple - Free download as Word Doc (.doc), PDF File (.pdf), Text File (.txt) or read online for free.
Read more

Análisis sintáctico (lingüística) - Wikipedia, la ...

El análisis sintáctico es el análisis de las funciones sintácticas o relaciones de concordancia y jerarquía que guardan las palabras cuando se agrupan ...
Read more

Analizador sintáctico - Wikipedia, la enciclopedia libre

Analizador sintáctico descendente (Top-Down-Parser): ..un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada, ...
Read more

El análisis sintáctico de una oración - YouTube

El análisis sintáctico de una oración es el análisis de las funciones sintácticas o relaciones de concordancia que guardan las palabras ...
Read more

Análisis Sintáctico - Palamedes - Google Sites

Abordar un análisis sintáctico completo puede llegar a ser una tarea bastante compleja, pero el nivel exigido a los alumnos de Bachillerato de Griego y ...
Read more