PARADIGMA: Manejar el silencio es más difícil que manejar la palabra...!!! ( Georges Clemenceau )

PARADIGMAS LINGÜISTICOS

Te doy la bienvenida al fantástico mundo de la lingüística artificial, componente de la magna ciencia semiótica en cuyo ámbito, luego de la migración del "Homo Sapiens", en "Homo Digitalis", este morador de la "Sociedad Globalizada", mediante los paradigmas sistémicos, digitaliza toda su información, cuyo manejo constituye el mayor poder estratégico de las naciones de vanguardia.

Dada la magnitud del universo lingüístico digitalizado, solo enfocaré mi propuesta a la óptica de las tecnologias aplicadas a las áreas que procesan automáticamente información, tratando de mínimizar la utilización de recursos lingüísticos, para lograr óptimos beneficios operatvos.
Si ya deseas ir al inicio teórico del tema clickea aqui.

En las siguientes matrices de links, además de entregarte la correspondiente documentacón impresa, trataré de exponerte los desarrollos de los lenguajes formales y los lenguajes de programación.

Lenguajes Formales:
Tipo
Grupo
Lenguaje
Gramatica
Automata
0
G0
Sin restricciones
Irrestricta
Turing
1
G1
Dependiente del contexto
Sensible al contexto
ALA
2
G2
Independiente del contexto
Contexto libre
De Pila
3
G3
Lenguaje regular
Gramatica Regular
Finito

Lenguajes de Programación
A S P
Basic
Builder
C++ C#
Delphi
Fox
Haskell
HTML
Java
PHP
Small
UML

Si te interesa conocer los antecedentes de todo este desarrollo, te cuento que la lingüistica nace en el origen de la cultura humana:

PARADIGMA: El talento más valioso es no usar nunca dos palabras
donde una alcanza. ..!! (Thomas Jefferson)

LA LINGÜÍSTICA ACTUAL
En 1916, los discípulos del suizo Ferdinand de Saussure, cofundador de la lingüística moderna, Charles Bally y Albert Séchehaye, publicaron "Curso de Lingüística General", que es el nacimiento formal de la lingüística, como ciencia que estudia el lenguaje, que evolucionó en varias direcciones:

PARADIGMA: Las palabras elegantes no son sinceras;
las palabras sinceras no son elegantes...!! (Lao Tsé)

Volver al principio

EL ESTUDIO LINGÜÍSTICO: Abarca el estudio de:
- Sonidos, las palabras y la sintaxis de una lengua concreta.
- Relaciones existentes entre las lenguas, o las características comunes a todas ellas.
- Aspectos psicológicos y sociológicos de la comunicación lingüística.

TIPOS DE ESTUDIO LINGÜÍSTICO

ENFOQUES DEL ESTUDIO LINGÜÍSTICO

PARADIGMA Cuando educas a un hombre, educas a una persona;
cuando educas a una mujer, educas a una familia..!!
(Wilucha)

PARTES DE LA LINGÜÍSTICA: Según el enfoque sistémico, sus partes son:

  1. SEMIÓTICA O SEMIOLOGÍA O CIENCIA DE LOS SIGNOS:
    Teoría que estudia la diferencia dentro del signo, entre la forma escrita del signo o "significante" y lo que representa o "significado".

    La semiótica enfoca la relación de las palabras con su significado, es decir, con la "SEMÁNTICA" y, por lo tanto, el modelo lógico de análisis será la pragmática de contexto trascendente. Mientras que para la gramática generativa la sintaxis es el único componente de una oración y su método de análisis fundamental.
    - C. S. Peirce: El filósofo estadounidense, usando los términos "signans" y "signatum". consideraba que la semiología era la base de la propia lógica, que la describe como "la ciencia de las leyes necesarias generales de los signos". Su obra intenta clasificar los signos en función de la naturaleza que existe entre significante, significado y objeto
    - Ferdinand de Saussure: Lingüista suizo, que usó "signifiant" o significante y "signifié" o significado, para estudiar el signo lingüístico y establecer una clasificación para distinguir entre diversos aspectos del lenguaje. Considerado fundador de la lingüística estructural y del estructuralismo, su análisi semiótico se desarrolla en términos de pares opuestos:

    Los estudios lingüísticos son diacrónicos (históricos) o sincrónicos (en un momento concreto).

    El lenguaje como lengua o habla, es el conjunto global de reglas sintácticas y semánticas de una lengua determinada o atendiendo a sus manifestaciones individuales.

    El signo consta de un significante y un significado; la relación que existe entre ambos es arbitraria y los dos dependen de una amplia red de diferencias.

    Volver al principio

  2. GRAMÁTICA:
    Define la estructura del lenguaje. Conceptualmente, la gramática es la técnica de hablar y escribir correctamente, ella se encarga de estructurar formalmente un lenguaje natural o artificial. A tal fin:
    - Define sus sentencias formadoras.
    - Proporciona los formatos validos de combinación de símbolos de su alfabeto y
    - Describe las normas para generar el correspondiente lenguaje formal.

    El lingüista estadounidense Noam Chomsky, a mediados del siglo XX, decia que la lingüística tiene que describir la estructura de las lenguas, lo que supone explicar cómo se entienden e interpretan las oraciones de cualquier lengua. Cree que el proceso es posible gracias a la gramática universal, que es una teoría o un modelo del conocimiento lingüístico o competencia.

    La competencia lingüística supone el conocimiento innato, e incluso inconsciente, que posee cualquier persona y que le permite producir y comprender las oraciones de su lengua, aun en el caso de que alguna no la haya escuchado jamás.

    La tesis según la cual la competencia lingüística supone un conocimiento innato y el lenguaje es una capacidad prefigurada genéticamente parece verse corroborada por recientes investigaciones que demuestran que esta capacidad humana se basa en módulos cerebrales especializados innatos y por el descubrimiento de un gen cuyas mutaciones producen deficiencias específicas en la función cerebral del lenguaje y no en otras.

    Gracias a esto es posible elaborar una gramática para cualquier lengua, que genere todas las oraciones gramaticales y elimine las agramaticales.

    Chomsky propone que hay unas cuantas reglas gramaticales universales y otras muchas específicas de cada lengua. Tales reglas son las que permiten que los elementos que forman una oración se puedan ordenar de varias maneras: Ejemplo: 'Batistuta ha metido un gol' y 'Este gol ha sido metido por Batistuta'.

    Según esto existe una:
    - GRAMATICA TRANSFORMACIONAL: Que dispone de las unidades semánticas subyacentes y luego las transforma mediante reglas en los elementos de una oración, que se pueden reconocer e interpretar.

    - GRAMATICA GENERATIVA: Que genera o produce todas las oraciones aceptables, y transformacional porque emplea las reglas, que se han llamado "transformaciones", para transformar las unidades subyacentes en aquello que entiende cualquier hablante.

  3. FONETICA:
    Rama de la lingüística que estudia los sonidos o fonemas de la lengua, abarca el estudio de los sonidos como unidades mínimas de significación en una lengua, así como los demás elementos fónicos llamados suprasegmentales (entonación en el caso del español).

  4. MORFOLOGIA:
    Trata la forma de las palabras. Estudia las unidades portadoras de significación de las lenguas, que se llaman morfemas, que pueden ser:
    • RAICES: Como la española –duc, que da lugar a producir, introducir, reducir, deducir.
    • DESINENCIAS: Como las de género, número, conjugación, tiempo verbal, etcétera (como -a, -o, -s, -er, -ré),
    • PREFIJOS: Que se añaden a la raíz para crear palabras compuestas (como pro-, intro-, con-, re-) o
    • SUFIJOS: Derivativos para formar aumentativos (como -ón, -azo), diminutivos (como -ito, -ico),
    • ADJETIVOS: Como -tivo, y adverbios como -mente.
    • ALTERACIONES FONETICAS: De las formas verbales en los verbos irregulares como poder, puedo, pude.

    La morfología en las lenguas flexivas, como en el caso del español o del alemán, describe las categorías gramaticales de las clases nominales y del verbo.

    PARADIGMA Quien lee sabe mucho;
    pero quien observa sabe todavía más..!! (Alejandro Dumas)

  5. SINTAXIS:
    Estudia las relaciones de las palabras en la oración, aquellas que se establecen entre los distintos elementos para formar una oración, planteando una tipología de las lenguas en función del orden de los elementos básicos sujeto-verbo-objeto.

    La sintaxis trata las reglas mediante las cuales se combinan las unidades lingüísticas para formar la oración. Las relaciones entre tales unidades lingüísticas, el enfoque y la definición de sintaxis son diferentes de una lengua a otra y entre las distintas escuelas lingüísticas.

    La sintaxis coordina las palabras para construir oraciones coherentes, y como no todas las combinaciones de símbolos, generan siempre palabras con significado coherente; para usar un lenguaje previamente deben formalizarse o identificarse sus cadenas componentes con sentido.

    En el entorno informático que usa lenguajes artificiales o abstractos, tales oraciones coherentes se forman con las "palabras formales", o "palabras reservadas" o "comandos reconocibles".

    Con este fin, dentro de tu entorno informático que usa lenguajes artificiales o abstractos, para identificar o generar tales palabras formales, o palabras reservadas o comandos reconocibles, será necesario que adoptes la gramatica correspondiente, que será la encargada de tales definiciones.

    PARADIGMA Tenemos dos oídos y una boca,
    porque escuchar es dos veces más necesario
    y difícil que hablar...!! (Zenón de Elea)

  6. SEMANTICA:
    Originada en el griego 'semantikos' ó 'lo que tiene significado', trata el significado de palabras y oraciones del lenguaje, determinando el significado de los signos lingüísticos, bajo el formato de palabras, expresiones y oraciones. Para ello analiza:

    - Qué signos existen y cuáles tienen significación, esto es, qué significan para los hablantes.

    - Cómo los designan, de qué forma se refieren a ideas y cosas.

    - Cómo los interpretan los oyentes.

    La semántica se estudia desde una

    • PERSPECTIVA FILOSÓFICA O SEMÁNTICA PURA: Basado en el conductismo, enfoca el proceso que establece la significación. A tal fin, sobre las ideas del suizo Ferdinand de Saussure, que investigó la forma que vincula el sentido a las expresiones y a los demás signos, el lingüista francés Jules Alfred Bréal propuso la "Ciencia de las Significaciones".

      En 1910 los filósofos británicos Alfred North Whitehead y Bertrand Russell publicaron su "Principia Mathematica", obra que influeye en el Círculo de Viena, integrado por filósofos que desarrollaron el: Positivismo Lógico, donde el significado es la relación que existe entre las palabras y las cosas, cuyo estudio tiene un fundamento empírico, pues el lenguaje, idealmente, es un reflejo de la realidad, sus signos se vinculan con cosas y hechos.

      El alemán Rudolf Carnap del Círculo de Viena, desarrolla la lógica simbólica; sistema formal que analiza los signos y lo que designan mediante notación matemática; este formato más preciso y claro que la lengua, es por sí mismo un lenguaje, o metalenguaje o lenguaje formal, que trata a la lengua como lengua objeto, cuya descripción es su semiotica, que posee tres aspectos:

      1. Semántico: Asigna designaciones específicas los signos palabras, expresiones y oraciones.
      2. Pragmático: Que indica las relaciones contextuales entre los hablantes y los signos.
      3. Sintáctico: Enfoca las relaciones formales existentes entre elementos del signo.

      Las reglas de la lengua objeto vinculan los signos a sus designaciones y cada signo interpretado tiene una condición de verdad a encontrar para que el signo sea verdadero. El significado del signo se conforma al satisfacer su condición de verdad, por ello, la expresión "Marte es de color rojo" se comprende pero puede o no ser verdad.

      La lógica simbólica de la escuela positivista intenta captar el significado a través de la verificación empírica de los signos es decir, comprobar si la verdad del signo se puede confirmar observando algo en el mundo real.

      El filósofo austriaco Ludwig Wittgenstein propone su filosofía del "lenguaje corriente" donde la verdad se basa en el lenguaje diario, destacando que no siempre los signos designan cosas que existen en el mundo, ni todos los signos se asocian a valores de verdad. En este enfoque de la semántica filosófica, las reglas del significado se revelan en el uso que se hace de la lengua.

    • PERSPECTIVA LINGÜÍSTICA O SEMÁNTICA TEÓRICA Y DESCRIPTIVA: Trata rasgos del significado y su relacionan dentro del sistema lingüístico.

      • SEMÁNTICA TEÓRICA O GENERATIVA: Busca dentro de la lengua una teoría general del significado que forma parte del conocimiento o competencia lingüística que todo humano tiene, dotando reglas para decidir cómo interpretar los signos y determinar qué signos carecen de interpretación aunque sean expresiones gramaticales. Tales reglas deciden la interpretación adecuada para oraciones ambiguas, como:"Murió la víbora de mi suegra" que tiene al menos dos interpretaciones.

        La semántica generativa explica la capacidad del hombre para producir y entender expresiones nuevas donde falla la gramática o la sintaxis, demostrando que comprende aún oraciones carentes de significado, aunque construida según reglas de una gramática, Ejemplo: "Escuchemos las rocas hablantes".

        Para esta semántica, la información necesaria para interpretar semánticamente un signo o una oración, está en su estructura sintáctica o gramatical. Tal estructura incluye lexemas entendidas como palabras o unidades del vocabulario formadas por rasgos semánticos seleccionados dentro del conjunto universal de rasgos semánticos.

        Según el fundador de esta escuela Noam Chomsky, dentro de la teoría de base sintáctica las estructura superficial y profunda determinan conjuntamente la interpretación semántica de una expresión.

      • SEMÁNTICA DESCRIPTIVA: Examina el significado de los signos en una lengua concreta, determinando así lo que es un nombre, un sintagma nominal, un verbo o un sintagma verbal, análisis efectuado por la relación sujeto-predicado, o por el significado de los signos que aparecen cuando se analiza su estructura oracional.

        Un signo es un operador combinado con argumentos que relaciona con otros elementos de la expresión como los sintagmas preposicionales o los adverbiales. Ejemplo: "El profesor registró inasistencia al alumno", 'registró' es un operador que relaciona los argumentos 'el profesor', 'al alumno', con el operador 'inasistencia'.

        En el análisis de componentes, los lexemas o palabras con unidad propia en el vocabulario, del mismo campo de significación integran el dominio semántico, caracterizado por rasgos semánticos distintivos que son unidades mínimas de significado que distinguen a un lexema de otro. Así, "asiento", abarca los lexemas silla, sillón, sofá, banco y banqueta, se diferenciadas entre sí por el tipo de respaldo, brazos, o altura de patas, pero esos lexemas tienen en común un componente o rasgo de significación: algo para sentarse.

        El análisis de componentes busca identificar el conjunto universal de rasgos semánticos existentes, sobre los cuales cada lengua construye el suyo, que la distigue de otra. Por ello, el antropólogo francés Claude Lévi-Strauss, aplicó esta hipótesis para analizar los sistemas de mito y parentesco de varias culturas; demostrando que los pueblos organizan sus sociedades según ciertas reglas, a pesar de las aparentes diferencias que muestran.

    • PERSPECTIVA SEMÁNTICA GENERAL: Trata el significado y su influencia sobre lo que hace y dice la gente; explica cómo los pueblos valoran las palabras y cómo influye esa valoración en su conducta; examina los distintos valores o connotaciones de los signos de igual significado.

      Ejemplo: "El Santo de la Espada" y "Libertador de America", ambos se refieren a San Martin.

      Los lingüistas USA Alfred Korzybski y S. I. Hayakawa, destacan los riesgos que implican tratar las palabras sólo en su condición de signos. Usan sus obras de semántica general para invalidar las generalizaciones poco rigurosas, las actitudes rígidas, la finalidad incorrecta y la imprecisión.

PARADIGMA: Muchas palabras no indican mucha sabiduría ..!!! (Tales de Mileto)

PARADIGMA Los hombres demuestran su grandeza
por la forma en que tratan a los pequeños...!!! (Thomas Carlyle)

TEORIA de los LENGUAJES FORMALES:
Sin restricciones
Dependiente de contexto
Independiente de contexto
Regular

Captar el ingenio de los teóricos de los lenguajes artificiales, como la del genial Noah Chomsky, implica comprender los fundamentos de:

| Lenguajes Formales | Producciones y Derivaciones | Diagrama Sintáctico | Esquemas de Traducción | Sistemas Canónicos|

TEORIA DE PALABRAS O CADENAS DE CARACTERES:

PARADIGMA La necesidad enseña a pedir hasta a los reyes..!! (Saber popular)

OPERACIONES CON PALABRAS: Con las cadenas o palabras podemos efectuar las siguientes operaciones:

Volver al principio

LOS LENGUAJES
Para conceptualizar esta teoría, conviene que previamente la ubicaremos dentro del contexto de los lenguajes en general y con este fin, si lees alguno de los libros de la bibliografía, hallarás diversos criterios sobre los lenguajes, pero en general se aproximan a los siguientes conceptos:

Cuando deseas trasmitir tus mensajes y comunicarte con otros entes, utilizas conjuntos de señales o símbolos o caracteres, los cuales conforman todos los lenguajes y que pueden agruparse como:

  • LENGUAJES NATURALES O IDIOMAS: Como el español o ingles, que usaras cuando tus mensajes estén destinados a tus congeneres.

    Estos lenguajes están conformados por conjuntos de palabras, cuya existencia fue anterior a sus correspondientes reglas gramaticales y que por tanto son lenguajes que evolucionan. Por suerte, este no es el enfoque que describiré en esta page..!!.

  • LENGUAJES ARTIFICIALES O ABSTRACTOS: Como los lenguajes de programación y que utilizaras cuando tus mensajes estén destinados a comunicarte con las máquinas tales como autómatas o computadoras.

    Estos lenguajes se estructuran a partir de conjuntos de cadenas de símbolos generadas por gramáticas preestablecidas, creadas para alcanzar objetivos específicos y que por lo tanto, hacen que estos lenguajes no evolucionen.
    Son conjuntos de palabras o cadenas o secuencia finita de símbolos generadas a partir de un alfabeto y el lenguaje sin ninguna cadena se llama "Lenguaje vacío".

    Pueden ser representados en dos formatos: Así, para el alfabeto A = {1}, un lenguaje L puede ser representado en formato de:

    1. EXTENSION: Como L = {1, 11, 111,..} cuyas palabras son cadenas de longitudes finitas de unos.

    2. COMPRENSION: Como L = {1(n)| para n = 1, 2, 3..}.

    Pueden describirse mediante dos alternativas:

    1. LENGUAJE FINITO: Se logra con solo enumerar todas sus palabras componentes.

    2. LENGUAJE INFINITO: Se logra definiendo sus reglas o requerimientos sintácticos.

  • SUB LENGUAJES: Para el alfabeto A, dados sus lenguajes L1 y L2, si todas las cadenas de L1 son también cadenas de L2, se dice que L1 es sublenguaje de L2
    
       Ejemplo:  Para los lenguajes
                 L1 = { zorra, arroz, amor, roma, oir, rio }    y 
                 L2 = { zorra, arroz, amor, roma,  oir, rio tecno }
    
                 Diremos que se dice que L1 es sublenguaje de L2 
    

  • CIERRE o CERRADURA: Denominado también cerradura o clausura, está simbolizada por la Estrella de Kleene E* y es el lenguaje compuesto por todas las cadenas sobre el alfabeto A, incluido L; por ello para cualquier alfabeto A * es infinito.

    Ejemplo: A = {1} A* = {L, 1, 11, 111,.....}.

  • COMPLEMENTO de LENGUAJES: Dados los lenguajes L1 y L2, se dice que el lenguaje ~L2 es complemento del lenguaje L1 si y solo si
    L1 = A* - L2 = { u Î A* - u Ï L1 }
    Por ello será: ~A* = Lenguaje vacio

OPERACIONES con LENGUAJES ABSTRACTOS:
Al igual que en las cadenas, también en los lenguajes se pueden efectuar las siguientes operaciones.

  1. UNIÓN DE LENGUAJES: È:
    Para el alfabeto A, sea w una cadena de los lenguajes L1 y L2, la unión È: de L1 con L2 contendrá todas las palabras que pertenezcan a cualquiera de los dos lenguajes; generando así un nuevo lenguaje formado por todas las palabras sin repetición, que pertenezcan alguno de estos lenguajes:

    L = L1 È L2 = { w | w Î L1 con w Î L2 }

    
       Ejemplo:  
                 Para los lenguajes
                 L1 = { zorra, arroz, amor, roma, oir, rio }    y 
                 L2= { zorra, arroz, amor, roma, tecno }
    
                 L = L1 È  L2 =  { zorra, arroz, amor, roma, oir, rio, tecno }
    

  2. INTERSECCIÓN DE LENGUAJES: Para el alfabeto A, sea w cadena de los lenguajes L1 y L2; la intersección L1 intersección L2 generará un nuevo lenguaje formado por todas las palabras que pertenezcan simultáneamente a los dos lenguajes: L = L1 intersección L2 = { w | w pertenece L1 intersección w pertenece L2 }
    
       Ejemplo:  Para los lenguajes
                 L1 = { zorra, arroz, amor, roma, oir, rio }    y 
                 L2= { zorra, arroz, amor, roma, tecno }
    
                 L = L1 intersección  L2  = { zorra, arroz, amor, roma }
    

  3. RESTA DE LENGUAJES: Para el alfabeto A, sea w una cadena de los lenguajes L1 y L2 =;
    la resta L1 - L2, generará un nuevo lenguaje formado por todas las palabras que pertenezcan a L1 y que no pertenezcan L2

    L = L1 - L2 = { w | w Î L1 y w Ï L2 }

    
    Ejemplo:  Para los lenguajes
    L1 = { zorra, arroz, amor, roma, oir, rio }    y 
    L2 = { zorra, arroz, amor, roma, tecno }
    
    La resta será:     L = L1 -  L2 = { oir, rio }
    

  4. PRODUCTO DE LENGUAJES: El producto de los lenguajes L1 y L2 se representada como:
    L1 . L2 = { uw | u Î L1 È w Î L2 },

    que es el lenguaje generado con cada palabra de L1 y concatenada a su derecha con cada palabra de L2.

  5. INVERSIÓN DE LENGUAJES: Es el inverso del lenguaje L

  6. CONCATENACIÓN DE LENGUAJES: Sean, respectivamente w y x cadenas de los lenguajes L1 y L2 del alfabeto A.

    Su lenguaje de concatenación L = L1 . L2 se generará por todas las palabras que se pueden formar por concatenación de una palabra de L1 y otra palabra L2 de modo que:

    L = L1 . L2 = {w.x | w pertenece L1 y x pertenece L2 };

    
      Ejemplo: Para los lenguajes 
               L1 = { pio }   y   
               L2 = { joso, nono } , 
    
               Lenguaje concatenado:   L =  L1 .  L2 = { piojoso, pionono }
    

  7. POTENCIA DE LENGUAJES: Sea L1 un lenguaje del alfabeto A, su potencia enésima se la expresa como la concatenación n veces del leguaje con si mismo y se la representa como

    L1n = L1.L1.. .L1 ( n factores )

    
    Ejemplo: 
    
        Para el lenguaje L1 = { pio }  se generan las potencias:  
        
        L1. L1 =  {piopio},   
        L1. L1. L1 = {piopiopio}
    

  8. RECURSIVIDAD de LENGUAJES: La definición recursiva abarca un proceso de:
    • Especificar algunos objetos primarios del conjunto.

    • Diseñar reglas para generar más objetos del conjunto, a partir de tales objetos primarios conocidos.

    • Plantear que solo los objetos construidos de este modo pueden pertenecer al conjunto.
    Volver al principio

  9. PRODUCCIÓN y DERIVACIÓN: Te recomiendo que analices y captes en su totalidad los siguientes conceptos, por que te simplificaran la vida a la hora de diseñar u operar gramáticas y autómatas.
    Sobre estos sencillos procedimientos operativos se basan tanto la generación como el reconocimiento de las cadenas que conforman un determinado lenguaje.

    PRODUCCION O REGLA: ( X ::= Y )
    Es un par ordenado de palabras ( x, y ), x, y Î A* de manera que si se encuentra x como parte de cualquier palabra v , se puede sustituir x por y en v, acción que posibilita transformar unas palabras en otras. Ejemplo:

    
                 Para L ( A2 ) = { 0, 1 }    
    
                 se pueden generar las siguientes producciones   
                 ( 000 ::= 010 )  o  
                 ( 10 ::= 01 )
    

    DERIVACIÓN: Como podrás deducir de la siguiente lectura, la derivación es una forma de aplicación de la producción.

    • DERIVACION DIRECTA: ( u --> w ):
      Aplicación de una producción ( x ::= y ) a una palabra v para convertirla en otra palabra w, donde v = x.y.u, w = z.y.u ( v, w, z, u Î A* ).
      Se cumple que para cada producción ( x ::= y ) existe una derivación directa x a y:
      x -> y, lo que se deduce de lo anterior con solo hacer x = u = L. Ejemplo: Con las producciones P1 = ( 000 ::= 010 ) y P2 = ( 10 ::= 01 ) y la palabra 1000, se pueden lograr las siguientes derivaciones directas:

      1000 (P1)--> 1010, 1010 (P2)--> 0110, 0110 (P2)--> 0101 y 0101 (P2)--> 0011

    • DERIVACION: ( u ?* w ) Aplicación de una sentencia de producciones a una palabra. Ejemplo: La ejecución continuada en el Ejemplo anterior, proporciona una derivación de la palabra 1000 a la palabra 0011.

      1000 (P1)--> 1010 (P2)--> 0110 (P2)--> 0101 (P2)--> 0011

    • DERIVACION MAS A LA IZQUIERDA: Ocurre cuando se utiliza en cada derivación directa la producción aplicada a los símbolos más a la izquierda de la palabra. La derivación más a la izquierda en el Ejemplo anterior será:

      1000 (P2)--> 0100 (P2)--> 0010 (P2)--> 0001 (P1)--> 0101 (P2)--> 0011

    • DERIVACION MAS A LA DERECHA: Ocurre cuando se utiliza en cada derivación directa la producción aplicada a los símbolos más a la derecha de la palabra. Para el Ejemplo anterior:

      1000 (P1)--> 1010 (P2)--> 1001 (P2)--> 0101 (P2)--> 0011

