Introducción a la gramática libre de contexto
Definition - Una gramática libre de contexto (CFG) que consta de un conjunto finito de reglas gramaticales es un cuádruple (N, T, P, S) dónde
N es un conjunto de símbolos no terminales.
T es un conjunto de terminales donde N ∩ T = NULL.
P es un conjunto de reglas, P: N → (N ∪ T)*, es decir, el lado izquierdo de la regla de producción P tiene cualquier contexto de derecha o izquierda.
S es el símbolo de inicio.
Example
- La gramática ({A}, {a, b, c}, P, A), P: A → aA, A → abc.
- La gramática ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε
- La gramática ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε
Generación de árbol de derivación
Un árbol de derivación o árbol de análisis es un árbol enraizado ordenado que representa gráficamente la información semántica, una cadena derivada de una gramática libre de contexto.
Técnica de representación
Root vertex - Debe estar etiquetado con el símbolo de inicio.
Vertex - Etiquetado con un símbolo no terminal.
Leaves - Etiquetado con un símbolo de terminal o ε.
Si S → x 1 x 2 …… x n es una regla de producción en un CFG, entonces el árbol de análisis sintáctico / árbol de derivación será el siguiente:
Hay dos enfoques diferentes para dibujar un árbol de derivación:
Top-down Approach −
Comienza con el símbolo de inicio S
Baja a las hojas de los árboles usando producciones
Bottom-up Approach −
Comienza con las hojas de los árboles
Continúa hacia arriba hasta la raíz que es el símbolo inicial. S
Derivación o rendimiento de un árbol
La derivación o el rendimiento de un árbol de análisis sintáctico es la cadena final que se obtiene al concatenar las etiquetas de las hojas del árbol de izquierda a derecha, ignorando los Nulos. Sin embargo, si todas las hojas son nulas, la derivación es nula.
Example
Sea un CFG {N, T, P, S}
N = {S}, T = {a, b}, Símbolo inicial = S, P = S → SS | aSb | ε
Una derivación del CFG anterior es "abaabb"
S → SS → aSbS → abS → abaSb → abaaSbb → abaabb
Árbol de forma oracional y derivación parcial
Un árbol de derivación parcial es un subárbol de un árbol de derivación / árbol de análisis de modo que todos sus hijos están en el subárbol o ninguno de ellos está en el subárbol.
Example
Si en algún CFG las producciones son -
S → AB, A → aaA | ε, B → Bb | ε
el árbol de derivación parcial puede ser el siguiente:
Si un árbol de derivación parcial contiene la raíz S, se denomina sentential form. El subárbol anterior también está en forma de oración.
Derivación más a la izquierda y más a la derecha de una cadena
Leftmost derivation - Se obtiene una derivación más a la izquierda aplicando la producción a la variable más a la izquierda en cada paso.
Rightmost derivation - La derivación del extremo derecho se obtiene aplicando la producción a la variable del extremo derecho en cada paso.
Example
Sea cualquier conjunto de reglas de producción en un CFG
X → X + X | X * X | X | una
sobre un alfabeto {a}.
La derivación más a la izquierda de la cadena "a+a*a" puede ser -
X → X + X → a + X → a + X * X → a + a * X → a + a * a
La derivación paso a paso de la cadena anterior se muestra a continuación:
La derivación más a la derecha de la cadena anterior "a+a*a" puede ser -
X → X * X → X * a → X + X * a → X + a * a → a + a * a
La derivación paso a paso de la cadena anterior se muestra a continuación:
Gramáticas recursivas izquierda y derecha
En una gramática libre de contexto G, si hay una producción en forma X → Xa dónde X es un no terminal y ‘a’ es una cadena de terminales, se llama left recursive production. La gramática que tiene una producción recursiva a la izquierda se llamaleft recursive grammar.
Y si en una gramática libre de contexto G, si hay una producción está en la forma X → aX dónde X es un no terminal y ‘a’ es una cadena de terminales, se llama right recursive production. La gramática que tiene una producción recursiva correcta se llamaright recursive grammar.