APCV 15 Lenguajes. Gramatica. Analizador sintactico. Parser, Parsing.

Summary

El análisis sintáctico es una parte fundamental en la construcción de un compilador, donde se revisa la estructura gramatical de las frases en un lenguaje de programación. Este proceso verifica que los componentes léxicos se encuentren en el orden correcto según las reglas de la gramática del lenguaje. Los analizadores sintácticos pueden ser descendentes, construyendo el árbol sintáctico a partir de la raíz, o ascendentes, partiendo de las hojas. La gramática proporciona una especificación precisa del lenguaje, lo que permite la creación automática de analizadores eficientes y la facilidad para incorporar nuevas construcciones al lenguaje. Los errores encontrados en la compilación se clasifican en léxicos, sintácticos y semánticos. Este video ofrece una visión general de los conceptos y procesos involucrados en el análisis sintáctico, así como ejemplos prácticos de cómo se aplican estas técnicas en diferentes gramáticas y lenguajes de programación.

Takeaways

• 📚 El analizador sintáctico es un módulo de un compilador que verifica la sintaxis o gramática de un programa para asegurarse de que sigue las reglas del lenguaje.
• 🌐 Recibe una secuencia de lexemas del analizador léxico y utiliza las reglas de derivación de la gramática del lenguaje para determinar si la secuencia es válida.
• 🔍 El proceso de análisis sintáctico implica intentar construir un árbol sintáctico para las frases que se quieren reconocer, aunque en la práctica se utilizan autómatas de pila en su lugar.
• 🛠️ Los analizadores sintácticos pueden ser de dos tipos principales: descendente, que construye el árbol a partir de la raíz hacia las hojas, y ascendente, que lo hace desde las hojas hacia la raíz.
• ✅ La gramática proporciona una especificación precisa y fácil de entender para un lenguaje de programación, lo que permite la construcción automática de un analizador eficiente.
• 🔧 Los lenguajes de programación evolucionan y se pueden añadir nuevas construcciones a un lenguaje más fácilmente si existe una descripción gramatical.
• 🔄 El proceso de construcción del analizador sintáctico puede revelar ambigüedades sintácticas y otras construcciones difíciles de analizar que podrían pasar desapercibidas en la fase inicial del diseño de un lenguaje.
• 📈 Los errores en la compilación se clasifican en léxicos, sintácticos y semánticos, cada uno correspondiendo a un tipo de problema en la estructura del programa.
• 🔗 El análisis léxico y el análisis sintáctico interactúan estrechamente, donde el último solicita al primero el siguiente componente léxico y ambos se comunican hasta completar el análisis del programa.
• 📖 La estructura sintáctica de un programa se basa en la sintaxis abstracta y concreta, y es fundamental para la traducción de un programa fuente a código objeto correcto y para la detección de errores.
• 🔬 Las gramáticas recursivas por la izquierda y las gramáticas con recursos inmediatos son conceptos clave en la construcción de analizadores sintácticos y pueden requerir técnicas especiales como la factorización para su manejo.

Q & A

¿Qué es el analizador sintáctico en el contexto de un compilador?

El analizador sintáctico es el módulo de un compilador que realiza la revisión de la sintaxis o gramática de un programa para verificar si una frase está bien formada o no según las reglas del lenguaje.

¿Cuál es la función del analizador léxico en la construcción de un árbol sintáctico?

El analizador léxico proporciona una secuencia de símbolos léxicos o lexemas al analizador sintáctico, que luego decide si la secuencia está bien escrita o no en base a las reglas de la gramática del lenguaje.

¿Cómo se describe el proceso de análisis sintáctico?

El proceso de análisis sintáctico se describe como el intento de construir un árbol sintáctico para las frases que se quieren reconocer, utilizando las reglas de derivación de la gramática del lenguaje.

¿Por qué en la práctica no se implementan los árboles de análisis sintáctico?

Los árboles de análisis sintáctico no se implementan en la práctica porque suelen requerir mucho espacio; en su lugar, se utilizan autómatas de pila que guardan información en la pila acerca de los nodos del árbol sintáctico relevante en cada frase.

¿Cómo se relaciona la gramática con el análisis sintáctico?

La gramática proporciona una especificación precisa y fácil de entender de un lenguaje de programación. A partir de algunas clases de gramática, se puede construir automáticamente un analizador eficiente que determine si un programa fuente está sintácticamente bien formado.

¿Qué son los errores léxicos, sintácticos y semánticos en el proceso de compilación?