DEFINICIÓN DE LENGUAJE FORMAL
Ahora que ya captaste la operativa de las derivaciones, ya puedes deducir que un lenguaje puede ser generado por iteración de las derivaciones efectuadas a partir una cadena primigenia, que recibe el nombre de axioma S.

Así:

  • Si representamos con S -->* w a todas las derivaciones posibles de la cadena w desde el axioma S;

  • El conjunto de todas las cadenas que conforman el lenguaje generado L(G), podemos definirlo como:

    L(G) = { w | S -->*w, w ÎST*}

    Donde ST* es la representación del alfabeto de todos los símbolos terminales, incluida la palabra vacía.

Volver al principio


Volver al principio

DIAGRAMA DE SINTAXIS
Es un método alternativo para desplegar las producciones de ciertas gramáticas de tipo 2 y consiste en una imagen de las producciones que permite al usuario ver las sustituciones en forma dinámica, es decir, verlas como un movimiento a través del diagrama.

Por Ejemplo los diagramas siguientes resultan de la traducción de conjuntos de producciones típicos, que son, por lo general, todas las producciones que aparecen en el lado derecho de algún enunciado BNF (forma Backus-Naur).

  • < w > ::= < w1 > < w2 > < w3 >

  • < w > ::= < w1 > < w2 > | < w1 >a | bc< w2 >

  • < w > ::= ab< w >.

  • < w > ::= ab | ab< w >.

La NOTACIÓN BNF (forma Backus-Naur Form): Describe la sintaxis, mediante un metalenguaje que utiliza los metasímbolos: < > ::= | y define las reglas por medio de "producciones"
Ejemplo: < digito > ::= 0|1|2|3|4|5|6|7|8|9

Esta notación es una alternativa para desplegar las producciones de las gramáticas de tipo 2 GIC, cuyos lados izquierdos son símbolos no terminales únicos.
Así, la gramática: GIC = ( ST, SN, S, P )= ({ 0, 1 }, { A, B }, A, P ) generará el lenguaje:


          L ={ 11, 101, 111 }, con las producciones:  

          P = { ( A ::= 1B1 ), ( A ::= 11), ( B ::= 1 ), ( B ::= 0 ) }, 

y las derivaciones:

	A -->    11
	A -->   1B1 -->   101
	A -->   1B1 -->   111                   

Para cada uno de los símbolos w, se combina todas las producciones que tienen a w como lado izquierdo.
El símbolo w permanece a la izquierda, y todos los lados derechos asociados con w son enumerados juntos, separados por el símbolo |.
El símbolo relacional se reemplaza por el símbolo ::=.

Los símbolos no terminales, cuando aparezcan, serán encerrados entre paréntesis agudos < >. Así, los símbolos no terminales pueden tener espacios dentro de ellos.

Así: < palabra1 palabra2>
Muestra que la cadena entre paréntesis debe considerarse como una "palabra", no como dos palabras. Es decir, se puede utilizar el espacio como una "letra" conveniente y legítima en una palabra, mientras que se utilice los paréntesis agudos para delimitar las palabras.

Ejemplo: En notación BNF, ciertas producciones pueden tener el siguiente formato:


		< oración>     ::=    < sujeto> < predicado> 
		
		< sujeto>       ::=    Juan | Julia 
		
		< predicado>  ::=    < verbo> < adverbio> 
		
		< verbo>        ::=    maneja | corre 
		
		< adverbio>    ::=    descuidadamente | rápido | frecuentemente 

PRODUCCION RECURSIVA: Ocurre cuando el lado izquierdo de una producción aparece en una de las cadenas del lado derecho.
Ejemplo: En la notación BNF, de ciertas producciones aparecerán:


	< vo >    ::=    a< w > 
	< w >     ::=    bb< w > | c
Como en el lado izquierdo de una producción aparecen también en una de las cadenas del lado derecho, pues, < w > aparece a la izquierda, y aparece en la cadena bb < w >, la producción w bbw es recursiva.

Ahora, 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.
En el lado derecho también pueden aparecer otros símbolos no terminales. La producción recursiva w bbw es normal.

Ejemplo: La notación BNF se utiliza con frecuencia para especificar los lenguajes de programación reales. PASCAL y muchos otros lenguajes tenían dadas sus gramáticas en BNF inicialmente.
En este Ejemplo se considerará un pequeño subconjunto de la gramática de PASCAL que describe la sintaxis de los números decimales y se puede ver como una minigramática cuyo lenguaje correspondiente consta precisamente de todos los números decimales formados de manera adecuada.
Sea:


	S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}.       (ST)

	N = {número-decimal, fracción-decimal, entero-sin-signo, dígito}.       (SN)

	V= S    N               ( V es la unión de S con el conjunto N  )

	G = ( ST, SN, A, P ) la gramática con conjuntos de símbolos V y S, 
	                     con el axioma o símbolo inicial A "número decimal" 
	                     y con las producciones P dadas en forma BNF 
	                     como sigue: 
  1. < número-decimal> ::= < entero-sin-signo> | < fracción-decimal> |
  2. < fracción-decimal> ::= < entero-sin-signo> < fracción-decimal>
  3. < entero-sin-signo> ::= < dígito> | < dígito> < entero-sin-signo>
  4. < dígito> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

La siguiente figura muestra un árbol de deducción, en esta gramática, del número decimal 23.14. Observe que el enunciado BNF número 3 es recursivo en la segunda parte de su lado derecho.

Es decir, la producción "entero-sin-signo dígito entero-sin-signo" es recursiva y también es normal. En general, se sabe que muchas gramáticas diferentes pueden producir el mismo lenguaje. Si se reemplaza la línea anterior número 3 con la línea: 3'.

< entero-sin-signo> ::= < dígito> | < entero-sin-signo> < dígito>

se tendría una gramática diferente que produce exactamente el mismo lenguaje, a saber, los números decimales formados de manera correcta. Sin embargo, esta gramática contiene una producción recursiva que no es normal.

Ejemplo: Se proporcionará una gramática que especifique una parte de varios lenguajes de programación reales. En estos lenguajes, un identificador (un nombre para una variable, función, subrutina, etcétera) debe estar compuesto por letras y dígitos y debe comenzar con una letra. La siguiente gramática, con las producciones dadas en BNF, tiene precisamente estos identificadores como su lenguaje.

  • G = (V, S, identificador, )
  • N = {identificador, resto, dígito, letra}
  • S = {a, b, c, . . . , z, 0, 1, 2, 3, . . . , 9}, V = N U S

  1. < identificador>::= < letra>| < letra>< resto>
  2. < resto>::= < letra>| < dígito>| < letra>< resto>| < dígito>< resto>
  3. < resto>::= a | b | c . . . | z
  4. < dígito>::= 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9

Se observa que las producciones "resto letra resto" y "resto dígito resto" que aparecen en el enunciado 2 BNF, son recursivas y normales. Volver al principio

ESQUEMAS DE TRADUCCION
Un esquema de traducción es una gramática independiente del contexto en la cuál se han asociado atributos a los símbolos de la gramática. Un atributo queda caracterizado por un identificador o nombre y un tipo o clase. Además se han insertado acciones, esto es, código Perl/Python/C, ...en medio de las partes derechas. En ese código es posible referenciar los atributos de los símbolos de la gramática como variables del lenguaje subyacente.

El orden en que se evalúan los fragmentos de código es el de un recorrido primero-profundo del árbol de análisis sintáctico. Mas específicamente, considerando a las acciones como hijos-hoja del nodo, el recorrido que realiza un esquema de traducción es:


 1     sub esquema_de_traduccion {
 2       my $node = shift;
 3 
 4       for my $child ($node->children) { # de izquierda a derecha
 5         if ($child->isa('ACTION') {
 6           $child->execute;
 7         }
 8         else { esquema_de_traduccion($child) }
 9       }
10     }
El bucle de la línea 4 recorre a los hijos de izquierda a derecha, se debe dar la siguiente condición para que un esquema de traducción funcione:

Para cualquier regla de producción aumentada con acciones, de la forma

A X1 ...Xj action{ ( $ A {b}, $ X1{c}. . . Xn{d} ) } Xj+1 ...Xn

Debe ocurrir que los atributos evaluados en la acción insertada después de Xj dependan de atributos y variables que fueron computadas durante la visita de los hermanos izquierdos o de sus ancestros. En particular no deberían depender de atributos asociados con las variables Xj+1 ...Xn. Ello no significa que no sea correcto evaluar atributos de Xj+1 ...Xn en esa acción.

Así, un ESQUEMA DE TRADUCCIÓN es la gramática independiente del contexto en cuyas partes derechas de sus reglas de producción se han insertado en las fragmentos de código denominados ACCIONES SEMÁNTICAS, que actúan, calculan y modifican los atributos asociados con los nodos del árbol sintáctico.

El orden en que se evalúan los fragmentos es el de un recorrido primero-profundo del árbol de análisis sintáctico.

Para poder aplicar un esquema de traducción hay que construir el árbol sintáctico y después aplicar las acciones empotradas en las reglas en el orden de recorrido primero-profundo. Por Ejemplo, si en la regla A a ß el nodo asociado con una producción: deducimos un fragmento de código:

A a {action}ß

La acción {action} se ejecutará después de todas las acciones asociadas con el recorrido del subárbol de a y antes que todas las acciones asociadas con el recorrido del subárbol ß.

El siguiente esquema de traducción recibe como entrada una expresión en infijo y produce como salida su traducción a postfijo para expresiones aritméticas con sólo restas de números:

  • .expr expr1 - NUM { $expr{TRA} = $expr[1]{TRA}." ".$NUM{VAL}." - "}
  • .expr NUM { $expr{TRA} = $NUM{VAL} }

Las apariciones de variables sintácticas en una regla de producción se indexan como se ve en el Ejemplo, para distinguir de que nodo del árbol de análisis estamos hablando.

Cuando hablemos del atributo de un nodo utilizaremos una indexación tipo hash. Aquí VAL es un atributo de los nodos de tipo NUM denotando su valor numérico y para accederlo escribiremos $NUM{VAL}. Análogamente $expr{TRA} denota el atributo "traducción" de los nodos de tipo expr.

Luego un atributo tal que su valor en un nodo puede ser computado en términos de los atributos de los hijos del nodo se dice que es un atributo sintetizado.
Un Ejemplo: de atributo heredado es el tipo de las variables en las declaraciones:

  • decl type{ $list{T} = $type{T} } list
  • type INT { $type{T} = $int }
  • type STRING{ $type{T} = $string }
  • List ID, { $ID{T} = $list{T}; $list[1]{T} = $list{T} }list1
  • List ID { $ID{T} = $list{T} }
Volver al principio

SISTEMAS CANONICOS
En el ámbito de la inteligencia artificial: La inteligencia suele asociarse con "regularidades" y el comportamiento inteligente suele asociarse a ejecutar reglas.
Newell y Simon 70's proponen los sistemas de producción como un modelo psicológico del comportamiento humano, suponiendo que el conocimiento humano se representa en forma de producciones o reglas de producción. Así, se asemeja al proceso de memoria humano: memoria a corto plazo (deducciones intermedias) y Memoria a largo plazo (producciones).
Los expertos tienden a expresar sus técnicas de solución de problemas en forma de reglas "situación - acción".

Las reglas de producción es un formalismo que se uso desde antes en teoría de autómatas, gramáticas formales y en el diseño de lenguajes de programación.
Originalmente las producciones eran reglas gramaticales para manipular cadenas de símbolos.

Ejemplo:
A = {a,b,c} (alfabeto)
Axiomas: a, b, c, aa, bb, cc

Producciones:
$ a$a
$ b$b
$ c$c

Estas reglas generan palíndromos, Ejemplo: bacab.

Las reglas de producción usadas en los sistemas expertos difieren un poco de las producciones, pero los principios son los mismos.
Reglas de producción manipulan estructuras de símbolos, como listas o vectores.
Se tiene:

  • Un conjunto N de nombres de objetos en el dominio
  • Un conjunto P de propiedades que representan atributos de los objetos
  • Un conjunto V de valores que los atributos pueden tener

Generalmente se usa una tripleta: (objeto atributo valor).

A veces las reglas se ponen: P1, . . .Pm Q1, . . .Qn. Que significa:
IF las condiciones P1 y P2 y . . .y Pm se cumplen
THEN realiza las acciones Q1 y Q2 y . . .y Qn.

Ejemplo:
IF Animal es_un carnivoro AND
Animal color cafe AND
Animal tiene rayas
THEN Animal es tigre

PROPIEDADES DE LAS REGLAS:

  • MODULARIDAD:
    Cada reglas define un pequeño y relativamente idependiente pedazo de conocimiento
  • INCREMENTALIDAD:
    Nuevas reglas pueden ser añadidas a la base de conocimiento relativamente independiente de las demás
  • MODIFICABILIDAD:
    Como consecuencia de la modularidad, las reglas viejas pueden ser modificadas
  • TRANSPARENCIA:
    Habilidad de explicar sus decisiones y soluciones

UN SISTEMA DE PRODUCCIÓN tiene:

  • UN CONJUNTO DE REGLAS: Base de conocimiento.
  • UN INTERPRETE DE REGLAS: O máquina de inferencia, que decide que regla aplicar, controla la actividad del sistema.
  • UNA MEMORIA DE TRABAJO: Que guarda los datos, metas, y resultados intermedios

PARADIGMA: No es más fuerte la razón
porque se exprese a gritos..!! (Alejandro Casona)

CLASIFICACIÓN DE LENGUAJE FORMAL: Según Noah Chomsky:

Lenguaje:
Sin restricciones
Dependiente del contexto
Independiente del contexto
Regular

  1. LENGUAJE SIN RESTRICCIONES: Llamado tambien Lenguaje Irrestricto, genéricamente se define como: L(G) = { w | S -->*w, w ÎST*}
    Donde:
    • S : Axioma o cadena primigenia, a partir del cual se efectuan las derivaciones para obtener las palabras del lenguaje.

    • S -->* w: Derivaciones posibles de la cadena w a partir del axioma S.

    • ST* : Alfabeto de Símbolos Terminales, incluida la palabra vacía.

    L(G) = { w | S -->*w, w ÎST*} , será un lenguaje irrestricto, si es generado por una Gramática Irrestricta, definida como:

    G = ( S T, SN, S, P)

    Donde:

    • ST: Alfabeto de Símbolos Terminales.
    • SN: Alfabeto de Símbolos No terminales.
    • S: Axioma.
    • P: Producciones que se caracterizan por que cada cadena generada, en su parte izquierda tiene al menos un símbolo no terminal y en su parte derecha no requiere de ningún tipo de restricción.

      P = { ( u::= v) | u = x Ay, u Î A+, v, x, y Î A*, A Î AN }

    EJEMPLO La gramática G = ( S T, SN, S, P) = ( { i, l, o, w }, { X, Y, S }, S, P)

    Con las producciones:

    • P = { ( S ::= Xi ), ( Xi ::= wYo ), ( Y ::= iY ),( Yo ::= l ),( Y ::= l )}

    • Las derivaciones serán:
      • S --> Xi --> wYo --> wil
      • S --> Xi --> wYo --> wiYo --> wilo

    Se genera el lenguaje de formato: L = { wil, wilo, . . .}

    EJEMPLO La gramática G = ( S T, SN, S, P) = ( { a, c, i, o, r, p }, { X, Y, S }, S, P)

    Con las producciones:

    • P = {( S ::= cX ),( X ::= aX ),( X ::= rY ),( Y ::= pY ),( Y ::= o ),( pY ::= io )}

    • Las derivaciones serán:
      • S --> cX --> caX --> carY --> caro
      • S --> cX --> caX --> carY --> carpY --> carpio

    Se genera el lenguaje de formato: L = { caro, carpio, . . .}

    EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { 0, 1 }, { A, B, S }, S, P)

    generará el lenguaje de formato: L = { 11, 101 , 111, . . .}, si sus producciones son:

    P = { ( S ::= A0 ), ( A ::= 1B1 ), ( 1 A ::= AB0 ), ( B ::= l ), ( B ::= 1 ), ( B ::= 0 )

    Con tales producciones, las derivaciones serán:

    • S --> AO --> 1B1 --> 1l1 --> 11
    • S --> AO --> 1B1 --> 1B1 --> 101
    • S --> AO --> 1B1 --> 1B1 --> 111

    Estas gramáticas irrestrictas, generan cualquier lenguaje formal irrestricto del tipo 0, sobre un alfabeto S, reconocidos por una Máquina de Turing, que permiten estructurar frases sin restricciones con el tipo de producciones: X=>Y, donde:

    • X: Cadena no vacía de símbolos no terminales y/o terminales.
    • Y: Cadena cualquiera de símbolos no terminales y/o terminales.

    Para evitar la generación indiscriminada de palabras insertando en cualquier tramo de una derivación una cadena Y, en las producciones de estas gramáticas la parte:

    • IZQUIERDA no puede ser la palabra vacía l, así no habrán producciones de la forma l => Y.
    • DERECHA puede ser la cadena vacía, así habrán producciones de la forma Y =>, así, si en el tramo de una derivación se produce una secuencia que contenga la subcadena Y, podrá eliminarse, reduciendo la longitud de la cadena durante una derivación.

    EJEMPLO: Podrás verificar que la gramática G = ( S T, SN, S, P) = ( { a }, { S,M,N,Q,R,T }, S, P)

    • generará el lenguaje de formato: L = { a2| Poencia + de 2}, si sus producciones son:

    • P = { ( S ::= MQaN ), ( Qa ::= MaQ ), ( QN ::= RN | T ), ( aR ::= Ra ), ( MR ::= MQ ), ( MT ::= l )


    Volver al principio

    PARADIGMA: Cuando todo el mundo se equivoca;
    todo el mundo tiena razón...!!! (Chaussee)

  2. LENGUAJE DEPENDIENTE DE CONTEXTO: Este lenguaje, genéricamente se define como: L(G) = { w | S -->*w, w ÎST*}
    Donde:
    • S : Axioma o cadena primigenia, a partir del cual se efectuan las derivaciones para obtener las palabras del lenguaje.

    • S -->* w: Derivaciones posibles de la cadena w a partir del axioma S.

    • ST* : Alfabeto de Símbolos Terminales, incluida la palabra vacía.

    • L(G) = { w | S -->*w, w ÎST*} , será un lenguaje dependiente del contexto, si es generado por una Gramática Dependiente del Contexto, definida como:

      G = ( S T, SN, S, P)

      Donde:

      • ST: Alfabeto de Símbolos Terminales.
      • SN: Alfabeto de Símbolos No terminales.
      • S: Axioma.
      • P: Producciones que se caracterizan por que las producciones para generar cada cadena, tienen en cuenta lo que viene antes y después del símbolo que se sustituye.

        P = { (S ::= l) o ( xAy::=xvy ) | x = y Î A*, A ÎSN, v ÎST+ }

        Las derivaciones efectuadas a partir de estas producciones, implican que las palabras generadas siempre tienen longitud mayor o igual que las anteriores en la derivación.

      Estas gramáticas "Sensibles al Contexto", se caracteriza porque las partes derechas e izquierdas debe tener una parte en común y solo admite como regla compresora S ::= l.

      Son dependientes del contexto porque tienen en cuenta lo que viene antes y después del símbolo que se sustituye. Por ello en la fórmula anterior x e y son el contexto de la transformación de A en v.

    EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { i, l, o, w }, { X, Y, Z, S }, S, P)

    Con las producciones:

    • P = { ( S ::= iXo ), ( iXo ::= iYl ), ( iYl ::= wiZl ),( iYl ::= wil ), ( iZl ::= ilo)}

    • Las derivaciones serán:
      • S --> iXo --> iYl --> wil
      • S --> iXo --> iYl --> wiZl --> wilo

    Se genera el lenguaje de formato: L = { wil, wilo, . . .}

    EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { a, c, i, o, r, p }, { X, Y, S }, S, P)

    Con las producciones:

    • P = { ( S ::= cXo ), ( cXo ::= caXo ), ( aXo ::= arYo ),( aXo ::= aro ), ( rYo ::= pYo), ( pYo ::= pio)}

    • Las derivaciones serán:
      • S --> cXo --> caXo --> caro
      • S --> cXo --> caXo --> carYo --> carpYo --> carpio

    Se genera el lenguaje de formato: L = { caro, carpio, . . .}


    Volver al principio

  3. LENGUAJE INDEPENDIENTE DE CONTEXTO Este lenguaje, genéricamente se define como: L(G) = { w | S -->*w, w ÎST*}
    Donde:
    • S : Axioma o cadena primigenia, a partir del cual se efectuan las derivaciones para obtener las palabras del lenguaje.

    • S -->* w: Derivaciones posibles de la cadena w a partir del axioma S.

    • ST* : Alfabeto de Símbolos Terminales, incluida la palabra vacía.

    • L(G) = { w | S -->*w, w ÎST*} , será un lenguaje independiente del contexto, si es generado por una Gramática Independiente del Contexto, definida como:

      G = ( S T, SN, S, P)

      Donde:

      • ST: Alfabeto de Símbolos Terminales.
      • SN: Alfabeto de Símbolos No terminales.
      • S: Axioma.
      • P: Producciones que al generar una cadena a partir de otra, el símbolo terminal a transformar no depende de sus símbolos vecinos, tanto a la izquierda como a la derecha; por ello, al efectuar derivaciones para transformar un no terminal, no hace falta saber que hay alrededor de el.

        P = { (S ::= l) ó ( A ::= v ) | A ÎSN, v ÎST+ }

    EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { i, l, o, w }, { X, Y, S }, S, P)

    Con las producciones:

    • P = { ( S ::= X ), ( X ::= wY ), ( Y ::= iY ),( Y ::= lY ),( Y ::= l ),( Y ::= o )}

    • Las derivaciones serán:
      • S --> X --> wY --> wiY --> wil
      • S --> X --> wY --> wiY --> wilB --> wilo

    Se genera el lenguaje de formato: L = { wil, wilo, . . .}

    EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { a, c, i, o, r, p }, { X, Y, S }, S, P)

    Con las producciones:

    • P = { ( S ::= cXo ), ( X ::= ar ), ( X ::= aYo ),( Y ::= pi )}

    • Las derivaciones serán:
      • S --> cXo --> caro
      • S --> cXo --> caYo --> carYo --> carpio

    Se genera el lenguaje de formato: L = { caro, carpio, . . .}

    EJEMPLO: En la gramática

    G = ( ST, NT, S, P )

    Para los parámetros:

    • ST : Símbolos terminales: { a, b }
    • SN : Símbolos no terminales: { S, A }
    • S: Axioma
    • P: Producciones

      S --> aB|ba
      A --> a | aS |bAA

    • B --> b | bS |aBB

    Derivaciones: S-->aB-->abS-->abba

    EJEMPLO: Sea la GIC cuyas producciones son:
    S --> AB;
    A --> aA | a;
    B --> bB | b

    La gramática tendrá la forma G = ( ST, SN, S, P ) cuyos elementos son:

    • ST : Símbolos terminales: { a, b }
    • SN : Símbolos no terminales: { S, A }
    • S: Axioma: A
    • P: Producciones:
      S --> A B
      A --> a A | a
      B --> b B | b

    Sus derivaciones serán:
    S ==> AB
    AB==> AbB
    AbB==> AbbB
    AbbB==> Abbb
    Abbb==> aAbbb
    aAbbb==> aabbb

    La cadena a a b b b se derivará como: S ==>AB==> AbB==> AbbB==> Abbb==> aAbbb==> aabbb

    Lenguaje Independiente de contexto: aceptado por el Autómata de Pila, posee dos formas equivalentes de caracterizarlo:

    • Por vaciado de Pila: El lenguaje aceptado es el conjunto de palabras que permite transitar desde el estado inicial hasta una descripción instantánea en la que tanto la entrada como la pila estén vacías.

      LV = { x | (q0, x, A0)|-*(q0, x, A0)
      y pÎQ y xÎS*}

      EJEMPLO Un lenguaje aceptado por vaciado de pila sería:

      LV = {x(1+l)x-1|x=(0+1)+}

      Intuitivamente, este autómata acepta ceros y unos en la entrada, que va introduciendo en la pila por medio del estado q0.

      En cualquier momento puede seguir leyendo la palabra x, o empezar a leer la misma palabra de entrada, pero al revés (su inversa) y transitar al estado q1 que se encargará de comprobar que lee bien la inversa.

    • Por Estado Final: El lenguaje aceptado por estado final es el equivalente al de los autómatas finitos, todas las palabras que permiten transitar desde el estado inicial a uno final.

      Se aceptarán todas las palabras que permitan pasar de la configuración inicial a una en la que se haya leído toda la palabra de entrada y el autómata esté en uno de los estados finales, independientemente del contenido de la pila.

      LEF = { x | (q0, x, A0)|-*(q0, l , X) y pÎF , xÎS*y XÎ T*

      Los lenguajes de los autómatas por vaciado de pila y por estado final son equivalentes, y siempre es posible obtener un AP que reconozca por vaciado de pila a partir de un AP que reconozca por estado final y viceversa.

  4. LENGUAJE REGULAR Este lenguaje, también denominado lineal, genéricamente se define como: L(G) = { w | S -->*w, w ÎST*}
    Donde:
    • S : Axioma o cadena primigenia, a partir del cual se efectuan las derivaciones para obtener las palabras del lenguaje.

    • S -->* w: Derivaciones posibles de la cadena w a partir del axioma S.

    • ST* : Alfabeto de Símbolos Terminales, incluida la palabra vacía.

    • L(G) = { w | S -->*w, w ÎST*} , será un Lenguaje Regular, si es generado por una Gramática Regular, definida como:

      G = ( S T, SN, S, P)

      Donde:

      • ST: Alfabeto de Símbolos Terminales.
      • SN: Alfabeto de Símbolos No terminales.
      • S: Axioma.
      • P: Producciones que al generar una cadena a partir de otra, restringen a la presencia de un solo Símbolo Terminal en la parte izquierda, mientras la parte derecha, debe poseer también un solo Terminal, el cual puede o no, estar seguido de un solo Símbolo No terminal.

        Sus producciones pueden ser:

        • Lineal por Izquierda:
          P = { (S ::= l) ó ( A ::= Ba ) ó ( A ::= a ) | A, B ÎSN, a ÎST+ }

        • Lineal por Derecha:
          P = { (S ::= l) ó ( A ::= aB ) ó ( A ::= a ) | A, B ÎSN, a ÎST+ }

    EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { i, l, o, w }, { X, Y, Z, S }, S, P)

    Con las producciones:

    • P = { ( S ::= X ), ( X ::= wX ), ( X ::= iY ),( Y ::= l ),( Y ::= lZ ),( Z ::= o )}

    • Las derivaciones serán:
      • S --> X --> wX --> wiY --> wil
      • S --> X --> wY --> wiY --> wilZ --> wilo

    Se genera el lenguaje de formato: L = { wil, wilo, . . .}

    EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { a, c, i, o, r, p }, { X, Y, Z, S }, S, P)

    Con las producciones:

    • P = { ( S ::= X ), ( X ::= cX ), ( X ::= aY ),( Y ::= rY ),( Y ::= o ),( Y ::= pZ ),( Z ::= iZ ),( Z ::= o )}

    • Las derivaciones serán:
      • S --> X --> cX --> caY --> carY --> caro
      • S --> X --> cX --> caY --> carY --> carpZ --> carpiZ --> carpio

    Se genera el lenguaje de formato: L = { caro, carpio, . . .}

    Los LENGUAJES REGULARES sobre un alfabeto S, están formados por:

    • El lenguaje vacío Ø,

    • Los lenguajes unitarios, incluido { e }

    • Los lenguajes obtenidos a partir de la concatenación AB,

    • Los lenguajes obtenidos a partir de la unión AÈB

    • Los lenguajes obtenidos a partir de la cerradura de estrella A* de lenguajes.

    DEFINICION de LENGUAJES REGULARES: Son definidos recursivamente por las siguientes condiciones de recursividad:

    1. Ø Es un lenguaje regular

    2. {e} Es un lenguaje regular

    3. Para todo a ÎS, {a} es un lenguaje regular

    4. Si A y B son lenguajes regulares, entonces AÈB, AB y A* son lenguajes regulares

    5. Ningún otro lenguaje S es regular.

    Luego, según es conceptos recursivos, para el alfabeto S = { a, b } podemos afirmar que el lenguaje es regular:

    1. Ø y { e } Porque cumple las condiciones 1 y 2 de la recursividad
    2. {a} y {b} Porque cumple la condición 3 de la recursividad
    3. {a, b} Porque cumple la condición 4, por existir unión de los lenguajes {a} y {b}
    4. {a . b} Porque cumple las dos razones anteriores
    5. {a, ab, b} Porque cumple las razones anteriores
    6. { ai | i 0 } Porque cumple la Condición 4: ai es potencia iésima de {a} que es concatenación sucesiva
    7. { ai bj | i 0, j0 } Porque cumple las razones anteriores
    8. { (ab)i | i 0 } Porque cumple las razones anteriores

    LENGUAJE GENERADO POR UNA GRAMATICA REGULAR: Representada como L(G) y está formado por todas las cadenas generadas por las producciones de tal gramática; o también podemos decir que L(G) está constituida por palabras obtenidas por la aplicación de derivaciones a partir del axioma de la gramática. Este lenguaje, podemos representarlo en formato:

    • L(G): FORMA SENTENCIAL: Representa a L(G) bajo el formato S -->* x donde x será la forma sentencial si existe una derivación desde el axioma hasta esa palabra, de esta manera al conjunto de todas las sentencias de la gramática L(G), quedará representada como:

      L(G) = { x | S -->*x, x ÎST*}

      En esta expresión diremos que x es SENTENCIA si es de forma sentencial y todos sus símbolos pertenecen al alfabeto de símbolos terminales.

      L(G): EJEMPLO: En la gramática G = ( ST, NT, S, P )

      Para los parámetros:

      • ST : Símbolos terminales: { a, b }

      • SN : Símbolos no terminales: { S, A }

      • S: Axioma: A

      • P: Producciones
        S --> b A
        A --> a a A | b | l

      L(G) contendrá todas las cadenas de forma: b a2n b y b a2n

      Lo cual significa que el lenguaje generado por la gramática será:

      L(G) = b ( a2n ) * ( b È l)

      Deducimos de esta definición que el lado derecho de una producción es una cadena que tiene la forma

      ST *( SN l ),

      donde l puede ser el lado derecho de tal producción.

      De manera que en nuestro ejemplo S --> l indicará que concluye la generación de la cadena, y del mismo modo que la producción A --> b borrará el símbolo no terminal A.

    • L(G): FORMA DE PARES: Para llevarlas al formato simplificado de pares de valores ( x, y ), cuya producción se representará como x --> y, emparejemos los símbolos no terminales de SN con las cadenas de

      ST *( SN È l),

      De manera que resultarán los pares ordenados:

      SN x ST *( SN È l);

      Así las producciones de nuestro ejemplo

      L(G) = b ( a2n ) * ( b È l)

      Podrán representarse como los siguientes pares:

      P = { ( S, b A ), ( A, a a A ), ( A, b ), ( A, l) }

      L(G): EJEMPLO: Dada la definición:

      G = ( ST, SN, S, P )

      Sea la gramática G1 = ( { 0, 1 }, { A, B }, A, P ), para los pares de producciones

      • ST : Símbolos terminales: { 0, 1 }

      • SN : Símbolos no terminales: { A, B }

      • S: Axioma: A

      • P: Producciones
        { ( A ::= 1B1 ), ( A ::= 0B0 ), ( B ::= A ), ( B ::= 1 ), ( B ::= 0 ), ( B ::= l ) }

      Derivaciones

      
      	 A ==> 1B1
      	 1B1 ==> 1 l 1 ==> 1 1
      	
      	 A ==> 1B1
      	 1B1 ==> 101
      	
      	 A ==> 1B1
      	 1B1 ==> 111
      	

      El lenguaje generado sería el de sus palabras palíndromos o simétricas.

      L(G) = { 11, 101, 111, 00, 000, 010, 1001, 1111, 0000, 0110,…}

      Esta producción también puede representarse como:

      A ::= 1B1 | 0B0; B ::= A | 1 | 0 | l

      SENTENCIA: Simbolizada como: S -->* x, Para: x È ST*

      Donde x es sentencia si es de forma sentencial y todos sus símbolos pertenecen al alfabeto de símbolos terminales.

      Así para la gramática anterior: G 1 = ( { 0, 1 }, { A, B }, A, P)

      Serán sentencias 0 1 0 y 1 0 0 1 pero no 1 A 1

    Los lenguajes regulares son aceptados por las Máquinas de Estados Finitos, las que se define como: L(A)=(Q,S, q0,F, f)

    Definido formalmente como: L(G) = { w | S -->*w, w ÎST* y f(q0, w) Î F)}

