Gramaticas Libres De Contexto

3.1
Gramáticas Libres de Contexto

Clasificación de los Lenguajes

Relación entre las distintas clases de Lenguajes

Introducción

Ejemplo

Definición formal de gramáticaDefinición Formal de Gramática

Convenciones de Notación

Convenciones de Notación

3.1.1 Definición

GLC y LLC

3.1.3 Ejemplos



::= a
::= bb | c

Se dice que la produccióncorrespondiente w bbw es
recursiva.
Si una producción recursiva tiene a w como lado
izquierdo, la producción es normal si w aparece sólo una
vez en el lado derecho y es el símbolo del extremo
derecho. Enel lado derecho también pueden aparecer
otros símbolos no terminales.

3.1.2 Forma de Backus Naur

3.1.3 Ejemplos
Sea S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}
Sea V la unión de S con el conjunto:N = {número-decimal, fracción-decimal, entero-sin-signo, dígito}
Así, sea G la gramática con conjuntos de símbolos V y S, con
símbolo inicial "número decimal" y con las producciones dadas enforma BNF como sigue:

::= | |
::=
::= |
::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

3.1.3 Ejemplos
G = (V, S, identificador, )
N = {identificador, resto, dígito, letra}
S = {a, b,c, . . . , z, 0, 1, 2, 3, . . . , 9},
V=NUS
::= |
::= | | |

::= a | b | c . . . | z
::= 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9

3.1.4 Derivaciones
La idea central es que seconsidera una
producción como una regla de reescritura, donde
el no terminal de la izquierda es sustituido por la
cadena del lado derecho de la producción.

3.1.4 Derivaciones

DerivacionesEjemplo de derivación

3.1.5 Árboles de Derivación

Definición de los árboles de Derivación

Ejemplo de árbol de derivación
Árbol de análisis sintáctico para la cadena zazabzbz usando lasiguiente gramática y cualquiera de las derivaciones

S-> zMNz
M-> aMa
M -> z
N->bNb
N-> z
S->zMNz
->zaMaNz
->zazaNz
->zazabNbz
->zazabzbz

Ejemplo de árbol de derivación

Ejemplos de...