Los errores léxicos ocurren cuando un símbolo no corresponde a ningún componente léxico del lenguaje. Los errores sintácticos ocurren cuando una secuencia de símbolos no se ajusta a las reglas de la sintaxis definida por la gramática. Los errores semánticos ocurren cuando no existe una relación semántica adecuada entre los componentes léxicos, como el uso incorrecto de un operador en tipos de datos incompatibles.

¿Cuáles son los dos tipos principales de análisis sintáctico?

Los dos tipos principales de análisis sintáctico son el análisis sintáctico descendente, que intenta construir un árbol de análisis sintáctico empezando desde la raíz, y el análisis sintáctico ascendente, que intenta construir un árbol de análisis sintáctico empezando desde las hojas.

¿Qué es una gramática recursiva por la izquierda y cómo se identifica?

Una gramática es recursiva por la izquierda si existe al menos una regla de derivación en la que el lado izquierdo tiene un no terminal y el lado derecho comienza con el mismo no terminal. Esto puede llevar a la ambigüedad en el análisis sintáctico.

¿Cómo se define la función 'primero' en el análisis sintáctico?

La función 'primero' de un símbolo alfa es un conjunto que consta de los terminales que inician las cadenas derivadas de alfa. Se utiliza para determinar los símbolos con los que puede comenzar una derivación que contenga a ese símbolo no terminal.

¿Qué es la reclusión por la izquierda y cómo se resuelve?

La reclusión por la izquierda es una situación en la que una regla de producción tiene un no terminal en el lado derecho que también aparece al inicio de la regla. Se resuelve creando una nueva regla de producción que extraiga el no terminal a una posición más a la derecha o introduciendo un nuevo símbolo no terminal.

¿Cómo se utiliza la función 'siguiente' en la construcción de la tabla de análisis sintáctico?

La función 'siguiente' se utiliza para determinar los símbolos que pueden seguir a un símbolo no terminal en una producción dada, considerando el contexto en el que aparece. Se utiliza para construir la tabla de análisis sintáctico, ayudando a decidir qué producción aplicar en un no terminal dado el símbolo siguiente en la entrada.

Outlines

00:00

😀 Introducción al Analizador Sintáctico

Este párrafo introduce el concepto de analizador sintáctico en el contexto de un compilador. Se discute su función de revisar la sintaxis o gramática para verificar la conformidad con el lenguaje. Se menciona que el analizador sintáctico recibe la secuencia de lexemas del analizador léxico y utiliza las reglas de derivación de la gramática para construir un árbol sintáctico. Además, se exploran los tipos de analizador sintáctico y se habla sobre cómo se puede implementar uno y ejercitar en su funcionamiento. Se destaca la importancia de la gramática en la especificación de un lenguaje de programación y cómo los errores léxicos, sintácticos y semánticos pueden ser identificados en el proceso de análisis.

05:00

📚 Ejemplos y Procesos de Análisis Sintáctico

Este párrafo profundiza en el proceso de análisis sintáctico con ejemplos prácticos. Se muestra cómo se construye un árbol de sintaxis para determinar si una frase pertenece a un lenguaje dada su gramática. Se utiliza el ejemplo de la gramática g11 para demostrar cómo se reconocen las frases que cumplen con la estructura definida por la gramática. Además, se describe el proceso de análisis ascendente, que comienza con las hojas de un árbol y sube hacia la raíz. Se discuten los errores que pueden ocurrir durante la compilación y cómo se pueden clasificar en léxicos, sintácticos y semánticos. Finalmente, se presenta un ejemplo de cómo se verifica la pertenencia de una frase al lenguaje utilizando un árbol sintáctico.

10:01

🔍 Gramáticas y Análisis Recursivo

Este párrafo se enfoca en las características de las gramáticas y cómo afectan el análisis sintáctico. Se definen las gramáticas recursivas por la izquierda y por la derecha, y se explica cómo se pueden eliminar las reglas recursivas para facilitar el análisis. Se introduce el concepto de gramática no reconocida inmediata y cómo, a través de derivaciones sucesivas, se puede llegar a una secuencia reconocible. Se discuten técnicas como la factorización de gramáticas para simplificar el proceso de análisis. Además, se describe la estructura de un análisis sintáctico descendente, incluyendo el uso de una tabla de análisis sintáctico y una pila para rastrear el proceso.

15:02

🛠️ Construcción de la Tabla de Análisis Sintáctico

