Linguagens Livres de Contexto e Autômatos de Pilha

Gramáticas livres de contexto geram linguagens com estrutura aninhada e recursiva, e autômatos de pilha reconhecem exatamente essas linguagens ao aumentar um controle finito com uma pilha ilimitada.

Definition

Uma linguagem livre de contexto é gerada por uma gramática cujas regras reescrevem um único símbolo não-terminal independentemente do contexto, e é reconhecida por um autômato de pilha, um autômato finito equipado com uma pilha que fornece memória last-in, first-out de profundidade ilimitada.

Scope

Este tópico abrange gramáticas livres de contexto e derivações, árvores de análise sintática e ambiguidade, a equivalência de gramáticas livres de contexto com autômatos de pilha, formas normais como a forma normal de Chomsky, o lema do bombeamento para linguagens livres de contexto, e as propriedades de fechamento e decisão que distinguem esta classe das linguagens regulares.

Core questions

• Que tipos de padrões aninhados ou recursivos exigem uma pilha em vez de memória finita?
• Por que as gramáticas livres de contexto e os autômatos de pilha são equivalentes em poder?
• Quando uma gramática é ambígua e por que a ambiguidade é importante para a análise sintática?
• Quais problemas de decisão para linguagens livres de contexto são solúveis e quais não são?

Key theories

Equivalência gramática–autômato

Uma linguagem é livre de contexto se e somente se for aceita por algum autômato de pilha, de modo que a visão de gramática gerativa e a visão de máquina de pilha descrevem a mesma classe de linguagens.

Forma normal de Chomsky

Toda gramática livre de contexto pode ser reescrita de modo que cada regra produza dois não-terminais ou um único terminal, uma forma normal que fundamenta algoritmos de análise sintática e provas indutivas sobre a classe.

Lema do bombeamento para linguagens livres de contexto

Toda string suficientemente longa em uma linguagem livre de contexto pode ser dividida de modo que duas de suas partes sejam 'bombeadas' juntas, uma propriedade que falha para linguagens que exigem mais do que memória de pilha e, portanto, as prova como não-livres de contexto.

Clinical relevance

Gramáticas livres de contexto especificam a sintaxe de quase todas as linguagens de programação e muitos formatos de dados, e algoritmos de análise sintática do tipo pushdown transformam essas gramáticas nos analisadores sintáticos no cerne de compiladores e interpretadores, tornando este tópico o fundamento teórico do processamento de linguagens de programação.

History

Chomsky introduziu as gramáticas livres de contexto no final da década de 1950 como parte de sua hierarquia, e elas foram usadas independentemente por Backus e Naur para definir a sintaxe da linguagem de programação ALGOL. A equivalência com autômatos de pilha e a teoria estrutural da classe foram desenvolvidas ao longo da década de 1960.

Key figures

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

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

Por que a análise sintática de uma linguagem de programação precisa de uma pilha?

Programas contêm construções aninhadas, como parênteses, blocos e chamadas de função, cuja profundidade de correspondência é ilimitada. Uma pilha registra cada construção inacabada e a remove quando fechada, o que é exatamente a disciplina de memória que um autômato de pilha fornece e um autômato finito não possui.

O que significa uma gramática ser ambígua?

Uma gramática é ambígua quando alguma string possui mais de uma árvore de análise sintática, o que significa que pode ser derivada com estruturas genuinamente diferentes. A ambiguidade é indesejável para linguagens de programação porque deixa o significado do código incerto, então os designers de linguagem buscam gramáticas não ambíguas ou adicionam regras de desambiguação.