Lenguajes Independientes del Contexto y Autómatas de Pila

Las gramáticas independientes del contexto generan lenguajes con una estructura anidada y recursiva, y los autómatas de pila reconocen exactamente estos lenguajes al aumentar un control finito con una pila ilimitada.

Definition

Un lenguaje independiente del contexto es generado por una gramática cuyas reglas reescriben un único símbolo no terminal independientemente del contexto, y es reconocido por un autómata de pila, un autómata finito equipado con una pila que proporciona memoria de tipo último en entrar, primero en salir (LIFO) de profundidad ilimitada.

Scope

Este tema abarca las gramáticas independientes del contexto y sus derivaciones, los árboles de análisis sintáctico y la ambigüedad, la equivalencia de las gramáticas independientes del contexto con los autómatas de pila, las formas normales como la forma normal de Chomsky, el lema de bombeo para lenguajes independientes del contexto, y las propiedades de cierre y decisión que distinguen esta clase de los lenguajes regulares.

Core questions

• ¿Qué tipos de patrones anidados o recursivos requieren una pila en lugar de memoria finita?
• ¿Por qué las gramáticas independientes del contexto y los autómatas de pila son equivalentes en potencia?
• ¿Cuándo es ambigua una gramática y por qué la ambigüedad es importante para el análisis sintáctico?
• ¿Qué problemas de decisión para los lenguajes independientes del contexto son resolubles y cuáles no?

Key theories

Equivalencia entre gramática y autómata

Un lenguaje es independiente del contexto si y solo si es aceptado por algún autómata de pila, por lo que la visión de la gramática generativa y la visión de la máquina de pila describen la misma clase de lenguajes.

Forma normal de Chomsky

Toda gramática independiente del contexto puede reescribirse de modo que cada regla produzca dos no terminales o un único terminal, una forma normal que subyace a los algoritmos de análisis sintáctico y a las pruebas inductivas sobre la clase.

Lema de bombeo para lenguajes independientes del contexto

Toda cadena suficientemente larga en un lenguaje independiente del contexto puede dividirse de modo que dos de sus partes se bombeen juntas, una propiedad que no se cumple para los lenguajes que requieren más que memoria de pila y, por lo tanto, demuestra que no son independientes del contexto.

Clinical relevance

Las gramáticas independientes del contexto especifican la sintaxis de casi todos los lenguajes de programación y muchos formatos de datos, y los algoritmos de análisis sintáctico de tipo pila convierten estas gramáticas en los analizadores sintácticos que son el corazón de los compiladores e intérpretes, lo que convierte a este tema en el fundamento teórico del procesamiento de lenguajes de programación.

History

Chomsky introdujo las gramáticas independientes del contexto a finales de la década de 1950 como parte de su jerarquía, y fueron utilizadas independientemente por Backus y Naur para definir la sintaxis del lenguaje de programación ALGOL. La equivalencia con los autómatas de pila y la teoría estructural de la clase se desarrollaron a lo largo de la década de 1960.

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

¿Por qué el análisis sintáctico de un lenguaje de programación necesita una pila?

Los programas contienen construcciones anidadas como paréntesis, bloques y llamadas a funciones cuya profundidad de emparejamiento es ilimitada. Una pila registra cada construcción inacabada y la extrae cuando se cierra, lo cual es exactamente la disciplina de memoria que proporciona un autómata de pila y de la que carece un autómata finito.

¿Qué significa que una gramática sea ambigua?

Una gramática es ambigua cuando alguna cadena tiene más de un árbol de análisis sintáctico, lo que significa que puede derivarse con estructuras genuinamente diferentes. La ambigüedad es indeseable para los lenguajes de programación porque deja el significado del código poco claro, por lo que los diseñadores de lenguajes buscan gramáticas no ambiguas o añaden reglas de desambiguación.