Volver al principio


PARADIGMA: Desdichado el que duerme en el mañana..!! (Hesiodo de Asera)

TEORIA de las GRAMATICAS FORMALES:
Gramática: Irrestricta
Sensible al Contexto
Contexto Libre
Regular

La gramática es la técnica de hablar y escribir correctamente, ella se encarga de estructurar formalmente un lenguaje natural o artificial. Para este fin, la gramática:

- DEFINE REGLAS: Formadoras de sus palabras componentes.

- PRORCIONA FORMATOS: Validos de combinación de símbolos de su alfabeto.

- DESCRIBE NORMAS: Para generar el correspondiente lenguaje formal.

Operativamente la gramática:
- GENERA al lenguaje y si este no existe.
- DESCRIBE al lenguaje y si este ya existe.

Para operar las cadenas que conforman un lenguaje, la gramatica desarrolla sobre un alfabeto el siguiente proceso:

  1. Parte de un símbolo inicial denominado AXIOMA.

  2. Detecta luego otros símbolos denominados NO TERMINALES, que representan subconjuntos o estados intermedios de generación de la cadena.

  3. Luego, sobre los anteriores, concreta un conjunto de PRODUCCIONES que permiten efectuar las correspondientes transformaciones de sus símbolos no terminales.

  4. Termina su tarea cuando la cadena queda constituido solo por símbolos TERMINALES.

DEFINICION DE GRAMATICA:
Todo lenguaje definido como: L(G) = { w | S -->*w, w ÎST*} será un Lenguaje formal, si es generado por una gramatica definida como:

G = ( ST, SN, S, P) , donde:
- ST: Alfabeto de Símbolos Terminales.
- SN: Alfabeto de Símbolos No terminales.
- S: Axioma.
- P: Producciones que permiten generar una cadena a partir de otra. Estas Producciones pueden ser:

  1. Gramática Irrestricta: P = { ( u::= v) | u = x Ay, u Î A+, v, x, y Î A*, A Î AN }

  2. Gramática Independiente del Contexto: P = { (S ::= l) ó ( A ::= v ) | A ÎSN, v ÎST+ }

  3. Gramática Dependiente del Contexto: P = { (S ::= l) o ( xAy::=xvy ) | x = y Î A*, A ÎSN, v ÎST+ }

  4. Gramática Regular:

    - Lineal por Izquierda: P = { (S ::= l) ó ( A ::= Ba ) ó ( A ::= a ) | A, B ÎSN, a ÎST+ }

    - Lineal por Derecha: P = { (S ::= l) ó ( A ::= aB ) ó ( A ::= a ) | A, B ÎSN, a ÎST+ }

PARADIGMA: La felicidad es tener la convicción que nos aman por lo que somos,
..o mejor dicho, a pesar de lo que somos..!! (Anónimo)

