5.4 Formas Normales de Chomsky:

 

5.4 Formas Normales de Chomsky:

En alguna ocasiones es posible transformar una Gramática en un otra debilmente equivalente, es decir que genera exactamente el mismo lenguaje pero con una estructura de árbol de derivación diferente. Alguna veces es algo conveniente porque los árboles de derivación de la nueva gramática podrían tener algunas propiedades de las cuales se podría tomar ventaja.

FNC #

Toda GLC se puede transformar en una gramática en la Forma Normal de Chomsky que requiere que las reglas tomen la siguiente forma:

$\begin{array}{ll}�\to & ��\\ �\to & �\\ �\to & �\end{array}$

Proceso de transformación #

Para transformar una gramática $(�,\mathrm{\Sigma },�,�)$ en su FNC se siguen los siguientes pasos:

0. Agregar un nuevo símbolo inicial$\begin{array}{ll}{�}_0\to & �\end{array}$

1. Quitar las transiciones ε

   • Identificar las producción $�\to �$
   • Producir nuevas producciones suponiendo que dónde aparece A es ε; por ejemplo si $�\to ���;�\to �;�\to �$ entonces se producen las nuevas reglas para P:$\begin{array}{ll}�\to & ��\mathrm{\mid }��\mathrm{\mid }�\end{array}$
   • Eliminar de la gramática las transiciones ε

2. Quitar las transiciones unitarias

   • Identificar las producción $�\to �$
   • Por cada $�\to �$ agregar las reglas:$\begin{array}{ll}�\to & �\end{array}$
   • Eliminar de la gramática las unitarias

3. Quitar las transiciones largas

   • Identificar las producción $�\to {�}_0{�}_1{�}_2\dots {�}_{�}$
   • Cortarlas usando símbolos auxiliares para encadenar la regla

4. Quitar los terminales binarios

• Identificar las producción $�\to ��$
• Agregar una regla con el no terminal (si es necesario) y remplazar en la regla original la aparición del terminal con ese no terminal
• • $\begin{array}{rl}�\to & {�}_{�}�\\ {�}_{�}\to & �\end{array}$

FNG #

Toda GLC se puede transformar en una gramática en la Forma Normal de Greibach que requiere que las reglas tomen la siguiente forma:

$\begin{array}{ll}�\to & �{�}_1\dots {�}_{�}\\ �\to & �\end{array}$

FNK #

Los diagramas sintácticos, de sintaxis o diagramas del ferrocarril son una forma de representar una gramática libre de contexto. Representan una alternativa gráfica para la Forma de Backus-Naur (BNF, por sus siglas en inglés) o la Forma Extendida de Backus-Naur (EBNF).

Constan de una serie de cajas o símbolos geométricos conectados por arcos dirigidos. Veamos las reglas que rigen la construcción de cada grafo:

Toda GDC se puede transformar en una gramática en la Forma Normal de Kudura que requiere que las reglas tomen la siguiente forma de gramáticas monotónicas:

$\begin{array}{ll}��\to & ��\\ �\to & ��\\ �\to & �\\ �\to & �\end{array}$

• $\begin{array}{rl}�\to & {�}_{�}�\\ {�}_{�}\to & �\end{array}$

 1. Cada símbolo terminal se representa por su nombre encerrado en un círculo o en una caja de bordes circulares.

Terminal: Un símbolo es terminal cuando tiene entidad propia y se describe por sí mismo.

5.6 Eliminación de la Ambigüedad:

ELIMINACIÓN DE LA AMBIGÜEDAD. La eliminación de la ambigüedad es difícil de realizar y entender por las siguientes razones:  No existe un algoritmo que nos indique si una gramática es ambigua.

5.7 Tipos de Analizadores Sintácticos:

Un analizador sintáctico (parser) o simplemente analizador es un programa informático que analiza una cadena de símbolos según las reglas de una gramática formal. El término proviene del latín pars, que significa parte (del discurso). Usualmente hace uso de un compilador, en cuyo caso, transforma una entrada en un árbol sintáctico de derivación.

El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Un analizador léxico crea tokens de una secuencia de caracteres de entrada y son estos tokens los que son procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol de análisis o árboles de sintaxis abstracta.

El lenguaje natural. Es usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional a un autómata de pila.

Los analizadores sintácticos fueron extensivamente estudiados durante los años 1970, detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la creación de programas generadores de analizadores sintáticos a partir de una especificación de la sintaxis del lenguaje en forma Backus-Naur por ejemplo, tales como yacc, GNU bison y javaCC.