Este párrafo se centra en el proceso de construcción de la tabla de análisis sintáctico, que es esencial para el análisis descendente. Se describen las funciones 'primero' y 'siguiente' y cómo se utilizan para determinar qué regla de producción aplicar en un momento dado. Se presentan reglas para obtener estas funciones y se muestra cómo se aplican en ejemplos concretos. Se discute el algoritmo para construir la tabla de análisis sintáctico y se ilustra con ejemplos cómo se usa para analizar frases específicas. Se destaca la importancia de estas tablas en la compilación de programas y cómo ayudan a identificar errores de sintaxis.

20:03

🌐 Análisis de Gramáticas para Lenguajes Específicos

Este párrafo explora cómo se aplican los conceptos previamente discutidos para el análisis de gramáticas que definen lenguajes específicos, como el cálculo proposicional y la teoría de conjuntos. Se presentan ejemplos de frases en estos lenguajes y se muestra cómo se utiliza la tabla de análisis sintáctico para determinar si las frases son válidas según la gramática. Se abordan técnicas para eliminar la recursión por la izquierda en las gramáticas y se describe cómo se construye el árbol de análisis sintáctico para frases en estos lenguajes. Se destaca la utilidad de estos análisis para la comprensión y la validación de las estructuras en lenguajes formales.

25:05

📚 Recursos y Bibliografía

Este párrafo ofrece recursos adicionales para aquellos interesados en profundizar en el tema de las gramáticas y el análisis sintáctico. Se invita a los lectores a suscribirse al canal para recibir más información y se proporcionan referencias bibliográficas para una mayor comprensión del tema. Se cierra el párrafo agradeciendo al lector por su interés y participación.

Keywords

💡analizador sintáctico

El analizador sintáctico es un módulo de un compilador que revisa la estructura de una frase o programa para verificar su conformidad con las reglas de sintaxis del lenguaje. Se encarga de construir un árbol sintáctico a partir de la secuencia de lexemas proporcionada por el analizador léxico, utilizando las reglas de derivación de la gramática del lenguaje. En el video, se discute cómo este proceso es fundamental para verificar si una frase o programa está bien formado sintácticamente.

💡gramática

Una gramática es un conjunto de reglas que definen la estructura y el orden de las palabras en una oración o programa para que tenga sentido en un lenguaje determinado. En el contexto del video, las gramáticas son utilizadas para describir el lenguaje de programación y para construir analizadores sintácticos que puedan verificar la sintaxis de las frases o programas. Las gramáticas también son útiles para la detección de errores y la generación de código objeto.

💡árbol sintáctico

Un árbol sintáctico es una representación jerárquica de la estructura de una frase o programa. Se construye utilizando las reglas de una gramática para mostrar cómo los elementos se combinan para formar una estructura significativa. En el video, se menciona que el proceso de análisis sintáctico intenta construir este tipo de árbol para las frases que se quieren reconocer, aunque en la práctica se utilizan autómatas de pila en su lugar.

💡autómatas de pila

Los autómatas de pila son una alternativa a los árboles sintácticos que se utilizan en la implementación de analizadores sintácticos. Estos autómatas guardan información en una pila, la cual representa los nodos del árbol sintáctico relevante en cada frase del proceso de análisis. En el video, se indica que los árboles de análisis sintáctico no se implementan a menudo debido al espacio que ocuparían y en su lugar se usan autómatas de pila.

💡análisis sintáctico descendente

Este es un método de análisis sintáctico que comienza con la raíz de un árbol sintáctico y trabaja hacia abajo, hacia las hojas. Se trata de obtener una derivación por la izquierda para una cadena de entrada, comenzando desde la raíz y creando los nodos del árbol en orden previo. En el video, se describe cómo este proceso se utiliza para construir un árbol de análisis sintáctico y verificar la sintaxis de una frase.

💡análisis sintáctico ascendente

El análisis sintáctico ascendente es un proceso que comienza con las hojas de un árbol sintáctico y sube hacia la raíz. Es equivalente a obtener una reducción desde una cadena hasta llegar al axioma. En el video, se menciona que este método se utiliza para construir un árbol de análisis sintáctico partiendo desde las hojas y subiendo hacia la raíz.

💡errores léxicos

Los errores léxicos son aquellos en los que un símbolo no corresponde a ningún componente léxico reconocido del lenguaje. Por ejemplo, podría ser un identificador mal escrito, un verbo o un operando incorrecto. En el video, se discuten los errores léxicos como una de las categorías de errores que pueden ocurrir durante el proceso de compilación.

