Gramática livre de contexto determinística

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

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.