docdownloader.com compiladores da teoria a praticapdf

Prévia do material em texto

UNIVERSIDADE TÉCNICA DE LISBOA
INSTITUTO SUPERIOR TÉCNICO
COMPILADORES:
da teoria à prática
Pedro Reis dos Santos
Departamento de Engenharia Informática
(Fevereiro, 2006)
18 CAPÍTULO 1. INTRODUÇÃO
�
�
�
�HHHHHHHH
-
PPPPPq
- interpretadorprograma resultados
dados
-
?
-
?
"
#
!
 
dados
resultados
compiladorexecutávelprograma
1.2 Linguagens e gramáticas
Foram os matemáticos Axel Thue, Emil Post e Stephen Kleene, entre outros, que come-
çaram a estudar as propriedades matemáticas das cadeias de caracteres e sequências
destas. No entanto, foi Noam Chomsky que, em 1956, que procurou caracterizar de
uma forma precisa a estrutura das linguagens naturais. O seu objectivo consistia em
utilizar regras matemáticas precisas para especificar a sintaxe das linguagens. Com a
divulgação dos computadores, nos anos seguintes, veio-se a verificar que as linguagens
a utilizar em computadores podiam ser especificadas por um dos modelos gramati-
cais identificados por Chomsky. Estas linguagens, designadas por livres de contexto,
podem ser linguagens de programação, podem ser linguagens de descrição de dados,
como imagens ou som, ou outro tipo de processos.
Nesta secção abordaremos as propriedades matemáticas fundamentais das linguagens
e dos sistemas usados para as gerar, tais como as gramáticas. As linguagens de pro-
gramação, desde o Fortran, podem ser especificadas de uma forma precisa através de
uma gramática. Além disso, a gramática permite escrever programas, designados por
analisadores sintácticos, que permitem determinar se a cadeia de caracteres está sin-
tacticamente correcta de acordo com a linguagem. Apesar dos avanços efectuados nos
últimos anos, a análise precisa de linguagens naturais, como o português ou o inglês,
1.2. LINGUAGENS E GRAMÁTICAS 19
ainda é limitada. O problema reside, principalmente, na inexistência de um acordo so-
bre quais as frases sintacticamente correctas, nem foi ainda proposta uma gramática
suficientemente precisa e consensual.
Nesta secção apresentaremos alguns sistemas formais que permitem definir famílias
de linguagens utilizadas frequentemente em computação. A nossa atenção principal
orienta-se para as linguagens livres de contexto, pois são as mais usadas para descrever
a sintaxe das linguagens de computação.
1.2.1 Terminologia
Antes de introduzir a especificação formal de linguagens apresentam-se algumas defi-
nições e terminologia.
alfabeto Um alfabeto, designado por Σ, é um conjunto finito não vazio de símbolos
indivisíveis. Por exemplo, a lingua inglesa contém as 26 letras alfabéticas e alguns sinais
de pontuação. A lingua portuguesa usa apenas 23 letras, mas inclui certos símbolos de
acentuação para algumas letras. O alfabeto ASCII ( American Standard Code for Infor-
mation Interchange ) utiliza 128 símbolos, sendo utilizado na maioria das comunicações
entre computadores. O alfabeto UNICODE, mais recente que o ASCII, pretende supor-
tar os símbolos de todas as linguagens utilizadas no planeta e possui, no momento da
escrita deste documento, mais de 38 mil símbolos. No entanto, os aspectos mais impor-
tantes das linguagens formais podem ser modelados com apenas duas letras.
cadeia Uma cadeia de um alfabeto Σ é uma sequência finita de símbolos de Σ. O
número de símbolos na cadeia x é designada por comprimento da cadeia e designado
por |x|. A cadeia vazia, de comprimento 0 ( zero ), é designada por ε.
conjuntos de cadeias O conjunto de todas as possíveis cadeias de um alfabeto desig-
naremos por Σ∗, enquanto Σ+ designa todas as cadeias não vazias e ∅ o conjunto vazio.
linguagem Uma linguagem sobre um alfabeto Σ é o conjunto de cadeias consideradas
válidas sobre esse alfabeto. Os membros da linguagem são também designados por
frases da linguagem.
Uma vez que as linguagens são apenas conjuntos é aceitável aplicar as operações tra-
dicionais, como a união, intersecção e complemento. Além disso, existem mais duas
operações base sobre linguagens: a concatenação e o fecho de Kleene.
20 CAPÍTULO 1. INTRODUÇÃO
concatenação A concatenação de duas linguagens L1 e L2 sobre um alfabeto Σ é o
conjunto {xy|x ∈ L1, y ∈ L2}. Onde x = a1a2 . . . an e y = b1b2 . . . bn são cadeias do
mesmo alfabeto e a sua concatenação, designada por xy, é a cadeia a1a2 . . . anb1b2 . . . bn.
fecho de Kleene Seja L0 = {ε} e Li = LLi para i ≥ 1, designa-se por fecho de Kleene
de L, representado por L∗, a linguagem L∗ =
⋃
i≥0 L
i. O fecho transitivo de L, repre-
sentado por L+, é a linguagem L+ =
⋃
i≥1 L
i. Por outras palavras, o fecho de Kleene da
linguagem L consiste em todas as cadeias que podem ser formadas pela concatenação
de zero ou mais frases de L.
1.2.2 Representação de linguagens
Uma linguagem é, em geral, um subconjunto de Σ∗ sobre alfabeto Σ. Enquanto uma
linguagem finita pode ser definida através da enumeração dos seus elementos, uma
linguagem infinita não pode ser exaustivamente enumerada. Algumas linguagens in-
finitas podem ser definidas por regras que caracterizam todos os seus elementos. Uma
larga gama de linguagens pode ser caracterizada por regras definidas por métodos sis-
temáticos. De entre estes métodos, as gramáticas são o formalismomais frequentemente
utilizado.
As gramáticas formais foram introduzidas em 1943 por Emil Post, que se baseou no
trabalho de Axel Thue e outros. No entanto, foi Noam Chomsky em 1956 que estudou
a sua utilização rigorosa na descrição formal e natural das linguagens.
O sistema mais genérico e útil para representar linguagens é baseado na noção formal
de gramática. Uma gramática é um quádruplo (Σ, V, S, P ), onde
1. Σ é um conjunto finito não vazio designado por alfabeto terminal, onde cada ele-
mento é designado por símbolo terminal.
2. V é um conjunto finito não vazio disjunto de Σ, cujos elementos são designados
por símbolos não terminais.
3. S ∈ V é um símbolo não terminal específico designado por símbolo inicial.
4. P é um conjunto finito de regras ( ou produções ) da forma α → β onde α ∈
(Σ
⋃
V )∗V (Σ
⋃
V )∗ e β ∈ (Σ
⋃
V ), ou seja, α é uma cadeia de terminais e não ter-
minais contendo pelo menos um não terminal e β é uma cadeia de terminais e não
terminais.
1.2. LINGUAGENS E GRAMÁTICAS 21
Exemplo 1.1 A gramática G = ({0, 1, 2}, {S,A}, S, P ), onde P é constituído pelas regras
S → 0 S A 2
S → ε
2 A → A 2
0 A → 0 1
1 A → 1 1
descreve as frases {0n1n2n, n ≥ 0}.
Hierarquia de gramáticas
As gramáticas podem ser divididas em quatro classes de restrições gradualmente cres-
centes à forma das regras. Esta classificação é designada por hierarquia de Chomsky.
Seja uma gramática G = (Σ, V, S, P )
1. G é também designada gramática tipo-0 ou gramática sem restrições.
2. G é tipo-1 ou gramática dependente do contexto se cada regra α → β de P obe-
dece a |α| ≤ |β|. Uma gramática ainda é do tipo-1 se tiver uma regra S → ε, desde
que S não surja no lado direito de nenhuma regra.
3. G é tipo-2 ou gramática livre do contexto se cada regra α → β de P obedece a
|α| = 1, ou seja, α é constituído por um só não terminal.
4. G é tipo-3 ou gramática regular se cada regra tiver uma das formasA→ cB,A→ c
ou A→ ε, onde A e B são não terminais ( podendo B = A ) e c é um terminal.
Cada classe de linguagens do tipo-i contém a classe de linguagens do tipo-i+1, para
i = 0, 1, 2.
Contudo, as classes de linguagens identificadas por Chomsky não reflectem apenas as
propriedades formais das mesmas mas também traduzem as características fundamen-
tais da sua computação. De facto, cada classe de gramática é processável por uma classe
de ferramentas,
máquinas de Turing processam gramáticas sem restrições.
autómatos linearmente limitados processam gramáticas dependentes do contexto.
autómatos de pilha processam gramáticas livre do contexto.
22 CAPÍTULO 1. INTRODUÇÃO
autómatos finitosprocessam gramáticas regulares.
Destes apenas trataremos os autómatos finitos e autómatos de pilha, bem como os ana-
lisadores que realizam esses autómatos.
Propriedades das gramáticas
fecho Uma classe de linguagens diz-se fechada numa operação particular se cada apli-
cação da operação nas linguagens da classe ainda é uma linguagem dessa classe. As
operações designam operações de união, intersecção, complemento, concatenação e fe-
cho de Kleene. As propriedades de fecho são úteis na construção de novas linguagens a
partir de linguagens existentes e para provar muitas propriedades teóricas das lingua-
gens e gramáticas.
As gramáticas sem restrições só não são fechadas pela operação de complemento. As
gramáticas livres de contexto não são fechadas pelas operações de complemento e inter-
secção. Finalmente, as linguagens regulares e as linguagens dependentes do contexto
são fechadas em todas as cinco operações.
Capítulo 2
Linguagens regulares
As linguagens regulares, designadas por tipo-3 na hierarquia de Chomsky ( ver 1.2.2 ),
são linguagens muito simples. Assim, a maioria das linguagens utilizadas em computa-
ção não são regulares, ou seja, não podem ser completamente descritas por gramáticas
regulares. No entanto, como o seu processamento é simples e eficiente, as gramáticas re-
gulares são frequentemente utilizadas para processar partes, por vezes significativas, de
linguagens mais complexas. Desta separação do processamento da linguagem por uma
gramática regular e por outra gramática, em geral livre de contexto, resulta uma maior
eficiência em termos de espaço ocupado pelo analisador e do tempo gasto na análise das
descrições. Resulta, ainda, uma simplificação da gramática livre de contexto, facilitando
a sua descrição, realização e execução.
O processamento da parte regular de uma linguagem designa-se por análise lexical. A
análise lexical tem a vantagem de ser um processo que podendo ser formalmente des-
crito através de expressões regulares pode produzir uma rotina que realiza essa análise.
Essa rotina modela um autómato finito derivado matematicamente das expressões re-
gulares especificadas.
A análise lexical é utilizada essencialmente na categorização dos elementos de uma lin-
guagem em classes de símbolos, em vez de caracteres individuais. Nomeadamente,
permite separar nomes em palavra reservadas, identificadores e literais, bem como clas-
sificar outros símbolos como terminadores, separadores e operadores. Permite ainda
encapsular dependências do sistema operativo, como por exemplo, o carácter ou carac-
teres de mudança de linha. Localiza a manipulação dos diferentes formatos de repre-
sentação de caracteres, como o ASCII, UNICODE ou, no caso da lingua portuguesa, o
ISO-LATIN-15 ou a página 860. Esconde do restante compilador elementos como co-
mentários e caracteres brancos ( em geral designam o espaço e o tabulador horizontal ).
Realiza a substituição de macros simples. Em resumo, facilita o processamento transfor-
mando uma linguagem descrita por uma sequência de caracteres numa sequência de
25
26 CAPÍTULO 2. LINGUAGENS REGULARES
elementos lexicais, designados por tokens. A restante análise da linguagem pode assim
ser baseada em elementos categorizados.
2.1 Expressões regulares
Expressões regulares foram introduzidas em 1956 por Stephen Kleene para o estudo
das propriedades das redes neuronais. As linguagens representadas por expressões re-
gulares são designadas por linguagens regulares. As expressões regulares apresentam
representações das linguagens que são frequentemente claras e concisas, contudo, mui-
tas linguagens não são regulares.
Uma expressão regular sobre um alfabeto Σ, e a linguagem regular que a expressão
regular representa, pode ser definida por:
1. o símbolo ∅ é uma expressão regular e representa a linguagem vazia.
2. o símbolo ε é uma expressão regular e representa a linguagem cujo único membro
é a cadeia vazia, ou seja, {ε}.
3. para cada c ∈ Σ, c é uma expressão regular e representa a linguagem {c}, onde o
único membro é a cadeia de um só carácter c.
4. se r e s são expressões regulares e representam as linguagensR e S, então (r|s), (rs)
e (r∗) são expressões regulares que representam R
⋃
S, RS e R∗, respectivamente.
Exemplo 2.1 A expressão regular ((0(0|1)∗)|((0|1) ∗ 0)) sobre o alfabeto {0, 1} representa a
linguagem regular que consiste em todas as cadeias de digitos binários que começam ou terminam
com 0.
2.1.1 Operadores das expressões regulares
De acordo com a definição acima, as expressões regulares são construídas por operado-
res com determinadas propriedades. A esses operadores atribuiremos prioridades por
forma a simplificar a escrita das expressões regulares. Considerando as propriedades
algébricas dos operadores base é possível introduzir identidades algébricas para expres-
sões regulares por forma a construir expressões equivalentes. Duas ou mais expressões
regulares que representam a mesma linguagem são designadas por equivalentes.
2.1. EXPRESSÕES REGULARES 27
Uma expressão regular pode ser formada pelos seguintes operadores, considerando
duas expressões regulares p, q:
união: designado por p|q é comutativo, associativo e idempotente ( p|p = p ), represen-
tando a união das expressões regulares originais. ∅ é o elemento neutro da união.
concatenação: designado por p q é associativo e distributivo em realção à escolha e
mais prioritário que a escolha. ε é elemento neutro e ∅ é o elemento absorvente na
concatenação.
fecho de Kleene: designado por p∗ é idempotente ( p ∗ ∗ = p∗ ) e mais prioritário que
a concatenação. Representa o conjunto de frases constituídas por zero ou mais
repetições das frases de p. Além disso p∗ = (p|ε)∗.
parênteses: permite alterar a prioridade dos operadores.
Exemplo 2.2 Atendendo às prioridades dos operadores, a expressão regular a|bca∗ sobre o alfa-
beto {a, b, c} corresponde a a|(b(c(a∗))).
Além dos operadores base é ainda usual utilizar outros operadores, construídos a partir
dos anteriores, que simplificam a descrição das linguagens através de expressões regu-
lares.
opção: designado por p? designa zero ou uma ocorrências de p, ou seja, p|ε.
fecho transitivo: designado por p+ designa uma ou mais ocorrências de p.
p+ é equivalente a p p∗, e p∗ é equivalente a p+ |ε.
parênteses rectos: designado por [pq] ou [p − q] designam p|q e os símbolos de ordem
entre p e q (inclusivé), respectivamente.
A ordem depende da representação utilizada ( ASCII, UNICODE, EBCDIC, etc. )
pelo que apenas se garante a ordem das letras maiúsculas [A − Z], minúsculas
[a− z] e digitos decimais [0− 9].
complemento: designado por [ˆpq] ou [ˆp−q] designam todos os símbolos deΣ excepto
p|q e todos os símbolos de Σ excepto os símbolos de ordem entre p e q (inclusivé),
respectivamente.
28 CAPÍTULO 2. LINGUAGENS REGULARES
2.1.2 Gramáticas regulares
Uma linguagem regular é descrita por uma gramática regular. Tal como vimos em 1.2.2
uma gramática regular tem apenas regras da forma A→ c,A→ ε, eA→ cB ouA→ Bc,
onde A e B são não terminais ( podendo B = A ) e c é um terminal. A gramática diz-se
linear à direita se usar regras da forma A → cB ou linear à esquerda se usar regras da
forma A → Bc, não podendo usar ambas as formas simultaneamente. Além disso, a
regra A→ c pode ser deduzida por substituição da regra B → ε numa das outras.
Se L tem uma gramática regular, então L é uma expressão regular. 1 Se L é uma ex-
pressão regular, então L é gerado por alguma gramática linear à esquerda e por alguma
gramática linear à direita. 2 Em resumo, gramáticas regulares caracterizam expressões
regulares, pois uma linguagem é regular se e só se tiver uma gramática linear à es-
querda e se e só se tiver uma gramática linear à direita. Ou seja, gramáticas regulares e
expressões regulares são representações equivalentes de linguagens regulares.
2.1.3 Propriedades das expressõesregulares
As expressões regulares são apenas uma forma mais concisa de descrever linguagens
regulares que as gramáticas regulares. Como as gramáticas regulares são fechadas nas
5 operações base ( ver 1.2.2 ) pode-se combinar livremente as expressões regulares que
ainda se tem uma expressão regular. Como uma expressão regular é fechada na con-
catenação qualquer técnica aplicada às expressões regulares a e b pode ser aplicada a
ab. Como é fechada na união, o que se pode fazer a uma expressão regular a1|a2|...|an
pode-se fazer individualmente a a1, a a2 etc. Como é fechada no fecho de Kleene pode-
se escrever regras concisas sem indicar o limite, por exemplo, criar expressões regulares
para padrões de dimensão finita mas arbitrária. Nomeadamente, os identificadores não
têm número limite de caracteres em muitas linguagens.
2.2 Autómatos finitos
A modelação de linguagens regulares, quer tenham sido especificadas por expressões
regulares como por gramáticas regulares, pode ser efectuada por autómatos finitos. Da
mesma forma, uma linguagem reconhecida por um autómato finito é uma linguagem
1teorema 9.1 de [HU79]
2teorema 9.2 de [HU79]
2.2. AUTÓMATOS FINITOS 29
regular. Existem diversos algoritmos, representados pelas setas da figura seguinte, que
permitem converter expressões regulares de e para diversos tipos de autómatos finitos,
cada um com o seu campo de aplicação.
-
?
ff
HH
HH
HH
HH
HH
HY
~Z
Z
Z
Z
ZZ}
	�
