Gramática livre de contexto determinística

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


Question book.svg
Este artigo não cita fontes confiáveis e independentes. (desde abril de 2013). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
Wikitext.svg
Este artigo ou seção precisa ser wikificado (desde abril de 2013).
Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.

Na teoria da gramática formal, as gramáticas livres de contexto determinísticas (GLCD) são um subconjunto das gramáticas livres de contexto. Elas podem ser derivadas a partir de autômatos com pilha determinísticos, que geram as linguagens livres de contexto determinísticas.

História[editar | editar código-fonte]

Na década de 1960, a pesquisa teórica em ciência da computação em expressões regulares e autômatos finitos levou à descoberta de que as gramáticas livres de contexto são equivalentes a autômatos com pilhas não determinísticos. Estas gramáticas foram concebidas para capturar a sintaxe das linguagens de programação. As primeiras linguagens de programação estavam em desenvolvimento na época e escrever compiladores era uma tarefa difícil. Mas o uso de gramáticas livres de contexto para ajudar a automatizar a parte de análise do compilador simplificou a tarefa. Gramáticas livres de contexto determinísticas foram particularmente úteis, porque elas poderiam ser analisadas seqüencialmente por um autômato com pilha determinístico, o que era uma exigência devido a restrições de memória de computador. Em 1965, Donald Knuth inventou o analisador sintático LR(k) e provou que existe uma gramática LR(k) para cada linguagem livre de contexto determinística. Este analisador sintático ainda necessitou de uma grande quantidade de memória. Em 1969, Frank DeRemer inventou o LALR um analisador sintático simples LR, ambos baseados no LR e os requisitos de memória foram muito reduzidos. O analisador LALR foi a alternativa mais poderosa. Estes dois analisadores já foram amplamente utilizadas em compiladores de várias linguagens de programação.