Gramática livre de contexto
A gramática é um formalismo gerador de linguagens livre de contexto.
Essa gramática é composta por um conjunto de regras que geram palavras válidas da linguagem sem depender do “contexto” em que os símbolos aparecem. Em outras palavras, as regras de produção da gramática são aplicadas independentemente de quais símbolos estão ao redor de uma variável.
Formalmente, uma gramática livre de contexto é definida como um quadrupla:
-
: Conjunto de variáveis (ou não-terminais), que são símbolos intermediários usados nas regras. -
: Conjunto de terminais, que são os símbolos finais que aparecem nas palavras da linguagem. -
: Conjunto de regras de produção, onde cada regra tem a forma , com e . -
: Símbolo inicial (uma variável de onde a derivação começa).