TIPOS DE GRAMATICAS

  • GRAMATICAS SIN RESTRICCIONES
    El lenguaje L(G) = { w | S -->*w, w ÎST*}
    , es un lenguaje sin restricciones, si es generado por una Gramática Irrestricta definida como: G = ( ST, SN, S, P) Donde:
    • ST: Alfabeto de Símbolos Terminales.
    • SN: Alfabeto de Símbolos No terminales.
    • S: AXIOMA o Cadena de Inicio o Cadena Primigenia, a partir de labcual se comienzan a generar nuevas cadenas.
    • P: PRODUCCIONES que al generar una cadena a partir de otra, restringen a la presencia de un solo Símbolo Terminal en la parte izquierda, mientras la parte derecha, debe poseer también un solo Terminal, el cual puede o no, estar seguido de un solo Símbolo No terminal. O sea que:

      P = { ( u::= v) | u = x Ay, u Î A+, v, x, y Î A*, A Î AN }


    Comprenderás esta estructura de producciones, recordando los formatos de las:
    • GRAMÁTICAS REGULARES: Por pares de formato: N x S* ( N È e ).
      Observa que el lado izquierdo cada producción está formado por un único símbolo no terminal, mientras que el derecho está compuesto por cualquier cadena de terminales seguida por un no terminal.

    • GRAMÁTICAS INDEPENDIENTES del CONTEXTO : La estructura de la parte derecha de las producciones se hizo menos restrictiva, permitiéndose que fueran pares del producto N x S* ( N È e ).
      Así el lado derecho podrá contener cualquier numero de símbolos no terminales, mientras que el lado izquierdo sigue restringido a un único no terminal.

    • GRAMÁTICAS MENOS RESTRIGIDAS: Aunque la estructura del lado derecho de las producciones de las GIC es más elástica, podríamos sugerir los siguientes cambios en el contenido del lado izquierdo, para lograr una gramática más elástica.
      • Aceptar en el lado izquierdo cadenas con no terminales, aún cadenas de no terminales y terminales.

      • Las cadenas no vacías de terminales y no terminales, es la forma mas general, de modo que las producciones podrían ser pares del producto ( N È S ) x S* ( N È e ). , así eliminamos las restricciones para formar las producciones.

      • Si se permitiera que en el lado izquierdo de una producción fuera la cadena vacía, se podría tener mas de un punto de partida para las derivaciones; aspecto no deseable. Por ello, no aceptaremos l como lado izquierdo de una producción.

    • GRAMÁTICAS IRRESTRICTAS: Estas gramáticas generan un lenguaje del tipo Irrestricto están dotadas de mayor potencia generativa que las gramáticas independientes del contexto o las regulares.
      En su parte izquierda debe tener al menos un símbolo no terminal y en su parte derecha de sus producciones no requiere de ningún tipo de restricción.

      P = { ( u::= v) | u = x Ay, u Î A+, v, x, y Î A*, A Î AN }

      EJEMPLO La gramática G = ( ST, SN, S, P) = ( { i, l, o, w }, { X, Y, S }, S, P), con las producciones:

      • P = { ( S ::= Xi ), ( Xi ::= wYo ), ( Y ::= iY ),( Yo ::= l ),( Y ::= l )}

      • Las derivaciones serán:
        • S --> Xi --> wYo --> wil
        • S --> Xi --> wYo --> wiYo --> wilo

      Se genera el lenguaje de formato: L = { wil, wilo, . . .}

      EJEMPLO La gramática G = ( ST, SN, S, P) = ( { a, c, i, o, r, p }, { X, Y, S }, S, P), con las producciones:

      • P = {( S ::= cX ),( X ::= aX ),( X ::= rY ),( Y ::= pY ),( Y ::= o ),( pY ::= io )}

      • Las derivaciones serán:
        • S --> cX --> caX --> carY --> caro
        • S --> cX --> caX --> carY --> carpY --> carpio

      Se genera el lenguaje de formato: L = { caro, carpio, . . .}

      EJEMPLO: La gramática G = ( ST, SN, S, P) = ( { 0, 1 }, { A, B, S }, S, P)

      • generará el lenguaje de formato: L = { 11, 101 , 111, . . .}, si sus producciones son:

      • P = { ( S ::= A0 ), ( A ::= 1B1 ), ( 1 A ::= AB0 ), ( B ::= l ), ( B ::= 1 ), ( B ::= 0 )

      • Con tales producciones, las derivaciones serán:
        • S --> AO --> 1B1 --> 1l1 --> 11
        • S --> AO --> 1B1 --> 1B1 --> 101
        • S --> AO --> 1B1 --> 1B1 --> 111

      EJEMPLO: La gramática G3 = ( ST, SN, S, P ) = ( { 0, 1 }, { A, B, S }, S, P) generará el lenguaje de formato

      L(G3) = { 11, 101 , 111}, si sus producciones son

      P = { ( S ::= A0 ), ( A 0 ::= 1B1 ), ( 1 A ::= AB0 ),(B ::= l ), ( B ::= 1 ), ( B ::= 0 ) }

      Las derivaciones serán:

      S=>AO=>1B1=>1l1=>11

      S=>AO=>1B1=>101

      S=>AO=>1B1=>111

      Esta gramática genera el lenguaje L(G3) = { 11, 101 , 111,...}

      Estas gramáticas irrestrictas, generan cualquier lenguaje formal irrestricto del tipo 0, sobre un alfabeto S, reconocidos por una Máquina de Turing, que permiten estructurar frases sin restricciones con el tipo de producciones: X =>Y , donde:

      - X: Cadena no vacía de símbolos no terminales y/o terminales.

      - Y: Cadena cualquiera de símbolos no terminales y/o terminales.

      Para evitar la generación indiscriminada de palabras insertando en cualquier tramo de una derivación una cadena Y, en las producciones de estas gramáticas la parte izquierda debe tener al menos un símbolo no terminal y en su parte derecha de sus producciones no requiere de ningún tipo de restricción.

      P = { ( u::= v) | u = x Ay, u Î A+, v, x, y Î A*, A Î AN }

      - - IZQUIERDA no puede ser la palabra vacía l, así no habrán producciones de la forma l => Y.
      - - DERECHA puede ser la cadena vacía, así habrán producciones de la forma Y =>, así, si en el tramo de una derivación se produce una secuencia que contenga la subcadena Y, podrá eliminarse, reduciendo la longitud de la cadena durante una derivación.

      EJEMPLO: La gramática G= ( S T , SN, S, P ) = ( { a }, { S, M, N, Q, R, T }, S, P) genera el lenguaje: L = {an| n > 2 } si sus producciones son

      • S=>MQaN
      • Qa=>MaQ
      • QN=>RN|T
      • aR=>Ra
      • MR=>MQ
      • aT=>Ta
      • MT=>l
    PARADIGMA: Dijo Dios al terminar de crear al primer hombre
    .."Lo puedo hacer mejor..." . . y creo a la mujer..!!
    (Wilucha)

    Volver al principio

  • GRAMATICA DEPENDIENTE DE CONTEXTO
    O GRAMATICA TIPO 1: Sensible al Contexto, posee en sus partes derechas e izquierdas una parte en común y solo admite como regla compresora S ::= l. Se la define como: G = ( S T, SN, S, P)
    Donde:
    • ST: Alfabeto de Símbolos Terminales.
    • SN: Alfabeto de Símbolos No terminales.
    • S: Axioma o Cadena Primigenia o Cadena Inicial
    • P: Las producciones para generar cada cadena, tienen en cuenta lo que viene antes y después del símbolo que se sustituye.

      P = { (S ::= l) o ( xAy::=xvy ) | x = y Î A*, A ÎSN, v ÎST+ }

      Las derivaciones efectuadas a partir de estas producciones, implican que las palabras generadas siempre tienen longitud mayor o igual que las anteriores en la derivación.

    EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { i, l, o, w }, { X, Y, Z, S }, S, P), Con las producciones:

    • P = { ( S ::= iXo ), ( iXo ::= iYl ), ( iYl ::= wiZl ),( iYl ::= wil ), ( iZl ::= ilo)}

    • Las derivaciones serán:
      • S --> iXo --> iYl --> wil
      • S --> iXo --> iYl --> wiZl --> wilo

    Se genera el lenguaje de formato: L = { wil, wilo, . . .}

    EJEMPLO La gramática G = ( S T, SN, S, P) = ( { a, c, i, o, r, p }, { X, Y, S }, S, P), Con las producciones:

    • P = { ( S ::= cXo ), ( cXo ::= caXo ), ( aXo ::= arYo ),( aXo ::= aro ), ( rYo ::= pYo), ( pYo ::= pio)}

    • Las derivaciones serán:
      • S --> cXo --> caXo --> caro
      • S --> cXo --> caXo --> carYo --> carpYo --> carpio

    Se genera el lenguaje de formato: L = { caro, carpio, . . .}

    EJEMPLO: La gramática: G3 = ( { 0, 1 }, { A, B, S }, S, P) no es del tipo 1, porque posee una regla compresora cuya parte izquierda no es el axioma S ::= L;
    En cambio: G4 = ( { 0, 1 }, { A, B }, A, P ) es del tipo 1,
    Donde:
    P = { ( A ::= 1B1 ), ( A ::= 11 ), (1B1 ::= 101 ), ( 1B1 ::= 111 ) }

    Estas gramáticas son equivalentes pues generan el mismo lenguaje: L(G4) = L(G3) = { 11, 101 , 111}


    Volver al principio

    PARADIGMA: Nadie puede evitar que los latosos entren en casa;
    pero es un error ofrecerles una silla...!!! (Proverbio Arabe)

  • GRAMATICA INDEPENDIENTE DE CONTEXTO
    El lenguaje L(G) = { w | S -->*w, w ÎST*}, es un lenguaje independiente del contexto, si es generado por una Gramática Independiente del Contexto definida como: G = ( ST, SN, S, P) Donde:

    - ST: Alfabeto de Símbolos Terminales.

    - SN: Alfabeto de Símbolos No terminales.

    - S: AXIOMA o Cadena de Inicio o Cadena Primigenia, a partir de la cual se comienzan a generar nuevas cadenas.

    - P: Producciones que al generar una cadena a partir de otra, el símbolo terminal a transformar no depende de sus símbolos vecinos, tanto a la izquierda como a la derecha; por ello, al efectuar derivaciones para transformar un no terminal, no hace falta saber que hay alrededor de el.

    P = { (S ::= l) ó ( A ::= v ) | A ÎSN, v ÎST+ } Cada gramática define el lenguaje formal de todas las sentencias que están formadas exclusivamente por los símbolos terminales a los que se puede llegar mediante derivación a partir del símbolo inicial.
    Noam Chomsky definió cuatro tipos de gramáticas formales, desde las mas generales a las mas especificas. Esta clasificación permite introducir, al mismo tiempo ,una clasificación en los lenguajes que estas generan, como en los autómatas que reconocen los lenguajes generados por las gramáticas; de acuerdo a la siguiente jerarquía gramatical:

    GEF: Gramática de Estructura de frase
    --- GIC: Gramática Independiente del Contexto
    --- GR: Gramática Regular

    Cuyas producciones, podemos representarlas bajo el formato: ( N U S)* N ( N U S )* -> ( N U S )*.

    PARADIGMA Educar a un alumno es esencialmente
    enseñarle a prescidir de nosotros..!!! (Berge)

    GRAMÁTICA DE ESTRUCTURA DE FRASES
    Si a la gramática independiente de contexto le eliminamos las restricciones del lado derecho de las producciones lograremos que la misma pueda estar formada por cualquier cadena sobre NÈå.

    Una Gramática de Estructuras de Frases es aquella en la que los lados izquierdos de las reglas de producción P pueden estar formados por cualquier cadena no vacía sobre NÈ å las cuales contienen algún no terminal:

    PÍ (NÈ å )*N(NÈ å )* x (NÈ å )*

    Se las conoce también como gramáticas no restringidas. Las Gramáticas Dependientes de Contexto poseen gramáticas de Estructura de Frases en las cuales las producciones se restringen a

    a ->b tal que |a |>=|b |.

    Su forma normal es a1Aa2->a1ba2 con b¹l , permite que el no terminal A sea reemplazado por b solo cuando A aparezca en el contexto de a1 y a2.

    LENGUAJE GENERADO POR UNA GIC
    Se simboliza L(G), y es el lenguaje formado por todas las cadenas que se puedan derivar, a partir del símbolo inicial, de las producciones de la gramática independiente de contexto G que tienen el siguiente formato:

    (PÍN x (å ÈN)*)

    Así para la GIC S-> aSb |l diremos que por inducción sobre n, se genera el LIC = { an bn | n>=0 }, el cual no es un lenguaje regular, por lo que podemos afirmar que a pesar que el conjunto de lenguajes regulares pertenecen al conjunto de LIC, existen LIC que no son regulares.

    En síntesis toda gramática regular es una GIC y todo lenguaje regular es una LIC.

    GIC: Ejemplo: Sea la GIC cuyas producciones son: S->AB; A->aA | a; B->bB | b

    Sus elementos son:

    • N={S, B, A}
    • å={a,b}
    • S símbolo inicial
    • Y sus producciones
      P: S->AB
      A->aA|a
      B->bB|b

    Si consideramos la cadena aabbb sus derivaciones serán:

    S=>AB
    AB=>AbB
    AbB=>AbbB
    AbbB=>Abbb
    Abbb=>aAbbb
    aAbbb=>aabbb

    La cadena a a b b b se derivará como: S=>AB=>AbB=>AbbB=>Abbb=>aAbbb=>aabbb

    GIC: Ejemplo: La gramática G = ( S T, SN, S, P) = ( { i, l, o, w }, { X, Y, S }, S, P)

    Con las producciones:

    • P = { ( S ::= X ), ( X ::= wY ), ( Y ::= iY ),( Y ::= lY ),( Y ::= l ),( Y ::= o )}

    • Las derivaciones serán:
      • S --> X --> wY --> wiY --> wil
      • S --> X --> wY --> wiY --> wilB --> wilo

    Se genera el lenguaje de formato: L = { wil, wilo, . . .}

    GIC: Ejemplo:La gramática G = ( S T, SN, S, P) = ( { a, c, i, o, r, p }, { X, Y, S }, S, P)

    Con las producciones:

    • P = { ( S ::= cXo ), ( X ::= ar ), ( X ::= aYo ),( Y ::= pi )}

    • Las derivaciones serán:
      • S --> cXo --> caro
      • S --> cXo --> caYo --> carYo --> carpio

    Se genera el lenguaje de formato: L = { caro, carpio, . . .}

    PARADIGMA DE VIDA
    Si un pájaro te dice que estás loco,
    debes estarlo pues los pájaros no hablan...!!

    GIC: Ejemplo: En la gramática: G = ( ST, NT, S, P )

    Para los parámetros:

    • ST : Símbolos terminales: { a, b }
    • SN : Símbolos no terminales: { S, A }
    • S: Axioma
    • P: Producciones
      S --> aB|ba
      A --> a | aS |bAA
    • B --> b | bS |aBB

    Derivaciones: S-->aB-->abS-->abba

    GIC: Ejemplo: Sea la GIC cuyas producciones son:

    S --> AB;
    A --> aA | a
    B --> bB | b

    La gramática tendrá la forma G = ( ST, SN, S, P ) cuyos elementos son:

    • ST : Símbolos terminales: { a, b }
    • SN : Símbolos no terminales: { S, A }
    • S: Axioma: A
    • P: Producciones:
      S --> A B
      A --> a A | a
      B --> b B | b

    Sus derivaciones serán:

    • S ==> AB
    • AB==> AbB
    • AbB==> AbbB
    • AbbB==> Abbb
    • Abbb==> aAbbb
    • aAbbb==> aabbb

    La cadena a a b b b se derivará como: S ==>AB==> AbB==> AbbB==> Abbb==> aAbbb==> aabbb

    GIC: Ejemplo: Supongamos la gramática G = ( N,å ,A ,P ) donde:

    N={S}
    å ={a,b}
    A=S (símbolo inicial)
    P: S->aSb|l ( cadena vacia)

    Verifiquemos si la cadena aabb es generada o no por la GIC:

    S=>aSb
    aSb=>aaSbb
    aaSbb=> aabb

    Observemos que la cadena sí es generada por esta gramática, porque que al derivar desde el símbolo inicial S llegamos a una cadena de símbolos terminales.

    GIC: Ejemplo: Definir la GIC para el siguiente lenguaje L={xn,ym | m,n>0 y m=n ó m=2n}

    Definimos las siguientes producciones para el alfabeto å={x,y} para la condición: m = n

    S-> xAy|l

    A-> xAy|l

    Definimos las producciones con el alfabeto ST = { x, y } para la condición m = 2n

    S->x B y y | l

    B-> x B y y | l

    La gramática buscada GIC = ( å, N, S, P ) donde å = { x, y }, N = { S, A, B }, S el axioma y combina ambos conjuntos de producciones P:

    S-> x A y | x B y y | l

    A-> x A y | l

    B-> x B y y | l

    Limpiando estas producciones:

    S-> x A y | x B y y | x y | x y y | l

    A-> x A y | x y

    B-> x B y y | x y y

    ARBOL de DERIVACION ó ANÁLISIS
    Su estructura gráfica que brinda la posibilidad de simplificar el estudio de las producciones por medio de la visualización del proceso de derivación de una cadena, siempre que este no sea extenso, porque puede resultar incómoda su representación gráfica.

    Para derivar una cadena a través de una GIC, el símbolo inicial se sustituye por alguna cadena, luego, los no terminales se van sustituyendo uno tras otro, por otras cadenas hasta que ya no quedan símbolos no terminales, formándo finalmente una cadena con sólo símbolos terminales.

    Cuando una cadena determinada puede obtenerse por medio de otro proceso de derivación; es decir, por un proceso equivalente, se concluye que que hay más de un árbol de derivación posible asociado a una misma cadena del lenguaje L(G); que obligan a plantear el análisis correspondiente. Bienvenido al mundo de los autómatas

    El árbol tiene:

    • Nodo Raíz: Contiene al símbolo inicial.
    • Nodos intermedios: Contienen símbolos terminales y no terminales.
    • Ramas: Son nodos que contienen símbolos no terminales.
    • Hojas: Contienen símbolos terminales hojas.
    • Arcos: Son las derivaciones se las representa por flechas.

    GIC: Ejemplo: Sea la gramática G=(N,å, S,P) con N={S,A,C} ; å={a,b,c} ; S el símbolo inicial; y cuyas producciones son:

    S->AC
    A->aAb|ab
    C->cC|c
    Que genera el lenguaje
    L(G)={ ai bic j | i>0 y j>=i}

    Para la cadena aabbccc perteneciente a L(G), tenemos la siguiente derivación:

    S=>AC
    AC=>aAbC
    aAbC=>aabbC
    aabbC=>aabbcC
    aabbcC=>aabbccC
    aabbccC=>aabbccc

    S=>AC=>aAbC=>aabbC=>aabbcC=>aabbccC=>aabbccc, su árbol de derivación seria:

    Existen muchas derivaciones posibles para la cadena aabbccc,las cuales tienen el mismo arbol de derivacion anterior, por ejemplo:

    S=>AC=>AcC=>AccC=>Accc=>aAbccc=>aabbccc
    S=>AC=>AcC=>aAbcC=>aAbccC=>aAbccc=>aabbccc

    Estas distintas derivaciones posibles corresponden a la eleccion de distintos no terminales a expandir.

    - En una derivacion por la izquierda el no terminal que se expande sera el que se encuentra mas proximo al extremo izquierdo.

    - En una derivacion por derecha el no terminal que se expande es el que se encuentra mas proximo al extremo derecho.

    GIC: Ejemplo:
    Bienvenido al mundo de los autómatas
    Cada cadena derivada mediante una GIC, parte del símbolo inicial que da origen a las sucesivas derivaciones quienes dan por resultado final tal cadena. Para ello, uno y solo un no terminal es sustituido en cada producción, por una cadena que puede formarse por terminales y/o no terminales.

    Ejemplo, dada la siguiente GIC G, donde:

    • G = (N, S , S, P)

    • N = {S, A, B}; S = {a, b}

    • S -> AB

    • A -> aA|a

    • B -> bB|b

    La cadena "aabbb" perteneciente a L(G) puede formarse así:

    S => AB => AbB => AbbB => Abbb => aAbbb => aabbb

    Cuyo árbol de derivación asociado puedes apreciar al principio de este link.

    AMBIGUEDAD: Si para una cadena existe mas de un árbol de derivación, decimos que estamos en presencia de una Gramática Ambigua. Así por ejemplo la gramática definida por las siguientes producciones:

    P: S->aSa|aBa|b
    B -> b

    Si analizamos las reglas de sustitución para la cadena aabaa, observaremos que puede ser generada por las siguientes derivaciones:

    • S=>aSa
    • aSa=>aaBaa
    • aaBbb=>aabaa

    En síntesis: S=>aSa=>aaBaa=>aabaa

    • S=>aSa
    • aSa=>aaSaa
    • aaSaa=>aabaa

    En Síntesis: S=>aSa=>aaSaa=>aabaa

    Por consiguiente decimos que dicha gramática es Ambigua.

    ANÁLISIS DE AMBIGÜEDAD DE UNA GIC: Cuyos postulados principales son:

    • Si para al menos una cadena perteneciente a L(G) existe más de un árbol de derivación, G se dice que es una GRAMÁTICA AMBIGUA.

    • Si para todas las cadenas pertenecientes a L(G) existe solo un árbol de derivación, se dice que G es una GRAMÁTICA NO AMBIGUA.

    • El lenguaje L(G) será un lenguaje ambiguo o un lenguaje no ambiguo según el resultado del análisis de ambigüedad para G.

    • Si todas las gramáticas generadoras del lenguaje L son ambiguas, se dice que el L es un LENGUAJE INHERENTEMENTE AMBIGUO.

    Pero además, el árbol de derivación permite encontrar reglas de derivación o símbolos no deseables en una GIC. Tal es el caso de:

    • Reglas de la forma A -> A (REGLAS INNECESARIAS).

    • Presencia de símbolos no terminales, cuyas producciones no derivan en ninguna cadena de terminales (NO TERMINALES SIN DERIVACIÓN).

    • Símbolos terminales o no terminales a los cuales nunca se puede llegar produciendo sobre S (SÍMBOLOS INACCESIBLES).

    Cuando en el árbol de derivación no se detectan estas falencias, se dice que la gramática es una GRAMÁTICA LIMPIA. Sin embargo, para alcanzar la mejor de las condiciones (GRAMÁTICA BIEN FORMADA), aun necesita verificar:

    - Inexistencia de REGLAS NO GENERATIVAS, las cuales responden a la forma A -> ç, con ç palabra vacía y A distinto de S. Cuando un no terminal que no es el símbolo inicial da lugar a una regla no generativa, se lo conoce como NO TERMINAL ANULABLE.

    - Ausencia de REGLAS DE REDENOMINACIÓN o PRODUCCIONES UNITARIAS, las cuales se notan bajo la forma A -> B, con A distinto de B y ambos pertenecientes a N.

    Niveles de Ambigüedad

    • Ambigüedad de Sentencia: Cuando existe mas de una derivación o árbol de derivación para una sentencia:

      EJEMPLO Sea la gramática G6 = ( { 1 },{S, A }, S,{(S::=1A), (S::=11), (A::=1) } )

      La cadena 11 puede ser derivada como S=>1A=>11 ó S=>11 las cuales se representan por distintos arboles de derivación.

    • Ambigüedad de Gramática: Cuando la gramática tiene en su estructura alguna sentencia ambigua.
      Ejemplo: La gramática anterior,G6 = ( { 1 },{S, A }, S,{(S::=1A), (S::=11), (A::=1) } ), debido a que existe una sentencia 11, que al derivarse por medio de esta gramática, es ambigua.

    • Ambigüedad de Lenguaje: Se presenta cuando un lenguaje es generado por una gramática ambigua. Ejemplo:
      Como la gramática es ambigua, G6 = ( { 1 },{S, A }, S,{(S::=1A), (S::=11), (A::=1) } ) es ambigua, el lenguaje L(G6)={11} es ambiguo.

      Si todas las GIC para un lenguaje son ambigüas, se dice que el lenguaje es un lenguaje independiente del contexto (LIC) inherentemente ambigüo.

    EJEMPLO: Para la GIC: S->S b S | S c S | a y la cadena abaca, podemos graficar dos árboles distintos pero producen la misma cadena.
    Unas derivaciones posibles son:

    S=>SbS =>SbScS

    SbScS=>SbSca
    SbSca=>Sbaca
    Sbaca=>abaca
    S=>SbS=>SbScS=>SbSca=>Sbaca=>abaca

    Otras derivaciones posibles son:

    S=>ScS=> SbScS

    SbScS=>abScS
    abScS=>abacS
    abacS=>abaca

    S=>ScS=>SbScS=>abScS=>abacS=>abaca

    Las cuales se corresponden con dos arboles distintos.

    Consideremos la Gramática Independiente del Contexto G = ( N, å, S,P) con N = { S, A, C } ; å = {a, b, c} ; S el símbolo inicial; y cuyas producciones son:

    S->AB
    A->aAb|ab
    B->bB|b

    La cadena: aabbb puede ser derivada mediante :

    S=>AB=>AbB=>AbbB=>Abbb=>aAbbb=>aabbb

    El siguiente presenta el árbol de derivación:
    Comenzamos en la raíz S ygeneramos los hijos A y B. A y B son raíz del subárbol correspondiente a la parte de la cadena final que ellos generan.

    Notar que los nodos hojas están etiquetados con símbolos terminales y leidas de izquierda a derecha se obtiene la cadena aabbb.

    Si la estructura de un lenguaje tiene más de una descomposición y si la construcción final determina su significado, entonces el significado es ambiguo.
    Una gramática se dice que es ambigua si hay dos o más árboloes de derivación distintos para la misma cadena.

    Ejemplo: Supongamos la gramática: P: S->SbS|ScS|a
    Podemos derivar la cadena abaca de dos formas distintas:
    S=>SbS=>SbScS=>SbSca=>Sbaca=>abaca

  • El árbol de derivación es:

    S=>ScS=>SbScS=>abScS=>abacS=>abaca
    El árbol de derivación es:

    Vemos que los dos árboles son distintos, aunque las cadenas producidas son las mismas. Por tal razón diremos que la gramática es ambigüa.

    NORMALIZACION
    La GIC proporciona escaso control sobre las producciones permitidas y ello, da lugar a la presencia de símbolos y producciones no deseables, que permiten la existencia de árboles de derivación demasiado profundos, demasiado anchos e incompletos.
    A fin de evitar tales inconvenientes, convendría establecer restricciones que no limiten la capacidad generativa de la GIC, para generar su forma normales o su modelo formal estándar, del cual resulten gramáticas bien formadas que limiten los árboles innecesariamente complejos o inútilmente sencillos.
    Para lograr tal forma normal, debemos aplicar las siguientes técnicas específicas de los algoritmos de limpieza gramatical.

    • ELIMINACIÓN DE NO TERMINALES SIN DERIVACIÓN
      Sea G = ( N, S , S, P ) una GIC. Será transformada en G' = ( N', S , S, P' ) de modo tal que:

      L(G) = L(G'). Para todo A perteneciente a N', A =>* w, w perteneciente a S * .

      Es decir, se obtendrá una nueva gramática, la cual será equivalente a la original, pero que la perfeccionará en el sentido de que en la nueva gramática, todos los no terminales, acabarán por derivar (=>*) en cadenas formadas solo por símbolos terminales (es decir, completarán su proceso de derivación). Con esto se soluciona el "problema del árbol incompleto".
      El algoritmo que da solución a este planteo es el siguiente:

      • Inicializar N' con todos los no terminales A para los cuales A -> w es una producción de G con w Î S *.
      • Inicializar P' con todas las producciones A -> w para las cuales A Î a N' y w Î S *.
      • Repetir hasta que no se puedan añadir más no terminales a N':
        - Añadir a N' todos los no terminales A para los cuales A -> w sea una producción de P tal que w Î ( N' U S )*.
        - Añadir esa producción A -> w a P'.

    • ELIMINACIÓN DE NO TERMINALES y TERMINALES INACCESIBLES
      Sea G = (N, E, S, P) una GIC. Será transformada en G' = (N', E', S, P') de modo tal que:
      - L(G) = L(G').
      - Para todo X perteneciente al conjunto (N' u E'), S =>+ wXw', para las subcadenas w y w' de la forma (N' u E')*.

      Es decir, que lo que se pretende es que todo símbolo terminal o no terminal de la nueva gramática (que será equivalente a la original), pueda ser alcanzado a partir de sucesivas derivaciones (=>+) que se apliquen sobre S. Con esto se garantiza que todo terminal y no terminal es útil dentro de la gramática.

      El algoritmo que da solución a este planteo es el siguiente:
      - Inicializar N' = {S} y P' = E' = {} (conjuntos vacíos).
      - Repetir hasta que no se puedan añadir nuevas producciones:

      Si A -> w pertenece a P y además A pertenece a N':
      - Agregar A -> w en P'.
      - Para todo terminal x de w, introducirlo en E'.
      - Para todo no terminal X de w, introducirlo en N'.

    • ELIMINACIÓN DE NO TERMINALES ANULABLES
      Un no terminal que verifica A =>* ç se dice "anulable". El único caso en que estos terminales son deseables es cuando ç pertenece a L(G); sin embargo, la única producción necesaria y deseable para que esto ocurra es la producción S -> ç. Entonces, todas las demás producciones de este tipo deben eliminarse de la gramática.

      Para ello, primero se identifica el conjunto Z de todos los no terminales anulables de una gramática mediante el siguiente algoritmo:
      - Inicializar Z con todos los no terminales A para los cuales existe la producción de la forma A -> ç.
      - Repetir hasta que no puedan añadirse más no terminales a Z: Si B -> w tal que w pertence a (N u E)* y todos los símbolos de w están en Z, agregar B en Z.

      Identificados los no terminales anulables, para todas las producciones B -> X1X2...Xn pertenecientes a P, se agrega en P' todas las combinaciones posibles de B -> Y1Y2...Yn tal que:
      - Con Xi no anulable, solo se considere Yi = Xi.
      - Con Xi anulable, se consideren las posibilidades Yi = Xi y además Yi = ç. Es decir, un anulable en P da lugar a dos producciones en P'.
      - Yi no es ç para todo i (si así lo fuera, se estaría introduciendo una producción ç).

    • ELIMINACIÓN DE PRODUCCIONES UNITARIAS
      El último algoritmo de limpieza, simplifica derivaciones de la forma A1 => A2 => ... => An generando la producción A -> An. Es decir, evita que el árbol de derivación sea innecesariamente delgado y profundo.

      El primer paso para la aplicación de este algoritmo es la definición del CONJUNTO UNITARIO de cada no terminal A, definido este como el conjunto de símbolos no terminales B tal que según P, exista la producción A =>* B utilizando solo producciones unitarias. Por definición, el primer elemento del conjunto Unitario(A) es el elemento {A}.

      Identificados los conjuntos unitarios de todos los no terminales de G = (N, E, S, P), se obtiene una gramática equivalente G' = (N, E, S, P') de modo que P' no contiene producciones unitarias:

      - Inicializar P' = P.
      - Para cada A perteneciente a N para el cual Unitario(A) sea distinto de {A}
      - Para cada B ( Unitario(A)
      - Para cada producción no unitaria B -> w de P, agregarla en P' bajo la forma A -> w.
      - Eliminar todas las producciones unitarias en P'.


    Volver al principio

  • GRAMATICA REGULAR
    El lenguaje L(G) = { w | S -->*w, w ÎST*} , es un Lenguaje Regular, si es generado por una Gramática Regular definida como:

    G = ( ST, SN, S, P) Donde:

    • ST: Alfabeto de Símbolos Terminales.
    • SN: Alfabeto de Símbolos No terminales.
    • S: AXIOMA o Cadena de Inicio o Cadena Primigenia, a partir de la cual se comienzan a generar nuevas cadenas.
    • P: PRODUCCIONES Producciones que al generar una cadena a partir de otra, restringen a la presencia de un solo Símbolo Terminal en la parte izquierda, mientras la parte derecha, debe poseer también un solo Terminal, el cual puede o no, estar seguido de un solo Símbolo No terminal.
      Estas producciones pueden ser:

      • Lineal por Izquierda: P = { (S ::= l) ó ( A ::= Ba ) ó ( A ::= a ) | A, B ÎSN, a ÎST+ }

      • Lineal por Derecha: P = { (S ::= l) ó ( A ::= aB ) ó ( A ::= a ) | A, B ÎSN, a ÎST+ }

      EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { i, l, o, w }, { X, Y, Z, S }, S, P)
      Con las producciones:

      • P = { ( S ::= X ), ( X ::= wX ), ( X ::= iY ),( Y ::= l ),( Y ::= lZ ),( Z ::= o )}
      • Las derivaciones serán:

        - S --> X --> wX --> wiY --> wil

        - S --> X --> wY --> wiY --> wilZ --> wilo

      Se genera el lenguaje de formato: L = { wil, wilo, . . .}

      EJEMPLO: La gramática G = ( S T, SN, S, P) = ( { a, c, i, o, r, p }, { X, Y, Z, S }, S, P)

      Con las producciones:

      • P = { ( S ::= X ), ( X ::= cX ), ( X ::= aY ),( Y ::= rY ),( Y ::= o ),( Y ::= pZ ),( Z ::= iZ ),( Z ::= o )}

      • Las derivaciones serán:
        • S --> X --> cX --> caY --> carY --> caro
        • S --> X --> cX --> caY --> carY --> carpZ --> carpiZ --> carpio

      Se genera el lenguaje de formato: L = { caro, carpio, . . .}

      EJEMPLO: La gramática
      G5 = ( { 0, 1 }, { A, B }, A, P )
      No es del tipo 3, por que en su parte derecha dos de sus primeras reglas no cumplen con ninguna de las categorías de la gramática lineal;
      en cambio
      G6 = ( { 0, 1 }, { A, B }, A, P )
      Donde: P = { ( A ::= 1B ), ( B ::= 1 ), ( B ::= 0C ), ( C ::= 1 ) }
      Es equivalente a G5 por que generan el mismo lenguaje
      L(G6) = L(G5) = { 11, 101 , 111}

    PARADIGMA
    Las palabras sinceras no son elegantes
    Las palabras elegantes, no son sinceras...!!!
    Proverbio Chino

    TEORIA de los AUTOMATAS:
    Turing
    ALA
    de Pila
    Finito

    Un Autómata me recuerdan al simpático cabezón con voz de lata llamado "Arturito", que en mi niñez fue autómata ayudante de la nave del film "Odisea del Espacio 2001", pero, dentro de los paradigmas informáticos, el formato humanoide del cabezón Arturito, no es aplicable porque, en esta teoría de autómatas nos referimos a mecanismos analíticos de funcionamiento automático y que se crearon para procesar datos en forma de cadenas de un lenguaje.

    • Conceptualmente un autómata es una máquina que no requiere en forma permanente de la intervención humana para funcionar. Es una máquina automática a la que el hombre le ha programado la operativa de su actividad y el objetivo de su existencia.
    • En este ámbito, los autómatas más que máquinas son una especie de algoritmos operativos que emulan un elemento motriz de estos mecanismos analíticos, capaces de funcionar como auditores gramaticales.
    • Una manera común de clasificar los autómatas suele abarcar:


    Volver al principio

    PARADIGMA
    Aprender es como remar contra la corriente
    Si no se avanza, se retrocede...!!!
    Proverbio chino

    AUTOMATAS TURING: MT
    La arquitectura de la MT, cuenta con una cinta infinita en ambas direcciones, organizada como una colección de celdas contiguas capaces de almacenar cada una, un único símbolo.

    La MT no posee una celda primera ni ultima, por ello, tiene una capacidad de almacenamiento ilimitada y los contenidos de las celdas pueden accederse en cualquier orden, además tiene asociada a la cinta, una cabezal de lectura | escritura que puede moverse sobre la cinta y por cada movimiento lee o escribe un símbolo.

    Arquitectura MT
    Definición: MT = ( Q, S, T, s, ß, F, d )
    
    Cinta S: | a1 | a2 | a3 | . . . | an | . . 
                     /\
                 <- / d \ -> Cabezal
    	| q1 |
    	| q2 |
    	| q3 |
    	  . 
    	  .
    	| qm |
     Estados:  Q
    

    • Q : Conjunto Estados : { q1, q2, q3, . . . }

    • S : Alfabeto Entrada : { a1, a2, a3, a4, . . . }

    • T : Alfabeto Cinta :

    • s Î Q : Estado Inicial :

    • ß Î T : Símbolo Blanco :

    • F Í Q : Datos de aceptación :

    • d : Función Transición : Que transforma (q,s) -> ( p, t, X )
      • q : Estado Actual
      • s : Símbolos de Cinta
      • p : Estado siguiente
      • t : Símbolo de la cinta
      • X : Movimiento del cabezal

    Ejemplo:

    • d --- b
    • q1 -- q2aD q2bD
    • q2 -- q2aD q3bI
    • q3 -- q4aD q4bD

