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.