Capítulo 2.
Linguagens formais
1. Conceitos básicos e notações
Definição : Um alfabeto, ou vocabulário, geralmente representado por V, é um conjunto finito de
símbolos ou caracteres. Os símbolos do alfabeto são designados por palavras.
Exemplos :
a) conjunto de palavras da língua portuguesa listados num dicionário;
b) conjunto V = { 0, 1 } que constitui o alfabeto binário.
Definição : Uma sequência finita de palavras de um dado alfabeto chama-se frase (“string”) desse
alfabeto.
Definição : O conjunto de todas as frases de um alfabeto V denota-se por V*.
Definição : O comprimento de uma frase α é o número de palavras que a frase contém e é
representado por |α|. A frase nula tem comprimento zero e é representada por ε. Logo, |ε| = 0.
Definição : A concatenação da frase α com a frase β, denominada por αβ, é uma frase formada pelas
palavras de α seguida pelas palavras de β.
A concatenação da frase α com ela própria n vezes, αα…α, é representada por αn. A operação
de concatenação goza das seguintes propriedades :
• ε constitui o elemento neutro da concatenação : para qualquer frase α, α ε = ε α = α
• a concatenação é associativa : para quaisquer frases α, β e δ, (α β) δ = α (β δ).
Definição : Dadas duas frases quaisquer, α e β, α é prefixo da frase αβ e β é sufixo da frase αβ. Uma
subfrase é formada retirando um prefixo e um sufixo de uma dada frase.
Definição : Uma linguagem L sobre um alfabeto V, é um conjunto de frases, em que cada frase é
composta por palavras pertencentes ao alfabeto V.
Uma linguagem não admite todas as combinações possíveis de palavras do seu alfabeto; apenas
certas combinações é que dão origem a frases válidas  ou seja, L ⊆ V*. Normalmente, a linguagem é
um conjunto infinito, o que torna a sua enumeração impossível.
Definição : Denomina-se por sintaxe de uma linguagem L sobre o alfabeto V, o conjunto de regras
que delimita o subconjunto V* constituinte da linguagem.
10
Gramáticas e linguagens
Exemplos :
• ∅ é uma linguagem vazia
• { ε } é uma linguagem formada pela frase nula
• { 0 } é uma linguagem formada por uma única frase, no alfabeto binário V = { 0, 1 }
• { 00, 01, 10, 11 } é a linguagem formada pelas frases de comprimento 2, no alfabeto binário V = { 0, 1 }
• conjunto de todos os programas em Pascal sintacticamente bem formados
• conjunto de todas as frases gramaticalmente correctas da língua portuguesa
A representação das frases de uma linguagem pode ser efectuada por duas formas :
1. Extensiva, em que são listadas todas as frases da linguagem
2. Predicativa, segundo uma fórmula baseada em linguagens previamente definidas. A forma
predicativa tem o seguinte formato :
{ fórmula sobre frases genérica | Predicado },
em que o predicado restringe as frases indicadas pela fórmula declarada à esquerda.
Exemplo :
{ an | n é par } é uma representação predicativa de uma linguagem baseada na linguagem { a }. Ou seja, de
todas as frases formadas por sequências de a, apenas são admitidas aquelas que têm comprimento par.
2. Gramáticas e linguagens
2.1. Definição de gramática geradora
Definição : Uma gramática geradora é todo o quádruplo ordenado G = (Σ, T, P, S), em que
• Σ é um conjunto finito, não vazio, de símbolos não-terminais ou variáveis;
• T é um conjunto finito, não vazio, de símbolos terminais;
• S ∈ Σ é designado por símbolo inicial;
• P ⊆ (Σ ∪ T)+ × (Σ ∪ T)* é um conjunto de regras sintácticas, ou de rescrita, também
designadas por produções ou derivações.
O conjunto V = Σ ∪ T constitui o vocabulário completo.
Normalmente, cada par em P é representado na forma X → α, no qual X ∈ (Σ ∪ T)+ e
α ∈ (Σ ∪ T)*, para representar que (X, σ) é um elemento de P. X e α são designados, respectivamente,
por lado esquerdo e lado direito da produção, e a produção lê-se X deriva (imediatamente) em α.
Duas produções com igualdade do primeiro membro do par, (Σ ∪ T)+, são frequentemente
designadas por alternativas.
É frequente as gramáticas serem descritas numa notação designada por BNF − Backus Naur
Form − que consiste no seguinte :
1. Os símbolos terminais são escritos em letras minúsculas, por vezes a carregado.
2. Os símbolos não-terminais são iniciados por uma letra maiúscula.
3. Numa produção, os lados esquerdo e direito são separados pelo símbolo → ou pelo símbolo ::=.
4. Produções alternativas, X → α1, X → α2, …, X → αn, são representadas por X → α1|α2|…|αn .
5. Se o lado direito de uma produção X → α não contém qualquer símbolo, então escreve-se X → ε.
Por vezes, as regras 1 e 2 são substituídas pela seguinte regra única : os símbolos não-terminais
são delimitados pelos símbolos < e >.
Linguagens formais
Gramáticas e linguagens
11
2.2. Grafos de sintaxe
As regras sintácticas de uma gramática podem ser representadas, graficamente, por forma a
incrementar a sua legibilidade.
Os grafos de sintaxe são construídos a partir da representação BNF de uma gramática com base
nas cinco regras descritas a seguir.
1. Símbolos terminais α são representados por círculos :
α
2. Símbolos não-terminais X são representados por caixas :
X
3. Produções na forma X → α1 α2 … αn são representadas pelo grafo :
X
α1
α2
…
αn
4. Produções na forma X → α1|α2| … |αn são representadas pelo grafo :
α1
α2
X
…
αn
5. Produções na forma X → { α } são representadas pelo grafo :
X
α
Por exemplo, dada a gramática,
S → Sa|Bc
a sua representação gráfica é a seguinte :
B → ε|bB
S
a
S
c
b
A representação gráfica é obtida por aplicação mecânica das regras de geração do grafo. Por vezes, há necessidade
de deslocar alguns elementos gráficos, por forma a evitar o cruzamento de linhas.
2.3. Derivação de frases
Informalmente, uma frase pertence a uma linguagem definida por uma determinada gramática,
se for possível executar, com sucesso, o seguinte algoritmo :
1. Começar pelo símbolo inicial da gramática.
2. Substituir sucessivamente os símbolos não-terminais pelo lado direito de produções que
contenham no lado esquerdo o símbolo seleccionado.
3. O processo termina quando se atingir a frase a detectar.
O processo de substituição de símbolos não-terminais denomina-se derivação. Podem definir-se dois
processos de derivação (definições seguintes).
Linguagens formais
12
Gramáticas e linguagens
Definição : Dada uma gramática G = (Σ, T, P, S) e dois símbolos gramaticais, X, Y ∈ (Σ ∪ T)+, diz-se
que Y deriva de X por uma derivação de um só passo e escreve-se
X ⇒ Y
G
se existirem símbolos gramaticais p1 e p2 em (Σ ∪ T)* e uma produção P → Q tal que
X = p1 P p2
e
Y = p1 Q p2
Definição : Se p1, p2, …, pm ∈ (Σ ∪ T)*, m ≥ 1, verificarem
p 1 ⇒ p 2 , p 2 ⇒ p 3 , ..., p m − 1 ⇒ p m
G
escreve-se
G
G
∗
p1 ⇒ pm
G
e diz-se que pm deriva de p1 na gramática G.
2.4. Linguagem gerada por uma gramática
Definição : A linguagem gerada pela gramática G contém todas as frases derivadas a partir do
símbolo inicial S que contenham somente símbolos terminais (caracteres),
∗
∗
G
G
L(G) = { p : S ⇒ p com p ∈ T* } = { p : S ⇒ p } ∩ T*
Os símbolos não-terminais são auxiliares nas derivações dos elementos de uma linguagem.
Repare que pela definição da relação em P, para a existência de uma produção é necessário que o
elemento da esquerda contenha um símbolo não-terminal. Uma derivação colapsa se existindo no
elemento da esquerda símbolos não-terminais não existem produções que possam ser aplicadas.
Logo, uma frase está na linguagem L(G) se e só se
(i) for constituída somente por elementos terminais;
(ii) for obtida por derivação a partir de S.
Exemplos :
1. Consideremos a gramática G = (Σ, T, P, S) onde
Σ={S}
T = { a, b }
P={S→aSb, S→ab}
isto é, S (símbolo inicial) é o único símbolo não-terminal, a e b são símbolos terminais, existindo
apenas as duas produções apresentadas.
O nosso objectivo é determinar a linguagem gerada pela gramática G, L(G).
(i) Ao aplicar-se a primeira produção (n−1)-vezes seguida pela aplicação uma vez da 2ª
produção, tem-se :
S ⇒ a S b ⇒ a a S b b ⇒ a3 S b3 ⇒ … ⇒ an-1 S bn-1 ⇒ an bn .
(ii) Repare-se agora que sempre que se faz uso da primeira produção, o número de S’s
mantém-se. Na utilização da segunda produção, o número de S’s decresce de uma
unidade. Logo, a utilização da segunda produção elimina os S’s na sequência resultante.
Como ambas as produções têm um único S à esquerda, a ordem pela qual as produções
podem ser aplicadas é S → a b, isto é, (i). Logo, L(G) = { an bn : n ≥ 1 }
NOTA :
Neste exemplo foi muito simples determinar que frases foram derivadas de S, assim como o
único tipo de frases derivadas de S. No entanto, geralmente, é difícil determinar a linguagem
gerada por uma dada gramática.
Linguagens formais
Gramáticas e linguagens
13
2. Consideremos a gramática geradora G = (Σ, T, P, S) onde
Σ = { S, A, B }
T = { a, b }
contendo as seguintes produções
S → aB
S → bA
A → bAA
A → a
A → aS
B → b
B → bS
B → aBB
Prova-se por indução que L(G) é o conjunto de frases em T* contendo um número igual de a’s e
de b’s :
L(G) = { σ ∈ T + : na (σ) = nb (σ) }
onde na (σ) representa o número de a’s que aparecem em σ ∈ T*.
3. Consideremos a gramática geradora G = (Σ, T, P, S) onde
Σ = { S, X, Y }
T = { a, b, c }
contendo as seguintes produções
S → abc
Xc → Ybcc
aY → aaX
S → aXbc
Xb → bX
bY → Yb
Prova-se que L(G) = { an bn cn : n = 1, 2, 3, … }
aY → aa
Definição : Uma derivação diz-se efectuada pela esquerda (“leftmost”), se em cada passo é
substituído o símbolo não-terminal situado mais à esquerda.
Definição : Uma derivação diz-se efectuada pela direita (“rightmost”), se em cada passo é
substituído o símbolo não-terminal situado mais à direita.
2.5. Derivação de formas sentenciais
O processo de derivação inicia-se no símbolo inicial da gramática e termina na frase. No meio
do processo, são obtidas sequências de símbolos terminais e não-terminais, as quais são designadas
por formas sentenciais.
Definição : Dada uma gramática G = (Σ, T, P, S), uma forma sentencial é uma sequência de símbolos
∗
∗
terminais e não-terminais, α, tal que existe uma frase s ∈ L(G) e existem 2 derivações S ⇒ α ⇒ s
2.6. Reconhecimento de uma frase
A operação inversa da derivação é o reconhecimento. Informalmente, um reconhecimento verifica
se uma sequência de palavras (frase) faz parte, ou não, da linguagem.
Definição : Seja L ⊆ T* uma linguagem. Um reconhecimento RL é um algoritmo que
aceita ⇐ s ∈ L
R L (s) = 
rejeita ⇐ s ∉ L
O reconhecimento não tem por objectivo apresentar a sequência de derivação da frase s, mas
apenas indicar se ela existe ou não.
2.7. Símbolos anuláveis e símbolos inúteis
Os símbolos não-terminais podem ser desnecessários em todas as derivações de frases da
linguagem, isto é, a partir do símbolo consegue-se derivar a frase nula. Neste caso, diz-se que os
símbolos são anuláveis.
Linguagens formais
14
Gramáticas e linguagens
Definição : Um símbolo não terminal A ∈ Σ diz-se anulável se existir uma produção A → ε.
Definição : Um símbolo não-terminal diz-se inútil ou não-necessário se :
a) não existir uma derivação de uma frase a partir dela;
b) quando não apareça em qualquer forma sentencial derivada com inicio no símbolo inicial.
No primeiro caso diz-se que a variável é inactiva ou morta. No segundo caso diz-se que é uma
variável inatingível.
Definição : Uma variável numa gramática G diz-se activa se pelo menos uma frase terminal for
originada a partir dela. Uma variável diz-se atingível se ocorrer em, pelo menos, uma forma
setencial derivada a partir do símbolo inicial da gramática.
2.8. Árvores de derivação
Uma árvore de derivação não é mais do que uma representação gráfica, em forma de árvore, da
sequência de derivação. Numa árvore de derivação, os nós interiores estão associados a símbolos nãoterminais e as folhas associadas a símbolos terminais.
Definição : Seja N um conjunto não-vazio. Chamaremos vértices aos elementos de N. O conjunto de
arestas, E, é todo o subconjunto E ⊆ N×N. Para cada aresta e = (n1, n2) ∈ E, s(e) = n1, t(e) = n2
dizem-se, respectivamente, o vértice inicial e o vértice terminal de e. Uma sucessão de arestas
e0, e1, …, ek diz-se um caminho orientado de comprimento k de s(e0) a t(ek) se s(ei+1) = t(ei) para
i = 0, 1, …, k-1. Um par ordenado (N, E) diz-se uma árvore orientada se existir um vértice r ∈ N
tal que
1) nenhum dos vértices terminais em E coincide com r;
2) existe um único caminho orientado a partir de r para qualquer outro vértice em N.
O vértice r diz-se a raiz da árvore. Pela própria definição, cada árvore admite uma única raiz.
Cada vértice da árvore é a raiz de uma sub-árvore. Vértices terminais que não sejam vértices iniciais
de uma aresta dizem-se folhas.
2.9. Recursividade
Definição : Uma gramática G = (Σ, T, P, S) diz-se recursiva à esquerda (à direita) se existirem A ∈ Σ
∗
∗
e a ∈ L(G), tal que existe uma derivação A ⇒ A a ( A ⇒ a A )
2.10. Hierarquia de Chomsky
2.10.1. Classificação de linguagens segundo Chomsky
Cada gramática gera uma única linguagem, mas a mesma linguagem pode ser gerada por
várias gramáticas.
Definição : Duas gramáticas dizem-se equivalentes se gerarem a mesma linguagem.
Apresenta-se em seguida uma classificação das linguagens de acordo com o tipo de produções
que contenham, devido a Chomsky.
Linguagens formais
Gramáticas e linguagens
15
Definição : Uma gramática geradora diz-se do tipo i se satisfazer as seguintes restrições :
i=0
se nenhuma restrição for imposta.
i=1
se toda a produção tiver a forma Q1 A Q2 → Q1 α Q2 para Q1, Q2, α ∈ V*, A ∈ Σ, onde α
i=2
i=3
não pode ser a frase vazia, Λ, excepto no caso em que o símbolo inicial não apareça no
lado direito das regras, caso esse em que se permite a presença da produção S → Λ.
toda a produção é da forma A → α para A ∈ Σ e α ∈ V*.
toda a regra em G é da forma A → αB e A → X, com A, B ∈ Σ, α ∈ T*.
Uma linguagem diz-se do tipo i se for gerada por uma gramática do tipo i. Representa-se por Li
a classe das linguagens do tipo i.
Gramáticas do tipo 0 dizem-se gramáticas com estrutura de frase.
Gramáticas do tipo 1 são chamadas gramáticas sensíveis ao contexto, porque as respectivas
regras só permitem a substituição da ocorrência de um símbolo não-terminal no contexto Q1, Q2.
As regras do tipo 2 dizem-se livres do contexto, uma vez que permitem a substituição de A por
P em qualquer contexto. Assim, as linguagens L2 dizem-se linguagens livres do contexto.
As gramáticas do tipo 3 constituem as gramáticas regulares ou gramáticas de estados finitos, e
estão relacionadas com os autómatos finitos.
Como consequências imediatas das definições, tem-se :
(a) L3 ⊆ L2 ⊆ L0
(b) L1 ⊆ L0
e também
L3 ⊂ L2 ⊂ L1 ⊂ L0
2.10.2. Operações com linguagens
Sendo as linguagens conjuntos, é legítimo estabelecerem-se as seguintes definições (com L1 e L2
designarem linguagens arbitrárias) :
• L1 ∩ L2 = { P : P ∈ L1 e P ∈ L2 }
•
L1 ∪ L2 = { P : P ∈ L1 ou P ∈ L2 }
•
L1 − L2 = { P : P ∈ L1 e P ∉ L2 } = L 1 ∩ L 2
O complemento de L relativamente a T* representa-se por L e é, por definição,
L = T* − L
• A justaposição dos elementos de T* permite estabelecer-se
L1L2 = { P1P2 : P1 ∈ L1 e P2 ∈ L2 }
Admitindo como generalização para cada inteiro i,
•
Li
pondo, para i = 0,
L0 = { ε }.
Toma-se ainda
L* =
U Li .
i ≥0
Teorema : Para cada gramática G = (Σ, T, P, S) existe uma gramática equivalente do mesmo tipo, na
qual as partes esquerdas das regras não contêm símbolos terminais.
Definição : As operações de união, justaposição e geração de linguagens (representada por *)
chamam-se operações regulares de linguagem.
Teorema : Cada classe de linguagem Li, i = 0, 1, 2, 3 é fechada para as operações regulares.
Linguagens formais
16
Linguagens independentes do contexto
Exemplo :
Sejam T1 e T2, respectivamente, o alfabeto da língua portuguesa e o conjunto dos dez algarismos
decimais. Pretende-se construir uma gramática do tipo 3 geradora de uma linguagem, L, das frases
que contenham só letras ou só dígitos, ou que começando por letras continuem com dígitos. Se
quisermos incluir a frase vazia, ε ∈ L, então ter-se-á
L = T1* ∪ T2* ∪ T1* T2* = T1* T2*
Consideremos dois símbolos S1, S2 que não pertençam a T1 e a T2, e consideremos as gramáticas
G1 = ( { S1 }, T1 , P1 , S1 )
G2 = ( { S2 }, T2 , P2 , S2 )
onde P1 contém
S1 → ε ;
e P2 contém
S1 → a S1 ; … ; S1 → z S1
S2 → ε ;
S2 → 0 S2 ; … ; S2 → 9 S2
É imediato que sendo estas gramáticas do tipo 3 se tem
L(G1) = T1* e que L(G2) = T2* .
Então, a gramática
G’ = ( { S1, S2 }, T1 ∪ T2 , P1‘ ∪ P2 , S1 )
com P1’ contendo
S1 → S2 ; S1 → a S1 ; … ; S1 → z S1
é do tipo 3 e gera T1* T2*
3. Linguagens independentes do contexto
3.1. Introdução
Uma das classes de gramáticas mais usadas, nomeadamente na definição de linguagens de
programação, são as independentes (livres) do contexto  do tipo 1.
Teorema : Para toda a gramática livre do contexto, G, é possível determinar uma gramática livre do
contexto, G’, onde os lados direitos das regras são todos diferentes de Λ, excepto quando Λ ∈ L(G)
 caso em que é permitida a regra S’ → Λ, sempre que S’ não apareça no lado direito das regras.