Ejemplo: Sea la máquina MT1 definida como: MT1 = ({ q 1,q 2, q 3, q 4 }, { a }, { a, ß }, q 1, ß,{ q 4 }, d )

Aplicando la definición: M = ( Q, S, T, s, ß, F, d )

Deducimos que sus parametros son:

  • Q : Conjunto Estados : { q 1, q 2, q 3, q 4 }

  • S : Alfabeto Entrada : { a }

  • T : Alfabeto Cinta : {a, ß }

  • s ' Q : Estado Inicial : q 1

  • ß ' T : Símbolo Blanco : ß

  • F Í Q : Datos de aceptación : { q4 }

  • d : Función Transición : d
    Transforma (q,s) -> ( p, t, X )
    • q : Estado Actual
    • s : Símbolos de Cinta
    • p : Estado siguiente
    • t : Símbolo de la cinta
    • X : Movimiento del cabezal

    En este caso la tabla de transiciones es:
    • d --- b
    • q1 -- q2aD q2bD
    • q2 -- q2aD q3bI
    • q3 -- q4aD q4bD


Volver al principio

PARADIGMA
Antes de nuestra venida nada le faltaba al mundo;
Despues de nuestra marcha, nada le faltará...!!!
Proverbio Persa

AUTOMATA LINEALMENTE ACOTADO (ALA)
Es una Máquina de Turing, cuyas computaciones están restringidas a la cantidad de cinta. Consiste en un conjunto finito de estados, un alfabeto finito de la cinta que incluye los símbolos marcadores(< >), que delimitan la cinta ,un estado inicial y un conjunto de instrucciones similares a la máquina de Turing.
El alfabeto de entrada estará escrito entre los marceadores < > y el ALA no contiene instrucciones para moverse después de ellos, ni borrarlos, ni reemplazarlos.

Arquitectura ALA
Definición: ALA = ( Q, S, T, <, >, s, ß, F, d )

Cinta S: | < | a1 | a2 | . . . | > | . . 
                 /\
             <- / d \ -> Cabezal
	| q1 |
	| q2 |
	| q3 |
	  . 
	  .
	| qm |
 Estados:  Q

  • Q : Conjunto Estados : { q1, q2, q3, . . . }

  • S : Alfabeto Entrada : { a1, a2, a3, a4, . . . }

  • T : Alfabeto Cinta : { <, a1, a2, a3, . . an, > }

  • s Î Q : Estado Inicial :

  • ß Î T : Símbolo Blanco :

  • F Í Q : Datos de aceptación :

  • < : Símbolo de inicio de cinta

  • > : Símbolo fin de cinta

  • d : Función Transición : Que transforma (q,s) -> ( p, t, X )
    • q : Estado Actual
    • s : Símbolos de Cinta
    • p : Estado siguiente
    • t : Símbolo de la cinta
    • X : Movimiento del cabezal

El funcionamiento del autómata requiere que se encuentre en un estado y el cambio de estado va ha depender del:

  • Estado actual en el que se encuentra y
  • Símbolo leído de la cinta de entrada

La arquitectura del Autómata Linealmente Acotado,consiste en una colección de celdas de extensión limitada.
  • Cada celda de almacenamiento puede almacenar un solo símbolo.
  • La colección de celdas esta limitada en ambas direcciones por dos marcadores. La cinta estará asociada con un cabezal de lectura /escritura que no podrá moverse mas allá de los marcadores.
  • Cinta de soporte de información: es de longitud limitada, por eso se definen dos marcadores de la cinta que delimitaran el principio y el fin. Contiene los caracteres de entrada a1 Î å
  • Cabezal de control: es un cabezal de lectura y escritura, no puede desplazarse mas a la izquierda del símbolo que delimita la izquierda, ni mas a la derecha del símbolo que delimita la derecha.Cada movimiento es registrado por un estado.
  • La función de transición, d va ha administrar los movimientos del autómata, que dependerán del estado actual en el que se encuentra y del símbolo de la cinta.

PARADIGMA: Manejar el silencio es más difícil que manejar la palabra...!!! ( Georges Clemenceau )

Volver al principio


Volver al principio

PARADIGMA
La personalidad es al hombre
lo que el perfume es a la flor...!!!
Schwab

AUTOMATA DE PILA: AP
La arquitectura del AP, cuenta con una cinta finita, organizada como una colección de celdas contiguas capaces de almacenar cada una, un único símbolo, al que puede accederse solamente en un solo sentido, mediante una cabeza de solo lectura, que puede moverse sobre la cinta y por cada movimiento lee un solo símbolo.

Arquitectura AP
Definición: AP = ( S, T, Q, Ao, qo, F, d )

Cinta S: | a1 | a2 | a3 | . . . | an | . . 
                 /\
                / d \ -> 
	| q1 |     Cabezal  | t0 |
	| q2 |            | t1 |
	| q3 |            | t2 |
	  . 
	  .
	| qm |            | ti |
 Estados:  Q           Pila:  T

  • Q : Conjunto Estados : { q1, q2, q3, . . . }

  • S : Alfabeto Entrada : { a1, a2, a3, a4, . . . }

  • T : Alfabeto de símbolos de pila

  • qo : Estado Inicial

  • F : Conjunto de estados finales

  • d : Función Transición : ( qi, ai , ti ) -> ( qi+1, ti+1 )
    • qi : Estado Actual
    • ai : Símbolos Actual leido en Cinta
    • ti : Símbolo leido en la cima de pila
Para procesar una LIC de la forma { an bn |n > 0 } precisaríamos memoria para un contador de aes, luego memoria para verificar que todas las aes precedan a las bes, por lo tanto, la única memoria del autómata finito, nos resultaría insuficiente. Por ello necesitaremos otra máquina, como el autómata de pila, con memoria para registrar tanto la cantidad de símbolos y otra para guardar tales símbolos.

TEOREMAS

  • Para cada GIC, existe un autómata de pila M tal que: L(G)=L(M)
  • Para cada autómata de pila M, existe una GIC tal que: L(M)=L(G)
  • Existe un GIC que no es el aceptado por ningún autómata de pila determinista.

El autómata de pila es la máquina que opera como una pila de datos y posee un mecanismo que le permite almacenamiento ilimitado, para contar o guardar los símbolos de las cadenas necesarias para efectuar comparaciones.

El AP opera en forma similar al AF, pues en todo momento se encuentra en un estado y el cambio de estado depende del estado actual y de una información adicional, que en el AF es el símbolo de entrada actual. El diagrama de transición para el lenguaje (a b )* es:

En el AP se incluye además del símbolo de entrada actual, el símbolo que está en ese momento en la cima de la pila. Por ello, cuando cambia de estado, el AP cambia también la cima de la pila.

A diferencia del "Autómata Finito. AF" que solo tiene capacidad para una "Memoria Finita", el AP puede reconocer cualquier LIC, para ello necesita guardar mucha información que usa para verificar, por ejemplo cuantas aes preceden a las bes o contar la cantidad de aes para establecer las limitaciones, etc.

  • El funcionamiento requiere que el AP esté se encuentre siempre en un estado.
  • El cambio de dicho estado depende del:

    • Estado actual.
    • Símbolo leído en la entrada.
    • Símbolo que en ese momento está localizado en la cima de la pila
  • Cuando cambia de estado también cambia tal símbolo de la cima.

Para operar esta estructura gráfica de modo más simple, consideraremos la siguiente representación literal:

Q: Estado S:Cinta T:Pila q1 q2q3...qm a1a2a3A0 A1A2A3

CONTROL: NO ACEPTA

Con color rojo marcamos el cabezal posicionado en ese elemento (símbolo de la cinta, estado actual o cima de la pila)

  • TRANSICIÓN:
    • f(q,a,Z)={(q1,z1), (q2,z2),...,(qn,zn)}
    • Las transiciones que ejecutan los autómatas de pila siguen la siguiente secuencia:
      • Leer un símbolo de la entrada.
      • Extraer un símbolo de la pila.
      • Insertar un símbolo en la pila.
      • Pasar a un nuevo estado.
    • (q,a,Z; qn,yn)
  • DESCRIPCION INSTANTANEA: Permite describir sencillamente la configuración del AP en cada momento.
    • Terna (q,x,z), qÎQ, xÎS*, zÎT* contiene el estado actual, la palabra que queda por leer y el símbolo en la cima de la pila.
    • Movimiento: (q,ay,ZX) |-(p,y,xX) describe el paso de una descripción instantánea a otra.
    • Sucesión de Movimientos: (q,ay,ZX) |-*(p,y,xX) representa que desde la primera descripción instantánea se puede alcanzar la segunda.
  • METODOS DE ACEPTACIÓN: Cada transición reclama un símbolo en la pila, por tanto si esta queda vacía el autómata se detiene y esta expresión indica que puede ocurrir que:
    • El AP puede terminar o no con la pila vacía , en el caso de que vacíe su pila a cadena es Aceptado por Vaciado de Pila.
    • La aceptación requiere que el AP se mueva a un estado final cuando la cadena de la cinta se agote.
  • TEOREMA: Para cada autómata de pila que acepte cadenas sin vaciar su pila, existe un autómata equivalente pero que vacía su pila antes de llegar a un estado de aceptación

El AP: autómatas de pila, que puede ser DETERMINISTA o NO DETERMINISTA, en función de la estructura de sus transiciones de un estado a otro.

Volver al principio


Volver al principio

PARADIGMA Se inventó la seda para que las mujeres;
pudieran ir desnudas con vestidos...!!! (Mahoma)

AUTOMATA FINITO
Dentro de las máquinas capaces de reconocer gramáticas regulares están:

  • Las Máquinas de Estados Secuenciales
  • El Autómatas Finito
  • El Autómata Probabilístico
  • El Autómata de Células de McCulloch-Pitts.

El AUTÓMATA FINITO tiene una cinta de infinita hacia la derecha con un cabezal capaz de realizar solamente la operación de lectura, lee un símbolo de la cinta de entrada y se desplaza un lugar hacia la derecha. Inicialmente la cinta tiene una secuencia cualquiera de símbolos de entrada seguida de espacios en blanco, el cabezal de esta cinta se encuentra sobre el primer símbolo de la secuencia de entrada.

Definición Formal: Un autómata finito es una quíntupla, es un mecanismo automático para verificar si una cadena pertenece o no a un determinado lenguaje, es decir una estructura algebraica A = donde:

  • Q : Conjunto finito de estados.
  • S : Alfabeto finito de entrada.
  • d : Función de transición d : QxS®P(Q), que determina el único estado siguiente para el par (qi , s) correspondiente al estado actual y a la entrada.
  • q0 : Estado inicial s, qo Î Q
  • F : Conjunto de estados finales F Î Q

Se pueden considerar a los Autómatas Finitos como una subclase de lasMáquinas Secuenciales, pues, la principal diferencia está en que la salida, está limitada a dos valores: aceptada la palabra o no aceptada. Los Autómatas Finitos transitan entre estados de un conjunto de estados según reciben los símbolos que forman la palabra de entrada.
Hay tres tipos de estados:
  • Inicial, que permite empezar la ejecución del Autómata
  • Finales, que permiten realizar la salida de aceptación de la palabra de entrada en él caso de que no haya mas símbolos en la entrada.
  • Estados intermedios.

Es decir que es una máquina que se define en términos de sus estados. El cambio de estado depende de la entrada y del estado en que se encuentre. Dicha máquina se llama Autómata Finito, una computadora ideal.
Los Autómatas Finitos pueden usarse para diseñar analizadores léxicos de los compiladores, circuitos electrónicos, editores de texto, etc.
Dependiendo de cómo se defina su capacidad para cambiar de estado se clasifican en dos tipos:
- Deterministas
- No deterministas

PARADIGMA: Los humanos tienen que respirar ...
..y las empresas tienen que generar dinero...!!! (Wilucha)


Volver al principio


Volver al principio

PARADIGMA: Una persona aburrida es la que habla
..cuando deseas que te escuche..!! (Ambrose Bierce)

INTRODUCCION a la TEORIA de COMPILADORES

Copia PDF Te ofrezco ver:

Introducción:

  • En 1946 nacía Wilo y también el primer ordenador digital..!!.
    Aquella máquina realizaba instrucciones registradas en códigos numéricos que señalaban a los circuitos de la máquina los estados correspondientes a cada operación.

  • Lenguaje máquina
    Es el nombre con el que se bautizó a esta laboriosa expresión de códigos numéricos, interpretado por un secuenciador cableado o por un microprograma.

    Los primeros programadores de estas máquinas, descubrieron la ventaja de escribir sus programas mediante claves más fáciles de recordar que esos códigos numéricos, al final, todas esas claves juntas se traducían manualmente a Lenguaje Máquina.

  • Lenguaje ensambladores.. Así se bautiza a tales claves, que se generalizaron en cuanto se dio el paso decisivo de hacer que las propias máquinas realizaran el proceso mecánico de la traducción. Esta operación se le llama ensamblar el programa.

    Tal lenguaje ensamblador seguía siendo el de máquina, pero más fácil de manejar y los trabajos de investigación se orientaron entonces hacia la creación de un lenguaje que expresara las distintas acciones a realizar de una manera lo más sencilla posible para el usuario.

  • En 1950.., John Backus dirigió una investigación en I.B.M. en un lenguaje algebraico.

    En 1954 nace FORTRAN (FORmulae TRANslator). Fue el primer lenguaje considerado de alto nivel, que permitía escribir fórmulas matemáticas de manera traducible por un ordenador.

    En 1957.. nace el concepto de un traductor, como un programa que traducía un lenguaje a otro lenguaje. Se introdujo para el uso de la computadora IBM modelo 704.

    Permitía una programación más cómoda y breve que la existente hasta ese momento, lo que suponía un considerable ahorro de trabajo.

    En el caso particular de que el lenguaje a traducir es un lenguaje de alto nivel y el lenguaje traducido de bajo nivel, se emplea el término compilador.

  • La tarea de realizar un compilador no fue fácil. El primer compilador de FORTRAN tardó 18 años-persona en realizarse y era muy sencillo.

  • Este desarrollo del FORTRAN estaba muy influenciado por una máquina objeto en la que iba a ser implementado. Como ejemplo de ello tenemos el hecho de que los espacios en blanco fuesen ignorados, debido a que el periférico que se utilizaba como entrada de programas (una lectora de tarjetas perforadas) no contaba correctamente los espacios en blanco.

  • Paralelamente al desarrollo del FORTRAN en América, en Europa surgió una corriente más universitaria, que pretendía que la definición de un lenguaje fuese independiente de la máquina y en donde los algoritmos se pudieran expresar de forma más simple.

  • Esta corriente estuvo muy influida por los trabajos sobre gramática de contexto libre publicados por Chomsky dentro de su estudio de lenguajes naturales.

  • Con estas ideas surgió un grupo europeo encabezado por el profesor F.L.Bauer (de la Universidad de Munich). Este grupo definió un lenguaje de usos múltiples independiente de una realización concreta sobre una máquina.

    Pidieron colaboración a la asociación americana A.C.M. (Association for Computing Machinery) y se formó un comité en el que participó J. Backus que colaboraba en esta investigación.

    De esa unión surgió un informe definiendo un Internacional Algebraic Language (I. A. L.), publicado en Zurcí (En 1958)

    Posteriormente este lenguaje fue revisado y llevó a una nueva versión que se llamó ALGOL 60. La versión actual es ALGOL 68, un lenguaje modular estructurado en bloques.

  • En el ALGOL aparecen por primera vez muchos de los conceptos de los lenguajes algorítmicos:

    1. Definición de la sintaxis en notación BNF (Backus-Naur Form).

    2. Formato libre.

    3. Declaración explícita de tipo para todos los identificadores.

    4. Estructuras iterativas más generales.

    5. Recursividad.

    6. Paso de parámetros por valor y por nombre.

    7. Estructura de bloques, lo que determina la visibilidad de los identificadores.

  • Junto a este desarrollo en los lenguajes, también se iba avanzando en la técnica de compilación. En 1958, Strong y otros proponían una solución al problema de que un compilador fuera utilizable por varias máquinas objeto. Para ello, se dividía por primera vez el compilador en dos fases, designadas como el “front end “y el “back end “.

  • La primera fase (front end) es la encargada de analizar el programa fuente y la segunda fase (back end) es la encargada de generar código para la máquina objeto.

  • El puente de unión entre las dos fases era un lenguaje intermedio que se designó con el nombre de UNCOL (UNiversal Computer Language).

  • Para que un compilador fuera utilizable por varias máquinas bastaba únicamente modificar su back end. Aunque se hicieron varios intentos para definir el UNCOL, el proyecto se ha quedado simplemente en un ejército teórico. De todas formas, la división de un compilador en front end y back end fue un adelanto importante.

  • En 1959.. se van poniendo las bases para la división de tareas en un compilador. Así, en 1959 Rabin y Scout proponen el empleo de Autómatas Deterministas y No Deterministas para el reconocimiento lexicográfico de los lenguajes.

    Rápidamente se aprecia que la construcción de analizadores léxicos a partir de expresiones regulares es muy útil en la implementación de los compiladores. En 1968, Johnson apunta a diversas soluciones. En 1975, con la aparición de LEX surge el concepto de un generador automático de analizadores léxicos a partir de expresiones regulares, basado en el sistema operativo UNIX.

  • A partir de los trabajos de Chomsky ya citados, se produce una sistematización de la sintaxis de los lenguajes de programación, y con ello un desarrollo de diversos métodos de análisis sintáctico.

  • Con la aparición de la notación BNF – desarrollada en primer lugar por Backus en 1960 cuando trabajaba en un borrador del ALGOL 60, modificada en 1963 por Naur y formalizada por Knuth en 1964 – se tiene una guía para el desarrollo del análisis sintáctico.

  • Los diversos métodos de parsers ascendentes y descendentes se desarrollaban durante la década de los 60.

  • En 1959, Sheridan describe un método de parking de FORTRAN que introducía paréntesis adicionales alrededor de los operandos para ser capaz de analizar las expresiones. Más adelante, Floyd introduce la técnica de la precedencia de operador y el uso de las funciones de precedencia. A mitad de la década de los 60, Knuth define las gramáticas LR y describe la construcción de una tabla canónica de parser LR.

  • Por otra parte, el uso por primera vez de un parking descendente recursivo tuvo lugar en el año 1961. En el año 1968 se estudian y definen las gramáticas LL así como los parsers predictivos. También se estudiaba la eliminación de la recursión a la izquierda de producciones que contienen acciones semánticas sin afectar a los valores de los atributos.

  • En los primeros años de la década de los 70, se describen los métodos SLR y LALR de parser LR. Debido a su sencillez y a su capacidad de análisis para una gran variedad de lenguajes, la técnica de parking LR va a ser la elegida para los generadores automáticos de parsers. A mediados de los 70, Johnson crea el generador de analizadores sintácticos YACC para funcionar bajo un entorno UNIX.

  • Junto al análisis sintáctico, también se fue desarrollando el análisis semántico. En los primeros lenguajes (FORTRAN y ALGOL 60) los tipos posibles de los datos eran muy simples, y la comprobación de tipos era muy sencilla. No se permitía la coerción de tipos, pues ésta era una cuestión difícil y era más fácil no permitirlo.

  • Con la aparición del ALGOL 68 se permitía que las expresiones de tipo fueran construidas sistemáticamente. Más tarde, de ahí surgió la equivalencia de tipos por nombre y estructural.

  • El manejo de la memoria como una implementación tipo pila se usó por primera vez en 1958 en el primer proyecto de LISP. La inclusión en el ALGOL 60 de procedimientos recursivos potenció el uso de la pila como una forma cómoda de manejo de la memoria. Dijkstra introdujo posteriormente el uso del display para acceso a variables no locales en un lenguaje de bloques.

  • También se desarrollaron estrategias para mejorar las rutinas de entrada y de salida de un procedimiento. Así mismo, y ya desde los años 60, se estudió el paso de parámetros a un procedimiento por nombre, valor y variable.

  • Con la aparición de lenguajes que permitan la localización dinámica de datos, se desarrolla otra forma de manejo de la memoria, conocida por el nombre de heap (montículo). Se han desarrollado varias técnicas para el manejo del heap y los problemas que con él se presentan, como son las referencias perdidas y la recogida de la basura.

  • La técnica de la optimización apareció desde el desarrollo del primer compilador de FORTRAN. Backus comenta cómo durante el desarrollo del FORTRAN se tenía el miedo de que el programa resultante de la compilación fuera más lento que si hubiera escrito a mano. Para evitar esto, se introdujeron algunas optimizaciones en el cálculo de los índices dentro de un bucle.

  • Pronto se sistematizan y se recoge la división de optimizaciones independientes de la máquina y dependientes de la máquina. Entre las primeras están la propagación de valores, el arreglo de expresiones, la eliminación de redundancias, etc. Entre las segundas se podría encontrar la localización de registros, el uso de instrucciones propias de la máquina y el reordenamiento de código.

  • A parir de 1970 comienza el estudio sistemático de las técnicas del análisis de flujo de datos. Su repercusión ha sido enorme en las técnicas de optimización global de un programa.

  • En la actualidad, el proceso de la compilación ya está muy asentado. Un compilador es una herramienta bien conocida, dividida en diversas fases. Algunas de estas fases se pueden generar automáticamente (analizador léxico y sintáctico) y otras requieren una mayor atención por parte del escritor de compiladores ( las partes de traducción y generación de código ).

  • De todas formas, y en contra de lo que quizá pueda pensarse, todavía se están llevando a cabo varias vías de investigación en este fascinante campo de la compilación. Por una parte, están mejorando las diversas herramientas disponibles (por ejemplo, el generador de analizadores léxicos Aadvard para el lenguaje PASCAL).

    También la aparición de nuevas generaciones de lenguajes – ya se habla de la quinta generación, como de un lenguaje cercano al de los humanos – ha provocado la revisión y optimización de cada una de las fases del compilador.

  • El último lenguaje de programación de amplia aceptación que se ha diseñado, el lenguaje Java, establece que el compilador no genera código para una máquina determinada sino para una virtual, la Java Virtual Machine ( JVM ), que posteriormente será ejecutado por un intérprete, normalmente incluido en un navegador de Internet.

    El gran objetivo de esta exigencia es conseguir la máxima portabilidad de los programas escritos y compilados en Java, pues es únicamente la segunda fase del proceso la que depende de la máquina concreta en la que se ejecuta el intérprete.

