APCV 15 Lenguajes. Gramatica. Analizador sintactico. Parser, Parsing.
Summary
TLDREl 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
😀 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.
📚 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.
🔍 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.
🛠️ 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.
🌐 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.
📚 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.
Mindmap
Keywords
💡analizador sintáctico
💡gramática
💡árbol sintáctico
💡autómatas de pila
💡análisis sintáctico descendente
💡análisis sintáctico ascendente
💡errores léxicos
💡errores sintácticos
💡errores semánticos
💡recursividad por la izquierda
💡función primero
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
5.0 / 5 (0 votes)