💡errores sintácticos

Los errores sintácticos ocurren cuando una secuencia de componentes léxicos no se ajusta a las reglas de la sintaxis definida por la gramática del lenguaje. Un ejemplo dado en el video es una expresión aritmética con paréntesis no equilibrados. Estos errores son detectados por el analizador sintáctico durante la revisión de la sintaxis del programa.

💡errores semánticos

Los errores semánticos son aquellos en los que no existe una relación semántica adecuada entre los componentes léxicos. En el video, se menciona un ejemplo de un error semántico como intentar sumar un número real con una variable booleana, lo que va en contra de las reglas de tipo del lenguaje.

💡recursividad por la izquierda

La recursividad por la izquierda se refiere a una regla de derivación en la que un no terminal deriva en una secuencia que inicia con el mismo no terminal. Esto puede llevar a problemas de análisis, como la capacidad de un analizador para determinar el correcto análisis de una frase. En el video, se discute cómo se puede eliminar la recursividad por la izquierda mediante la construcción de una nueva gramática.

💡función primero

La función 'primero' es una herramienta utilizada en la construcción de la tabla de análisis sintáctico. Define el conjunto de terminales que pueden aparecer al inicio de cualquier cadena derivada de un no terminal. En el video, se describe cómo se calcula la función 'primero' y cómo es esencial para la creación de la tabla de análisis sintáctico.

Highlights

El analizador sintáctico es el módulo de un compilador responsable de revisar la sintaxis o gramática de un programa para verificar su conformidad con el lenguaje.

Recibe la secuencia de tokens del analizador léxico y decide si la secuencia está bien formada según las reglas gramaticales.

El proceso de análisis sintáctico implica construir un árbol sintáctico para las frases que se quieren reconocer.

Los autómatas de pila se utilizan como alternativa a los árboles de análisis sintáctico para manejar la información de los nodos del árbol.

La gramática proporciona una especificación precisa y fácil de entender para un lenguaje de programación, lo que facilita la construcción de analizadores eficientes.

Los lenguajes de programación evolucionan y se pueden añadir nuevas construcciones más fácilmente si se basa en una descripción gramatical.

La construcción del analizador sintáctico puede revelar ambigüedades sintácticas y construcciones difíciles de analizar que podrían pasar desapercibidas en la fase inicial del diseño de un lenguaje.

Existen dos tipos principales de análisis sintáctico: descendente, que construye el árbol a partir de la raíz, y ascendente, que lo hace a partir de las hojas.

Las gramáticas libres de contexto son comunes para describir la sintaxis en las construcciones de los lenguajes de programación.

Los errores de compilación se clasifican en léxicos, sintácticos y semánticos, cada uno correspondiendo a un tipo de incumplimiento en la estructura del lenguaje.

El análisis de la gramática y la construcción del árbol sintáctico son métodos para verificar si una frase pertenece a un lenguaje definido por una gramática.

La reclusión por la izquierda en las gramáticas puede ser un problema, pero se puede solucionar con técnicas como la factorización y la introducción de nuevos no terminales.

La función 'primero' y la función 'siguiente' son herramientas clave para construir la tabla de análisis sintáctico y manejar la reclusión por la izquierda.

El algoritmo de análisis sintáctico descendente utiliza una tabla de análisis sintáctico para determinar qué producción debe aplicarse a un no terminal dado.

La estructura del análisis sintáctico ascendente comienza con las hojas y sube hacia la raíz, lo que es equivalente a obtener una reducción hasta llegar al axioma.

Los errores léxicos, sintácticos y semánticos son comunes en la compilación y se pueden detectar y corregir mediante la interacción entre los diferentes módulos del compilador.

La gramática recursiva por la izquierda y la gramática con recursos inmediatos son conceptos importantes para entender las capacidades y limitaciones de las gramáticas en la descripción de lenguajes.

La construcción de un analizador sintáctico para un lenguaje específico implica la creación de una tabla de análisis sintáctico a partir de la gramática del lenguaje y la aplicación de técnicas para evitar la reclusión por la izquierda.

Transcripts

hola amigos en el contexto de un

compilador el analizador sintáctico es

el módulo que realiza el proceso de

revisión de la sintaxis o gramática para

verificar si una frase está tendencia o

no al lenguaje para ello recibe el

examen soto kings del analizador léxico

veremos en la siguiente presentación