�
�
�
��
Thompson
subconjuntos
Hopcroft
autómato
finitofinito det.
minimizado
regulares
expressões
autómato
autómato
finito não
determinista
determinista
Kleene
gramática
regular
Nas secções seguintes abordaremos esses autómatos e os algoritmos que permitem obtê-
los.
Os autómatos finitos são constituídos por um conjunto de estados e por transições di-
rigidas e etiquetadas entre esses estados. As etiquetas são símbolos da gramática ou
ε. Um desses estados é designado por inicial, podendo ter um mais estados finais. O
autómato finito pode ser representado graficamente ou por tabela.
2.2.1 Diagrama de transição
Um autómato finito pode ser presentado graficamente por um diagrama de transição,
ou seja, um quádruplo D = (S, δ, SF , q0) onde:
• S é um conjunto de estados, representados por círculos.
• δ(qi, x) = qj , onde qi ∈ S, qj ∈ S e x ∈ Σ ∪ {ε}, são transições entre estados
representadas por setas etiquetadas por um dos símbolos de entrada ou ε.
• SF ∈ S e #S ≥ 1, é um conjunto constituído por um ou mais estados finais,
representados por círculos duplos concêntricos.
• q0 ∈ S é um estado inicial, indicado por uma seta sem origem em outro estado.
30 CAPÍTULO 2. LINGUAGENS REGULARES
O reconhecimento de uma frase pode ser efectuado por simulação da rede, começando
o processamento no estado inicial. Se no fim do processamento nos encontrarmos num
estado final a frase está correcta e faz parte da linguagem em questão. Se o estado
corrente, no fim do processamento, não for um estado final devem-se procurar outros
caminhos.
Exemplo 2.3 A expressão regular (a|b) ∗ abb, que designa as frases do alfabeto Σ = {′a′,′ b′}
que terminam em abb, pode ser representada por
��
ff�
I ��
ff�
I ��
ff�
I��
ff�
ffifl
�fi
- -- -
ll
##A
AU
�
�
bb�
��
0
’b’
1 I 2 3
’b’
’a’ ’b’
’a’
2.2.2 Tabela de transição
Uma outra representação, menos intuitiva mas mais útil do ponto de vista computaci-
onal, é a tabela de transição. Na tabela de transição os estados representam uma das
dimensões da tabela bidimensional e as etiquetas a outra dimensão. Cada posição da
tabela representa os estados que podem ser atingidos a partir desse estado com esse
símbolo ou etiqueta. Os estados finais são representados dentro de caixas e o estado
inicial assume-se ser o primeiro estado da tabela.
Exemplo 2.4 A expressão regular do exemplo 2.3, pode ser representada por
estado ’a’ ’b’
0 {0, 1} {0}
1 ∅ {2}
2 ∅ {3}
0 ∅ ∅
2.2.3 Autómato finito não determinista
Um autómato finito não determista é um quintuplo (S,Σ ∪ {ε}, δ, SF , s0), onde S são os
estados, Σ o alfabeto, uma função de transição δ, um estado inicial s0 ∈ S e um conjunto
de estados finais SF ⊆ S. A função de transição δ : S × Σ 7→ 2S faz corresponder a cada
par estado e símbolo de entrada um conjunto, eventualmente vazio, de estados. Onde o
conjunto de todos os subconjuntos de S, designado por powerset, é representado por 2S.
2.2. AUTÓMATOS FINITOS 31
A utilização de transições vazias, que não consomem nenhum símbolo da sequência de
entrada, facilita a construção do autómato, mas existe sempre um autómato não deter-
minista equivalente sem transições vazias 3. Quer o exemplo 2.3 como o exemplo 2.4
são duas representações de um autómato finito não determinista.
Para descobrir se uma frase, ou sequência de entrada, faz parte da linguagem é neces-
sário procurar um caminho entre o estado inicial e um dos estados finais do autómato.
A procura pode ser efectuada de diversas formas, como por exemplo em profundidade
e em largura. Se a procura for em profundidade segue-se um caminho possível e, caso
não seja atingido um estado terminal, recua-se e tenta-se outra possível solução. Na
procura em largura vão sendo simultaneamente consideradas as diversas opções em
cada estado. Computacionalmente a solução de procura em profundidade parece mais
simples de realizar mas a sua execução é pesada.
Algoritmo de Thompson
Existe sempre um autómato não determinista, com transições vazias, que aceita a lin-
guagem descrita por uma expressão regular 4. O algoritmo de Thompson não é mais
que a demonstração da afirmação anterior. Para tal começamos pela três expressões
com que definimos as expressões regulares ( ver 2.1 ),
ffifl
�fi
��
ff�
- q 0 ��
ff�
- q 0��
ff�
- q 0 ffifl
�fi
��
ff�
ffifl
�fi
��
ff�
-q qf f
’a’
r = ε r = ∅ r = a
como as expressões regulares são fechadas nas operações base ( ver 1.2.2 ), temos que a
operação de união de duas expressões regulares r e s é também a união das linguagens
descritas por cada uma destas expressões regulares L(r|s) = L(r) ∪ L(s),
��
ff�
- q 0
��
ff�
q 2 ��
ff�
2f
��
ff�
1f��
ff�
q 1
ffifl
�fi
��
ff�
Z
Z
Z~ �
��3
Q
QQs�
�
�>
0f
ε
ε ε
ε
L(s)
L(r)
3teorema 2.2 de [HU79]
4teorema 2.3 de [HU79]
32 CAPÍTULO 2. LINGUAGENS REGULARES
a operação de concatenação de duas expressões regulares r e s é a concatenação das
linguagens descritas por cada uma destas expressões regulares L(rs) = L(r)L(s),
��
ff�
q 2 ��
ff�
2f��
ff�
1f��
ff�
q 1 ffifl
�fi
- -ε
L(r) L(s)
na prática, o estados f1 e q2 podem ser fundidos num só, poupando um estado e elimi-
nando a transição vazia.
O fecho de Kleene de uma expressão regular s é o fecho de Kleene da linguagem descrita
pela expressão regular L(s∗) = L(s)∗,
��
ff�
- q 0 ffifl
�fi
��
ff�
0f��
ff�
1f��
ff�
q 1 --
6
?
ε ε
L(s)
ε
ε
Notar o sentido das setas nas transições vazias.
A construção de uma expressão regular complexa resume-se à sucessiva aplicação das
diversas ocorrências das operações por ordem decrescente de prioridade.
Exemplo 2.5 A expressão regular do exemplo 2.3 é representada pelo autómato finito não deter-
minista da figura, construído pelo algoritmo de thompson,
��
ff�
��
ff���
ff�
��
ff�
��
ff�
��
ff���
ff�
��
ff�
��
ff�
��
ff�
��
ff�
��
ff�
ffifl
�fi
��
ff�
��
ff�
- -
��*
-
-
HHj
Z
Z~
�
�>
- -
?
ff
?
6
ff ff ff
10
3
2 4
5
6 7 8
910
a
b
ε
ε ε
ε
ε ε
ε
ε
13
b
12
ε
11
b ε
ε
a
2.2. AUTÓMATOS FINITOS 33
2.2.4 Autómato finito determinista
Um autómato finito determista é um quintuplo (S,Σ, δ, SF , s0), onde S são os estados, Σ
o alfabeto, uma função de transição δ, um estado inicial s0 ∈ S e um conjuntode estados
finais iSF ⊆ S. A função de transição δ : S × Σ 7→ S faz corresponder a cada par estado
e símbolo de entrada um conjunto, eventualmente vazio, de estados.
Num autómato finito não determinista as transições a partir de cada estado são disjun-
tas e não vazias. Ou seja, não podem existir transições vazias e, no máximo, só pode
haver um transição para cada símbolo a partir de um estado.
Do ponto de vista da tabela de transição, a restrição introduzida pelos autómatos fini-
tos determinista, implica que cada posição da tabela só contém um único estado. Se
cada estado for representado pelo seu número, basta representar o conjunto vazio por
um número inválido, correspondente a uma situação de erro, por exemplo -1. Assim,
cada expressão regular é representada por uma tabela de transição, a que teremos de
acrescentar uma coluna para indicar os estados finais.
Por outro lado, como o autómato é determinista, não existe necessidade de tentar di-
versas transições para encontrar uma solução válida. De facto, ou existe uma transição
válida ou a sequência de entrada não obedece à expressão regular que originou a tabela.
Desta forma, por cada carácter lido da sequência de entrada, o analisador executa um
passo, consultando a tabela que indica o estado seguinte. Ou seja, em linguagem C,
algo do tipo,
int lexical(int tabela[][256], int final[]) {
int ch, estado = 0;
while ((ch = getchar()) != EOF)
if ((estado = tabela[estado][ch]) == EOF) return FALSE;
return final[estado];
}
onde a tabela suporta todos os 256 caracteres que podem ser devolvidos pela função de
leitura getchar() e EOF representa quer o fim da sequência de entrada, quer o estado
de erro na tabela. A tabela final tem tantos elementos quantos os estados, ou seja o
número de linhas da tabela, indicando se cada estado é final ou não.
34 CAPÍTULO 2. LINGUAGENS REGULARES
2.2.5 Conversão por construção de subconjuntos
Se uma linguagem é aceite por um autómato finito não determinista então existe um
autómato finito determinista que aceita essa mesma linguagem. 5 O algoritmo de cons-
trução de subconjuntos permite obter um autómato finitos determinista a partir de um
não determinista, através de uma procura em largura.
A construção de subconjuntos inicia-se no estado inicial e, a partir deste estado, calcula-
se todos os restantes estados que se podem atingir a partir deste estado apenas através
de transições vazia. Este conjunto de estados, incluindo o estado inicial, é designado
por fecho − ε({q0}) e passa a representar o estado inicial do autómato finito determi-
nista, que designaremos por I0. A partir de cada um dos estados que contituem I0
vamos determinar quais os estados que são atingidos através de uma só transição para
cada um dos símbolos do alfabetoΣ. Estes novos conjuntos, designados pormove(I0, a),
onde a ∈ Σ, formam o núcleo dos novos estados deterministas. O estado determinista
é completamente calculado através do fecho − ε(move(I0, a)), para cada símbolo. No
entanto, se o núcleo de um novo estado é igual ao núcleo de um estado já existente, não
é necessário calcular o seu fecho, pois trata-se de uma repetição do estado anterior, que
identificaremos colocando o estado entre parênteses e colocaremos ... para designar os
restantes estados do fecho. O processo termina quando não houver mais estados deter-
ministas por calcular. Os estados deterministas considerados finais são todos aqueles
que contenham pelo menos um estado final do autómato não determinista, que repre-
sentaremos colocando um quadrado à volta do estado.
Para construir os subconjuntos utilizaremos uma tabela com 5 colunas, que representam
respectivamente: o estado determinista a calcular, o símbolo de entrada a considerar, o
núcleo não determinista que obtém, o restante fecho − ε e, finalmente, o novo estado
determinista. Notar que o estado determinista indicado na última coluna é constituído
pelos estados não deterministas das duas colunas anteriores.
Exemplo 2.6 A tabela de construção de subconjuntos da expressão regular do exemplo 2.3 re-
presentada pelo autómato finito não determinista do exemplo 2.5 é
5teorema 2.1 de [HU79]
2.2. AUTÓMATOS FINITOS 35
estado entrada move fecho− ε\move novo estado
0 1, 2, 3, 7, 8 I0
I0 a 4, 9 1, 2, 3, 6, 7, 8, 10 I1
b 5 1, 2, 3, 6, 7, 8 I2
I1 a 4, 9 . . . (I1)
b 5, 11 1, 2, 3, 6, 7, 8, 12 I3
I2 a 4, 9 . . . (I1)
b 5 . . . (I2)
I3 a 4, 9 . . . (I1)
b 5, 13 1, 2, 3, 6, 7, 8 I4
I4 a 4, 9 . . . (I1)
b 5 . . . (I2)
A partir da tabela, e eliminando as duas colunas referentes aos estados do autómato
não determinista, ficamos com as transições do autómato determinista. O estado da
primeira coluna tem uma transição etiquetada pelo símbolo da segunda coluna para
o estado da última coluna. A partir desta informação é possível construir a tabela de
transição ou a representação gráfica.
Exemplo 2.7 A tabela do exemplo 2.6 permite determinar o diagrama de transição, de onde
eliminámos o prefixo I pois já não existe confusão com os estados não deterministas,
ffifl
�fi
��
ff�
��
ff�
��
ff�
��
ff�
��
ff�
- - - -
?��/
SSo
ff
��7
-
J
J^
0 3 4
2
b
b
b
a bb
a
a
a
a
1
A correspondente tabela de transições pode ser igualmente deduzida da tabela do exemplo 2.6 ou
do diagrama de transição acima,
estado a b
0 1 2
1 1 3
2 1 2
3 1 4
4 1 2
36 CAPÍTULO 2. LINGUAGENS REGULARES
A representação computacional da tabela é directa, contendo apenas duas colunas pois o alfabeto
tem apenas dois elementos.
2.2.6 Minimização da tabela
O número de estados do autómato finito determinista obtido através da construção de
subconjuntos não é, necessariamente, mínimo. De facto, é frequente encontrar estados
absolutamente equivalentes a outros, podendo ser fundidos num só estado. O número
destes estados pode ser significativo para tabelas que representam linguagens regulares
de interesse prático.
O algoritmo de Hopcroft permite determinar os estados equivalentes a partir de suces-
sivas partições dos estados calculados. A partição inicial é constituída por três grupos,
um contendo os estados finais, outra os estados não finais e uma última contendo o
estado de erro, correspondente ao conjunto vazio. De facto, mesmo que existissem esta-
dos equivalentes entre esses grupos a sua fusão implicaria a perda da informação sobre
se a sequência era aceite ( estado final ) ou não.
O algoritmo consiste em fragmentar os grupos iniciais em outros subgrupos, se os res-
pectivos estados não poderem ficar juntos. Para que os estado possam permanecer num
mesmo grupo é necessário que, qualquer que seja o símbolo de entrada, todos esses es-
tados transitem para estados que, também eles, pertençam a um mesmo grupo. Como
em cada nova interação, que se designa por partição, vão sendo criados novos grupos,
estados que antes pertenciam ao mesmo grupo podem não poder continuar juntos. O
processo repete-se até que não sejam criados novos subgrupos.
Notar que os grupos criados podem conter vários estados, desde que estes contenham
todos transições para os mesmos estados da partição anterior. Também não se deve
assumir que apenas estados com entradas iguais na tabela é que podem ser agrupados,
podendo ter transições para estados distintos de um mesmo grupo para cada símbolo.
Exemplo 2.8 A tabela do exemplo 2.7 não tem estado de erro pelo que a partição inicial contém
apenas dois grupos. Para mais, todos os estados transitam para o estado 1 com o símbolo de
entrada a. Desta forma, e neste caso, apenas o símbolo b pode forçar a separação dos estados. Dos
quatro estados não terminais, apenas o estado 3 transita com b para um grupo diferente, ou seja
o grupo dos estados finais. Assim, o estado 3 deve ser separado dos restantes passando a haver 3
grupos na nova partição. Agora é o estado 1 que transita também com b para umgrupo distinto
dos outros dois estados, pois na nova partição o estado 3 já está separado.
2.2. AUTÓMATOS FINITOS 37
ffifl
�fi
��
ff�
4
ffifl
�fi
��
ff�
4
ffifl
�fi
��
ff�
4
��
ff�
��
ff�
��
ff�
�
�
�
�
�
�
�
�
?
6
-
?
6
��7
-
@
@
-
?
ZZ}
@
@
ff
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
6 ��7 ��7
1
3
0, 20, 1, 2
3
b
a
b
b
aa
ab
b
a,b
0, 1, 2, 3
aa,b
P PP0 1 2
a a
Notar que os estados 0, 1, 2, 3 da partição P0 transitam para eles próprio com o símbolo a, mas
divergem quanto às transições com o símbolo b. Conseqeuntemente, na partição P1 o estado 3
é separado pois é o único que transita para fora do grupo com o símbolo b. No entanto, os três
estados restantes ainda não concordam quanto à transição com o símbolo b, pois com a saída do
estado 3 do grupo apareceram novas inconsistências. Desta forma, na partição P2 o estado 1 é
igualmente isolado, já sendo possível representar todas as transições do autómato inicial. Assim,
apenas os estados 0 e 2 podem ser agrupados.
Graficamente podemos representar as sucessivas partições, de uma forma mais simples, por uma
árvore,
�
�
��
@
@
@R
-
S
S
SSw
-PPPPPPq
-
-- 44
3
1
3
4
0, 2
0P P P1 2
0, 1, 2, 3 0, 1, 2
A partir do autómato finito determinista, na sua representação gráfica ou por tabela,
pode-se obter directamente uma gramática regular. Para tal basta considerar os tipos
de regras apresentadas em 2.1.2, transformando cada transição δ(qi, a) = qj numa regra
Si → aSj e acrescentando para cada estado final qf uma regra Sf → ε.
38 CAPÍTULO 2. LINGUAGENS REGULARES
Exemplo 2.9 Considerando a tabela, já minimizada, do exemplo 2.7, obtém-se directamente a
gramática regular correspondente, que representaremos com 4 símbolos não terminais cujo índice
reproduz o número do estado do autómato,
estado a b
0 1 0
1 1 3
3 1 4
4 1 0
S0 → a S1 | b S0
S1 → a S1 | b S3
S3 → a S1 | b S4
S4 → a S1 | b S0 | ε
2.2.7 Construção de Kleene∗
Se uma linguagem é aceite por um autómato finito determinista, então pode ser descrita
por uma expressão regular 6. Ou seja, se a partir do autómato finito determinista gerado
é possível produzir a expressão regular inicial, ou uma expressão regular equivalente.
Assim, fecha-se o ciclo e garante-se a correcção de todo o processo.
Considere-se que Rkij é o conjunto de todas as sequências do autómato entre os estado
qi e qj sem passar por nenhum estado com número superior a k. Notar que para passar
por um estado é necessário entrar e sair. Logo i ou j podem ser maiores que k. Uma vez
que nenhum estado tem um número superior a n, Rnij representa todas as sequências
entre qi e qj .
O autómato não pode ter entradas no estado inicial, logo caso tais entradas existam é
necessário acrescentar um novo estado inicial com uma transição vazia para o anterior
estado inicial.
O algoritmo consiste em introduzir as transições existentes em R0ij = {a|δ(qi, a) = qj} ∪
{ε|i = j}, ou seja, se i = j então ε faz parte de R0ij e se existirem transições directas entre
os estados qi e qj então os símbolos dessas transições também fazem parte de R0ij .
Os restantes valores são calculados recursivamente com base nos anteriores através da
expressão Rkij = R
k−1
ik (R
k−1
kk ) ∗R
k−1
kj |R
k−1
ij para k ≤ n onde n é o estado de maior número.
Ou seja, construindo caminhos sucessivamente mais compridos e que passam por mais
estados. As expressão regular final é a união de todas as expressões regulares entre o
estado inicial e cada um dos estados finais L = |sj∈SFR
n
0j .
Exemplo 2.10 Considerando a tabela do exemplo 2.7, verifica-se que como existe um só estado
terminal 4 , uma expressão regular que representa o autómato é obtida por R404. A expressões
R0ij que representam as todas as transições possíveis entre os vários estados,
6teorema 2.4 de [HU79]
2.3. ANALISADOR LEXICAL 39
R0ij j = 0 j = 1 j = 2 j = 3 j = 4
i = 0 ε a b ∅ ∅
i = 1 ∅ a | ε ∅ b ∅
i = 2 ∅ a b | ε ∅ ∅
i = 3 ∅ a ∅ ε b
i = 4 ∅ a b ∅ ε
Calculando apenas as expressões intermédias necessárias ao cálculo de R404, e simplificando
R404 = R
3
04(R
3
44) ∗R
3
44 | R
3
04 = R
3
04(R
3
44)∗, temos,
Rkij expressão resultante simplificação
R102 a(a | ε) ∗ ∅ | b b
R103 a(a | ε) ∗ b | ∅ a+ b
R104 a(a | ε) ∗ ∅ | ∅ ∅
R122 a(a | ε) ∗ ∅ | (b | ε) b | ε
R123 a(a | ε) ∗ b | ∅ a+ b
R124 a(a | ε) ∗ ∅ | ∅ ∅
R132 a(a | ε) ∗ ∅ | ∅ ∅
R133 a(a | ε) ∗ b | ε (a+ b) | ε
R134 a(a | ε) ∗ ∅ | b b
R142 a(a | ε) ∗ ∅ | b b
R143 a(a | ε) ∗ b | ∅ a+ b
R144 a(a | ε) ∗ ∅ | ε ε
R203 b(b | ε) ∗ (a+ b) | (a + b) b ∗ a + b
R204 b(b | ε) ∗ ∅ | ∅ ∅
R233 ∅(b | ε) ∗ (a+ b) | (a+ b | ε) a+ b | ε
R234 ∅(b | ε) ∗ ∅ | b b
R243 b(b | ε) ∗ (a+ b) | (a + b) b ∗ a + b
R244 b(b | ε) ∗ ∅ | ε ε
R304 (b ∗ a+ b)(a + b | ε) ∗ b | ∅ b ∗ (a + b) + b
R344 (b ∗ a+ b)(a + b | ε) ∗ b | ε b ∗ (a + b) + b | ε
R404 (b ∗ (a+ b) + b)(b ∗ (a + b) + b | ε)∗ (b ∗ (a + b) + b)+
A expressão resultante obtida (b ∗ (a+ b) + b)+ pode ser convertida em (b ∗ (a ∗ ab) ∗ a ∗ abb)+
que é equivalente à expressão original (a|b) ∗ abb.
2.3 Analisador lexical
Saber se uma frase, ou sequência de entrada, obedece a uma gramática regular é apenas
parte do problema. Na realidade, a análise lexical de linguagens deve conseguir identi-
40 CAPÍTULO 2. LINGUAGENS REGULARES
ficar repetições de subconjuntos da linguagem e permitir associar acções à identificação
desses conjuntos. Só dessa forma é possível produzir resultados como consequência da
identificação de componentes da linguagem.
A solução consiste em dividir a linguagem numa união de expressões regulares L =
(r1|r2| . . . |rn)∗. Devido às propriedades de fecho das expressões regulares sobre a ope-
ração de união, podemos subdividir o problema. Para tal basta considerar um estado
inicial que deriva, através de transições vazias, cada uma das expressões regulares. O
autómato resultante considera, simultaneamente, as diversas expressões regulares.
Para determinar qual a expressão regular reconhecida, é necessário associar cada estado
final com a respectiva expressão regular. O processamento de uma frase pode atravessar
diversos estados finais, só parando quando se atinge um estado de erro. Neste ponto é
necessário procurar o último estado final atingido e considerar reconhecida a respectiva
expressão regular. O analisador recomeça o processamento no estado inicial e os sím-
bolos lidos após o último estado final considerado devem ser novamente processados.
Notar que este processamento considera sempre o reconhecimento da sequência de en-
trada mais comprida. Convém não confundir com a expressão regular mais comprida.
Caso contrário, as sequências de entrada curtas mas válidas impediriam o reconheci-
mento das restantes.
A minimização da tabela segue o mesmo princípio enunciado atrás, mas a partição ini-
cial tem de considerar os estados finais de expressões regulares distintas como perten-
cendo a grupos iniciais distintos. Assim, além do grupo de estados não terminais e do
grupo de erro, é necessário considerar tantos grupos de estados finais quantas as ex-
pressões regulares existentes. Se o grupo de estados finais de uma expressão regular for
um conjunto vazio, então essa expressão regular nunca é reconhecida.
Exemplo 2.11 O autómato finito não determinista que descreve a linguagem composta pela
união das expressões regulares aaa e (a|b) pode ser representada por,
��
ff�
-a��
ff���
ff�
��
ff�
��
ff�
��
ff�
ffifl
�fi
��
ff�
��
ff�
��
ff�
��
ff�
ffifl
�fi
��
ff�-
�
�
���
Z
Z
Z~
-- -
�
�3
-
Q
QQs
ZZ~
�
�>
0
e
e
aa1 2 a 43
r1
b
e
e e
e
5 10
r2
97
86
A tabela de análise resultanteé
2.3. ANALISADOR LEXICAL 41
estado a b regra
0 1 2
1 3 E 2
2 E E 2
3 4 E
4 E E 1
Notar que os estados 2 e 4 não podem ser agrupados, embora sejam ambos finais e contenham as
mesmas transições, pois pertencem a grupos finais distintos. Relembra-se que os estados podem
ser agrupados mesmo que não tenham transições iguais, basta que tenham transições para estados
que pertençam ao mesmo grupo.
A análise da frase aa termina no estado 3, depois de ter passado pelo estado 1. Como este estado
não é final é necessário procurar o último estado final, neste caso o estado 1. Caso não exista um
estado final no caminho percorrido a sequência de entrada é incorrecta. No caso da frase aa é
necessário recuar um estado, e consequentemente repor o último símbolo de volta na sequência
a processar, aceitando a expressão regular (a|b). O analisador é depois reiniciado no estado 0 e
processa novamente a letra a, que acabou de repor, aceitando mais uma vez a mesma expressão
regular e terminando o processamento por ter atingido o fim da frase.
No caso de um estado final, do autómato determinista, conter mais de um estado fi-
nal do autómato não determinista, existe um conflito. O conflito é resolvido, em geral,
optando por uma das possíveis expressões regulares. A solução mais frequentemente
adoptada pelas ferramentas consiste em considerar prioritária a expressão regular que
surje em primeiro lugar na especificação da gramática. Contudo, esta solução obriga a
uma cuidada escrita das expressões regulares, por forma a garantir que todas são devi-
damente reconhecidas. Notar que os conflitos surjem apenas entre expressões regulares
que possam reconhecer sequências de igual comprimento.
Exemplo 2.12 Considere-se a linguagem descritas pela união das seguintes expressões regulares
identificadas por ordem de prioridade decrescente, bem como a tabela de análise resultante,
r1 aab
r2 aa
r3 (a|b)*
estado a b regra
0 1 2 3
1 3 2 3
2 4 2 3
3 4 5 2,3
4 4 2 3
5 4 2 1,3
da tabela de análise conclui-se que caso a expressão regular 3 tivesse prioridade sobre as restantes,
estas nunca seriam reconhecidas.
42 CAPÍTULO 2. LINGUAGENS REGULARES
2.3.1 Compactação da tabela
Na prática, na tabela de um linguagem, com um alfabeto constituídos pormuitos símbo-
los distintos, é frequente encontrar colunas iguais. Também podem existir linhas iguais
se pertencerem a grupos de minimização distintos, mas tais ocorrências são escassas.
Notar que a utilização de digitos decimais é em geral indistinto do seu valor, ficando
cada uma das 10 colunas com entradas iguais na tabela. O mesmo pode acontecer com
certas classes de caracteres e operadores ou separadores.
Estes conjuntos de caracteres, cujas entradas na tabela têm os mesmos valores para to-
dos os estados do autómato finito determinista minimizado, são designados por classes
de equivalência. A compactação da tabela é efectuada introduzindo um vector de com-
primento igual ao alfabeto da linguagem, onde cada entrada indica a coluna da tabela
a utilizar. Nesta situação podem-se remover todas as colunas duplicadas, apontando
todos os símbolos da mesma classe de equivalência para a mesma coluna.
Do ponto de vista do analisador lexical é desejável que todos os operadores e separado-
res constituídos por um único carácter possam ser reconhecidos por uma só regra, por
exemplo [− + ∗/(); , :], em vez de se reconhecer individualmente cada um. Na grande
maioria dos casos, esta solução não tem implicações na restante análise das linguagens
pois os analisadores sintácticos já reconhecem caracteres individuais. O reconhecimento
individual de cada carácter obriga a considerar expressões regulares distintas, o que
obriga criar mais estados finais distintos.
A tabela de análise resultante, após a compressão das colunas iguais, pode ainda ser
mais comprimida através de métodos genéricos de compressão de matrizes esparsas.
Estes métodos, que trataremos mais adiante, permitem tirar partido do facto de certo
valor, por exemplo 0, existir em mais de metade das entradas da tabela. Embora as
tabelas de análise lexical não apresentem tais características, ao contrário das tabelas de
análise sintáctica, pode-se considerar entradas por omissão ( default, em inglês ). Para
tal cria-se uma nova coluna na qual se coloca o valor mais frequente em cada linha.
As ocorrências desse valor em cada linha são substituídas por uma entrada especial, em
geral codificada com o valor 0, o que significa que quando este valor é encontrado deve-
se considerar a entrada por omissão. A tabela resultante passa a conter uma quantidade
significativa de valores por omissão, podendo em casos reais atingir 90% de todas as
entradas da tabela. A tabela pode agora ser compactada por algoritmos genéricos de
compressão de matrizes esparsas.
2.3. ANALISADOR LEXICAL 43
2.3.2 Analisadores explicitamente codificados
Até ao momento considerámos que o autómato finito determinista era codificado como
uma tabela, como a do exemplo 2.7, e que um pequeno programa, como o apresentado
na secção 2.2.4, determina o estado seguinte com base na tabela e carácter lido. Con-
tudo, existem soluções que não utilizam tabelas e que se designam por explicitamente
codificados ou hardcoded. Estas soluções são em geral mais rápidas à custa de um exe-
cutável de maiores dimensões, em especial no caso de máquinas RISC.
Consideremos uma abordagem baseada em saltos (gotos) que, contudo, não pode ser
utilizada em linguagens sem essa instrução como o Java. Cada estado é identificado
por uma etiqueta, efectuando saltos de acordo com carácter lido logo após a etiqueta.
Por exemplo, a partir do estado 4 da tabela do exemplo 2.9 obtém-se
state4:
in = *input++;
if (in == ’a’) goto state1;
if (in == ’b’) goto state0;
if (in == 0) return 1; /* só para estados finais */
goto error; /* termina cada estado */
Outra solução possível, sem recurso a saltos, consiste em codificar cada estado como
uma função, sendo os saltos para as etiquetas subtituídos por chamadas às rotinas que
representam os respectivos estados. No entanto, esta solução não é tão eficiente, pois
as chamadas e retorno das rotinas são em geral operações lentas. Além disso, utiliza a
pilha do processador para coleccionar os estados por onde vai passando. Assim, a pro-
fundidade máxima da pilha limita a maior sequência a ser reconhecida. Tal limitação
não tem vantagem pois, ao contrário dos analisadores sintácticos descendentes predi-
tivos que veremos adiante, a informação deixada na pilha não tem interesse prático
(excepto, eventualmente, para efeitos de backtracking). A partir da gramática regular do
exemplo 2.9, a regra S4 correspondente ao estado 4 pode ser codificada como
static int state4() {
register char in = *input++;
if (in == ’a’) return s1();
if (in == ’b’) return s0();
return 1; /* estados não finais retornam 0 */
}
44 CAPÍTULO 2. LINGUAGENS REGULARES
2.4 Exercícios
Exercício 2.1 Considere o diagrama de transição do autómato finito não determinista do exem-
plo 2.3. Determine, através do método dos subconjuntos, a tabela de transição do autómato finito
determinista. Compare o resultado que obteve com a tabela do exemplo 2.9.
Exercício 2.2 Considere a expressão regular (aa|ab|ba|bb)∗ definida sobre o alfabetoΣ = {a, b}:
1. Construa o autómato finito não determinista (NFA) pelo algoritmo de Thompson a que
corresponde à expressão regular.
2. Construa algoritmicamente o autómato finito determinista (DFA) equivalente a partir do
NFA da alínea anterior, e represente o seu diagrama de estados.
Explicite quais os estados do NFA realizado em cada estado do DFA.
3. Minimize algoritmicamente o número de estados do autómato finito determinista (DFA),
indicando todas as partições intermédias e respectivos grupos.
Exercício 2.3 Construa o diagrama de estados do autómato finito determinista da expressãoregular (ε|b)((ε|a)b)∗a, indicando em quantos passos é analisada a sequência de entrada bbabba.
Construa a tabela de transição minimizada e justifique quantos passos são agora necessários para
processar a mesma sequência de entrada.
Exercício 2.4 Construa a tabela de transição determinista minimizada das seguintes expressões
regulares:
1. a(a|b) ∗ a
2. (a?b∗)∗
3. a ∗ ba ∗ ba∗
4. (a|b) ∗ abb(a|b)∗
5. a(a|b) + b
6. (aba|bab)∗
2.4. EXERCÍCIOS 45
Exercício 2.5 Construa a tabela de transição determinista minimizada da gramática regular,
sobre o alfabeto {x, y, z} e onde A é símbolo não terminal inicial,
A → xB
B → y C | z D | ε
C → y C | z D | ε
D → y C | z D | ε
Indique em quantos passos é processada a sequência de entrada xxzy.
Exercício 2.6 Considere a sequência ordenada de expressões regulares aa, a∗, a|b definida sobre
o alfabeto Σ = {a, b}:
1. Determine algoritmicamente os subconjuntos do autómato finito determinista (DFA) equi-
valente a partir do autómato finito não determinista (NFA) construído pelo algoritmo de
Thompson a que corresponde a sequência ordenada de expressões regulares.
Explicite quais os estados do NFA realizado em cada estado do DFA.
2. Minimize algoritmicamente o número de estados do autómato finito determinista (DFA),
indicando todas as partições intermédias e respectivos grupos.
Represente a tabela de transição de estados resultante.
3. Indique, justificando, em quantos passos é processada a sequência de entrada: aabbaaa.
Exercício 2.7 Construa a tabela de análise da linguagem definida pela sequência ordenada das
seguintes expressões regulares ab, ab∗, a|b definida sobre o alfabeto Σ = {a, b}. Indique, justifi-
cando, em quantos passos é processada a sequência de entrada: abaabb.
Exercício 2.8 ∗ Determine uma expressão regular que defina a linguagem descrita pela tabela
de análise:
est a b
0 1 2
1 E 2
2 1 2
Exercício 2.9 Apresente a tabela de análise minimizada e compactada que analisa a linguagem
definida pela expressão regular u(a(e|o)) ∗ i, definida sobre o alfabeto Σ = {a, e, i, o, u}.
Capítulo 5
Análise sintáctica ascendente por tabela
Um analisador ascendente constroí a árvore sintáctica das folhas para a raiz. Ao con-
trário da análise descendente, que necessita prever qual a regra a utilizar, a análise
ascendente atrasa a escolha da regra até ter lido todos os símbolos que constituem a
derivação ( lado direito de uma produção ), mais os símbolos de antevisão necessários.
A principal decisão de um analisador ascendente consiste em determinar quando uma
sequência de símbolos corresponde a alguma das regras da gramática. Esta tarefa não
é trivial, pois pode haver mais de uma regra com a mesma derivação e casos em que,
apesar da semelhança, não se tratam de derivações possíveis.
Como os analisadores ascendentes substituem uma derivação de uma regra pelo sím-
bolo não terminal que a origina são globalmente designados por LR(k). A análise LR(k)
é efectuada lendo a sequência de entrada da esquerda para a direita (Left to right), em-
parelhando as derivações das regras da direita para esquerda (Right to left), usando no
máximo k símbolos de antevisão. Estes analisadores são os mais utilizados pois são
menos limitativos que os correspondentes analisadores preditivos descentes LL.
Neste capítulo estudaremos em detalhe apenas os analisadores mais simples e menos
exigentes, em termos da dimensão das tabelas necessárias. Contudo, a análise determi-
nista da grande maioria das linguagens usadas em computação pode ser efectuada com
base em gramáticas processáveis por analisadores LALR(1). Os analisadores LALR(1)
apresentam tabelas da mesma dimensão das formas mais simples SLR(1) e LR(0), mas
permitem analisar um maior número de gramáticas. Relembra-se que uma mesma lin-
guagem pode ser descrita por diversas gramáticas equivalentes, bastando encontrar
uma dessas gramáticas que seja pelo menos LALR(1).
O funcionamento de um analisador ascendente baseia-se em duas operações fundamen-
tais: o deslocamento (shift) de símbolos da sequência de entrada para a pilha auxiliar e
a redução (reduce) dos símbolos de derivação de uma regra ao símbolo não terminal que
57
58 CAPÍTULO 5. ANÁLISE SINTÁCTICA ASCENDENTE POR TABELA
a origina. Inicialmente a pilha começa vazia, sendo deslocados símbolos até ser encon-
trada uma derivação válida. O processamento termina quando se atínge uma operação
de aceitação (accept) ou de erro (error).
5.1 Construção do analisador
Para que a análise determinista de uma linguagem por um analisador ascendente seja
correcta basta que os deslocamentos e a aceitação sejam permitidos apenas em certas
situações. A diferença entre os analisadores LR(0), SLR(1) e LALR(1) consiste apenas
na colocação das reduções. No entanto, se uma redução for erradamente executada,
o seu resultado não poderá ser deslocado, pelo que as sequências de entrada erradas
são igualmente detectadas, mas com algum atraso. A determinação dos deslocamentos
é efectuada com base num autómato determinista muito semelhante ao utilizado na
análise das linguagens regulares.
gramática aumentada Para que a sequência de entrada seja correctamente detectada
pela gramática é necessário introduzir uma regra auxiliar que explicite o fim do pro-
cessamento. Desta forma, não é possível terminar prematuramente o processamento,
deixando símbolos por processar. Esta regra auxiliar contém uma só derivação com o
símbolo inicial da gramática e o símbolo $, símbolo que utilizaremos para designar o
fim da sequência de entrada (end of file).
Exemplo 5.1 Considerando uma gramática com símbolo inicial S,
S → ’(’ A ’)’
A → ’a’
| S
| A ’,’ ’a’
a gramática aumentada inclui também a regra S’→ S $, passando S’ a ser o novo símbolo inicial
da gramática aumentada, ou seja,
S’ → S $
S → ’(’ A ’)’
A → ’a’
| S
| A ’,’ ’a’
5.1. CONSTRUÇÃO DO ANALISADOR 59
estados do autómato A análise ascendente baseia-se na construção de um autómato
não determinista e na sua conversão em determinista, pelos mesmos processos utili-
zados para o tratamento de linguagens regulares. Para tal, cada regra é dividida nos
diversos estados em que o processamento da regra se pode encontrar, designados por
itens, que correspondem aos estados do autómato não determinista. Assim, uma regra
em que a derivação é composta porN símbolos, terminais ou não terminais, é composta
por N+1 itens, sendo o primeiro correspondente ao estado antes de iniciar o processa-
mento da regra, o segundo após consumir o primeiro símbolo e o último após o proces-
samento de todos os símbolos da derivação da regra. A cada um destes itens é atribuído
um número único que destingue cada estado do autómato finito não determinista. Os
diversos itens de cada regra são ligados, pela ordem de processamento, por transições
que consomem os símbolos da derivação da regra.
Exemplo 5.2 Considerando a primeira regra do exemplo 5.1 S→ ’(’ A ’)’ , são gerados qua-
tro itens, onde o símbolo • representa o ponto de processamento da regra no respectivo estado do
autómato não determinista,
S→ • ’(’ A ’)’ 1
′(′
−→ S→ ’(’ • A ’)’ 2
A
−→ S→ ’(’ A • ’)’ 3
′)′
−→ S→ ’(’ A ’)’ • 4
Para tornar a leitura mais legível e compacta representaremos cada estado, do autómato
finito não determinista, pelo seu número colocado no ponto de processamento da regra,
ficando a regra do exemplo 5.2 reduzida a S→ 1 ’(’ 2 A 3 ’)’ 4.
transições vazias Além das transições entre os diversos itens de uma regra, etiqueta-
das pelos símbolos consumidos, é necessário considerar que ao processar um símbolo
não terminal devem ser consideradas todas as regras que esse símbolo pode derivar.
Assim, no item que antecede o processamento de um símbolo não terminal inserem-se
transições vazias para todos os itens iniciais das regras que esse símbolo não terminal
deriva. Na representaçãoque utilizaremos, não etiquetaremos essas transições com o
símbolo ε, como fizemos nas linguagens regulares, nem representaremos por completo
o arco que une os estados. Desta forma, o item 2 da regra do exemplo 5.2 será repre-
sentado por 2 ր A, significando que no item 2 existem transições vazias para os itens
iniciais das três regras que o símbolo A deriva. Para posterior referência, indicaremos
antes de cada regra o seu número de ordem, correspondendo r0 ( regra zero ) à regra au-
xiliar da gramática aumentada. Tal representação pretende apenas simplificar e tornar
mais compacto e legível o autómato, sendo funcionamente equivalente à representação
utilizada nas linguagens regulares.
60 CAPÍTULO 5. ANÁLISE SINTÁCTICA ASCENDENTE POR TABELA
Exemplo 5.3
O autómato finito não determinista da gramática aumentada usada no exemplo 5.1 fica
r0 S’ → 0 ր S 1 $
r1 S → 2 ’(’ 3 ր A 4 ’)’ 5
r2 A → 6 ’a’ 7
r3 | 8 ր S 9
r4 | 10 ր A 11 ’,’ 12 ’a’ 13
aconselha-se a numerar os itens sequencialmente dentro de cada regra por forma a facilitar a
consistência das transições, embora apenas se exija que cada item tenha um número distinto de
todos os outros do autómato finito não determinista.
Notar que na regra auxiliar da gramática aumentada existem apenas dois itens, pois não é possí-
vel passar além do fim da sequência de entrada.
autómato determinista A construção do autómato finito determinista segue exacta-
mente o mesmo processo utilizado nas linguagens regulares. No entanto, como número
de símbolos é potencialmente grande omitiremos todas as transições que produzam es-
tados deterministas que sejam conjuntos vazios.
Exemplo 5.4
A determinação dos estados do autómato determinista do exemplo 5.3 resume-se a
estado entrada move fecho− ε\move novo estado
0 2 I0
I0 S 1 I1
’(’ 3 6, 8, 10, 3 I2
I2 A 4, 11 I3
’a’ 7 I4
S 9 I5
’(’ 3 . . . (I2)
I3 ’)’ 5 I6
’,’ 12 I7
I7 ’a’ 13 I8
5.1. CONSTRUÇÃO DO ANALISADOR 61
construção da tabela de análise Tal como no caso das linguagens regulares, também
a análise sintáctica ascendente utiliza uma tabela de análise. No entanto, para o seu
processamento é necessária uma pilha de dados auxiliar, onde são colocados tempora-
riamente os símbolos até que uma regra seja identificada e a sua derivação substituída
pelo símbolo não terminal que lhe dá origem. Neste caso, a tabela inclui cinco tipos de
operações distintas:
deslocamento (shift) : corresponde a retirar o símbolo da sequência de entrada e co-lo-
cá-lo no topo da pilha, seguido do estado indicado na operação de deslocamento.
Por exemplo s2 ( ou seja, shift 2 ), corresponde a deslocar o símbolo que estiver
à cabeça da sequência de entrada e mover para o estado 2 ( do autómato finito
determinista ).
movimento (goto) : corresponde a mover para o estado indicado, colocando-o no topo
da pilha, representado por g2 ( ou seja, goto 2 ).
erro (error) : não é representado na tabela de análise, correspondendo às posições dei-
xadas em branco.
redução (reduce) : corresponde a substituir os símbolos de derivação de uma regra exis-
tente no topo da pilha pelo símbolo não terminal que deriva essa mesma regra. É
representado por r2 ( ou seja, reduce 2 ), mas apenas neste caso o número 2 não
representa um estado do autómato mas sim o número da regra
aceitação (accept) : corresponde à redução da regra auxiliar da gramática aumentada,
representando o fim do processamente, podendo apenas existir na coluna corres-
pondente ao fim do processamento ( representado por $ ).
A tabela de análise é constituída por todos símbolos terminais, incluindo o fim de pro-
cessamento $ ( que pode ser lido de um ficheiro ), e todos os símbolos não terminais
da gramática inicial ( exclui-se a regra auxiliar da gramática aumentada ). Muita da
literatura separa a tabela de deslocamentos da tabela de movimentos pelo que, embora
utilizaremos uma única tabela, explicitaremos a sua individualização por uma dupla
barra.
O autómato finito determinista permite preencher as operações de deslocamento e mo-
vimento da tabela de análise. O preenchimento é idêntico, diferindo apenas no facto
de se tratar de um deslocamento para símbolo terminais ( aqueles que podem ser ob-
tidos da sequência de entrada ) e de um movimento para os símbolos não terminais.
Com base no cálculo do autómato finito determinista, e ignorando as duas colunas que
contêm os estados não deterministas, ficamos com os valores a preencher
62 CAPÍTULO 5. ANÁLISE SINTÁCTICA ASCENDENTE POR TABELA
Exemplo 5.5
Eliminando os estados do autómato finito não determinista da tabela do exemplo 5.4, o preen-
chimento das operações de deslocamento e movimento na tabela de análise é directo. As duas
primeiras colunas designam, por ordem, a linha e a coluna da tabela do autómato finito determi-
nista e a última designa o valor a preencher nessa posição.
estado entrada novo estado
I0
I0 S I1
’(’ I2
I2 A I3
’a’ I4
S I5
’(’ (I2)
I3 ’)’ I6
’,’ I7
I7 ’a’ I8
′(′ ′a′ ′)′ ′,′ $ S A
0 s2 g1
1
2 s2 s4 g5 g3
3 s6 s7
4
5
6
7 s8
8
5.1.1 Gramáticas LR(0)
O autómato LR(0) anterior permite construir tabelas para analisadores LR(0), SLR(1) e
LALR(1), diferindo apenas na forma como as reduções são inseridas na tabela. Como
já foi referido, são os deslocamentos e movimentos que determinam se a sequência de
entrada está correcta ou não, pelo que mesmo que sejam colocadas reduções desneces-
sárias, mais tarde ou mais cedo a falha será detectada.
O analisador mais simples é o analisador LR(0), que como o nome sugere não usa sím-
bolos de antevisão ( representado pelo número entre parenteses, ou seja 0 símbolos de
antevisão ). Para compreender o seu funcionamento basta representar graficamente o
autómato finito determinista, considerando que uma vez atingido o último estado de
uma regra esta fica pronta a ser reduzida.
Tal como no processamento de expressões regulares, a determinação de quais os estados
do autómato finito determinista em que as diversas regras são reduzidas baseia-se na
identificação dos estados finais de cada regra no autómato finito não determinista. As-
sim, todos os estados deterministas, que incluam esse estado não determinista, reduzem
a regra.
Exemplo 5.6 A representação gráfica do autómato finito determinista cálculado no exemplo 5.4
pode ser representado pela figura abaixo.
5.1. CONSTRUÇÃO DO ANALISADOR 63
I
I
I
I
I
I II
I r35
r1
r4
0
1
2
3
4
6
7 8
r2
S
A
S
’(’
’)’
’a’
’a’
’,’
’(’
acc (r0)
Como nos analisadores LR(0) não existem símbolos de antevisão, a redução será efectu-
ada para todos os símbolos terminais da linguagem em questão. Excepção feita à regra
auxiliar da gramática aumentada, que apenas pode ser reduzida para o símbolo de fim
de processamento $, pois para qualquer outro símbolo significaria que a sequência não
estava completamente processada.
Exemplo 5.7 A tabela de análise LR(0) para a gramática do exemplo 5.1 fica concluída com
o preenchimento das reduções das regras e da operação de aceitação para a regra auxiliar da
gramática aumentada. Todas as posições deixadas em branco representam situações de erro.
′(′ ′a′ ′)′ ′,′ $ S A
0 s2 g1
1 acc
2 s2 s4 g5 g3
3 s6 s7
4 r2 r2 r2 r2 r2
5 r3 r3 r3 r3 r3
6 r1 r1 r1 r1 r1
7 s8
8 r4 r4 r4 r4 r4
Notar que nenhuma linha da tabela pode ficar totalmente em branco, pois esse estado não seria
necessário. Da mesma forma, nenhuma coluna da tabela pode ficar totalmente em branco por
esse símbolo nunca seria processado. No caso de um símbolo terminal, significa que esse símbolo
nunca pode ser lido, enquanto no caso de um símbolo não terminal, significa que nenhuma das
regras que ele deriva é alguma vez reduzida ( uma vez que após uma redução existe sempre um
movimento, excepto paraa regra auxiliar ).
64 CAPÍTULO 5. ANÁLISE SINTÁCTICA ASCENDENTE POR TABELA
5.1.2 Análise ascendente por tabela
Oprocessamento de uma sequência de entrada por um analisador ascendente por tabela
utiliza as operações atrás referidas. Tal como no caso da análise preditiva descendente
por tabela, recorre-se a uma pilha. Neste caso, a pilha irá conter alternadamente estados
do autómato finito determinista e símbolos, terminais e não terminais, da gramática.
Inicialmente a pilha contém apenas o estado inicial ( sempre designado por 0 nos exem-
plos aqui apresentados ). A determinação da operação a realizar utiliza o elemento no
topo da pilha e o símbolo à cabeça da sequência de entrada, correspondendo respec-
tivamente às linha e coluna da tabela de análise. Após uma redução, o topo da pilha
fica com o símbolo não terminal que deriva a regra reduzida, utilizando-se neste caso
os dois elementos do topo da pilha para determinar a operação a realizar.
Exemplo 5.8 Considere-se a análise da sequência de entrada (a,a) através da tabela do exem-
plo 5.7 para a gramática do exemplo 5.1:
pilha entrada acção
0 (a, a)$ shift-2
0(2 a, a)$ shift-4
0(2a4 , a)$ reduce-2
0(2A , a)$ goto-3
0(2A3 , a)$ shift-7
0(2A3, 7 a)$ shift-8
0(2A3, 7a8 )$ reduce-4
0(2A )$ goto-3
0(2A3 )$ shift-6
0(2A3)6 $ reduce-1
0S $ goto-1
0S1 $ accept
No primeiro passo da análise procura-se na tabela o estado 0 ( topo da pilha ), correspondente à
primeira linha, e na coluna ’(’ a operação a executar, ou seja s2 ( shift-2 ). No terceiro passo, para
efectuar a redução da regra 2 necessitamos retirar do topo da pilha todos os símbolo que derivam a
regra e respectivos estados colocando em seu lugar o símbolo não terminal que deriva essa regra.
Neste caso apenas a 4 é retirado da pilha, sendo colocado o símbolo A, pois a regra 2 é apenas
A→ a. Para as restantes reduções do exemplo acima o processo é idêntico, mas para as regras 4
e 1, ou seja, A→ A′,′ a e S →′ (′A′)′, respectivamente. Notar que, ao contrário dos analisadores
preditivos descendentes, a pilha cresce da esquerda para a direita para que as derivações da regra
5.1. CONSTRUÇÃO DO ANALISADOR 65
apareçam na pilha pela mesma ordem que são escritas na gramática, apenas contendo os números
dos estados entre os símbolos.
Após cada redução existe sempre uma operação de movimento, utilizando-se os dois elementos
do topo da pilha para determinar as linha e coluna na tabela. Assim, no quarto passo, o topo da
pilha indica linha 2 e coluna A, ou seja, g3 ( goto-3 ).
5.1.3 Gramáticas SLR(1)
As gramáticas LR(0), ou seja aquelas que podem produzem tabelas LR(0) sem gerar
conflitos ( mais de uma operação por posição na tabela de análise ), são bastante restriti-
vas. Embora não tenha as limitações de recursividade ou factorização dos analisadores
preditivos descendentes, o método de construção LR(0) produz frequentemente con-
flitos. Para uma sequência de entrada correcta, uma regra só pode ser seguida pelos
seus símbolos de FOLLOW, todas as restantes reduções estão erradas. Assim, em vez
de efectuar a redução e vir a detectar o erro no próximo deslocamento, o método de
construção SLR(1) apenas preenche as reduções para os símbolos de FOLLOW.
Exemplo 5.9 Considerando o exemplo 5.1 temos que FOLLOW(S) = {$ , ′)′ , ′,′ } e FOL-
LOW(A) = {′)′ , ′,′ } logo a regra 1 reduz apenas nos três símbolos de FOLLOW e as regras
2, 3 e 4 nos dois símbolos atrás calculados, ficando a tabela
′(′ ′a′ ′)′ ′,′ $ S A
0 s2 g1
1 acc
2 s2 s4 g5 g3
3 s6 s7
4 r2 r2
5 r3 r3
6 r1 r1 r1
7 s8
8 r4 r4
Notar que a análise da tabela gerada pelo método SLR(1) é igual à análise da tabela
LR(0), apenas em caso de redução com símbolo de antevisão que não pertença ao con-
junto FOLLOW é imediatamente gerado um erro e parado o processamento. Além
disso, caso existam operações de deslocamento nessas posições, deixa de haver confli-
tos, sendo essas gramáticas SLR(1) mas não LR(0).
66 CAPÍTULO 5. ANÁLISE SINTÁCTICA ASCENDENTE POR TABELA
5.2 Gramáticas LALR(1)
O método de construção LALR(1) leva o princípio do SLR(1) um passo mais adiante.
Nomeadamente, nem todos os símbolos de FOLLOW são utilizados em todas as regras,
mas apenas um subconjunto destes, ou seja os símbolos de antevisão ( LOOKAHEAD ).
Cada ocorrência da regra, e não apenas a regra em si, pode apresentar símbolos de
antevisão distintos. Determinando caso a caso, quais são efectivamente os símbolos
de antevisão na activação regra, permite-se que em cada redução se possa restringir
ainda mais o número de posições preenchidas com reduções. Tal facto permite, em
primeiro lugar evitar conflitos com outras reduções ou com deslocamentos, tornando
as gramáticas LALR(1) mais gerais que as que vimos até ao momento. Em segundo
lugar, torna a tabela mais esparsa, ou seja contém mais posições vazias, o que acelera a
determinação de erros e permite uma maior compressão da tabela resultante.
Exemplo 5.10 Considere-se a gramática seguinte e o respectivo autómato finito não determi-
nista LR(0)
S → A ’b’ ’b’
| ’a’ ’a’ ’b’
| ’b’ A ’a’
A → ’a’
r0 S’ → 0 ր S 1 $
r1 S → 2 ր A 3 ’b’ 4 ’b’ 5
r2 | 6 ’a’ 7 ’a’ 8 ’b’ 9
r3 | 10 ’b’ 11 ր A 12 ’a’ 13
r4 A → 14 ’a’ 15
a conversão em autómato finito determinista LR(0)
estado entrada move fecho− ε\move novo estado
0 2, 6, 10, 14 I0
I0 S 1 I1
A 3 I2
’a’ 7, 15 I3
’b’ 11 14 I4
I2 ’b’ 4 I5
I3 ’a’ 8 I6
I4 A 12 I7
’a’ 15 I8
I5 ’b’ 5 I9
I6 ’b’ 9 I10
I7 ’a’ 13 I11
a que corresponde a tabela de análise SLR(1), sabendo que
FOLLOW(S) = {$}
FOLLOW(A) = {′a′ , ′b′}
5.2. GRAMÁTICAS LALR(1) 67
′a′ ′b′ $ S A
0 s3 s4 g1 g2
1 acc
2 s5
3 s6/r4 r4
4 s8 g7
5 s9
6 s10
7 s11
8 r4 r4
9 r1
10 r2
11 r3
Pode-se verificar que no estado 3 para o símbolo ’a’ existe um conflito deslocamento-redução. No
entanto, fazendo o processamento mental, verificamos que ao ler o primeiro carácter ’a’, ficamos
no fim da regra 4 vindo da regra 1, bem como no segundo estado da regra 2. Porém, dependendo
do carácter seguinte podemos determinar qual das duas opções é efectivamente a correcta. Tal
deve-se ao facto de quando se processa a regra 4 vindo da regra 1 apenas o símbolo ’b’ se pode
seguir, embora quer ’a’ como ’b’ serem FOLLOW do símbolo não terminal A.
O método de construção de tabelas de análise LALR(1) produz autómatos de igual di-
mensão que o LR(0), mas onde cada ocorrência do estado não determinista transporta
o conjunto de símbolos de antevisão necessários. A redução é efectuada apenas para os
símbolos de antevisão associados a cada ocorrência do estado não determinista, corres-
pondente ao final da regra.
Notar que o estado 14 da regra 4 do exemplo 5.10 terá símbolos de antevisão distintos
consoante têm origem na regra 1 ou na regra 3, respectivamente ’b’ e ’a’. Os símbolos
de antevisão devem ser depois ser sucessivamente transportados até ao último item
da regra, o estado 15 no exemplo, por forma a poderem ser utilizados na sua redução.
Desta forma, os símbolos de antevisão necessitam apenas ser calculados nas transições
vazias, coorespondendo à antevisão após o não terminal que lhe está associado. Caso
esse não terminal seja o último símbolo da regra, então são símbolos de antevisão todos
os símbolos de antevisão do estado anterior à transição vazia.
O estado inicial tem por antevisão o fim do ficheiro, representado por 0$.
Exemplo 5.11 Associando os símbolos de antevisão às transições vazias ficamos com um autó-
mato finito não determinista semelhante ao do exemplo 5.10
68 CAPÍTULO 5. ANÁLISE SINTÁCTICA ASCENDENTE POR TABELA
r0 S’ → 0 ր
$
S 1 $
r1 S → 2 ր
′b′
A 3 ’b’ 4 ’b’ 5
r2 | 6 ’a’ 7 ’a’ 8 ’b’ 9
r3 | 10 ’b’ 11 ր
′a′
A 12 ’a’ 13
r4 A → 14 ’a’ 15
o primeiro passo no cálculo do autómato determinista tem presente que o estado0 transporta o
símbolo de antevisão $ para os estados 2, 6, 10, mas que o estado 2 apenas transporta o símbolo
de antevisão ’b’ para o estado 14, pois quando a regra A →′ a′ reduzir só poderá ter a seguir o
símbolo ′b′,
estado entrada move fecho− ε\move novo estado
0$ 2$, 6$, 10$, 14
′b′ I0
no segundo passo todos os símbolos de antevisão são transportados para o respectivo estado se-
guinte da regra, que de acordo com a sequência de numeração utilizada corresponde também ao
número seguinte. Apenas a transição vazia do estado 11 para o estado 14 necessita calcular novos
símbolos de antevisão,
estado entrada move fecho− ε\move novo estado
0$ 2$, 6$, 10$, 14
′b′ I0
I0 S 1
$ I1
A 3$ I2
’a’ 7$, 15
′b′ I3
’b’ 11$ 14
′a′ I4
a tabela fica completa transportando os restantes símbolos de antevisão,
estado entrada move fecho− ε\move novo estado
0$ 2$, 6$, 10$, 14
′b′ I0
I0 S 1
$ I1
A 3$ I2
’a’ 7$, 15
′b′ I3
’b’ 11$ 14
′a′ I4
I2 ’b’ 4
$ I5
I3 ’a’ 8
$ I6
I4 A 12
$ I7
’a’ 15
′a′ I8
I5 ’b’ 5
$ I9
I6 ’b’ 9
$ I10
I7 ’a’ 13
$ I11
5.2. GRAMÁTICAS LALR(1) 69
Notar que agora o estado 15 aparece com o símbolo de antevisão ’b’ em I3, mas com ’a’ em I8.
Desta forma, a redução da regra 4 é apenas colocada na coluna ’b’ para o estado I3 e apenas na
coluna ’a’ para o estado I8. Podemos verificar, através de uma observação cuidada da gramá-
tica do exemplo que este é efectivamente o caso, ficando a tabela de análise gerada pelo método
LALR(1)
′a′ ′b′ $ S A
0 s3 s4 g1 g2
1 acc
2 s5
3 s6 r4
4 s8 g7
5 s9
6 s10
7 s11
8 r4
9 r1
10 r2
11 r3
Quando os símbolos de antevisão não podem ser identificados no autómato não deter-
minista, quando o não terminal é o último símbolo da regra, utilizaremos o símbolo ∝
para indicar o transporte dos símbolos de antevisão anteriores para os estados atingidos
pela transição vazia. Por exemplo, S→ 25 ր
∝
A 26.
Como foi referido, os autómatos não determinista e determinista LALR(1) são iguais
aos LR(0), com a excepção da anotação dos símbolos de antevisão a cada ocorrência do
estado não determinista. Assim, quando se repete um conjunto de estados não determi-
nista é porque se está na presença do mesmo estado determinista. Contudo, o cálculo
dos símbolos de antevisão tem de ser completamente calculada, pois pode diferir da
ocorrência inicial. Sempre que existe discrepância entre os símbolos de antevisão dos
diversos estados não determinista, de um mesmo estado determinista, estes devem ser
fundidos. No entanto, caso já tenham sido calculados novos estados, os símbolos de
antevisão devem ser propagados a esses estados.
Exemplo 5.12 Considere-se uma simplificação da instrução if com e sem else da linguagem C
r0 S’ → 0 ր
$
S 1 $
r1 S → 2 ’i’ 3 ր
∝
S 4
r2 | 5 ’i’ 6 ր
′e′
S 7 ’e’ 8 ր
∝
S 9
r3 | 10 ’x’ 11
70 CAPÍTULO 5. ANÁLISE SINTÁCTICA ASCENDENTE POR TABELA
o cálculo do autómato finito determinista até à repetição do estado I2 é idêntica ao exemplo 5.11
estado entrada move fecho− ε\move novo estado
0$ 2$, 5$, 10$ I0
I0 S 1
$ I1
’i’ 3$, 6$ 2$, 5$, 10$ I2
’x’ 11$ I3
I0 S 4
$, 7$ I4
’i’ 3$, 6$ 2
′e′ , 5
′e′ , 10
′e′ (I2)
neste ponto surje uma nova ocorrência do estado I2 = {3, 6, 2, 5, 10} mas com símbolos de
antevisão distintos nos estados 2, 5, 10. Para que os símbolos de antevisão das duas ocorrências
fiquem coerentes é necessário que esses três estados passem a ter ambos os símbolos de antevisão,
passando I2 = {3
$, 6$, 2$,
′e′ , 5$,
′e′ , 10$,
′e′} em ambas as ocorrências. No entanto, os estados I3
e I4 já foram entretanto calculados com base nos anteriores símbolos de antevisão de I2, embora
haja situações em os novos símbolos de antevisão de I2 não afectam I3 e I4 este não é o caso.
Assim, o processo deve ser repetido a partir da primeira ocorrência de I2, mas agora com os novos
símbolos de antevisão
estado entrada move fecho− ε\move novo estado
0$ 2$, 5$, 10$ I0
I0 S 1
$ I1
’i’ 3$, 6$ 2$,
′e′ , 5$,
′e′ , 10$,
′e′ I2
’x’ 11$,
′e′ I3
I0 S 4
$,′e′ , 7$,
′e′ I4
’i’ 3$,
′e′ , 6$,
′e′ 2$,
′e′ , 5$,
′e′ , 10$,
′e′ (I2)
notar que mais uma vez a segunda ocorrência de I2 ficou com símbolos de antevisão distintos da
primeira ocorrência, mas desta vez nos estados 3 e 6. O processo repete-se, mas desta vez sem
consequências para os estados entretanto já re-calculados, ficando a tabela completa
5.3. ELIMINAÇÃODE CONFLITOS 71
estado entrada move fecho− ε\move novo estado
0$ 2$, 5$, 10$ I0
I0 S 1
$ I1
’i’ 3$,
′e′ , 6$,
′e′ 2$,
′e′ , 5$,
′e′ , 10$,
′e′ I2
’x’ 11$,
′e′ I3
I0 S 4
$,′e′ , 7$,
′e′ I4
’i’ 3$,
′e′ , 6$,
′e′ 2$,
′e′ , 5$,
′e′ , 10$,
′e′ (I2)
’x’ 11$,
′e′ (I3)
I4 ’e’ 8
$,′e′ , 7$,
′e′ 2$,
′e′ , 5$,
′e′ , 10$,
′e′ I5
I5 S 9
$,′e′ I6
’i’ 3$,
′e′ , 6$,
′e′ 2$,
′e′ , 5$,
′e′ , 10$,
′e′ (I2)
’x’ 11$,
′e′ (I3)
finalmente a tabela de análise apresenta, como seria de esperar, um conflito deslocamento-redução,
′i′ ′e′ ′x′ $ S
0 s2 s3 g1
1 acc
2 s2 s3 g4
3 r3 r3
4 s5/r1 r1
5 s2 s3 g6
6 r2 r2
5.3 Eliminação de conflitos
Se surjem conflitos na construção de tabelas de análise pelo método LALR(1) é neces-
sário determinar a origem desses conflitos. Uma gramática ambígua produz sempre
conflitos e, muito provavelemente, não reflecte a linguagem que pretende modelar. De
facto, as linguagens utilizadas em computadores, sejam linguagens de programação
ou outras, não são ambíguas, excepto em casos muitos particulares. Noutras situações
apenas, um símbolo de antevisão pode não ser suficiente, sendo necessário resolver o
problema noutras fases do processamento, como a análise lexical ou a análise semântica.
No entanto, a maioria das linguagens utilizadas pelos computadores não só não é am-
bígua como pode ser processada com apenas um símbolo de antevisão. Tal deve-se ao
facto de quem criou a linguagem ter tido presente as ferramentas de análise existen-
tes, salvo poucas excepções. O problema reside no facto de encontrar uma gramática
LALR(1) que descreva a linguagem em questão. De facto, mesmo que tal gramática, ou
72 CAPÍTULO 5. ANÁLISE SINTÁCTICA ASCENDENTE POR TABELA
gramáticas, existam nada me garante que a minha análise da linguagem produza uma
dessas gramáticas.
Nesta secção tentaremos ver alguns procedimentos simples que permitem modificar a
gramática por forma a evitar conflitos desnecessários e que resultam, em geral, de vícios
do utilizador ou de descrições que dirigem o utilizador para soluções menos conflituo-
sas.
Os conflitos têm sempre origem em reduções, sendo estas efectuadas quando se atínge o
último estado de uma regra, para certos símbolos de antevisão. Se o estado determinista
contiver outros estados não deterministas em posição de redução ou deslocamento, para
o mesmo símbolo de antevisão, então esse estado tem um conflito. Desta forma a pri-
meira regra para evitar conflitos é criar regras compridas, ou seja com muitos símbolos,
face a muitas regras curtas, pois cada regra usada necessita ser reduzida. Existe ainda
uma vantagem no desempenho do analisador já que cada regra usada consome dois
passos de processamento, um para a redução e outro para o movimento, e provavel-
mente necessitará de mais estados na tabela de análise. Além disso cada novo símbolo
não terminal acrescenta mais uma coluna à tabela.
5.3.1 Conflitos deslocamento-redução
Um conflito deslocamento-redução tem origem numa regra estar em condições de ser
reduzida para o símbolo de antevisão em questão, enquanto outra regra ou regras po-
dem deslocar esse símbolo.
Exemplo 5.13 Considere-se a gramática
S → ’x’ ’y’ ’z’
| A ’y’
| A ’z’
A → ’x’
onde a sequência xy pode ser reconhecida pela primeira regra ou pela segunda regra seguida da
quarta.