PARADIGMA
Quien no calla el hecho,
tampoco callará su autor..!!
Séneca

Los siguientes conceptos constituyen el vocabulario básico para comenzar a entender la teoría de los compiladores.

  • TRADUCTOR:
    Es aquel programa computacional que toma como entrada un texto escrito en un lenguaje llamado "Lenguaje Fuente" y produce como salida otro texto en un lenguaje, denominado "Lenguaje Objeto".

    Texto Lenguaje Fuente -> TRADUCTOR -> Texto Lenguaje Objeto

  • COMPILADOR:
    Es el traductor cuyo lenguaje fuente es un lenguaje de programación de alto nivel y la salida es un lenguaje de bajo nivel o ensamblador o código de máquina; así, genera un programa ejecutable a partir de un programa fuente en el lenguaje de alto nivel

    • LINKER:
      Construye un fichero ejecutable añadiendo al fichero objeto generado por el compilador las cabeceras necesarias y las funciones de librería utilizadas por el programa fuente.

    • DEPURADOR:
      Permite seguir paso a paso la ejecución de un programa, siempre que el compilador haya generado adecuadamente el programa objeto.

    • ENSAMBLADOR:
      Compilador cuyo lenguaje fuente es el lenguaje ensamblador. Algunos compiladores, en vez de generar código objeto, generan un programa en lenguaje ensamblador que debe después convertirse en un ejecutable mediante un programa ensamblador.

    • INTERPRETE:
      A diferencia del compilador que genera un programa equivalente, este toma una sentencia del programa fuente en lenguaje de alto nivel y luego la traduce al código equivalente y al mismo tiempo lo ejecuta.

    PARADIGMA
    En los ojos del joven arde la llama.
    En los ojos del viejo brilla la luz.
    Víctor Hugo

    COMPILAR O INTERPRETAR?

    Ventajas de compilar frente a interpretar:

    • Se compila una vez, se ejecuta varias veces.

    • La compilación de bucles genera código equivalente al bucle, pero interpretándolo se traduce tantas veces una línea como veces se repite el bucle.

    • La información de mensajes de error es más detallada, por que el compilador tiene vista global del programa.

    Ventajas del intérprete frente al compilador:

    • El intérprete requiere menos memoria que un compilador.

    • En tiempo de desarrollo, permite más interactividad con el código.

  1. TIPOS DE COMPILADORES

    • ENSAMBLADOR:
      El lenguaje fuente es lenguaje ensamblador y posee una estructura sencilla.

    • COMPILADOR CRUZADO:
      Genera código en lenguaje objeto para una máquina diferente de la que se está utilizando para compilar. Es perfectamente normal construir un compilador de Pascal que genere código MS- DOS y que el compilador funcione en Linux y se haya escrito en C++.

    • COMPILADOR CON MONTADOR:
      Compila distintos módulos de forma independiente y después es capaz de enlazarlos.

    • AUTOCOMPILADOR:
      Compilador escrito en el mismo lenguaje que se va a compilar, por tanto no puede ejecutarse la primera vez. Sirve para ampliar lenguajes, mejorar el código generado, etc.

    • METACOMPILADOR:
      Compilador de compiladores, es un programa que recibe como entrada las especificaciones del lenguaje para el que se desea obtener un compilador y genera como salida el compilador para ese lenguaje.

    • DESCOMPILADOR:
      Programa que acepta como entrada código máquina y lo traduce a un lenguaje de alto nivel, realizando el proceso inverso a la compilación.

    Lenguaje Fuente ? COMPILADOR ? Lenguaje Objeto

    La descompilación es factible si el programa objeto se guarda la tabla de símbolos y si no se hizo optimización de código. Por ello existen más que buenos descompiladotes, buenos desensambladotes.

  2. ETAPAS DE LA COMPILACIÓN
    
                                            	PROGRAMA FUENTE
                                                          |
                                          |  Análisis Léxico          |
                                          | Análisis Sintáctico       |
    		Tabla de Símbolos  >     | Análisis Semántico        |  >  Manejo de errores
                                          | Generar código Intermedio |
                                          | Optimización de Código    |
                                          | Generación de Código      |
                                                          |
                                            	PROGRAMA OBJETO
    
    

    Gracias a los sistemas de memoria virtual, el fichero ejecutable del compilador es relativamente pequeño comparado con el de otros programas del sistema, por tanto para compilar un programa medio ya no existen los viejos problemas de escasez de memoria.

    Actualmente se tiende a reducir el número de ficheros leídos o escritos para reducir el numero de pasadas, incluso en las realizadas en memoria, sin escribir ni leer nada del disco, así se disminuye el tiempo destinado a escribir y leer un fichero de tamaño similar o mayor que el de programa fuente en cada fase.

    Las fases se agrupan en dos partes o etapas:

    • FRONT END:
      Fase de análisis, que depende del lenguaje fuente y es independiente de la máquina objeto para que la que se va a generar el código.

    • BACK END:
      Fase de generación y optimización de código que depende del lenguaje objeto y debe ser independiente del lenguaje fuente.

    Ambas etapas se comunican mediante una representación intermedia generada por el frond end, que puede ser una representación de la sintaxis del programa o bien puede ser un programa en un lenguaje intermedio.

  3. ANÁLISIS LÉXICO O SCANNER (AL)

    Desde la entrada lee los caracteres uno a uno, para formar TOKENS o secuencia de caracteres con alguna relación entre sí, que serán tratados como una única entidad, que serán la entrada para la siguiente etapa del compilador. En esta fase se manejan los siguientes conceptos:

    • TOKENS:
      Símbolos terminales de cada gramática como palabras reservadas, identificadores, signos de puntuación, constantes numéricas, operadores, cadenas, etc. Existen tokens con varios signos, como “: =”, “= =”, “+ =”, “???”, etc. Los tokens que tiene dos componentes: Tipo y Valor, pueden estar constituidas por:

    • TIRAS ESPECÍFICAS:
      Son las palabras reservadas, if then else, function, while, etc, el punto y coma, la asignación, los operadores aritméticos o lógicos, etc. Estas tiras sólo tienen tipo.

    • TIRAS NO ESPECÍFICAS:
      Constituidas por los identificadores, constantes o etiquetas. Estas tiras tienen tipo y valor. Por ejemplo, si “contador” es un identificador, el tipo de token será identificador y su valor será la cadena “contador”.

    • PATRÓN:
      Expresión regular que define el conjunto de cadenas que puede representar a cada uno de los tokens.

    • LEXEMA:
      Cadena que se produce al analizar el texto fuente y encontrar una cadena de caracteres que representan un token determinado. Así, el lexema es una secuencia de caracteres del código fuente que concuerda con el patrón de un token.

    • ATRIBUTOS:
      Información adicional sobre los tokens en forma de atributos asociados, cuyo número de depende de cada token; aunque en la práctica el único atributo es el registro que contiene la información propia como, lexema, tipo de token y línea y columna en la que fue encontrado.

    En la misma pasada el AL puede funcionar como subrutina del analizador sintáctico, es la etapa del compilador que identifica el formato del lenguaje, leyendo para ello, los caracteres del programa e ignorando sus elementos innecesarios para la siguiente fase, como tabuladores, comentarios, espacios en blanco, etc.

    El AL agrupa por categorías léxicas los caracteres de entrada, estableciendo el alfabeto con el que se escriben los programas válidos en el lenguaje fuente y rechaza cadenas con símbolos ilegales del alfabeto, desarrollando para ello las siguientes operaciones:

    • PROCESO LÉXICO DEL PROGRAMA FUENTE: Identificador de tokens y de sus lexemas que deberán entregar al analizador sintáctico e interaccionar con la tabla de símbolos.

    • MANEJA EL FICHERO DEL PROGRAMA FUENTE; Abre, lee sus caracteres y cierra.

    • IGNORA COMENTARIOS: Como separadores, espacios blancos, tabuladores, retornos de carro, etc.

    • LOCALIZA ERRORES: Cuando se produce un error sitúa la línea y la posición en el programa fuente y registra las líneas procesadas.

    • PROCESO DE MACROS, definiciones, constantes y órdenes de inclusión de otros ficheros.

    Para reconocer un tokens el AL lee los caracteres hasta llegar a uno que no pertenece a la categoría del token leído, el último carácter es devuelto al buffer de entrada para ser leído en primer lugar en la próxima llamada al analizador léxico. Cuando el AS vuelve a llamar al AL, éste lee los caracteres desde donde quedó en la llamada anterior, hasta completar un nuevo token y devolver el par Token - Lexema.

    El funcionamiento de una analizador léxico puede representarse mediante la máquina de estados, llamada diagrama de transición (DT), muy parecida a un autómata finito determinista.

    CREACION DE ANALIZADORES LEXICOS:
    Las alternativas son:

    • USAR UN GENERADOR AUTOMÁTICO de analizadores léxicos, como el LEX: su entrada es un código fuente con la especificación de las expresiones regulares de los patrones que representan a los token del lenguaje, y las acciones a tomar cuando los detecte.

    • ESCRIBIR el AL en LENGUAJE DE ALTO NIVEL de uso general utilizando sus funciones de E/S.

    • HACERLO EN LENGUAJE ENSAMBLADOR.

    ERRORES LEXICOS

    En esta etapa, donde el compilador tiene solo una visión muy local del programa los pocos errores característicos detectados por el analizador léxico son:

    • Uso de caracteres que no pertenecen al alfabeto del lenguaje (“ñ” o”?”).

    • Palabras que no coinciden con ninguno de los patrones de los tokens posibles

    La detección de un error puede implicar:

    • Ignorar los caracteres no válidos hasta formar un token según los patrones dados;

    • Borrar los caracteres extraños;

    • Insertar un carácter que pudiera faltar;

    • Reemplazar un carácter presuntamente incorrecto por uno correcto;

    • Conmutar las posiciones de dos caracteres adyacentes.

  4. ANÁLISIS SINTÁCTICO O PARSER: (AS)

    El AS además de comprobar la corrección de la sintaxis del programa fuente, construye una representación interna del programa o caso contrario enviar un mensaje de error. Comprueba si los token van llegando en el orden definido, para luego generar la salida con formato de árbol sintáctico.

    Me modo que sus funciones serán:

    • Aceptar solo lo que es válido sintácticamente.

    • Explicitar el orden jerárquico que tienen los operadores en el lenguaje de que se trate.

    • Guiar el proceso de traducción dirigida por la sintaxis.

    A partir del árbol sintáctico que representa la sintaxis de un programa, el AS construye una derivación con recorridos por la izquierda o por la derecha del programa fuente, y partir de ellos construye una representación intermedia de ese programa fuente, que puede ser un árbol sintáctico abstracto o bien un programa en un lenguaje intermedio.

    TIPOS DE ANÁLISIS SINTÁCTICO:

    Según la teoría de Análisis Sintáctico, hay dos estrategias para construir el árbol sintáctico:

    • ANÁLISIS DESCENDENTE: Opera desde la raíz de árbol y va aplicando reglas por la izquierda, de forma de obtener una derivación por izquierda de la cadena de entrada. Recorriendo el árbol en profundidad de izquierda a derecha, encontraremos en las hojas los tokens, que nos devuelve el A.L. en ese mismo orden.

    • ANÁLISIS ASCENDENTE: Desde la cadena de entrada se construye el árbol empezando por las hojas, luego se crean nodos intermedios hasta llegar a la raíz; construyendo así al árbol de abajo hacia arriba. El recorrido se hará desde las hojas a la raíz. El orden en el que se van encontrando las producciones corresponde a la inversa de una derivación por la derecha.

    PARADIGMA: La pluma puede llegar a ser
    más cruel que la espada..!! (Robert Burton)

  5. ANÁLISIS SEMÁNTICO

    Determina el tipo de los resultados intermedios, comprueba que los argumentos que tiene un operador pertenecen al conjunto de los operadores posibles, y si son compatibles entre sí, comprueba que el significado de lo que va leyendo sea válido, de manera de generar como salida teórica un árbol semántico, que es un árbol sintáctico cuyas ramas han adquirido el significado conserniente.

    En caso del símbolo único con varios significados u operador polimórfico, el análisis semántico determina cuál es aplicable; así, para el signo “+”, que permite sumar números, concatenar cadenas de caracteres y unir conjuntos, este análisis comprobará que B y C sean de tipo compatible y que se les pueda aplicar dicho operador y si B y C son números los sumará, si son cadenas las concatenará y si son conjuntos calculara su unión.

    Los compiladores analizan semánticamente los programas para verificar su compatibilidad con las especificaciones semánticas del lenguaje al cual pertenecen y así poder comprenderlos, para permitir la recepción por parte del procesador de las órdenes cuando ese programa se ejecuta. Luego de verificar la coherencia semántica, traduce al lenguaje de la máquina o a una representación portable entre distintos entornos.

    Esta fase efectúa la traducción asociada al significado que cada símbolo de la gramática adquiere por aparecer en una producción, asociándole información o atributos, y acciones semánticas a las reglas gramaticales, que serán código en un lenguaje de programación; para evaluar los atributos y manipular dicha información de las tareas de traducción, mediante los siguientes pasos:

    • Análisis léxico del texto fuente.

    • Análisis sintáctico de la secuencia de tokens producida por el analizador léxico.

    • Construcción del árbol de análisis sintáctico.

    • Recorrido del árbol por el analizador semántico ejecutando las acciones semánticas.

    Al actuar la semántica y la traducción, los árboles de análisis sintáctico reciben en cada nodo información o atributos, dando lugar a los árboles con adornos, de manera que cada símbolo, se comporta como un registro, cuyos campos son cada uno de sus propios atributos con información semántica, dando lugar al concepto de gramática atribuida.

  6. GENERACION DE CÓDIGO INTERMEDIO

    Usar lenguaje intermedio permite construir en menor tiempo un compilador para otra máquina y compiladores para otros lenguajes fuente, generando códigos para la misma máquina. Así, el compilador de C de GNU distribuido con Linux es una versión de una familia de compiladores de C para diferentes máquinas o sistemas operativos: Alpha, AIX, Sun, HP, MS-DOS.

    La generación de código intermedio transforma el árbol de análisis sintáctico en una representación en lenguaje intermedio, de código simple para poder luego generar código máquina.

    OPTIMIZACIÓN DE CÓDIGO

    Abarca los procesos del compilador para generar programas objetos más eficientes, rápido en ejecución, que insuman menos memoria; pero como no podemos asegurar haber conseguido el programa optimo, el termino optimización no es apropiado.

    GENERACIÓN DE CÓDIGO

    El código intermedio optimizado se traduce a una secuencia de instrucciones en ensamblador o en el código de máquina del procesador que nos interese, así la sentencia Z : = X + Y se convertirá en:

    
    		LOAD        X
    		ADD         Y
    		STORE       Z
    

    TABLA DE SIMBOLOS

    Es una estructura de datos internos donde el compilador almacena información de objetos que encuentra en el texto fuente, como variables, etiquetas, declaraciones de tipos, etc. En esta tabla, el compilador puede insertar un nuevo elemento en ella, consultar información relacionada con un símbolo, borrar un elemento, etc.

    MANEJO DE ERRORES

    Esta tarea del compilador, más solicitada en la etapa de análisis sintáctico y semántico, se dificulta por que muchas veces un error:

    • Ocultan otros
    • Provoca una avalancha de muchos errores que se solucionan con el primero.

    Frente a esto se plantean dos criterios para manejar errores:

    • Pararse al detectar el primer error
    • Detectar todos los errores de una pasada.

  7. ESPECIFICAR UN COMPILADOR

    Para diseñar un compilador, la especificación del lenguaje fuente se divide en tres partes:

    • ESPECIFICACIÓN LÉXICA:
      Mediante expresiones regulares se detallan los componentes léxicos o tokens o palabras del lenguaje. A partir de estas expresiones regulares se construye el analizador léxico del compilador.

    • ESPECIFICACIÓN SINTÁCTICA:
      Detalla la sintaxis o forma o estructura que tendrán los programas en este lenguaje fuente. Tal tarea utiliza una gramática independiente del contexto en notación BNF o un diagrama sintáctico que posteriormente se convierte en una gramática; a partir de la gramática se construye el analizador sintáctico del compilador.

    • ESPECIFICACIÓN SEMÁNTICA:
      Describe el significado de cada construcción sintáctica y las reglas semánticas que deben cumplirse.

PARADIGMA
El saber y la razón hablan,
la ignorancia y el error gritan..!!
A. Graf


Volver GENERACION DE CÓDIGO INTERMEDIO

  • Cuando una empresa desarrolla un compilador para un lenguaje fuente y un lenguaje objeto determinados, normalmente no es el único compilador que la empresa piensa desarrollar; es más muchos fabricantes de microprocesadores tienen una división de dedicada a desarrollar compiladores para los nuevos chips que construya.

  • Cuando el número de lenguaje fuente crece hasta un número grande M, y/o cuando el número de lenguajes objeto también crece hasta un número grande N, es necesario encontrar una técnica para evitar tener que diseñar M x N compiladores.

    La solución consiste en utilizar un lenguaje intermedio o una representación intermedia; de esta forma sólo hay que construir M programas que traduzcan de cada lenguaje fuente al lenguaje intermedio (los front ende), y N programas que traduzcan del lenguaje intermedio a cada lenguaje objeto (los back end).

  • No existe un único lenguaje intermedio en todos los compiladores, sino que cada empresa que diseña compiladores suele tener su propio lenguaje intermedio.

    La utilización de un lenguaje intermedio permite construir en, mucho menos tiempo un compilador para otra máquina y también permite construir compiladores para otros lenguajes fuente generando códigos para la misma máquina.

  • Por ejemplo, el compilador de C de GNU que se distribuye con Linux es una versión de una familia de compiladores de C para diferentes máquinas o sistemas operativos: Alpha, AIX, Sun, HP, MS-DOS, etc..

    Además, GNU ha desarrollado un compilador de FORTRAN y otro de Pascal que, al utilizar el mismo lenguaje intermedio, pueden ser portados a todos los sistemas y máquinas en las que y a existe un compilador de C de GNU con relativamente poco esfuerzo.

  • La generación de código intermedio transforma un árbol de análisis sintáctico (semántico) en una representación en un lenguaje intermedio, que suele ser código suficientemente sencillo para poder luego generar código máquina.

  • Una forma de hacer esto es mediante el llamado código de tres direcciones. Una sentencia en código de tres direcciones es: A := B op C, donde A, B y C son operandos y op es un operador binario. También permite condiciones simples y saltos.

    OPTIMIZACIÓN DE CÓDIGO

  • Esta fase se añade al compilador para conseguir que el programa objeto sea más rápido en ejecución t que necesite menos memoria a la hora de ejecutarse. El termino optimización no es correcto, ya que nunca podemos asegurar que conseguimos un programa optimo. Con una buena optimización, el tiempo de ejecución puede llegar a reducirse a la mitad, aunque hay máquinas que pueden no llevar esta etapa y generar directamente código máquina.

    Ejemplos de posibles optimizaciones locales:

    1. cuando hay dos saltos seguidos se puede quedar uno sólo.

    2. Eliminar expresiones comunes a favor de una sola expresión. Por ejemplo:
          
      A : = B + C + D
      E : = B + C + F
      Se convierte en:
      
       T1 : =   B + C
        A : =  T1 + D
        E : =   T1 + F
      

    3. Optimización de bucles y lazos. Se trata de sacar de los bucles y lazos las expresiones que sean invariantes dentro de ellos. Por ejemplo, dado el siguiente código:
          
               REPEAT
                    B : =  1
                    A :=   A – B
               UNTIL   A  = 0
      
      Se trata de sacar del bucle la asignación B : = 1

    GENERACION DE CODIGO

  • En esta parte el código intermedio optimizado es traducido a una secuencia de instrucciones en ensamblador o en el código de máquina del procesador que nos interese. Por ejemplo: la sentencia A : = B + C se convertirá en:
        
                    LOAD       B
                    ADD        C
                    STORE      A
    

  • Suponiendo que estas instrucciones existan de esta forma en el ordenador de que se trate.

  • Una conversión tan directa produce generalmente un programa objeto que contiene muchas cargas (load) y almacenamientos (store) redundantes, y que utiliza los recursos de la máquina de forma ineficiente. Existen técnicas para mejorar esto, pero son complejas. Una, por ejemplo, es tratar de utilizar al máximo los registros de acceso rápido que tenga la máquina. Así, en el procesador 8086 tenemos los registros internos AX, BX, CX, DX, etc. y podemos utilizarlo en vez de direcciones de memoria

    TABLA DE SÍMBOLOS

  • Un compilador necesita guardar y usar la información de los objetos que se va encontrando en el texto fuente, como variables, etiquetas, declaraciones de tipos, etc.. Esta información se almacena en una estructura de datos internos conocida como tabla de símbolos.

  • El compilador debe desarrollar una serie de funciones relativas a la manipulación de esta tabla como insertar un nuevo elemento en ella, consultar la información relacionada con un símbolo, borrar un elemento, etc.. Como se tiene que acceder mucho a la tabla de símbolos los accesos deben ser lo más rápido posible para que la compilación sea eficiente.

    MANEJO DE ERRORES

  • Es una de las misiones más importantes de un compilador, aunque, al mismo tiempo, es lo que más dificulta su realización. Donde más se utiliza es la etapa de análisis sin táctico y semántico, aunque los errores se pueden descubrir en cualquier fase de un compilador. Es una tarea difícil, por dos motivos:

    • A veces unos errores ocultan otros

    • A veces un error provoca una avalancha de muchos errores que se solucionan con el primero.

  • Es conveniente un buen manejo de errores, y que el compilador detecte todos los errores que tiene el programa y no se para en el primero que encuentre. Hay, pues, dos criterios a seguir a la hora de manejar errores:

    • Pararse a detectar el primer error

    • Detectar todos los errores de una pasada.

  • En el caso de un compilador interactivo (dentro de un entorno de desarrollo integrado, como Turbo Pascal o Borland C++) no importa que se pare en el primer error detectado, debido a la rapidez y facilidad para la corrección de errores.

    ESPECIFICAR UN COMPILADOR

  • Cuando se va diseñar un compilador, puesto que se trata de un traductor entre dos lenguajes, es necesario especificar el lenguaje fuente y el lenguaje objeto, así como el sistema operativo sobre el que va a funcionar el compilador y el lenguaje utilizado para construir el compilador. Existen algunas herramientas formales para especificar los lenguajes objetos, pero no existe ninguna herramienta cuyo uso sea extendido.

    La especificación del lenguaje fuente se divide en tres partes:

    1. Especificación léxica: en esta parte se especifican los componentes léxicos (tokens) o palabras del lenguaje para ello se utilizan expresiones regulares. A partir de estas expresiones regulares se construye el analizador léxico del compilador.

    2. Especificación sintética: en esta parte se detalla la forma o estructura (la sintaxis) que tendrán los programas en este lenguaje fuente. Para esta tarea se utiliza una gramática independiente del contexto en notación BNF o un diagrama sintáctico que posteriormente se convierte en una gramática; a partir de la gramática se construye el analizador sintáctico del compilador.

    3. Especificación semántica.: en esta parte se describe el significado de cada construcción sintáctica y las reglas semánticas que deben cumplirse, aunque existen notaciones formales para especificar la semántica del lenguaje, normalmente se especifica con palabras (lenguaje natural). Algunas veces es posible recoger en la especificación sintáctica algunas partes (restricciones, asociatividad, y precedencia, etc.) de la especificación semántica. El analizador semántico y el generador de código intermedio se construye apartir de la especificación semántica.

    APLICACIONES

  • La importancia practica de lenguaje en la informática se manifiesta principalmente en el uso cotidiano que hace el profesional informático de compiladores e interpretes, consustancial al la gestión y programación de los sistemas informáticos. Así pues, un conocimiento acerca del funcionamiento interno de estas herramientas básicas resulta fundamental. Pero los conocimientos adquiridos en su estudio encuentren aplicación fuera del campo de la compilación. Es probable que ocas personas realice o mantenga un compilador para un lenguaje de programación, pero mucha gente puede obtener provecho del uso de un gran número de sus técnicas para el diseño de software en general.

  • En efecto, entre los campos de la informática en los que encuentra aplicación las técnicas aprendidas en COMPILADORES e INTÉRPRETES se puede citar lo siguiente:

    1. Tratamiento de ficheros de texto con información estructurada. Lenguaje como Perl y TEL, o comandos como el sed o egrep de UNIX, incorpora tratamiento de expresiones regulares para la detección y/o modificación de patrones sin texto.

    2. Procesadores de texto. Procesadores como vi o Emacs incorporan también la posibilidad de efectuar búsquedas y sustituciones mediante expresiones regulares. Existen también procesadores (entre ellos los Emacs) capaces de analizar y tratar ficheros de texto de organización compleja.

    3. Diseño e interpretación de lenguaje para formateo y texto y descripción de gráficos. Sistema de formateo de texto (como el HTML o el TEX) o para la especificación de tablas (tbl), ecuaciones (eqn), gráficos (postscript), etc. requieren sofisticados microprocesadores.

    4. Gestión de base de datos. Las técnicas que estamos considerando pueden explotarse tanto en la exploración y proceso de ficheros de información como en la realización de la interfase de usuario.

    5. Traducción de formato de fichero.

    6. Calculo simbólico.

    7. Reconocimiento de formas. Las técnicas de análisis sintáctico son ampliamente utilizadas en la detección de patrones en texto, el reconocimiento automático del habla o la visión por computador.