cómo se realiza este proceso

nuestra agenda consiste en lo siguiente

conocer el concepto de analizador

sintáctico

conocer los tipos de analizador

sintáctico especificar e implementar un

analizador sintáctico y ejercitarse en

el funcionamiento de un analizador

sintáctico

todo lenguaje definido por una gramática

por ejemplo en nuestro lenguaje la frase

juan estudia mucho

consta de un sujeto un verbo y predicado

en ese orden igualmente un programa en

un lenguaje informal se rige por una

gramática el proceso de análisis

sintáctico verifica que los componentes

léxicos que son entregados por el

analizador de léxico se encuentran en un

orden prescrito

el analizador sintáctico recibe una

secuencia de toppings o lexemas del

analizador léxico y decide si la

secuencia está bien escrita o no para

ello hace uso de las reglas de

derivación de la gramática del lenguaje

el proceso de análisis sintáctico puede

describirse como el intento de construir

un árbol sintáctico para las frases que

se quiere reconocer aunque en la

práctica los árboles de análisis

sintáctico no se implementan porque

compartían mucho espacio es por esta

razón que se usan como alternativa los

autómatas de pila que guardan

información en la pila acerca de los

nodos del árbol sintáctico relevante en

cada frase del proceso de análisis la

sintaxis en las construcciones de los

lenguajes de programación pueden

describirse por medio de gramáticas

libres de contexto

tenemos ahí la estructura de un

compilador los módulos iniciales

corresponden a la fase de análisis

léxico sintáctico y semántico y los

siguientes módulos corresponden al

proceso de síntesis generación de código

intermedio optimización de código y

generación de código

vemos aquí la interacción entre el

analizador léxico y en el señor

sintáctico este último le solicita al

léxico que le entregue el siguiente

componente léxico él le provee siente

como en el léxico y conversan entre sí

hasta terminar el programa fuentes que

están reconocidas

veamos algunas ventajas del analizador

sintáctico la gramática proporciona una

especificación precisa y fácil de

entender de un lenguaje de programación

a partir de algunas clases de gramática

se puede construir automáticamente un

analizador eficiente que determine si un

programa fuente está sintácticamente

bien formado es decir cumplir con la

gramática del lenguaje

los lenguajes evolucionan con el tiempo

adquiriendo nuevas construcciones y

realizando tareas adicionales

y estas nuevas construcciones se pueden

añadir con más facilidad a un lenguaje

cuando existen una aplicación basada en

una descripción gramatical

una gramática imparte una estructura un

lenguaje de programación útil para la

traducción de un programa fuente a

código objeto correcto y para la

detección de errores el proceso de

construcción del analizador sintáctico

puede revelar ambigüedades sintácticas y

otras construcciones difíciles de

analizar que podrían pasar sin ser

detectadas en la fase inicial del diseño

de un lenguaje y de eso compiladora

la estructura sintáctica

de un programa se basa en la sintaxis

abstracta y la sintaxis concreta

la sintaxis desempeñan dos funciones

basadas en estos dos conceptos

tenemos aquí cuatro programas escritos

en lenguajes diferentes

sin embargo cumplen

la

gramática en forma trata

tenemos dos tipos de del sabor

sintáctico el análisis sintáctico

descendente y el ascendiente

el análisis sintáctico descendente

intenta construir un árbol de análisis

sintáctico empezando desde la raíz y

descendiendo hacia las hojas los que lo

mismo intenta obtener una derivación por

la izquierda para una cadena de entrada

comenzando desde la raíz y creando los

nodos del árbol en orden previo

por otro lado el análisis sintáctico

ascendente intenta construir un árbol de

análisis sintáctico empezando desde las

hojas la cadena misma y ascendiendo

hacia arriba hacia la raíz lo que es lo

mismo que intentar obtener una reducción

desde una cadena hasta llegar al axioma

el lenguaje definido por una gramática

lo vamos a notar como el deje y consta

del conjunto de frases w que son

derivadas del axioma s aplicamos recibas

derivaciones pero esto no basta me doble

tiene que pertenecer a la cerradura de

pesos es decir veedor debe constar de

puros terminales cuando una frase w

constan de terminales o no terminales se

dice que es una forma asistencial y

cuando la frase tiene puros terminales

se dice que es una sentencia

otra forma de verificar si una frase

pertenece a un lenguaje es construyendo

el árbol de sintaxis para la frase si

será bueno construir el árbol decimos