Corolário : L2 ⊆ L1.
Definição : Uma gramática G diz-se ε−livre se nenhum dos lados direitos das regras de G contiver o
símbolo ε.
3.2. Forma normal de Chomsky
Definição : Uma gramática livre do contexto diz-se que está na forma normal de Chomsky, se as
respectivas regras forem dos dois tipos seguintes :
1) X → a , X ∈ Σ, a ∈ T
2) X → Y Z , X, Y, Z ∈ Σ
Teorema : Para cada gramática do tipo 2 ε−livre, G = (Σ, T, P, S), é possível determinar uma
gramática equivalente, G’ = (Σ, T, P’, S’), na forma normal de Chomsky.
Linguagens formais
Linguagens independentes do contexto
17
3.3. Árvores de derivação
É possível associar uma árvore a cada derivação de uma frase numa linguagem independente
do contexto, chamada árvore de derivação. Para tal, à raiz da árvore associaremos o símbolo inicial S. A
qualquer outro símbolo do vocabulário V = Σ ∪ T corresponde um vértice, que é rotulado por ele,
sendo necessariamente os símbolos terminais associados a folhas na árvore. Se todas as folhas da
árvore forem rotuladas por símbolos terminais, a árvore (de derivação) representa a derivação de
uma frase da linguagem.
Exemplo :
Considere-se a gramática G = ( { S, A, B }, { a, b, c }, P, S) onde o conjunto P é constituído pelas
produções seguintes :
(1) S → A B c (2) A → A B
(3) A → B c
(4) B → a A c (5) B → b c
A seguinte derivação em G
S ⇒ Abc ⇒ AaAcc ⇒ BcaAcc ⇒ BcaaBcc ⇒ bccaaBcc ⇒ bccaabccc
pode ser representada pela seguinte árvore de derivação
S
A
B
b
B
c
c
a
c
A
a
c
B
b
c
NOTA :
Uma árvore de derivação não especifica a ordem pela qual as produções são utilizadas. No
exemplo anterior a regra A → Bc foi aplicada antes da regra B → bc. No entanto, é indiferente a
ordem de aplicação das regras B → aAc e A → Bc. Para evitar as escolhas possíveis considera-se
uma derivação à esquerda numa árvore de derivação, convencionando que em cada passo se
substitui, em primeiro lugar, o símbolo não-terminal mais à esquerda. Duas derivações serão
equivalente se diferirem somente pela ordem de aplicação das regras, isto é, se originarem a
mesma árvore de derivação.
3.4. First, Follow e Lookahead
3.4.1. First
Se α é uma forma sentencial, isto é, α ∈ (Σ ∪ T)*, então First (α) é o conjunto dos símbolos
terminais que começam as cadeias de derivação a partir de α :
∗
First (α) = { a ∈ T : α ⇒ a β , β ∈ (Σ ∪ T)* }.
∗
Se α ⇒ ε então ε ∈ First (α).
Linguagens formais
18
Linguagens independentes do contexto
Para se calcular o First (X) para todos os símbolos gramaticais (terminais e não terminais) da
gramática G, aplique-se as seguintes regras até que nenhum terminal ou ε possa ser adicionado a
qualquer conjunto First :
1. Se X for um terminal (X ∈ T), então First (X) = { X }.
2. Se X → ε for uma produção de G, adicionar ε a First (X)  ε ∈ First (X).
3. Se X for um não terminal (X ∈ Σ) e X → Y1Y2 … Yn uma produção, então a ∈ First (X) se, para
∗
algum i, a ∈ First (Yi) e Y1Y2 … Yi−1 ⇒ ε (isto é, ε ∈ First (Yk), ∀ k = 1, 2, …, i−1).
∗
Se Y1Y2 … Yn ⇒ ε, então ε ∈ First (X).
3.4.2. Follow
Seja A um símbolo não terminal (A ∈ Σ). Define-se Follow (A) como sendo o conjunto de
símbolos terminais a que podem figurar imediatamente à direita de A em qualquer forma sentencial :
∗
Follow (A) = { a ∈ T : S ⇒ α A a β ,  α, β ∈ (Σ ∪ T)* }
Note-se que podem ter existido, nalgum instante da derivação, símbolos entre A e a, mas, se assim o
foi, os mesmos derivaram ε e desapareceram. Se A puder ser o símbolo mais à direita nalguma forma
sentencial, então $ (marcador de fim de entrada à direita) está em Follow (A).
Para calcular Follow (A) para todos os símbolos não terminais da gramática G, aplique-se as
seguintes regras até que nada mais possa ser adicionado a qualquer conjunto Follow :
1. Colocar $ em Follow (S), onde S é o símbolo inicial de G : $ ∈ Follow (S).
2. Se existir uma produção A → α B β, então qualquer a ∈ First (β) (a ≠ ε), a ∈ Follow (B).
3. Se existir uma produção A → α B ou uma produção A → α B β onde First (β) contém ε, então
qualquer a ∈ Follow (A), a ∈ Follow (B).
3.4.3. Lookahead (símbolos directores)
Por vezes o conjunto Lookahead não é apresentado nalguns livros sobre compiladores, porque
este conjunto é definido com base nos conjuntos First e Follow. Desta forma, define-se conjunto L
(Lookahead) na gramática G, da seguinte forma :
1. Dado A ∈ Σ,
∗

