Lenguaje libre de contexto
| ||||||
Lenguaje libre de contexto. En Lingüística, Matemáticas e Informática y en la jerarquía de Chomsky se refiere a los lenguajes de tipo 2, aquellos que pueden representarse mediante gramáticas libres de contexto y autómatas finitos.
Son los lenguajes formales que engloban a los lenguajes regulares y constituyen los mecanismos de representación y reconocimiento de los lenguajes de programación desde el punto de vista sintáctico. Por tanto, tienen gran aplicación en la teoría y construcción de intérpretes y compiladores de lenguajes de programación (LP) o de especificación o formato de información, específicamente en el analizador sintáctico o parser que comprueba la corrección de sintaxis en los códigos fuentes de los LP.
Definiciones
Se dice que un lenguaje es libre de contexto (LLC) si y sólo si puede ser reconocido por una gramática libre de contexto (GLC) G=<N,T,P,S>, donde N es el conjunto de los símbolos no terminales o derivables, T es el conjunto de los símbolos terminales o alfabeto; P, la colección de producciones de la forma 
, donde A es un no terminal de N y 
; S es el símbolo inicial.
Un lenguaje libre de contexto (LLC) L es aquel cuyas cadenas pueden ser reconocidas por autómatas de pila.
Ejemplos
Uno de los casos más sencillos de los LLC son las del pareamiento de paréntesis y que puede modelarse con la gramática LLC 
.
Este caso de "matching" de paréntesis (y de otros signos de agrupación) es muy socorrido en las expresiones aritméticas o de otra naturaleza dentro de los LPs, por ejemplo este caso de una GLC que define una asignación a una variable representada por su identificador de una expresión aritmética típica de Python:
G=<{S,E, L},{num, id, (, ), +, -, *, /, //, %, =, **}, P, S>; donde el sistema de producciones P se define:
S => id = E
E => id(L)
E => (E)
E => E**E
E => +E | -E
E => E*E | E/E | E//E | E % E |
E => E+E | E-E
E => id | num
L => E | E,L
Como puede verse se ha incluido el llamado a funciones y una especie de orden de precedencia operacional que desde el punto de vista sintáctico no tiene por qué cumplirse pero se ha definido así con el objetivo de ilustrar el aspecto de la precedencia de las operaciones aritméticas en los LP, hecho que es soportado por generadores automáticos de analiadores sintácticos como el Yacc.
Consecuencias
- Un LLC puede ser también modelado como un conjunto de todas las secuencias de terminales aceptadas por la GLC equivalente.
- La unión y concatenación de dos LLC es también otro LLC.
- La intersección de dos LLC no necesariamente es un LLC.
- El inverso de un LLC es también LLC.
- El complemento de un LLC no tiene por que ser libre de contexto.
- Los lenguajes regulares son libres de contexto al poder ser descritos mediante GLC.
- Las producciones de una gramática regular tienen la forma
donde 
- Las producciones de una gramática regular tienen la forma
- La intersección de un lenguaje libre de contexto y un lenguaje regular es siempre libre de contexto.
- Existen gramáticas dependientes del contexto (GDC) que no son libres de contexto, aunque todas las GLC son GDC.
- Para demostrar que un lenguaje dado no es libre de contexto, se puede emplear el Lema del bombeo para lenguajes libres de contexto.
- El problema de determinar si una gramática sensible al contexto describe un lenguaje libre del contexto es indecidible.
Importancia
Los LLC tienen vital importancia en el diseño e implementación de lenguajes de programación pues sus implementaciones informáticas suelen constituir los núcleos de los parsers o analizadores sintácticos y son parte del análisis semántico.
Subconjuntos de los LLC como los LL(k) y los LR(k) sirven para la automatización del proceso de desarrollo de párseres y existen herramientas consolidadas como el Yacc, Bison, COCO/R, entre otras que favorecen el trabajo de los desarrolladores de LP; aunque suele exigirse que las gramáticas hayan sido reducidas a esas formas.
También los LLC son la base de programas que sirven para traducir el código fuente de un LP a otro o en las herramientas de modelación de la ingeniería de software como el Rational Rose que también transforma los diagramas de entidades en fuentes de distintos LPs según desee el desarrollador.
Véase también
Fuentes
- Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
- Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la Universidad de Oriente. Santiago de Cuba, 2000.
- GLC en Wikipedia. Consultado el 30 de noviembre de 2013.
- Acevedo Martínez, Liesner; Osorio Ramírez, Karel. Manual de apoyo a la docencia. Técnicas de Compilación: Manual Práctico para estudiantes de Informática. Libro electrónico en PDF. UCI. La Habana, 2011.