que la frase está en el lenguaje si no

se dan a construir decimos que no

pertenece al lenguaje

veamos el ejemplo de la gramática g11

tenemos la gramática con unos terminales

s/a y b&b terminales a veces de

minúsculas las reglas se deriven a la

deriva a ab ab y débil derive en dvd o

cd

tenemos aquí dos ejemplos de árboles

sintácticos para reconocer la frase abs

de y otra que reconoce a bb cd

el lenguaje generado por g11 consta de

frases de la forma a la mba la m sea a

la n de a la n donde m y n es mayor o

igual que 1 vemos aquí que el número de

as y debés es el mismo mientras que el

número de se mide también es el mismo

sin embargo la cantidad de aceves

seguidas no es la misma que la cantidad

de 6 y 10 seguidas

vemos ahora cómo se construye el árbol

en forma descendente comenzamos en la

raíz y usando la regla de derivación se

deriva en ave descendemos en el árbol

luego a deriva y se debe a la vez

deriven se sella se llega a las hojas

etiquetadas con abs de por tanto decimos

que la secuencia de abc de pertenece al

lenguaje

veamos ahora el proceso de árbol

ascendente comenzamos ahora con las

hojas vsd y vamos ascendiendo usando la

ley las reglas de derivación los nuevos

ave se reducen

al no terminar los nodos 7 se reducen al

no terminal b y luego el nodo a y el 9

se reduce a ese luchando la regla 1 por

tanto decimos que la secuencia pertenece

al lenguaje

durante el proceso de compilación

ocurren diversos errores esto lo podemos

clasificar en errores léxicos errores

sintácticos y errores semántico los

decimos que un error este tipo léxico

cuando un ex tema no corresponde a

ningún componente léxico del lenguaje

por ejemplo escribir mal un

identificador un verbo u operando

ocurre uno sintáctico cuando una

secuencia de componentes léxico no se

ajusta a las reglas de la sintaxis

definida por la gramática ejemplo una

expresión aritmética con paréntesis no

equilibrados

y ocurre un error semántico cuando no el

7 relación semántica entre la secuencia

de componentes léxicos por ejemplo un

operador aplicado para los incompatibles

por ejemplo intentar sumar un número

real con una variable booleana

tenemos aquí como ejemplo la frase al

igual base por altura entre 2

el proceso de análisis de léxico gráfico

en la columna del cuadro de la izquierda

se aprecia que todos los componentes

léxicos son correctos

mientras que en el cuadro de color verde

se detectan dos errores

el eczema doblar base no corresponde

ningún componente léxico igualmente el

eczema 2

no corresponde a ningún componente por

tanto se dice que son errores

lexicográficos

tenemos como ejemplo la gramática

reducida del español muy reducida y

vamos a verificar si la frase el pequeño

niño corre rápidamente la tendencia el

lenguaje intentamos construir el árbol y

vemos que si llegamos a partir del

axioma hacia la frase que están

etiquetadas con las hojas el pequeño

niño corre rápidamente por tanto decimos

que la frase si pertenece al lenguaje

queremos verificar si la secuencia la

estudios alumna estudia mucho para tener

ese lenguaje generado por la gramática

intentamos construir el árbol

partimos de la acción s y usando las

reglas de derivación llegamos a las

hojas etiquetadas con la frase la

estudiosos alumna estudia mucho por

tanto decimos que la frase de

pertenencia al lenguaje

una gramática se hice recursiva por la

izquierda si existen por lo menos una

regla de derivación en el conjunto p

de tal forma que en el lado izquierdo

tenemos un no terminal y en el lado

derecho una secuencia de símbolos que

inicia con el mismo no terminal

la gramática se dice recurso inmediata

si existe una regla de producción de la

forma a derivan a alfa para un alfa una

gramática puede ser no reconocida

inmediata pero puede ser recursiva

aplicando sucesivas derivaciones

en el subte orem a una gramática y

reconocida por izquierda cuando existe a

no terminal que deriva en una secuencia

que inicie con un nuevo terminal a alfa

y beta donde beta en nombre inicia con

la de igual forma una gramática de

recogida por la derecha cuando él no

termina la deriva en una secuencia que

termina con la de la misma o deriva en

beta que no termina como para algún alfa

o beta

para eliminar la reclusión por la

izquierda con tenemos una nueva

gramática que prima

supongamos que tenemos la gramática a

deriva a alfa obieta construimos una

nueva gramática introduciendo un nuevo

