Tundra

Solo disponible en BuenasTareas
  • Páginas : 6 (1265 palabras )
  • Descarga(s) : 0
  • Publicado : 15 de febrero de 2011
Leer documento completo
Vista previa del texto
Gramáticas de Contexto Libre
La flexibilidad proporcionada por las gramáticas de contexto libre es tal que es la mas usada para definir la sintaxis de los lenguajes de programación.
Una definición formal de una gramática de conexto sensitivo es la siguiente:
Es un cuadruplo G= (V, S , P, S) donde V es un conjunto finíto de variables, S es un conjunto finíto de símbolos terminales, P es unconjunto finíto de reglas y S es el símbolo inicial. Cada
producción tiene la forma uàv, donde u es una variable del conjunto V, y v es un miembro de (V È S)* . Esto quiere decir En la parte izquierda dela producción viene siempre una variable (símbolo no terminal) y en la parte derecha pueden venir cualquier número de símbolos terminales y no terminales incluyendo la cadena nula.

Arboles DeDerivacion ==
Existen básicamente dos formas de describir cómo en una cierta gramática una cadena puede ser derivada desde el símbolo inicial. La forma más simple es listar las cadenas de símbolos consecutivas, comenzando por el símbolo inicial y finalizando con la cadena y las reglas que han sido aplicadas. Si introducimos estrategias como reemplazar siempre el no terminal de más a laizquierda primero, entonces la lista de reglas aplicadas es suficiente. A esto se le llama derivación por la izquierda.
Por ejemplo, si tomamos la siguiente gramática:
: (1) S → S + S
: (2) S → 1
y la cadena “1 + 1 + 1″, su derivación a la izquierda está en la lista [ (1), (1), (2), (2), (2) ]. Análogamente, la derivación por la derecha se define como la lista que obtenemos si siemprereemplazamos primero el no terminal de más a la derecha. En ese caso, la lista de reglas aplicadas para la derivación de la cadena con la gramática anterior sería la [ (1), (2), (1), (2), (2)].
La distinción entre derivación por la izquierda y por la derecha es importante porque en la mayoría de analizadores la transformación de la entrada es definida dando una parte de código para cada producción que esejecutada cuando la regla es aplicada. De modo que es importante saber qué derivación aplica el analizador, por que determina el orden en el que el código será ejecutado.
Una derivación también puede ser expresada mediante una estructura jerárquica sobre la cadena que está siendo derivada. Por ejemplo, la estructura de la derivación a la izquierda de la cadena “1 + 1 + 1″ con la gramáticaanterior sería:
:S→S+S (1)
:S→S+S+S (1)
:S→1+S+S (2)
:S→1+1+S (2)
:S→1+1+1 (2)
: { { { 1 }S + { 1 }S }S + { 1 }S }S
donde { … }S indica la subcadena reconocida como perteneciente a S. Esta jerarquía también se puede representar mediante un árbol sintáctico:


S

/|
/ |
/ |
S ‘+’ S

/|\ |

/ | \|

S ‘+’ S ‘1′

| |

‘1′ ‘1′
La derivación por la derecha:
:S→ S + S (1)
:S→ 1 + S (2)
:S→ 1 + S + S (1)
:S→ 1 + 1 + S (2)
:S→ 1 + 1 + 1 (2)
define el siguiente árbol sintáctico:
S

/|
/ |
/ |
S ‘+’ S

| /|
| / |
‘1′ S ‘+’ S

| |‘1′ ‘1′
Si para una cadena del lenguaje de una gramática hay más de un árbol posible, entonces se dice que la gramática es ambigua. Normalmente estas gramáticas son mas fáciles difíciles de analizar por que el analizador no puede decidir siempre decidir siempre que producción aplicar.
Conteo de árboles de derivación
‘-Para una gramática libre de contexto G=(V,T,P,s0), su seriegenerativa puede hacerse corresponder con una serie en de manera que las ecuaciones impuestas por las producciones en P se satisfagan también en . En efecto, a cada símbolo s en asociémosle una incógnita Xs. Sea . Tratemos ahora el producto de incógnitas como si fuera conmutativo, pues de hecho lo es en. Con esto, la serie generativa pL de L(G) corresponde con una serie en. Observamos dos...
tracking img