Javiermartin jc: Texto reemplazado: «
» por «»

2019-07-06T20:48:10Z

Texto reemplazado: «<div align="justify">» por «»

Carlos idict en 13:07 23 dic 2013

2013-12-23T13:07:35Z

Jhonlier12017 jc.hlg: Página creada con '{{Definición|nombre=Lenguaje libre de contexto|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la jerarquía de Chomsky son los lenguajes de tipo 2, reconocibles con [[autó...'

2013-12-01T17:16:28Z

Página creada con '{{Definición|nombre=Lenguaje libre de contexto|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la jerarquía de Chomsky son los lenguajes de tipo 2, reconocibles con [[autó...'

Página nueva

{{Definición|nombre=Lenguaje libre de contexto|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la [[jerarquía de Chomsky]] son los lenguajes de tipo 2, reconocibles con [[autómata de pila|autómatas de pila]].}}
<div align="justify">
'''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ática libre de contexto|gramáticas libres de contexto]] y [[Autómata de pila|autómatas finitos]].

Son los [[Lenguaje formal|lenguajes formales]] que engloban a los [[lenguaje regular|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érprete|intérpretes]] y [[Compilador|compiladores]] de [[Lenguaje de programacion|lenguajes de programación]] (LP) o de [[Lenguaje de especifcación|especificación]] o [[Lenguaje de formato|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 [[Archivo:LLC_A_produce_x.gif|middle]], donde ''A'' es un no terminal de ''N'' y [[Archivo:LLC_x_pertenece_N_U_T_U_Xi_Clausura.gif|middle]]; ''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.

[[Archivo:Jerarquia_Chomsky.gif|center|Ubicación de los LLC en la Jerarquía de Chomsky]]

==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 [[Archivo:GLC_Pareamiento_Parentesis.gif|middle]].

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]]:

<pre>
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
</pre>

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 [[Archivo:LLC_A_produce_x.gif|middle]] donde [[Archivo:X_pertenece_T_union_Chi_concat_N_union_Chi.gif|middle]]
* 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==
* [[Gramática regular]].
* [[Jerarquía de Chomsky]].

==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|Departamento de Ciencias de la Computación]] de la [[Universidad de Oriente]]. [[Santiago de Cuba]], [[2000]].
# [http://es.wikipedia.org/wiki/Gramática_libre_de_contexto 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]].
</div>
[[Categoría:Lingüística]][[Categoría:Matemáticas]][[Categoría:Informática]]

@@ Línea 1: / Línea 1: @@
 {{Definición|nombre=Lenguaje libre de contexto|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la [[jerarquía de Chomsky]] son los lenguajes de tipo 2, reconocibles con [[autómata de pila|autómatas de pila]].}}
-<div align="justify">
 '''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ática libre de contexto|gramáticas libres de contexto]] y [[Autómata de pila|autómatas finitos]].

@@ Línea 58: / Línea 58: @@
 ==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|Departamento de Ciencias de la Computación]] de la [[Universidad de Oriente]]. [[Santiago de Cuba]], [[2000]].
+# Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la [[Universidad de Oriente]]. [[Santiago de Cuba]], [[2000]].
 # [http://es.wikipedia.org/wiki/Gramática_libre_de_contexto 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]].
 </div>
 [[Categoría:Lingüística]][[Categoría:Matemáticas]][[Categoría:Informática]]

Lenguaje libre de contexto - Historial de revisiones

Javiermartin jc: Texto reemplazado: «» por «»

Carlos idict en 13:07 23 dic 2013

Jhonlier12017 jc.hlg: Página creada con '{{Definición|nombre=Lenguaje libre de contexto|imagen=Jerarquia_Chomsky_A.gif|concepto=Según la jerarquía de Chomsky son los lenguajes de tipo 2, reconocibles con [[autó...'

Javiermartin jc: Texto reemplazado: «
» por «»