no terminal a prima y hacemos que él no

tiene la derive en beta a prima y en la

prima insertado derive en alfa prima o

también en landa vemos ahí los árboles

construidos con la gramática inicial y

la gramática modificada

en este teorema generaliza la reclusión

por la izquierda

también podemos factorizar

si tenemos una gramática

[Música]

el cual un no terminal deriva en una

secuencia de frases de la forma alfa

beta 1 alfa beta 2 alfa beta n o gamma

podemos reemplazar la gramática por una

nueva de esta forma que la deriva en

alfa a prima a primeras un nuevo no

terminal o gamma y en la prima deriva en

beta 1 o beta 2 o beta n

ahí tenemos un ejemplo que deriva en if

expresión de proporción o expresión de

en proposición s proposición o a

sin factor izamos tenemos feder y 20 y

expresión de proposición de prima este

prima es un nuevo terminal que va a

derivar en ese de holanda

tenemos ahora la estructura de el

análisis sintáctico descendente tenemos

en el diagrama

w en la frase que se quiere analizar que

se encuentra un buffer tenemos la tabla

de análisis sintáctico que vamos a

construir posteriormente asimismo

hacemos de una pila el análisis

sintáctico ascendente intenta construir

el árbol de análisis sintáctico

empezando desde la raíz y desciende

hacia las hojas el objetivo de

determinar qué producción debe aplicarse

a un no terminal

tenemos ahí

el algoritmo de análisis sintáctico

descendente

el mismo algoritmo en un lenguaje más

formal

veamos como ejemplo tenemos una

gramática que reconoce especiales

aritméticas pero podemos ver que es

reconocida por la izquierda en la

primera producción tenemos a deriven a

mabe o beta tiene la forma a deriven a

alfa beta viste anteriormente por tanto

reemplazamos estas producciones por las

siguientes a la deriva en bea prima y la

prima deriva en más de a prima holanda

de igual forma las reglas de deriva en

este disco se hace se reemplazan por be

deriva en se ve prima y de prima derive

en asterisco se deprima holanda por

último se derive en paréntesis izquierdo

francis derecho y de oye no es recogida

por la izquierda por tanto se copió de

la misma forma tenemos ahí la tabla de

análisis sintáctico para esta gramática

por ahora la vamos a utilizar más

adelante y mostraremos cómo se construye

esta tabla

vemos algunos ejemplos

tenemos aquí la frase y de maside por d

aplicando el algoritmo

como la piel tenemos un no tener ientras

tenemos y d

buscamos en la tabla en la fila columna

y d

encontramos ahí la red de producción a

la deriva en vea prima el algoritmo nos

dice que tenemos que desempleada y

reemplazar en su lugar el vera prima en

orden inverso tenemos entonces en la

segunda fila doblar a primera vez que

reemplazó a la y en la entrada permanece

igual sin ningún cambio

en el siguiente iteración tenemos ve en

la pila y de la entrada nuevamente

buscamos en la matriz en la fila b

columna y de y encontramos la regla de

deriva en c

breide esto significa que de sentiremos

desde la pila y enfilamos el lado

derecho de la regla de producción se

deprima en orden inverso

esto va a seguir hasta que encontremos

en el top de la pila

un elemento que se igual a la entrada en

el paso 4 vemos que entonces la pila

tenemos y de entrada tenemos idea el

algoritmo manda que en este caso se dé

simple el ide y se avanza una posición

de la entrada y no hay ninguna

derivación que aplicar

para construir la tabla de análisis

sintáctico hacemos uso de la función

primero y la función siguiente

la definición del primero de alfa y la

siguiente a es un conjunto y consta de

los terminales

que inicia las cadenas derivadas de alfa

w construyen una secuencia de cero más

terminales solo terminales

vemos aquí algunas reglas para obtener

la función primero

la definición de primero de alfa y la

siguiente a es un conjunto y consta de

los terminales

que inicia las cadenas derivadas de alfa

w construyen una secuencia de 0 +

terminales son los terminales

vemos aquí algunas reglas para obtener

la función primero

siguiente vea es también un conjunto

constituido por los terminales que le

siguen al elemento a

en el contexto alfa como hábitat donde

haya ciertas consecuencias de acero más

terminales o no terminales

el símbolo se entiende en el dólar

siempre está en siguiente del símbolo

distinguido de la gramática

2 si existe una producción a deriven

alfa de verdad entonces decimos que

primero de meta sin él anda está

incluido en siguiente dv