Follow (A )
se A ⇒ ε
L (A) = First (A) ∪ 
= First (First (A) Follow (A) )
∅
caso contrário
2. Para qualquer produção A → α

Follow (A )
L (A) = First (α) ∪ 
∅
∗
se α ⇒ ε
= First (First (α) Follow (A) )
caso contrário
3.5. Gramáticas redundantes
Definição : Uma gramática independente do contexto diz-se redundante se contiver símbolos nãoterminais não-necessários.
NOTA : É evidente que a eliminação das variáveis inactivas e inatingíveis numa gramática
independente do contexto não altera a linguagem por ela gerada. Assim, é possível determinar
uma gramática equivalente não-redundante para cada gramática independente do contexto dada.
É, no entanto, mais fácil determinar as variáveis activas e as variáveis atingíveis.
Linguagens formais
Linguagens independentes do contexto
19
Definição : Uma gramática independente do contexto é não-redundante ou reduzida se toda a
variável for activa e atingível.
Teorema : Para cada gramática independente do contexto é possível determinar uma gramática
equivalente não-redundante.
Método para determinar uma gramática reduzida de uma dada gramática G :
1. Eliminação dos símbolos inactivos :
Relativamente à gramática dada definam-se, por recursão, os seguintes conjuntos :
A1 = { X ∈ Σ : X → P, para algum P ∈ T* }
A2 = A1 ∪ { X ∈ Σ : X → W, para algum W ∈ (T ∪ A1)* }
…
ou ainda
Ai+1 = Ai ∪ { X ∈ Σ : X → W, para algum P ∈ (T ∪ Ai)* }
Os conjuntos Ak constituem uma sequência não decrescente de subconjuntos de Σ, conjunto finito,
A1 ⊆ A2 ⊆ … ⊆ Ai ⊆ Ai+1 ⊆ …
Logo, existe um k tal que Ak = Ak+j , para j = 1, 2, 3, … .
Pela própria definição, Ak é o conjunto das variáveis activas da gramática.
Por último, eliminam-se todos os símbolos que não pertençam a Ak, assim como todas as
produções onde estes ocorrem.
2. Eliminação dos símbolos inatingíveis :
Da mesma maneira define-se, também recursivamente e depois de eliminar os símbolos inactivos,
o conjunto das variáveis atingíveis, do modo seguinte :
R1 = { S }
R2 = R1 ∪ { Y ∈ Σ : S → U Y W, para U, W ∈ (Σ ∪ T)* }
…
ou ainda
Ri+1 = Ri ∪ { Y ∈ Σ : X → U Y W, para algum X ∈ Ri , e para U, W ∈ (Σ ∪ T)* }
Existe então um inteiro m tal que
Rm+j = Rm , para j = 1, 2, 3, … .
Tal conjunto, Rm , constitui o conjunto das variáveis atingíveis.
Ao eliminar-se todos os símbolos que não pertençam a Rm, assim como todas as produções onde
estes ocorrem, obtém-se uma gramática equivalente (gramática reduzida) à gramática G.
NOTA :
Pode-se aplicar este teorema para se verificar se uma linguagem gerada por uma gramática, L(G), é
vazia, ou não : L(G) é vazia se e só se o símbolo inicial S for inactivo.
3.6. Gramáticas do tipo LL(1)
O significado de LL(1) é o seguinte :
L “Left-scan”, leitura da frase de entrada da esquerda para a direita
L “Leftmost” derivation”, derivação da esquerda para a direita
(1) O uso de um (1) único símbolo de entrada como lookahead a cada passo para tomar decisões.
As gramáticas LL(1) possuem várias propriedades distintas. Nenhuma gramática ambígua ou
recursiva à esquerda pode ser LL(1). Pode também ser mostrado que uma gramática independente do
Linguagens formais
20
Linguagens independentes do contexto
contexto G é LL(1) se e só se para cada par de produções A → α | β distintas de G, vigorarem as
seguintes condições :
1. α e β não derivem, ao mesmo tempo, cadeias que começam pelo mesmo símbolo terminal
a, qualquer que seja a.
2. No máximo um dos dois, α e β, derive a cadeia vazia (ε).
∗
3. Se β ⇒ ε , então α não deriva qualquer cadeia que comece por um terminal pertencente a
Follow (A).
Por outras palavras, e utilizando a definição do conjunto Lookahead, uma gramática
independente do contexto G é LL(1) se e só se para cada par de produções A → α | β distintas de G
L(A → α) ∩ L(A → β) = ∅.
3.7. Gramáticas do tipo LL(k)
Uma gramática do LL(k), é definida segundo dois parâmetros :
1. O conjunto dos primeiros k símbolos, da seguinte forma :
First (k, t) = { t }, para t ∈ T ;
First (k, ε) = { ε }
α
se
α ≤k
First (k, α) = 
se α = βδ : β = k
β
First (k, A B … X) = First ( k, First (k, A) First (k, B) … First (k, X) )
First (k, A) = U First (k , α )
A→ α
2. O conjunto dos k símbolos seguidores, da seguinte forma :
∀p : B → αAδ
Follow (k, A) = U First ( k , First (k , δ) Follow(k , B))
δ,B
∀p
: B → αSδ
Follow (k, S) = { $ } ∪
U
First ( k , First (k , δ) Follow(k , B))
δ,B
3. O conjunto dos k símbolos directores, da seguinte forma :
∗
L(k, A) = First (k, A) ∪ { Follow (k, A), se A ⇒ ε }
= First (k, First (k, A) Follow (k, A))
∗
L(k, A → α) = First (k, α) ∪ { Follow (k, A), se A ⇒ ε }
= First (k, First (k, α) Follow (k, A))
Definição : Uma gramática independente do contexto é do tipo LL(k) se e só se :
L(k, A → α) ∩ L(k, A → β) = ∅
para qualquer par de produções A → α | β.
Exemplo :
Estudar a gramática com as seguintes produções :
S → bRS | RcSa | ε
R→ acR | b
Prova-se que a gramática é do tipo LL(2).
Linguagens formais
Linguagens independentes do contexto
21
3.8. Gramáticas de atributos
Uma gramática de atributos não é mais do que uma gramática independente de contexto, na
qual as produções são enriquecidas por regras semânticas por forma a que os símbolos (terminais ou
não terminais) recebam valores.
As gramáticas de atributos têm sido usadas na definição de compiladores : a gramática
independente de contexto descreve a linguagem formal e as regras semânticas permitem a translação
da entrada para uma linguagem objecto, tipicamente uma representação intermédia.
3.8.1. Definição
Definição : Uma gramática de atributos AG consiste em :
• uma gramática independente de contexto G = (Σ, T, P, S);
• para cada símbolo gramatical X ∈ (Σ ∪ T), um conjunto finito de atributos sintetizados, S(X), e
um conjunto de atributos herdados, I(X).
Os conjuntos S(X) e I(X) possuem as seguintes restrições :
− S(X) e I(X) são conjuntos disjuntos, isto é, S(X) ∩ I(X) = ∅
− I(S) = ∅, isto é, o símbolo inicial da gramática não possui atributos herdados
− ∀ x ∈ Σ, S(x) = ∅, isto é, os símbolos terminais não possuem atributos sintetizados.
A(X) = S(X) ∪ I(X) representa a união dos conjuntos S(X) e I(X). A cada atributo a é atribuído
um domínio Da, ou seja, o conjunto de valores possíveis.
• a cada produção P na forma
X0 → X1 . . . Xn
Para todos os atributos a ∈ S(X0) e para todos os atributos a ∈ I(Xi), 1 ≤ i ≤ n, existe um
conjunto de regras semânticas ΓP na forma :
A(Xi) = f(b1(Xi ), . . ., bk(Xi ))
1
k
nas quais são verificadas as seguintes restrições :
− 0 ≤ i ≤ n e i1, . . ., ik ≤ n ;
− a, b1, ..., bk são atributos ;
f é uma função Db × . . . × Db → Da ;
1
k
− a ∈ A(Xi), b1 ∈ A(Xi ), . . ., bk ∈ A(Xi )) ;
−
1
k
se a é um atributo sintetizado, então i = 0 ;
− se a é um atributo herdado, então 1 ≤ i ≤ n ;
−
Cada atributo tem um identificador e um domínio. Normalmente, o identificador do atributo
possui a forma
símbolo . id
Nas funções semânticas apenas podem ser usados :
• literais ;
• valores de atributos em ocorrências de símbolos na produção ;
• funções puras, isto é, sem efeitos colaterais.
Definição
: Seja uma gramática de atributos AG, α uma frase de LAG e t uma árvore de derivação
+
S ⇒ α. Num nó n de t, etiquetado por X ∈ (Σ ∪ T), a diz-se ocorrência (ou instância) de um atributo
em t se e só se a ∈ A(X). O atributo a possui um valor de Da.
3.8.2. Grafos de dependência local
As dependências nas regras semânticas entre os atributos de uma gramática podem ser
representados graficamente por grafos de dependência local.
Linguagens formais
22
Linguagens e expressões regulares
As representações gráficas de cada elemento dos grafos de dependência local são descritos na
seguinte tabela :
Elemento
Representado por
Atributo
Círculo
Símbolo gramatical
Identificador
Dependência entre atributos
Arco entre círculos
Os atributos e os símbolos gramaticais são inscritos dentro de um rectângulo. Os identificadores
dos atributos são colocados ao lado do símbolo gramatical respectivo. O lado do rectângulo onde se
posicionam os atributos depende do lado onde o símbolo gramatical se encontra na produção.
Posição na produção
Lado de rectângulo
Esquerdo
Superior
Direito
Inferior
O fluxo de cálculo de atributos sintetizados é representado graficamente por setas ascendentes,
ou por setas horizontais, e o fluxo de cálculo de atributos herdados é representado graficamente por
setas descendentes.
4. Linguagens e expressões regulares
As linguagens regulares constituem uma classe bastante importante das linguagens. Elas são
usadas, por exemplo, para definir os elementos léxicos de uma linguagem de programação a partir do
alfabeto formado pelos caracteres latinos.
Definição : Uma linguagem diz-se regular se puder ser obtida aplicando um número finito de
operações sobre as seguintes linguagens :
• linguagem vazia;
• linguagem cuja única frase é a frase nula;
• linguagens com uma única frase.
Os operadores aplicáveis a quaisquer duas linguagens L1 e L2 são :
1. Concatenação : L1 L2 = { u v : u ∈ L1 ∧ v ∈ L2 }
2. Exponenciação : L0 = { ε } e Li = L Li-1
3. União : L1 ∪ L2 = { u : u ∈ L1 ∨ u ∈ L2 }
4. Fecho de Kleene (zero ou mais concatenações de L) : L* = U ∞i =0 L i
Exemplo :
Seja T = { a, b }. Como exemplos de linguagens regulares tem-se :
• ({ a } ∪ { b })* { a }  são utilizados o operador de fecho de Kleene e o operador de
concatenação sobre a linguagem base La = { a }. A linguagem resultante é, portanto, L*T L a e
descreve o conjunto de frases terminadas em a (com comprimento superior ou igual a 1).
•
{ a }{ a }*  resulta na linguagem L a L*a e descreve o conjunto de frases iniciadas em a.
Atendendo a que um conjunto finito de frases pode ser considerado como uma linguagem
regular (onde o conjunto das regras será S → P, para os elementos P desse conjunto), é possível a
partir de um conjunto finito de frases construir uma linguagem regular por aplicação das operações
regulares nesse conjunto.
Linguagens formais
Gramáticas lineares e linguagens regulares
23
As expressões regulares permitem representar, de modo sucinto, as linguagens regulares. Uma
das vantagens das expressões regulares reside na possibilidade da sua utilização como linguagem de
especificação de analisadores léxicos.
Definição : Uma expressão regular sobre um alfabeto T define uma linguagem L, segundo o
seguinte conjunto de regras :
• Λ é uma expressão regular que define a linguagem vazia;
• ε é uma expressão regular que define uma linguagem que consiste na frase nula { ε };
• dado a ∈ T, a é uma expressão regular que representa a linguagem La, tal que La = { a };
• dadas 2 expressões regulares, p e q, que representam, respectivamente, as linguagens Lp e Lq
− p + q é uma expressão regular que representa a linguagem Lp ∪ Lq
− pq é uma expressão regular que representa a linguagem Lp Lq
− p* é uma expressão regular que representa a linguagem L*p
− (p) é uma expressão regular que representa a linguagem Lp
Os operadores que aparecem nas expressões regulares têm a seguinte prioridade (da maior para
a menor) : fecho de Kleene, concatenação e união. Todos os operadores são associativos à esquerda.
Para facilitar a definição de expressões regulares, acrescentaram-se os seguintes operadores :
• fecho transitivo “+”  corresponde a uma ou mais ocorrências. Por exemplo, p+ é
equivalente a pp* e p* é equivalente a p+ + ε
• parêntesis rectos “[ ]”  servem para substituir classes de símbolos de V. Por exemplo, [pq]
corresponde a p + q. Caso os símbolos de V sejam ordenados, podem ser definidos
intervalos como [p−q].
Notações : Considere-se o alfabeto T = { a, b }. Então pode-se representar por
a* = (a)*
a linguagem { a }*
a linguagem { a, b }*
(a ∪ b)*
a* b
a linguagem { a }* { b }
b ∪ a b*
a linguagem { b } ∪ { a } { b }*
a linguagem { a, b } { a }*
(a ∪ b) a*
Definição : Duas expressões regulares α e β dizem-se equivalentes, α ≡ β, se e só se definirem a
mesma linguagem (isto é, Lα = Lβ)
Teorema : Toda a expressão regular representa uma linguagem regular e toda a linguagem regular
pode ser representada por uma expressão regular.
5. Gramáticas lineares e linguagens regulares
Definição : Uma gramática independente do contexto diz-se linear se as respectivas produções
forem dos dois tipos seguintes :
(1) A → P
A ∈ Σ, P ∈ T*
(2) A → Q1 B Q2
A, B ∈ Σ, Q1, Q2 ∈ T*
A gramática diz-se linear à esquerda (linear à direita) se em cada regra do tipo (2), Q1 (Q2) for a
frase vazia (ε).
NOTA :
Pela própria definição, as gramáticas lineares à direita são as gramáticas regulares (do tipo 3).
Teorema : Toda a gramática linear à esquerda gera uma linguagem regular.
Corolário : Toda a linguagem regular pode ser gerada por uma gramática linear à esquerda.
Linguagens formais
24
Linguagens sensíveis ao contexto e linguagens com estrutura de frase
Teorema : Toda a gramática regular é equivalente a uma gramática contendo unicamente regras do
tipo seguinte :
(1) X → aY
X, Y ∈ Σ , a ∈ T
(2) X → ε
X∈Σ
Teorema : Sendo L ∈ L2 e L’ ∈ L3 então L ∩ L’ ∩ L2 , isto é, a linguagem intersecção de uma
linguagem livre do contexto com uma linguagem regular é uma linguagem livre do contexto.
6. Linguagens sensíveis ao contexto e linguagens com estrutura de frase
Definição : Uma gramática com estrutura de frase (do tipo 0), G, diz-se de comprimento crescente
(ou mais propriamente, de comprimento não decrescente) se todas as produções de G, P → Q,
verificarem |P| ≤ |Q|.
Teorema : Toda a gramática de comprimento crescente gera uma linguagem sensível ao contexto.
Corolário : A classe das linguagens livres do contexto está propriamente contida na classe das
linguagens sensíveis ao contexto, isto é, L2 ⊂ L1 .
Definição : Uma gramática de comprimento crescente diz-se na forma normal de Kuroda se as
respectivas produções forem do tipo :
(1) A → a
(2) A → B
(3) A → B C
(4) A B → C D
Teorema : Toda a gramática de comprimento crescente é equivalente a uma gramática na forma
normal de Kuroda.
Corolário : Toda a linguagem sensível ao contexto ε-livre é gerada por uma gramática na forma
normal de Kuroda.
Teorema : Para toda a gramática com estrutura de frase, G, existe uma gramática equivalente, G’, em
que cada regra é de um dos tipos seguintes :
(1) S → A
(4) A → B C
(2) A → a
(5) A B → A C
(3) A → B
(6) A B → B
e onde o símbolo inicial S só pode ocorrer no lado esquerdo das regras.
Linguagens formais