Gramáticas livres de contexto

Tradicionalmente, gramáticas livres de contexto têm sido utilizadas para realizar a análise sintática de linguagens de programação. Nem sempre é possível representar neste tipo de gramática restrições necessárias a algumas linguagens -- por exemplo, exigir que todas as variáveis estejam declaradas antes de seu uso ou verificar se os tipos envolvidos em uma expressão são compatíveis. Entretanto, há mecanismos que podem ser incorporados às ações durante a análise -- por exemplo, interações com tabelas de símbolos -- que permitem complementar a funcionalidade da análise sintática.

A principal propriedade que distingüe uma gramática livre de contexto de uma gramática regular é a auto-incorporação. Uma gramática livre de contexto que não contenha auto-incorporação pode ser convertida em uma gramática regular.

Auto-incorporação é definida como se segue. Se uma gramática $G$ tiver um símbolo não-terminal $A$ para o qual

$$A \overset{\ast}{\underset{G}{\Longrightarrow}} \alpha_1 A \alpha_2$$

onde $\alpha_1$ e $\alpha_2$ são strings não vazias de símbolos terminais e/ou não-terminais, então diz-se que a gramática tem a propriedade da auto-incorporação. Esse tipo de regra é necessário para expressar sentenças com parênteses, colchetes ou delimitadores de blocos balanceados.