Los Lenguajes Independientes del contexto (También llamados Lenguajes Incontextuales, Lenguajes libres de contexto o Lenguajes Insensibles al contexto) es un tipo de lenguaje formal, que están un grado más arriba en la jerarquía de Chomsky, por encima de los lenguajes regulares.
Sus palabras son generadas por las gramáticas independientes del contexto (o gramáticas de tipo2) y las palabras son reconocidas por los autómatas de pila los cuales son un autómata finito que poseen una memoria auxiliar llamada pila.
La relación de los Lenguajes Independientes del Contexto con los lenguajes de programación está en expresiones aritméticas y cómo se forman las sentencias de programación. Es decir, que de alguna forma la importancia está en el orden de los lexemas provistos por el lexer.
Dentro de un compilar tenemos a el analizador léxico gráfico, el analizador sintáctico y otras fases del compilador. El analizador léxico gráfico va a ser quien le va a dar al analizador sintáctico los lexemas y los tokens que han sido matcheados contra el patrón de la expresión regular. El analizador sintáctico tiene la gramática independiente del contexto y con esta, va a ver si cada uno de los lexemas y los tokens provistos por el analizador léxico gráfico llevan ese orden guiado u orientados por la gramática independiente del contexto.
La relación entre los lenguajes de programación y los lenguajes independientes del contexto se encuentra en el proceso de compilación. Un compilador es un programa que traduce el código fuente escrito en un lenguaje de programación específico a un código ejecutable por la computadora. En el proceso de compilación, el analizador léxico es el encargado de reconocer los lexemas, que son los componentes básicos del lenguaje de programación, como palabras clave, identificadores, operadores y constantes. El analizador léxico utiliza expresiones regulares para identificar y agrupar los lexemas en tokens. A continuación, los tokens generados por el analizador léxico se pasan al analizador sintáctico. El analizador sintáctico utiliza una gramática independiente del contexto para verificar si los tokens están organizados de acuerdo con las reglas sintácticas del lenguaje de programación. La gramática independiente del contexto define la estructura y las reglas de formación de las sentencias de programación válidas. -GPT
Siguen formadas por la cuádrupla de una gramática formal:
Estructura de una GIC
Dado el siguiente lenguaje: L = {$a^n b^n / n ≥ 1$}
Podemos formar las palabras que contienen ‘a’ y ‘b’ en la misma cantidad: L = {ab, aabb, aaabbb, aaaabbbb, …};