Volver ANALISIS LÉXICO

  • El analizador léxico es la primera fase de un programa traductor. Es, por otra parte, el único que gestiona el fichero de entrada. Es la parte del compilador que lee los caracteres del programa fuente y que construye unos símbolos intermedios (elementos léxicos que llamaremos “tokens”) que serán posteriormente utilizados por el analizador sintáctico como entradas.

  • El analizador sintáctico debe obtener una representación de la estructura (sintaxis) del programa fuente. Para realizar esta tarea debería concentrarse solamente en la estructura y no en otros aspectos menos importantes, como los espacios construidos con una gramática que genere los programas carácter no son útiles para construir una traducción.

  • ¿Por qué separar el análisis léxico del sintáctico?

    • El diseño de las partes posteriores dedicadas al análisis queda simplificado.

    • Con fases separadas, se pueden aplicar técnicas específicas y diferenciadas para cada fase, que son más eficientes en sus respectivos dominios.

    • Se facilita la portabilidad. Si se quiere cambiar alguna característica del alfabeto del lenguaje (por ejemplo para adaptarlo a determinados símbolos propios de máquinas distintas) sólo tenemos que cambiar el analizador léxico.

    Si tomamos por ejemplo las expresiones “6 – 2 * 30 / 7” y “6 – 2 * 30 / 7”, podemos comprobar que la estructura de ambas expresiones es equivalente, sin embargo, los caracteres que componen ambas cadenas no son los mismos.

    Si tuviéramos que trabajar directamente con los caracteres estaríamos dificultando la tarea de obtener la misma representación para ambas cadenas.

    Si consideramos además la cadena “8 – 2 * 3 / 5”, la estructura de esta cadena es de nuevo la misma que la de las cadenas anteriores, lo único que cambia son los valores concretos de los números. Por estos motivos (y también por eficiencia), el procesamiento de los caracteres se deja en mano del analizador léxico que entregará a las sucesivas etapas del compilador los componentes léxicos (tokens) significativos.

    Donde cada token ha sido representado por un par en el que la primera componente de cada par es el tipo de token y la segunda componente es el lexema (el valor concreto de ese token). La tercera cadena del ejemplo anterior tendría la misma estructura que las otras dos, pero con distintos valores de los lexemas.

    En definitiva, el análisis léxico agrupará los caracteres de la entrada por categorías léxicas, establecidas por la especificación léxica del lenguaje fuente como veremos más adelante. Esta especificación también establecerá el alfabeto con el que se escriben los programas válidos en el lenguaje fuente y, por tanto, el analizador léxico también deberá rechazar cualquier texto en el que aparezcan caracteres ilegales (no recogidos en ese alfabeto) o combinaciones ilegales (no permitidas por las especificaciones léxicas) de caracteres del alfabeto.

    Veremos que los componentes léxicos se especifican mediante expresiones regulares que generan lenguajes regulares, más sencillos de reconocer que los lenguajes independientes del contexto, y permiten hacer un análisis más rápido. Además, una gramática que represente la sintaxis de un lenguaje de alto nivel carácter a carácter sería mucho más compleja (para implementar un proceso de traducción a partir de ella) que otra que representase la misma sintaxis en función de sus componentes léxicos.

    2.2 ERRORES LEXICOS

    Pocos son los errores característicos de esta etapa, pues el compilador tiene todavía una visión muy local del programa. Por ejemplo, si el analizador léxico encuentra y aísla la cadena “While” creerá que es un identificador, cuando posiblemente se tratara de un while mal escrito y no será él el que informe del error, sino que lo harán sucesivas etapas del análisis del texto.

    Los errores que típicamente detecta el analizador léxico son:

    • Utilizar caracteres que no pertenecen al alfabeto del lenguaje (por Ej.: “ñ” o”?”).
    • Se encuentra una cadena que no coincide con ninguno de los patrones de los tokens posibles (por Ej.: “123dfxr”o “123.456.789”si la especificación léxica no los permite).

    Cuando el analizador léxico encuentra un error, lo habitual es parar su ejecución e informar, pero hay una serie de posibles acciones por su parte para anotar los errores, recuperarse de ellos y seguir trabajando:

    • Ignorar los caracteres no válidos hasta formar un token según los patrones dados;
    • Borrar los caracteres extraños;
    • Insertar un carácter que pudiera faltar;
    • Reemplazar un carácter presuntamente incorrecto por uno correcto;
    • Conmutar las posiciones de dos caracteres adyacentes.

    Estas transformaciones se realizan sobre el prefijo de entrada que no concuerda con el patrón de ningún token, intentando conseguir un lexema válido. No obstante, todas son complicadas de llevar a cabo y peligrosas por lo equivocadas que pueden resultar para el resto del análisis.

    2.3 FUNCIONAMIENTO DEL ANALIZADOR LEXICO

    La principal función del analizador léxico es procesar la cadena de caracteres y devolver pares (token, lexema). Debe funcionar como una subrutina del analizador sintáctico.

    Operaciones que realiza el analizador léxico:

    • Proceso léxico del programa fuente: identificador de tokens y de sus lexemas que deberán entregar al analizador sintáctico y (puede que) interaccionar con la tabla de símbolos.
    • Maneja el fichero del programa fuente; es decir: abrirlo, leer sus caracteres y cerrarlo. También debería ser capaz de gestionar posibles errores de lectura.
    • Ignorar los comentarios y, en los lenguajes de formato libre, ignora los separadores (espacios en blanco, tabuladores, retornos de carro, etc.).
    • Cuando se produzca una situación de error será el analizador léxico el que sitúe el error en el programa fuente (tal línea, tal posición). Lleva la cuenta de las líneas procesadas.
    • Proceso de macros, definiciones, constantes y órdenes de inclusión de otros ficheros.

    Cada vez que el analizador sintáctico llame al léxico éste debe leer caracteres desde donde se quedó en la anterior llamada hasta conseguir completar un nuevo token, y en ese momento debe devolver el par (token, lexema).

    Cuando el analizador léxico intenta reconocer algunos tipos de tokens como los identificadores o los números se produce una circunstancia especial: el analizador léxico debe leer caracteres hasta que lea uno que no pertenece a la categoría del token que está leyendo; ese último carácter (que no tiene por qué ser un espacio en blanco) no puede perderse, y debe devolverse el buffer de entrada para ser leído en primer lugar la próxima vez que se llame al analizador léxico.

    EJEMPLO
    En la cadena:
    “Grande / 307 ??=” marcamos las posiciones a las que tiene que llegar el analizador léxico para decidir qué tokens ha reconocido.
    Grande / 307 ??=

    Como se puede observar, para el caso del identificador “Grande”, ha tenido que ir una posición más allá del final del mismo, pues sólo allí, al encontrar el espacio en blanco puede que el nombre del identificador ha concluido. Para encontrar el símbolo “/” basta con ponerse sobre él y verlo si consideramos que no es prefijo de ninguno otro (para este lenguaje imaginario).

    Para el número “307” sucede lo mismo que con el identificador: hay que llegar hasta un carácter que no sea un número para saber que el número ha terminado.

    Este símbolo es este caso es el signo”?” de “?=” (mayor o igual que).
    Después, para reconocer este nuevo token el léxico avanzará para ver si es el “=” lo que sigue al “?”.
    Como sí que lo es y suponemos que “=” no es prefijo de ningún otro, el analizador devolverá el token “mayor o igual”, si no hubiera aparecido el igual al avanzar, hubiera tenido que retroceder una posición y devolver el token “mayor”.

    El analizador léxico debe intentar leer siempre el token más largo posible. Puede ocurrir que haya leído ya un token correcto y al intentar leer un token más largo no sea posible; en este caso no se debe producir un error, sino que el analizador léxico debe devolver al token correcto y debe retroceder en el buffer de entrada hasta el final de ese token.

    EJEMPLO
    Si el operador “!=” (distinto) pertenece al lenguaje pero el carácter “!” No, cuando aparezca en la entrada este carácter, el analizador debe leer el siguiente carácter; si es un “=”, deberá el token correspondiente al operador distinto, pero si no es un “=”, debe producir un error léxico `puesto que el carácter “!” por si solo no pertenece al lenguaje.

    2.4 ESPECIFICACIONES DE UN ANLIZADOR LEXICO

    Definición de términos comunes en esta fase:

    • Tokens:
      son los símbolos terminales de cada gramática (por ejemplo: palabras reservadas, identificadores, signos de puntuación, constantes numéricas, operadores, cadenas de caracteres, etc.). Es posible, dependiendo del lenguaje, que varios signos formen un solo token (“: =”, “= =”, “+ =”, “???”, etc.).

    • Patrón:
      expresión regular que define el conjunto de cadenas que puede representar a cada uno de los tokens.

    • Lexema:
      secuencia de caracteres del código fuente que concuerda con el patrón de un token. Es decir, cuando analizamos el texto fuente y encontramos una cadena de caracteres que representan un token determinado diremos que esa cadena es un lexema.

    • Atributos:
      el análisis léxico debe proporcionar información adicional sobre los tokens en sus atributos asociados.
      El número de atributos depende de cada token. En la práctica, se puede considerar que los tokens tiene un único atributo, un registro que contiene toda la información propia de cada caso (por ejemplo, lexema, tipo de token y línea y columna en la que fue encontrado).
      Lo normal es que toda esa información se entregue a los analizadores sintácticos y semánticos para que la usen como convenga.

    Cuando el analizador léxico encuentra un lexema devuelve como información a qué token pertenece y todo lo que sabe de él, incluido el propio lexema. En el último caso, se supone que esa palabra pertenece a un lenguaje en el que mayúsculas y minúsculas son equivalentes.

    Para especificar correctamente el funcionamiento de una analizador léxico se debe utilizar una máquina de estados, llamada diagrama de transición (DT), muy parecida a un autómata finito determinista, con las siguientes diferencias:

    • Un AFD sólo dice se la cadena de caracteres pertenece al lenguaje o no; un DT debe funcionar como un analizador léxico; es decir, debe leer caracteres hasta que complete un token, y en ese momento debe retornar, (en los estados de aceptación) el token que ha leído y dejar el buffer de entrada preparado para la siguiente llamada.

    • Un DT no puede tener estados de absorción (para cadenas incorrectas en AFDs) ni de error (se considerará que las entradas para las que no hay una transición desde cada estado son error).

    • De los estados de aceptación de un DT no deben salir transiciones.

    • En el caso de las tiras no especificadas, necesitamos otro estado a que ir cuando se lea un carácter que no puede formar parte del patrón. En este último estado (al que se llega con la transición especial otro) se debe devolver al buffer de entrada el carácter leído (que puede ser parte del siguiente token), lo cual se indica marcando el estado con un asterisco, y se debe retornar el token correspondiente a ese estado de aceptación. Por ejemplo, para reconocer números enteros, con un AFD son necesarios solamente dos estados; con un DT necesitamos ese otro estado al que ir cuando se lea un carácter que no que no pueda formar parte del número.

    En el caso más general, se suelen utilizar estos diagramas de transiciones para conocer los tokens de entrada, construidos a partir de sus patrones correspondientes, expresados mediante las respectivas expresiones regulares.

    Estos autómatas se combinan en una máquina única que, partiendo de un único estado inicial, sigue un recorrido u otro por los estados hasta llegar a alguno de los estados de aceptación.

    En función de en cual se detenga devolverá un token u otro. Si no llega a un estado de aceptación o recibe una entrada que no le permite hacer una transición a otro estado, entonces dará error.

    EJEMPLO
    A continuación se muestra un ejemplo de reconocedor de números enteros sin signo mediante la expresión regular [0-9].

    El AFD sería:

    y el DT:

    Como se observa, en el DT surge un nuevo estado, que es realmente el de aceptación y que está marcado con un asterisco que indica que se llega a él leyendo un carácter a la entrada. La transición a ese estado se hace mediante la entrada otro que significa cualquier otro carácter del alfabeto del lenguaje que no esté en el rango [0-9].

    Si durante el recorrido del autómata se produce una transición no autorizada o la tira de entrada finaliza en un estado no de aceptación, el analizador informará del error. Este tipo de máquinas es útil para lenguajes con grandes conjuntos de elementos léxicos distintos y de las matrices de transición resultantes tienen grandes zonas vacías que conviene comprimir y resumir mediante algoritmos adecuados.

    Cuando los lenguajes son poco extensos es mejor redactar los analizadores “a mano”, tratando de tomar decisiones adecuadas en función de los caracteres que van apareciendo en la entrada (ver apartado de implementación, más adelante).

    El analizador suele tener unos subprogramas auxiliares encargados de gestionar el buffer (técnicas de doble buffer, saltos de línea, < EOF < , etc.) y de ir devolviendo caracteres al buffer de entrada cada vez que el procedimiento de reconocimiento y aislamiento de tokens lo requiere.

    Identificación de palabras reservadas:

    Las palabras reservadas son aquellas que los lenguajes de programación reservan para usos particulares. El problema que surge es: ¿cómo reconocer las palabras reservadas si responden al mismo patrón que los identificadores, pero son tokens diferentes al token “identificador”?.

    Existen dos enfoque para resolver este problema: 1) saltándose el formalismo para buscar una solución práctica (factible si se implementa el A.L. “a mano”); 2) integrando los DT (más complicado pero necesario si usamos programas de conversión automática de especificaciones en analizadores).

    La primera solución citada consiste que las palabras reservadas son en principio identificadores, y entonces leer letras y dígitos hasta completar un identificador, e inmediatamente antes de retomar el token identificador, comparar el lexema leído con una lista de las palabras reservadas, para ver si coinciden con alguna de ellas.

    En definitiva, se procede normalmente tratando las palabras reservadas como lexemas particulares del patrón del identificador, y cuando se encuentra una cadena que responde a dicho patrón, se analiza si es una palabra reservada o un identificador.

    Una posible solución para ello es, en el A.L.:

    • Primero inicializar la tabla de símbolos con todas las palabras reservadas (lo normal es hacerlo por orden alfabético para facilitar la posterior búsqueda y acceso).
    • Cuando encuentre un identificador se irá a mirar la tabla de símbolos.
    • ==> Si lo encuentra en la zona reservada para ellas ENTONCES es una palabra reservada
    • ==> SI NO, será un identificador, que, como tal, será añadido a la tabla de símbolos.

    EJEMPLO
    Si se encuentra el identificador “Cont.” en la entrada, antes de que el A.L. devuelva el token identificador deberá comprobar si se trata de una palabra reservada. Si el número de palabras reservadas es muy grande lo mejor es tenerlas almacenadas desde el principio de la compilación en la tabla de símbolos, para ver si allí ya se encuentra definida esa cadena como tal. Aquí hemos supuesto que no es así y “Cont.” queda registrado como un identificador.

        
    		Tabla de Símbolos
    		do
    		Pal. Reservada
    		end
    		Pal. Reservada
    		for
    		Pal. Reservada
    		while
    		Pal. Reservada
    		...
    		....
    		cont.
    		Identificador
    

    La disposición de una tabla ordenada con las palabras reservadas es útil cuando el número de estas es grande. Cuando el lenguaje tiene sólo unas pocas puede ser más práctico el realizar la identificación “directamente”, mediante una serie de ifs que comparen con las cadenas correspondientes a esas palabras.

    Cuando la detección de palabras reservadas se hace, en cambio, formalmente, entonces los patrones de la especificación léxica del lenguaje tendrán su correspondencia en el diagrama de transiciones global a partir del cual se implementará el analizador léxico.

    Las especificaciones léxicas de las palabras reservadas, como tira especificadas que son, constarán de concatenaciones de caracteres y pueden ser siempre prefijos de identificadores (como por ejemplo “do” –palabra reservada- y “dos” –identificador-).

    Cuando en la especificación léxica del lenguaje coexisten expresiones regulares de tiras no específicas como los identificadores con las de específicas como las palabras reservadas, hay que llevar más cuidado porque cualquiera de las palabras reservadas puede ser un prefijo de un identificador válido. Esto motiva que los subautómatas que reconocen las palabras deben estar comunicados con el de los identificadores (ver ejemplo más abajo).

    Por otra parte, cuando un elemento léxico es prefijo de otro y ambos son tiras específicas, aparecerán estados de aceptación que partirán de estados intermedios (ver ejemplo de la página siguiente)

    EJEMPLO
    Constrúyase un diagrama de transiciones para el reconocimiento de identificadores, números enteros sin signo y las palabras reservadas “do” y “done”.

    Notación: d = dígito; l = letra; t = otro; f = otro alfanumérico (dígito o letra); a n = ir al estado n.

    Como se observa en este diagrama de transiciones, todos los estados de aceptación están marcados con asterisco, por lo que siempre que devolver el último carácter leído al buffer de entrada. Esto es debido, en este ejemplo a que todos los tokens son bien unos prefijos de otros (do?done?identificador) o bien son tiras no especificadas (entero e identificador).

    EJEMPLO
    Constrúyase un diagrama de transiciones para el reconocimiento de números enteros con signo negativo o sin signo (ER: (-???*?d+) y los operadores suma (“+”) y doble incremento (“+++”).

    Notación: d=dígito; t=otro.

    Obsérvese que el estado de aceptación del token “doble incremento” no lleva asterisco por ser una tira específica y no ser prefijo de ninguna otra, y por tanto no necesita la lectura del siguiente carácter y el retroceso. Si que lo llevan los estados de aceptación del token “suma” a pesar de ser específicas, pues son prefijos del “doble incremento”. Además, uno de ellos lleva dos asteriscos, indicando que si se llega a ese estado hay que retornar el token “suma” pero hay que devolver dos caracteres al buffer de entrada.

    2.5 IMPLEMENTACION DE ANALIZADORES LEXICOS
    existen distintas posibilidades para de crear un analizador léxico, las tres más generales son:

    1. Usar un generador automático de analizadores léxicos, como el LEX: su entrada es un código fuente con la especificación de las expresiones regulares de los patrones que representan a los token del lenguaje, y las acciones a tomar cuando los detecte.
      • Ventaja: comodidad y rapidez en el desarrollo.
      • Inconveniente: ineficiencia del analizador resultante y complicado mantenimiento de código generador.

    2. Escribir el AL en un lenguaje de alto nivel de uso general utilizando sus funciones de E/S.
      • Ventaja: más eficiente.
      • Inconveniente: hay que hacerlo todo a mano.

    3. Hacerlo en lenguaje ensamblador.
      • Ventaja: máxima eficiencia.
      • Inconveniente: muy complicado de desarrollar.

      Como se ha indicado, la forma más cómoda de implementar un analizador léxico es con un generador automático de analizadores léxicos, como lex, si bien no es la forma más eficiente. Si se opta por hacerlo “a mano”, se puede hacer de varias maneras: implementando el diagrama de transiciones simulando las transiciones entre estados o bien se pueden implementar “directamente”, usando estructuras de selección múltiple (switch en C, case en Pascal, etc.) para, según cual sea el primer carácter del tolken, leer caracteres hasta completar el token. Por supuesto, con esta técnica también es necesario al buffer de entrada.

      Por otro lado, lo normal cuando se construye un A.L. es establecer criterios para dar más prioridad a unos tokens que a otros. Criterios:
      * Dar prioridad al token para el que encontramos el lexema más largo. Por ej: “DO” / “DOT”, el generador se quedaría con el más largo (“DOT”) como identificador (otro ejemplo: “>”" y “>=” se debe quedar con el segundo).
      Si el lexema es el mismo que se puede asociar a dos tokens (patrones), estos patrones estarán definidos en un orden, así se asociará al que esté primero.


Volver ANALIZADOR SINTÁCTICO

  • La principal tarea del analizador sintáctico (o parser) no es comprobar que la sintaxis del programa fuente sea correcta, sino construir una representación interna de ese programa y, en el caso en que sea un programa incorrecto, dar un mensaje de error.

    Para ello, el analizador sintáctico (A.S.) comprueba que el orden en que el analizador léxico le va entregando los tokens es válido. Si esto es así significar que la sucesión de símbolos que representan dichos tokens puede ser generada por la gramática correspondiente al lenguaje del código fuente.

  • La forma más habitual de representar la sintaxis de un programa es el árbol de análisis sintáctico, y lo que hacen los analizadores sintácticos es construir una derivación por la izquierda o por la derecha del programa fuente, que en realidad son dos recorridos determinados del árbol de análisis sintáctico. A partir de ese recorrido el analizador sintáctico debe construir una representación intermedia de ese programa fuente: un árbol sintáctico abstracto o bien un programa en un lenguaje intermedio; por este motivo, es muy importante que la gramática esté bien diseñada, e incluso es frecuente rediseñar la gramática original para facilitar la tarea de obtener la representación intermedia mediante un analizador sintáctico concreto.

    EJEMPLO
    Los árboles sintácticos abstractos son materializaciones de los árboles de análisis sintáctico en los que se implementan los nodos de éstos, siendo el nodo padre el operador involucrado en cada instrucción y los hijos sus operandos.

    Por otra parte, las representaciones intermedias son lenguajes en los que se han eliminado los conceptos de mayor abstracción de los lenguajes de programación de alto nivel.

    Sea la instrucción “a=b+c-d”. A continuación se muestra su representación mediante ambos esquemas citados.

    Árbol sintáctico abstracto
    Lenguaje intermedio

    Sumar b c t1
    Restar t1 d t2
    Asignar t2 a
    

    El A.S. constituye el esqueleto principal del compilador. Habitualmente el analizador léxico se implementa como una rutina dentro del sintáctico, al que devuelve el siguiente tokens que encuentre en el buffer de entrada cada vez que éste se lo pide. Así mismo, gran parte del resto de etapas de un programa traductor están integradas de una u otra forma en el analizador sintáctico.

    Principalmente hay dos opciones para implementar un parser:

    1. “a mano”, utilizando una serie de técnicas que se describirán en los siguientes temas;

    2. utilizando un generador de analizadores sintácticos (por Ej. el YACC).

    Como siempre, ambos enfoques tienen ventajas e inconvenientes, muy similares al caso de los analizadores léxicos (para el segundo caso el inconveniente de la ineficiencia y la ventaja de la sencillez, y viceversa para el primero).
    En este tema nos centramos técnicas para implementar a mano parsers para determinados tipos de gramáticas.

    3.2 NOTACIÓN EBNF

    EBNF son las siglas de Extended Backus-Naur Form. La idea surgió como herramienta para reducir el número de producciones en las gramáticas, Para ello se añaden unas notaciones adicionales a las ya contenidas en la notación BNF.

    1. Alternativas de una regla:
      Como un mismo símbolo auxiliar puede definirse como varios símbolos, utilizamos una única producción utilizando el símbolo '|' para separar las distintas posibilidades que definen al no terminal de la izquierda.
      
            Ejemplo: si 	A --> a
            A --> b
            A --> c
      

      estas tres producciones las resumimos en una equivalente: A -->a | b | c

      Otro: --> |

    2. Llaves: { }, lo que aparece entre llaves se repite de cero a n veces.
      Ejemplos:
      --> {, }
      --> { }

    3. Llaves con repetición especificada: { }xy, lo que aparece entre llaves se repite un número de veces comprendido entre x e y.
      Ejemplo:
      tren con 3, 4 ó 5 vagones: --> { }35

    4. Corchetes: [ ], lo que está entre los corchetes puede o no aparecer. Es un caso particular de 3.-, pues es equivalente a { }o1
      Ejemplo:
      Sentencia IF completa en Pascal:

      IF THEN [ELSE ]

    PARADIGMA: Más mueven los ejemplos que las palabras...!!! (Séneca)

    DISEÑO DE GRAMÁTICAS PARA LENGUAJES DE PROGRAMACIÓN

    El diseño de gramáticas para lenguajes de programación es una materia que difícilmente puede enseñarse en su totalidad, sino que debe ser aprendida en la mayor medida posible. Sin embargo, la roma de recoger parte de la semántica de los operadores en la gramática es bastante sencilla de explicar. A continuación vamos a ver cómo se plasma en el aspecto de las reglas sintácticas algunas propiedades de los operadores y operandos en los lenguajes de programación.

    3.3.1 RECURSIVIDAD

    Una de las principales dificultades a la hora de diseñar un compilador es que debe procesar correctamente un número, en principio, infinito de programas distintos. Por otro lado, es evidente que la especificación sintáctica de un lenguaje debe ser finita.

    El concepto que hace compatible las dos afirmaciones anteriores es el de recursividad. Ésta nos permite definir sentencias complicadas con un número pequeño de sencillas reglas de producción.

    EJEMPLO
    Supongamos que queremos expresar la estructura de un tren formado por una locomotora y un número cualquiera de vagones detrás. Si lo hiciéramos de esta forma:

          tren --> locomotora
          tren --> locomotora vagón
          tren --> locomotora vagón vagón
    

    Necesitaríamos infinitas reglas de derivación (una por cada número de vagones posibles en el tren). Para expresar lo mismo con un par de sentencias podemos utilizar la recursividad de la siguiente manera:

    1°) definimos la regla base (no recursiva), la cual define el concepto elemental de partida y que en este caso sería: tren --> locomotora

    2°) definimos una o más reglas recursivas que permiten el crecimiento ilimitado de la estructura partiendo del concepto elemental anterior. En este caso una nos basta: tren --> tren vagón
    y con esto nos ahorramos la utilización de muchas más reglas.

    Estructura de la recursividad:

    1. Regla no recursiva que se define como caso base.

    2. Una o más reglas recursivas que permiten el crecimiento a partir del caso base.

    Definición:
    Una gramática se dice que es recursiva, si podemos derivar una tira en la que nos vuelve a aparecer el símbolo no terminal que aparece en la parte izquierda de la regla de derivación. A => ?A? Unos casos especiales de recursividades son aquellos en los que aparecen derivaciones como A => ?? o A => ?A y se denominan recursividad izquierda y derecha, respectivamente.

    Un no terminal A se dice que es recursivo si a partir de A se puede derivar una forma sentencial en aparece él mismo en la parte derecha.

    3.3.2 AMBIGÜEDAD

    Una gramática es ambigua si el lenguaje que define contiene alguna sentencia que tenga más de un único árbol de análisis sintáctico. Es decir, si se pueden construir más de un árbol sintáctico quiere decir que esa sentencia puede “querer decir” cosas diferentes (tiene más de una interpretación). Una gramática es no ambigua cuando cualquier tira del lenguaje que representa, tiene un único árbol sintáctico.

    Como veremos más adelante, no es posible construir ana1izadores sintácticos eficientes para gramáticas ambiguas y, lo que es peor, al poderse obtener más de un árbol sintáctico para la misma cadena de entradas, es complicado conseguir en todos los casos la misma representación intermedia. Por estos motivos debemos evitar diseñar gramáticas ambiguas para los lenguajes de programación; aunque no disponemos de técnicas para saber a priori si una gramática es ambigua o no, si ponemos ciertas restricciones a la gramática estaremos en condiciones de afirmar que no es ambigua.

    La única forma de saber que una gramática es ambigua es encontrando una cadena con dos o más árboles sintácticos distintos (o dos derivaciones por la izquierda). Las gramáticas que vamos a utilizar normalmente generan lenguajes infinitos, por tanto no es posible encontrar en un tiempo finito esa cadena con dos o más árboles sintácticos. Sin embargo, si la gramática tiene alguna de las siguientes características, es sencillo encontrar una cadena con dos o más árboles:

    PARADIGMA
    El camino de la juventud.. lleva toda una vida..!!
    Pablo Picasso

    ASOCIATIVIDAD Y PRECEDENCIA DE LOS OPERADORES

    Asociatividad
    Define como se operan tres o más operandos; se dice que la asociatividad de un operador ‘#’ es por la izquierda si aparecen tres o más operandos que se evaluando izquierda a derecha: primero se evalúan los dos operandos de más a la izquierda, y el resultado de esa operación se opera con el siguiente operando por la izquierda, y así sucesivamente.

    Si la asociatividad del operador es por la derecha, los operandos se evalúan de derecha a izquierda. En los lenguajes de programación imperativos más utilizados, la asociatividad de la mayoría de los operadores y en particular la de los operadores aritméticos es por la izquierda.

    EJEMPLO
    Si la asociatividad del operador ‘#’ es por la izquierda, la expresión ‘2 # a # 7.5’ se evalúa operando primero el ‘2’ con la variable ‘a’, y operando después el resultado con ‘7.5’. si la asociatividad fuera por la derecha, primero se operarían la variable ‘a’ con el ‘7.5’ y después se operaría el ‘2’ con el resultado de esa operación.

    EJEMPLO
    En Fortran existen cinco operadores aritméticos: suma (“+”), resta (“-”), multiplicación (“*”), división (“/”) y exponenciación (“**”). Los cuatro primeros son asociativos por la izquierda, mientras que el último lo es por la derecha:

    * A / B / C se evalúa como A / B y el resultado se divide por C *

    X ** Y ** Z se evalúa como Y ** Z y X se eleva al resultado

    Cuando la asociatividad del operador es por la izquierda, la regla sintáctica en la que interviene dicho operador debe ser recursiva por la izquierda, y cuando es por la derecha, la regla en la que interviene debe tener recursión por la derecha.

    Precedencia
    Especifica el orden relativo de cada operador con respecto a los demás operadores; si un operador ‘#’ tiene mayor precedencia que otro operador ‘%’, cuando en una expresión aparezcan los dos operadores, se debe evaluar primero el operador con mayor precedencia.

    EJEMPLO
    Si aparece una expresión como ‘2 % 3 # 4’, al tener el operador ‘#’ mayor precedencia, primero se operarían el ‘3’ y el ‘4’, y después se operaría el ‘2’ con el resultado de esa operación.

    En la mayoría de los lenguajes de programación los operadores multiplicativos tienen mayor precedencia que los aditivos, se evalúan las multiplicaciones y divisiones de izquierda a derecha antes que las sumas y restas.

    La forma de reflejar la precedencia de los operadores aritméticos en una gramática es bastante sencilla. Es necesario utilizar una variable en la gramática por cada operador de distinta precedencia. Cuanto más “cerca” este la producción de la del símbolo inicial, menor será la precedencia del operador involucrado.

    Parentización
    Se utilizan los paréntesis (que son operadores especiales que siempre tienen la máxima precedencia) para agrupar los operadores según la conveniencia del programador y sortear las precedencias y asociatividades definidas en el lenguaje.

    Para incluirlos en la gramática, se añade una variable que produzca expresiones entre paréntesis los operandos a la mayor distancia posible del símbolo inicial.

    EJEMPLO
    Suponiendo los operadores +, -, con asociatividad por la izquierda y los operadores *, / con asociatividad por la derecha. Sean para los dos tipos de operadores la precedencia habitual en los lenguajes de programación y los paréntesis tienen la máxima precedencia. La gramática que genera las expresiones con estos operadores y además recoge la asociatividad y la precedencia es la siguiente:

    Esta gramática refleja la precedencia y asociatividad de los operadores. Esto es importante puesto que en la mayoría de los lenguajes objeto los operadores no tienen precedencia o asociatividad. Si el árbol sináptico mantiene correctamente agrupados los operandos de dos en dos será más sencillo evaluar la expresión y traducirla a un lenguaje objeto típico.

    TIPOS DE ANÁLISIS SINTÁCTICO

    Los algoritmos de Análisis Sintáctico general para gramáticas independientes del contexto tienen un coste demasiado elevado para un compilador.

    Desde el punto de vista de la teoría de Análisis Sintáctico, hay dos estrategias para construir el árbol sintáctico:

    * Análisis descendente:
    partimos de la raíz de árbol (donde estará situado el axioma o símbolo inicial de la gramática) y se van aplicando reglas por la izquierda, de tal forma se obtiene una derivación por la izquierda de la cadena de entrada. Para decidir que regla aplicar se lee un token de la entrada. Recorriendo el árbol en profundidad de izquierda a derecha, encontraremos en las hojas los tokens, que nos devuelve el A.L. en ese mismo orden.

    * Análisis ascendente:
    partiendo de la cadena de entrada se construye el árbol empezando por las hojas y se van creando nodos intermedios hasta llegar a la raíz; construyendo así al árbol de abajo hacia arriba. El recorrido se hará desde las hojas a la raíz. El orden en el que se van encontrando las producciones corresponde a la inversa de una derivación por la derecha.

    Las dos estrategias recorren la cadena de entrada de izquierda a derecha una sola vez, y necesitan un análisis eficiente para que la gramática no sea ambigua.

    EJEMPLO
    Ambos tipos de análisis son eficientes pero no son capaces de trabajar con todo tipo de gramáticas. Algunas gramáticas adecuadas para estos tipos de análisis son muy convenientes para describir la mayoría de lso lenguajes de programación, por ejemplo los siguientes:

    * Análisis LL(n)

    * Análisis LR(n)

    Donde
    L Left to Right: la secuencia de tokens de entrada se analiza de izquierda a derecha.
    L Left-most (R = Right-most): utiliza las derivaciones más a la izquierda (a la derecha).
    n: es en número de símbolos de entrada que es necesario conocer en cada momento para poder hacer el análisis.

    Una gramática LL(2) es aquella cuyas cadenas son analizadas de izquerda a derecha y para las que es necesario mirar dos tokens para saber que derivación tomar para el no terminal más a la izquierda en el árbol de análisis. Conn estos tipos de análisis podemos implementar un analizador para cualquier gramática de contexto libre.

    PARADIGMA
    La ignorancia niega o agrede o critica
    La ciencia duda..!!
    wilocarpio

    ANÁLISIS SEMÁNTICO
    Traducción dirigida por la sintaxis:
    Los compiladores analizan semánticamente los programas para ver si son compatibles con las especificaciones semánticas del lenguaje al cual pertenecen y así poder comprenderlos, teniendo claro que la comprensión para la máquina representa la recepción por parte del procesador de una serie de órdenes cuando ese programa se ejecuta.

    Cuando el compilador verifica la coherencia semántica lo traduce al lenguaje de la máquina o a una representación que permita una mayor portabilidad entre distintos ambientes.

    Es la fase de análisis semántico la que lleva a cabo acciones de traducción asociada al significado que cada símbolo de la gramática adquiere por aparecer en una producción u otra. Para que los símbolos puedan adquirir significados, se les asociará información (atributos) y a las reglas gramaticales, acciones semánticas, que serán código en un lenguaje de programación; y cuya misión es evaluar los atributos y manipular dicha información para llevar a cabo las tareas de traducción.

    Para el análisis semántico se deben haber llevado a cabo los siguientes pasos:

    • * Análisis léxico del texto fuente.
    • * Análisis sintáctico de la secuencia de tokens producida por el analizador léxico.
    • * Construcción del árbol de análisis sintáctico.
    • * Recorrido del árbol por el analizador semántico ejecutando las acciones semánticas.

    La cadena de entrada se analiza sintácticamente, construyendo su árbol de análisis sintáctico, y el recorrido del árbol lleva implícito la evaluación en sus nodos del resultado de ejecutar las reglas de traducción.

    Como resultado se obtendrá la traducción a lenguaje objeto de la cadena de elementos léxicos que fue suministrada por el analizador léxico y supervisada en su orden por el sintáctico.

    El concepto de gramática con atributos y la inclusión de las acciones semánticas lleva a que conforme se va haciendo el análisis se vayan evaluando las acciones semánticas. Los analizadores sintácticos y semánticos se implementarán como un único subprograma, imposible de disociar por un programador no experto en el diseño de compiladores.

    Veremos que estas operaciones de traducción son propias de cada nodo del árbol. El comportamiento de la información siempre es el mismo en cada regla.

    PARADIGMA: Los hombres demuestran su grandeza
    por la forma en que tratan a los pequeños...!!! (Thomas Carlyle)

    CONCEPTOS Y TIPOS DE ATRIBUTOS
    Cuando la semántica y la traducción entran en juego, a los árboles de análisis sintáctico se les añade información en cada nodo. Estos árboles reciben el nombre de “árboles con adornos”. Para que esa información pueda viajar atrtavés del árbol hace falta un “almacenes”, que se llaman atributos. Cada símbolo tiene sus propios atributos en los que almacena la información semántica.

    La existencia de atributos para los símbolos de la gramática, conduce al concepto de gramática atribuida. Cada símbolo puede contemplarse como un registro, cada uno de cuyos campos es un atributo distinto:

    A = (A.tipo, A.valor, A.dirección, …)

    Cualquier producción de la gramática tiene asociado un árbol sintáctico:

    Si A --> a1 a2 … an su árbol será: A

    La evaluación de los atributos se realiza mediante operaciones que reciben el nombre de reglas o acciones semánticas. Estas se realizan sobre los valores de los atributos de los símbolos de esa misma regla (sub-árbol):

    A.a = f(a1.ai, a2.ai, …, an.an, A.ai)

    Los atributos mantienen este carácter a lo largo de toda la gramática. Si un atributo es heredado (o sintetizado) debe ser siempre heredado (o sintetizado) en todas las producciones. Si en una regla se le asigna un valor a un atributo heredado de un símbolo, en todas las demás reglas en las que aparezca ese símbolo en la parte derecha se le debe asignar un valor a ese atributo.

    Los atributos de los terminales (tokens) son siempre sintetizados y vienen suministrados por el analizador léxico. Los atributos heredados suelen ser “herramientas para la comunicación” entre diferentes partes del árbol. Sirven a menudo para expresar la dependencia, con respecto al contexto en el que aparece, de una construcción de un lenguaje de programación.

LENGUAJES DE PROGRAMACIÓN:
A S P
Basic
Builder
C++ C#
Delphi
Fox
Haskell
HTML
Java
PHP
Small
UML

PARADIGMA Se conoce el corazón del hombre por lo que hace,
..y su sabiduría, por lo que dice...!!
(Taleb)

LENGUAJES DE PROGRAMACION
Si deseas optar por un lenguaje en particular para codificar tus sistemas de información, convendría que evalues previamente los siguientes aspectos básicos:

  1. CARACTERÍSTICAS de tu PROBLEMA
    En este momento, año 2003..!!!, todos los lenguajes lo hacen prácticamente todo..!!, pero un lenguaje siempre es más apropiado que otro, cuando se va ha operar un determinado tipo de información y proceso.

    Pero, generalmente si tu problema requiere efectuar transacciones:

    • En la WEB, se impone que uses JAVA , HTML y PHP

    • De BASES DE DATOS, te recomiendo comenzar con VISUAL FOX y luego profundizar con SQL.

      Es cierto que puedes operar bases de datos con Visual Basic o Delphi, pero estos, como C++ Builder usan instrumentos intermediarios, tales como los tipo record set, que generan sistemas "más pesados" que insumen más recursos de tu configuración.

    • De soft de APLICACIÓN, resulta efectivo que uses el lenguaje C o C++

    • De soft ENLATADO, te simplifica la vida, si recurres al uso de las poderosos entornos que te ofece C++ Builder o DELPHI y luego continuar con el entorno de Visual Studio Net.

    Ante la duda, nunca olvides, que la mejor regla te aconseja:

    "Un sistema es mejor que otro, cuando hace lo mismo, más rápido y con menores recursos"

    En administración, ademas de la eficiencia, esto mejora la rentabilidad de tu sistema..!!

  2. LOS DATOS
    La elección de un lenguaje adecuado, también pasa por conocer la clase de información de tus transacciones ; por tanto, recuerda que en el mundo algorítmico, los datos debemos entenderlos como la información que deseamos procesar con nuestros programas y que podemos organizarlos así:

    1. DATO SIMPLE
      • NUMERICO
        • Entero
        • Real
          • Decimal
          • Exponencial
      • NO NUMERICO
        • Boleano
        • Caracter

      PARADIGMA: En los ojos del joven arde la llama.
      En los ojos del viejo brilla la luz. ( Víctor Hugo )
    2. DATO ESTRUCTURADO
      • ESTATICO
        • Arreglo
        • Enunciado
        • Cadena
        • Registro
        • Conjunto
      • DINAMICO
        • ARCHIVO
        • PUNTERO
          • Lineal
            • Cola
            • Pila
            • Lista
          • No Lineal
            • Arbol

    PARADIGMA: La ignorancia afirma o niega
    La ciencia duda..!! ( Voltaire )

  3. TIPOS DE PROGRAMACION
    Otro factor más que determinante para que adoptes un lenguaje para que desarrolles tus sistemas es la "Escuela de Programación" de tu corazoncito, que dominas y que por tanto, te resulta familiar.

    De acuerdo a este criterio, por ejemplo, si no dominas la filosofía de la programación orientada a objetos, no podrás optar por el poderoso lenguaje Java.

    En esta introducción solo te enumero las alternativas mas tradicionales. Más adelante, en mis links te desarrollo la teoría paradigmática correspondiente y encontrarás una descripción más detallada.

    1. PROGRAMACION BASADO EN REGLAS:
      De aplicación en la ingeniería del conocimiento para desarrollar sistemas expertos, con núcleo de reglas de producción del tipo if then.

    2. PROGRAMACIÓN LÓGICA:
      Entorno de programación conversacional, deductivo, simbólico y no determinista apoyada en asertos y reglas lógicas.

    3. PROGRAMACIÓN FUNCIONAL:
      Entorno de programación interpretativo, funcional y aplicativo, de formato funcional.

    4. PROGRAMACIÓN HEURÍSTICA:
      Moldean los problemas para aplicar heurísticas según sistemas de visualización, búsqueda y métodos de solución. Pueden ser:

      4.1.-Programación Paralela

      4.2.-Programación Orientado a Objetos

      4.3.-Programación Basado en Restricciones

      4.4.-Programación Basado en Flujo de Datos

  4. CONFIGURACION de tu EQUIPO
    Juega un factor determinante el software de desarrollo con que cuentes y por tanto el hardware que poseas para operar el lenguaje que hayas elegido. Recuerda que trabajo creativo será menos tedioso si tienes frente tuyo "La maquina capaz de procesar el soft de ultima generación".

    Te recomiendo verificar, además del correcto funcionamiento tanto en la edición como en la compilación y la depuración de tus programas; el aspecto legal, especialmente del software de desarrollo. Conviene que seas un combatiente del software apócrifo e ilegal.

    Guiado por estos criterios, en función de las características particulares de tu problema, y de la configuración del equipo que dispones, ahora ya puedes adoptar el lenguaje de programación que más se adecua a tus necesidades particulares.

PARADIGMA: Olvida que eres indispensable
en tu trabajo, tu casa o tu grupo habitual.
Por más que eso te desagrade,
todo camina sin tu actuación,
salvo vos mismo..!! (Wilucha)

Te cuento que mucha de la información que hallarás en mis pages, apenas le encuentres el saborcito, seguramente que te quedará con gusto a poco; por ello, luego para afianzar tus conocimientos, te recomiendo recurrir a la siguiente....

BIBLIOGRAFÍA LIBRO AUTOR EDITORIAL Teoría de autómatas - Hopcroft, Motwani - Adison Wesley Introducción a teoría de autómatas lenguajes - Hopcroft, John E. Jeffrey D. Ullman - CECSA, México Autómatas y Lenguajes Formales - DEAN KELLEY - Prentice Hall Lenguajes, Gramáticas y Autómatas - Pedro ISASI Martinez Borrajo - Adison Wesley Teoría de la Computación - J. G. Brookshear - Addison-Wesley Teoría de Lenguajes,Gramáticas y Autómatas - Alfonseca, Sancho Martínez - Ediciones Unive eBook: Teoría de Autómatas - G. Morales - CINVESTAV-IPN Visual C#.NET - Cristina Sanchez - Edit MACRO Visual C# - Erika Alarcon - Megabyte Programación C++ - Luis Joyanes - Mc Graw Hill C++ Cómo programar - Deitel y Deitel - Prentice Hall Visual C++ - Kate gregory - Prentice Hall Visual C++ - Cris H. Pappas - Mc Graw - Hill Visual C++ Manual - Beck Zaratian - Mc Graw Hill Visual C++ - Holzner - Mc Graw Hill Manual C / C++ - Wiliam H. Murray - Mc Graw Hill Visual C++ - María Cascon Sánchez - Prentice Hall Visual C++ - Ori y Nathan Gurenwich - SAMS Publishing C++ Builder - Fransisco Charte - Anaya Visual FoxPro Manual - Microsoft Corporation - Mc Graw Hill Visual Fox Pro - Pedro Hernandez Muñoz - Mc Graw Hill Delphi - Germán Galeano Gil - Anaya Delphi - Kent Reisdorph - Prentice Hall Delphi - Tom Swan - Anaya Java J++ - Stephen R Davis - Mc Graw Hill Visual J++ - Microsoft Press Visual Basic - Javier Ceballos - RAMA Visual Basic - Microsoft Press Visual Basic - William R. Vaughn - Mc Graw Hill Orientación a Objetos - Carlos Fontela - Nueva Librería

Paradigma
Cultivo una rosa blanca
..en julio, como en enero
para el amigo sincero
que me da su mano franca..!!

Y para el cruel que me arranca
el corazón con que vivo,
cardo ni ortiga cultivo;
..cultivo una rosa blanca..!

José Martí

Facu Sofy Yo..!! Pity Cayo Wilin Wilo

Paradigma: Lo que se hace por amor
está más allá del bién y del mal.! ( Nietzsche )

LENGUAJES FORMALES:
Tipo
Grupo
Copia PDF Lenguaje
Copia PDF Gramatica
Copia PDF Automata
0
G0
Sin restricciones
Irrestricta
Turing
1
G1
Dependiente del contexto
Sensible al contexto
ALA
2
G2
Independiente del contexto
Contexto libre
De Pila
3
G3
Lenguaje regular
Gramatica Regular
Finito

Esta page está en: www.wilocarpio.com.ar - Te espero en: wilocarpio@gmail.com

Volver al principio

20/11/2014