Linguagens Formais E Aut Matos Unidade II

Unidade II

Unidade II
5 LINGUAGENS LIVRES DE CONTEXTO – Parte 1

As Linguagens Livres de Contexto são geradas por Gramáticas Livres de Contexto.
A Gramática Livre de Contexto foi definida por Chomsky (1956). Trata-se de um dispositivo mais poderoso que aquele das Linguagens Regulares, visto que apresenta regras que permitem expressar como os elementos de uma forma sentencial se organizam em grupos hierárquicos complexos.
De fato, considere o seguinte exemplo:
A limpava menina casa a vassoura uma com.
Trata-se de uma sentença não gramatical, dado que os seus elementos constituintes não estão agrupados corretamente.
A organização adequada dos elementos da frase é apresentada no quadro a seguir. a menina limpava a casa com uma vassoura a menina a menina

limpava a casa com uma vassoura limpava a a casa casa com uma vassoura com uma vassoura uma vassoura

Figura 29

As Gramáticas Livres de Contexto representam um importante formalismo para o processamento das linguagens naturais, bem como das artificiais, em particular das linguagens de programação.
O estudo das Linguagens Livres de Contexto é aplicado no projeto e na implementação do analisador sintático, módulo funcional do compilador.
Exemplo: apresenta-se uma Gramática Livre de Contexto para uma pequena linguagem de programação (SEBESTA, 2003).
G = (V, S, P, <programa>), onde:
V = {<programa>, <lista_inst>, <inst>, <comando>, <var>, <expressão>}
54

Linguagens Formais e Autômatos
S = {A, B, C, +, -, begin, end}
<programa> é o símbolo inicial
P = {<programa> → begin <lista_inst> end
<lista_inst> → <inst> | <commando>; <lista_inst>
<inst> → <var> = <expressão>
<var> → A | B | C
<expressão> → <var> + <var> | <var> - <var> | <var>
5.1 Gramática Livre de Contexto: dispositivo gerador de uma Linguagem
Livre de Contexto

Seja G = (V, S, P, S). Diz-se que G é livre de contexto, se as produções apresentarem o seguinte padrão:
A→ b, onde: A∈ V e b∈ (V ∪ T)*
A expressão acima indica que no lado esquerdo da produção