Gramáticas independientes del contexto

UNIVERSIDAD TECNICA "LUIS VARGAS TORRES"

Grupo #4

Integrantes:

Docente:

AVILA ALEXIS, BERMELLO LUIS,MALDONADO KENEN,USIÑA JONATHAN.

ING. MENDOZA JAVIER

Frase motivadora

TEMA:

Gramáticas independientes del contexto

Introducción

La gramática independiente de contexto hace el uso de convenciones regulares, utiliza operaciones que son muy similares entre sí y tiene en cuenta que las reglas libres de contexto son muy recursivas. Debido a la recursividad incorporada en estos algoritmos, el algoritmo utilizado para reconocer esta estructura también es muy diferente del algoritmo de análisis léxico.

Gramáticas independientes del contexto.

Una gramática independiente de contexto, básicamente, consiste en un conjunto finito de reglas gramaticales. Con el fin de definir reglas de la gramática, asumimos que tenemos dos tipos de símbolos: los terminales, que son los símbolos del alfabeto, y los no terminales que se comportan como las variables.

El símbolo :: = significa “puede expandirse en” y “puede ser reemplazado por”

+ info

Ejemplo:

En esta gramática, los símbolos terminales son:

La gramática con las siguientes producciones define expresiones aritméticas simples.

Los símbolos no terminales son expr y op, y expr es el símbolo inicial.

Convenciones de notación

Para evitar tener que establecer siempre que "estos son los terminales'', "estos son los no terminales'', etcétera, a partir de ahora se emplearán las siguientes convenciones de notación con respecto a las gramáticas.

Estos símbolos son terminales

• Las primeras letras minúsculas del alfabeto, como a, b, c.
• Los símbolos de operador como +, - , etcétera

+ info

Estos símbolos son no terminales

• Las primeras letras mayúsculas del alfabeto, como A, B, C.
• La letra S. que cuando aparece suele ser el símbolo inicial.
• Los nombres en cursivas minúsculas, como expr o prop.

+ info

Arboles de análisis sintáctico y derivaciones

Base

Inducción

Ambigüedad

Se dice que una gramática que produce más de un árbol de análisis sintáctico para alguna frase es ambigua, o, dicho de otro modo, una gramática ambigua es la que produce más de una derivación por la izquierda o por la derecha para la misma frase.

Suponga que ya hemos construido un árbol de análisis sintáctico con el producto αi-1 = X1X2… Xk (tenga en cuenta que, de acuerdo a nuestras convenciones de notación, cada símbolo gramatical Xi es un no terminal o un terminal)

Un árbol de análisis sintáctico se puede considerar como una representación gráfica de una derivación que no muestra la elección relativa al orden de sustitución.

El árbol para αi = A es un solo nodo, etiquetado como A.

Conclusión:

La gramática libre de contexto le permite describir la mayoría de los lenguajes de programación. De hecho, la gramática de la mayoría de los lenguajes de programación está definida por la gramática libre de contexto.

ESCRIBE UN TÍTULO AQUÍ

AVILA ALEXIS

BERMELLO LUIS

alexis.avila.marcillo@utelvt.edu.ec

luis.bermello.zambrano@utelvt.edu.ec

MALDONADO KENEN

USIÑA JONATHAN

kenen.maldonado.garci@utelvt.edu.ec

jonathan.usiña,andagoya@utelvt.edu.ec

¡Muchas gracias!