3 si existe una regla de producción a

deriven alfa b

existe otra regla deriven alfa beta

donde la cndh está en primero de beta es

decir de verdad se puede derivar a landa

decimos en este caso que siguiente día

está incluido el siguiente debe

que tenemos un ejemplo

de una gramática

con operadores adicción solamente

tenemos la frase v ac y su derivación

para verificar si la frase está en el

lenguaje continuo es el conjunto primero

y el conjunto siguiente

con las reglas descritas anteriormente

tenemos otro ejemplo parecido al

anterior en este caso la gramática

reconoce expresiones aritméticas con

operadores adición y multiplicación

tenemos el conjunto primero y el

conjunto el siguiente obtenido con las

reglas descritas anteriormente

tenemos aquí el algoritmo para construir

la tabla el s sintáctico

tenemos las tablas del ejemplo anterior

la función primero

con su algoritmo y la función siguiente

consideremos la gramática que reconoce

frases del cálculo proposicional

queremos verificar por ejemplo si la

frase

pertenece al lenguaje intentamos

construir el árbol partimos de la acción

mapa y usando las reglas de derivación

digamos en p ocu luego puede viva en q

q de viva en ere ere deriven de este

precise que derive en q

y q nuevamente de viven q y r recuerden

que los símbolos en rojo son terminales

y los nuevos en azul son no terminales

luego que vive en él y termina en pe

leer de biden p

por tanto

vemos que las hojas están etiquetadas en

color rojo y contienen la expresión p y

q r

por tanto decimos que la frase de

pertenencia al lenguaje

consideremos ahora la frase p

verificamos si es reconocida comenzamos

con el axioma p diríamos en q nuevo q

deriva en q y r

q deriva en r

a su vez deriva en paréntesis de parejas

la p deriven p

se deriven rp y por otro lado la derecha

deriva en el aire y luego en b

finalmente r deriva en p revisamos los

nodos en color rojo y tenemos que

paréntesis p

p paréntesis

te pertenece el lenguaje generado por la

gramática

para el mismo lenguaje del cálculo de

proposiciones queremos construir su

analizador sintáctico vemos que la regla

p implica p

y q deben cubrir son recursos por la

izquierda por tantos eliminamos la

reclusión por la izquierda y tenemos una

nueva gramática en el lado derecho

construimos el conjunto primero y el

conjunto siguiente

y luego construimos la tabla con un

algoritmo explicado anteriormente

tenemos una fila y p

columna p la regla p deriva en cu p

prima

en la fila p columna paréntesis

izquierdo tenemos la regla p deriva en

cupey

y así sucesivamente

tenemos luego el análisis para la frase

entre paréntesis o p

y luego de aplicar la regla de

derivación y

el algoritmo explicado anteriormente

llegamos a que en el paso 24 la pila

queda vacía así mismo una entrada y las

reglas de derivación que están en la

columna salida constituyen los pasos

para construir el árbol de análisis

sintáctico

consideremos la gramática para el

lenguaje de expresiones de teoría

conjuntos por ejemplo frases de la forma

a unión ve a unión b intersección ce a

intersección b unión c tenemos las

reglas de derivación a deriven a unión b

vez deriven b interés acción seo se se

deriva en entre paréntesis o la

proposición p

vemos que esta gramática es reconocida

por izquierda dado que la primera regla

tiene una forma a la deriva a unión b y

la segunda vez deriva en b intersección

se eliminamos la reclusión por la

izquierda y tenemos una nueva gramática

construimos luego el conjunto primero y

conjunto siguiente de forma similar al

ejemplo anterior construimos la tabla de

análisis sintáctico

la siguiente gramática es similar a la

anterior habiéndose añadido en la

operación complemento de un conjunto

denotamos con ce en color marrón

complemento de un conjunto tenemos ahí

ejemplo los complementos de la unión b

complemento de la unión b intersección c

las reglas de producción son similares

excepto en la última al cual se le ha

añadido se deriva en complemento de a

cómo una gramática sigue siendo

reconocida por la izquierda se elimina

la recolección por la izquierda y

tenemos la nueva gramática construimos

en forma similar con los algoritmos

anteriores la función primero y función

siguiente y nuevo la tabla

y podemos revisar

mayor información en la dirección si

tienen interés en gramáticas políticas

de hipertexto

tenemos algunas referencias

bibliográficas para mayor

complementación y les invito a

suscribirse al canal para enviarles

mayor información gracias