ANÁLISE SINTÉTICA

Prévia do material em texto

INTRODUÇÃO 
 
Cada linguagem de programação possui as regras que descrevem a estrutura sintática 
dos programas bem formados. Em Pascal por exemplo, um programa é constituído por 
blocos, um bloco por comandos, um comando por expressões , uma expressão por 
tokens e assim por diante. A sintaxe das construções de uma linguagem de 
programação pode ser descrita pelas gramáticas livres de contexto ou pela notação 
BNF (Forma de Bakcus – Naur). As gramáticas oferecem vantagens significativas 
tanto para os projetistas de linguagens quanto para os escritores de compiladores. 
 
 Uma gramática oferece, para uma linguagem de programação, uma 
especificação sintática precisa e fácil de entender. 
 Para certas classes de gramáticas, podemos construir automaticamente um 
analisador sintático que determine se um programa-fonte está sintaticamente 
bem-formado. Como benefício adicional, o processo de construção do 
analisador pode revelar ambigüidades sintáticas bem como outras construções 
difíceis de se analisar gramaticalmente, as quais poderiam, de outra forma, 
seguir indetectadas na fase de projeto inicial de uma linguagem e de seu 
compilador. 
 Uma gramática propriamente projetada implica uma estrutura de linguagem de 
programação útil à tradução correta de programas-fonte em códigos objeto e 
também à detecção de erros. Existem ferramentas disponíveis para a 
conversão de descrições de traduções, baseadas em gramáticas, em 
programas operativos. 
 As linguagens evoluíram ao longo de um certo período de tempo, adquirindo 
novas construções e realizando tarefas adicionais. Essas novas construções 
podem ser mais facilmente incluídas quando existe uma implementação 
baseada numa descrição gramatical da linguagem. 
 
2 O PAPEL DO ANALISADOR SINTÁTICO 
 
Existem três tipos gerais de analisadores sintáticos. Os métodos universais de análise 
sintática, tais como o algoritmo de Cocke-younger-Kasami e o de Earley, podem tratar 
qualquer gramática. Esses métodos, entretanto, saio muito ineficientes parta se usar 
num compilador de produção. Os métodos mais comumente usados nos compiladores 
são classificados como top-down ou bottom-up. Como indicado por seus nomes, os 
analisadores sintáticos top-down, constroem árvores do topo (raiz) para o fundo 
(folhas), enquanto que os bottom-up começam pelas folhas e trabalham árvore acima 
 3 
até a raiz. Em ambos os casos, a entrada é varrida da esquerda para a direita, um 
símbolo de cada vez. 
 
Os métodos de análise sintática mais eficientes, tanto top-down quanto bottom-up, 
trabalham somente em determinadas subclasses de gramáticas, mas várias dessas 
subclasses, como as das gramáticas LL e LR, são suficientemente expressivas para 
descrever a maioria das construções sintáticas das linguagens de programação. Os 
analisadores implementados manualmente trabalham freqüentemente com gramáticas 
LL; por exemplo. Assumimos que a saída de um analisador sintático seja alguma 
representação da árvore gramatical para o fluxo de tokens produzido pelo analisador 
léxico. Na prática, existe um certo número de tarefas que poderiam ser conduzidas 
durante a análise sintática, tais como coletar informações sobre os vários tokens na 
tabela de símbolos, realizar a verificação de tipos e outras formas de análise 
semântica, assim como gerar o código intermediário. 
 
3 TRATAMENTO DE ERROS DE SINTAXE 
 
Se um compilador tivesse que processar somente programas corretos, seu projeto e 
sua implementação seriam grandemente simplificados. Mas os programadores 
freqüentemente escrevem programas incorretos, e um bom compilador deveria assistir 
o programador na identificação e localização de erros. É gritando que, apesar dos 
erros serem lugar-comum, poucas linguagens sejam projetadas tendo-se o tratamento 
de erros em mente. Nossa civilização seria radicalmente diferente se as linguagens 
faladas tivessem as mesmas exigências de correção sintática que as das linguagens 
de computadores. A maioria das especificações das linguagens de programação não 
descreve como um compilador deveria responder aos erros; tal tarefa é deixada para o 
projetista desde o início poderia ser tanto simplificar a estrutura de um compilador 
quanto melhorar sua resposta aos erros. 
 
Sabemos que os programas podem conter erros em muitos níveis diferentes. Por 
exemplo, os erros podem ser: 
 
 léxicos, tais como errar a grafia de um identificador, palavra-chave ou operador 
 sintáticos, tais como uma expressão aritmética com parênteses não 
balanceados 
 semânticos, tais como um operador aplicado a um operando incompatível 
 lógicos, tais como uma chamada infinitamente recursiva 
 
 4 
Freqüentemente, boa parte da detecção e recuperação de erros num compilador gira 
em torno da fase de análise sintática. Isto porque os erros ou são sintáticos por 
natureza ou são expostos quando o fluxo de tokens proveniente do analisador léxico 
desobedece às regras gramaticais que definem a linguagem de programação. Outra 
razão está na precisão dos modernos métodos de análise sintática; podem detectar 
muito eficientemente a presença de erros sintáticos num programa. Detectar 
precisamente a presença de erros semânticos ou lógicos em tempo de compilação é 
muito mais difícil. 
 
Um tratador de erros num analisador sintático possui metas simples de serem 
estabelecidas: 
 
 Deve relatar a presença de erros clara e acuradamente. 
 Deve se recuperar de cada erro suficientemente rápido a fim de ser capaz de 
detectar erros subseqüentes. 
 Não deve retardar significativamente o processamento de programas corretos. 
 
A realização efetiva dessas metas apresenta desafios difíceis. 
 
Felizmente, os erros comuns são simples e freqüentemente basta um mecanismo de 
tratamento de erros relativamente direto. Em alguns casos, entretanto, um erro pode 
ter ocorrido muito antes de sua presença ter sido detectada e sua natureza precisa 
pode ser muito difícil de ser deduzida. Em casos difíceis, o tratador de erros pode ter 
que advinhar o que o programador tinha em mente quando o programa foi escrito. 
 
Vários métodos de análise sintática, tais como os métodos LL e LR, detectam os erros 
tão cedo quanto possível. Mais precisamente, possuem a propriedade do prefixo 
viável, significando que detectam que um erro ocorreu tão logo tenham examinado um 
prefixo da entrada que não seja o de qualquer cadeia da linguagem. 
 
Como deveria um tratador de erros reportar a presença de um erro? No mínimo, 
deveria informar o local no programa fonte onde o mesmo foi detectado, uma vez que 
existe uma boa chance de o erro efetivo ter ocorrido uns poucos tokens antes. Uma 
estratégia comum empregada por muitos compiladores é a de imprimir a linha ilegal 
com um apontador para a posição na qual o erro foi detectado. Se existir um razoável 
prognóstico de que o erro realmente foi, uma compreensível mensagem de 
diagnóstico informativa é também incluída; por exemplo, “ponto-e-vírgula ausente 
nesta posição”. 
 5 
Uma vez que o erro tenha sido detectado, como deveria o analisador sintático se 
recuperar? Existe um número de estratégias gerais, mas nenhum método claramente 
se impõe sobre os demais. Na maioria dos casos, não é adequado para o analisador 
sintático encerrar logo após detectar o primeiro erro, porque o processamento da 
entrada restante ainda pode revelar outros. Usualmente, existe alguma forma de 
recuperação de erros na qual o analisador tenta restaurar a si mesmo para um estado 
onde o processamento da entrada possa continuar com uma razoável esperança de 
que o resto correto da entrada será analisado e tratado adequadamente pelo 
compilador.Um trabalho inadequado de recuperação pode introduzir uma avalancha de erros 
“espúrios”, que não foram cometidos pelo programador, mas introduzidos pelas 
modificações no estado do analisador sintático durante a recuperação de erros. Numa 
forma similar, uma recuperação de erros sintáticos pode introduzir erros semânticos 
espúrios que serão detectados posteriormente pelas fases de análise semtântica e de 
geração de código. Por exemplo, ao se recuperar de um erro, o analisador pode pular 
a declaração de alguma variável, digamos zap. Quando zap for posteriormente 
encontrada nas expressões, não haverá nada sintaticamente errado, mas como não 
há uma entrada na tabela de símbolos para zap, a mensagem “zap não definido” será 
gerada. 
 
Uma estratégia cautelosa para o compilador é a de inibir as mensagens de erro que 
provenham de erros descobertos muito proximamente no fluxo de entrada. Em alguns 
casos, pode haver erros demais para o compilador continuar um processamento 
sensível (por exemplo, como deveria um compilador Pascal responder ao receber um 
programa Fortran como entrada?). Parece que uma estratégia de recuperação de 
erros tem que ser um compromisso cuidadosamente considerado levando em conta os 
tipos de erros que são mais propensos a ocorrer e razoáveis de processar. 
 
Alguns compiladores tentam reparar os erros, num processo em que tentam adivinhar 
o que o programador queria escrever. O compilador PL/C (Conway e Wilcox [1973]) é 
um exemplo desse tipo. Exceto, possivelmente, num ambiente de pequenos 
programas escritos por estudantes principiantes, a reparação extensiva de erros não é 
propensa a pagar o seu custo. De fato, com a ênfase crescente na computação 
interativa e bons ambientes de programação, a tendência parece estar na direção de 
mecanismos simples de recuperação de erros. 
 
 
 6 
4 ANÁLISE SINTÁTICA TOP-DOWN 
 
A análise sintática top-down pode ser vista como uma tentativa de ser encontrar uma 
derivação mais à esquerda para uma cadeia de entrada. Equivalentemente, pode ser 
vista como uma tentativa de se construir uma árvore gramatical, para a cadeia de 
entrada, a partir da raiz, criando os nós da árvore gramatical em pré ordem. 
Consideramos agora uma forma geral de análise sintática top-down, chamada de 
descendência recursiva, que pode envolver retrocesso, ou seja, a realização de 
esquadrinhamentos repetidos da entrada. Por outro lado, os analisadores sintáticos 
com retrocesso não são vistos muito freqüentemente. Uma razão está em que o 
retrocesso é raramente necessitado para analisar sintaticamente construções de 
linguagens de programação. Em situações tais como a análise sintática de linguagens 
naturais, o retrocesso ainda é ineficiente e métodos tabulares, tais como o algoritmo 
de programação dinâmica ou método de Earley [1970] são preferidos. 
 
O retrocesso é exigido no próximo exemplo, e iremos sugerir uma forma de controlar a 
entrada quando o mesmo ocorrer. 
 
Exemplo: Consideremos a gramática 
 
S cAd 
A ab | a 
 
E a cadeia de entrada w=cad. Para construir uma árvore gramatical para esta cadeia, 
de cima para baixo, criamos inicialmente uma árvore constituindo de um único nó 
rotulado S. O apontador da entrada aponta para c, o primeiro símbolo de w. Em 
seguida, usamos a primeira produção para S a fim de expandir a árvore e obter a da 
figura (a). 
 
 
 
 
 
 
 
 
 
S 
 
 c d 
A 
 
 
 
(a) 
S 
 
 c d 
A 
 
 a b 
 
(b) 
S 
 
 c d 
A 
 
 
a 
(c) 
 7 
A folha mais à esquerda, rotulada c, reconhece o primeiro símbolo de w e, por 
conseguinte, avançamos o apontador da entrada para a, o segundo símbolo de w, e 
consideramos a próxima filha, rotulada A. Em seguida, expandimos A usando a sua 
primeira alternativa, obtendo a árvore da figura (b). Temos agora um reconhecimento 
para o segundo símbolo da entrada e, conseqüentemente, avançamos para o 
apontador da entrada para d, o terceiro símbolo da entrada, e comparamos d com a 
próxima folha, rotulada b. Como b não é igual a d, reportamos uma falha e retornamos 
a A a fim de verificar se existe uma outra alternativa que não tenhamos tentado ainda, 
mas que poderia produzir um reconhecimento. 
 
Ao irmos de volta para A, precisamos restabelecer o apontador da entrada para a 
posição 2, aquela que o mesmo detinha quando passamos pela primeira vez por A, o 
que significa que o procedimento para A precisa armazenar o apontador da entrada 
numa variável local. Tentamos agora a segunda alternativa de A afim de obter a árvore 
na figura (c). A folha a reconhece o segundo símbolo de w e a folha d o terceiro. Uma 
vez que produzimos uma árvore gramatical para w, paramos e anunciamos o término 
com sucesso da análise sintática. 
 
Uma gramática recursiva à esquerda pode levar um analisador sintático de 
descendência recursiva, mesmo com retrocesso, a um laço infinito. Isto é, quando 
tentamos expandir A, podemos eventualmente nos encontrar de novo tentando 
expandir A sem ter consumido nenhum símbolo da entrada. 
 
 
5 ANALISADORES SINTÁTICOS PREDITIVOS 
 
Em muitos casos, escrevendo-se cuidadosamente uma gramática, eliminando-se a 
recursão a esquerda e fatorando-se à esquerda a gramática resultante, podemos obter 
uma nova gramática processável por um analisador sintático de descendência 
recursiva que não necessite de retrocesso, isto é, um analisador preditivo. Para 
construir um analisador sintático preditivo, precisamos conhecer, dado o símbolo 
corrente de entrada a e o não terminal A a ser expandido, qual das alternativas de 
produção A  α1 | α2 |... | αn é a única que deriva uma cadeia começando por a. Ou 
seja, a alternativa adequada precisa ser detectável examinando-se apenas para o 
primeiro símbolo da cadeia que a mesma deriva. As construções de controle de fluxo 
na maioria das linguagens de programação, com suas palavras-chave distintivas, são 
usualmente detectáveis dessa forma. Por exemplo, se tivermos as produções: 
 
 8 
cmd  if expr then cmd else cmd 
 | while expr do cmd 
 | begin lista_de_comandos end 
 
então as palavras-chave if, while e begin nos informam qual alternativa é a única que 
possivelmente teria sucesso, se quiséssemos encontrar um comando. 
 
 
5.1 Diagramas de Transições para Analisadores Sintáticos Preditivos 
 
As várias diferenças entre os diagramas de transições para um analisador léxico e um 
analisador sintático preditivo são imediatamente aparentes. No caso de um analisador 
sintático, existe um diagrama para cada não terminal. Os rótulos dos lados são tokens 
e não terminais. Uma transição em um token (terminal) significa que devemos realizá-
la se aquele token for o próximo símbolo da entrada. Uma transição num não-terminal 
A é chamada de procedimento para A. 
 
Para construir um diagrama de transições de um analisador sintático preditivo a partir 
de uma gramática, eliminamos primeiro da gramática a recursividade à esquerda e, 
em seguida, a fatoramos à esquerda. Para cada não-terminal A, então fazemos o 
seguinte: 
 
1. Criamos um estado inicial e um final (de retorno). 
2. 2. Para cada produção A  X1,X2...Xn, criamos um percurso a partir do estado 
inicial até o estado final, com os lados rotulados X1,X2,...,Xn. 
 
O analisador preditivo ao trabalhar sobre os diagramas de transições se comporta 
como segue. Começa no estado inicial para o símbolo de partida. Se após algumas 
ações estiver no estado s, o qual possui um lado rotulado pelo terminal a apontado 
para o estado t, e se o próximo símbolo de entrada for a, move o cursor de entrada 
uma posiçãoà direita e vai para o estado t. Se, de outra feita, o lado for rotulado pelo 
não terminal A, vai para o estado de partida A, sem movimentar o cursor de entrada. 
Se em algum instante for atingido o estado final de A, vai imediatamente para o estado 
t, tendo como efeito, “lido” A a partir da entrada, durante o tempo em que se movia do 
estado s para t. Finalmente, se existir um lado de s para t rotulado Є, vai, a partir do 
estado s, imediatamente para o estado t, sem avançar na entrada. 
 
 9 
Um programa de análise sintática preditiva baseado num diagrama de transições tenta 
reconhecer símbolos terminais na entrada e faz uma chamada de procedimento 
potencialmente recursiva sempre que precisar seguir um lado rotulado por um não 
terminal. Uma implementação não recursiva pode ser obtida empilhando-se o estado s 
quando existir uma transição em um não terminal para fora de s e removendo-se o 
topo da pilha quando o estado final para o não terminal for atingido. 
 
A abordagem acima funcionará se o diagrama de transições dado for determinístico, 
isto é, não existir mais de uma transição de um mesmo para outros à mesma entrada. 
Se a ambigüidade ocorrer, deveremos estar capacitados a resolvê-la de uma forma 
ad-hoc. Se o não determinismo não puder ser eliminado, não poderemos construir um 
analisador sintático preditivo, mas poderemos construir um analisador de 
descendência recursiva com retrocesso, de forma a tentar sistematicamente todas as 
possibilidades, se esta fosse a melhor estratégia de análise que pudéssemos 
encontrar. 
 
 
5.2 Análise Sintática Preditiva Não-Recursiva 
 
É possível construir um analisador preditivo não-recursivo mantendo explicitamente 
uma pilha, ao invés de implicitamente através de chamadas recursivas. O problema-
chave durante a análise preditiva é determinar que produção deve ser aplicada a um 
dado não terminal. 
 
Um analisador sintático preditivo dirigido por uma tabela possui um buffer de entrada, 
uma pilha, uma tabela sintática e um fluxo de saída. O buffer de entrada possui a 
cadeia a ser analisada, seguida por um $ à direita para indicar o fim da cadeia de 
entrada. A pilha contém uma seqüência de símbolos gramaticais, com $ indicando o 
fundo da pilha. Inicialmente, a pilha contém o símbolo de partida da gramática acima 
de $. Uma tabela sintática é um array bidimensional M[A,a], onde A é um não terminal 
e a é um terminal ou outro símbolo $. 
 
O analisador sintático é controlado por um programa que se comporta como segue. O 
programa considera X o símbolo ao topo da pilha e a o símbolo corrente de entrada. 
Esses dois símbolos determinam a ação do analisador. Existem três possibilidades: 
 
1. Se X=A=$, o analisador pára e anuncia o término com sucesso da análise 
sintática. 
 10 
2. Se X=a≠$, o analisador sintático remove X da pilha e avança o apontador da 
entrada para o próximo símbolo. 
3. Se X é um não terminal, o programa consulta a entrada M[X,a] da tabela 
sintática M. Essa entrada será uma produção – X da gramática ou uma entrada 
de erro. Se, por exemplo, M[X,a]={X  UVW}, o analisador substitui X no topo 
da pilha por WVU (com U ao topo). Como saída, iremos assumir que o 
analisador sintático simplesmente imprima a produção usada; de fato, qualquer 
outro código poderia ser executado aqui. Se M[X,a]=erro, o analisador chama 
uma rotina de recuperação de erros. 
 
O comportamento do analisador sintático pode ser descrito em termos de suas 
configurações, que dão o conteúdo da pilha e a entrada restante. 
 
5.2.1 Primeiro e Seguinte 
 
A construção de um analisador sintático preditivo é auxiliada por duas funções 
associadas à gramática G. Essas funções, Primeiro e Seguinte, nos permitem 
preencher as entradas de uma tabela sintática preditiva para G, sempre que possível. 
Os conjuntos de tokens produzidos pela função seguinte podem também ser usados 
como tokens de sincronização durante a recuperação de erros na modalidade do 
desespero. 
 
Se α for qualquer cadeia de símbolos gramaticais, seja primeiro(α) o conjunto de 
terminais que começam as cadeias derivadas a partir de α. Definamos seguinte(A), 
para o não terminal A, como sendo um conjunto de terminais a que podem figurar 
imediatamente à direita de A em alguma forma sentencial, isto é, o conjunto de 
terminais a tais que exista uma derivação para algum α e β. Se A puder ser o símbolo 
mais à direita em alguma forma sentencial, então $ está em SEGUINTE(A). 
 
 
5.3 Recuperação de Erros na análise Preditiva 
 
A pilha de um analisador preditivo não recursivo torna explícitos os terminais e não 
terminais que o mesmo espera reconhecer com o restante da entrada. Iremos 
conseqüentemente nos referir aos símbolos na pilha do analisador da discussão que 
se segue. Um erro é detectado durante a análise preditiva quando o terminal ao topo 
da pilha não reconhece o próximo símbolo de entrada ou quando o não terminal A está 
 11 
ao topo da pilha, a é o próximo símbolo de entrada e a entrada da tabela sintática 
M[A,a] está vazia. 
 
A recuperação de erros na modalidade do desespero está baseada na idéia de se 
pular símbolos na entrada até que surja um token pertencente a um conjunto pré 
selecionado de tokens de sincronização. Sua efetividade depende da escolha do 
conjunto de sincronização. Os conjuntos deveriam ser escolhidos de tal forma que o 
analisador se recuperasse rapidamente dos erros que tendessem a ocorrer na prática. 
Algumas técnicas heurísticas são: 
 
1. Como ponto de partida, podemos colocar todos os símbolos de SEGUINTE(A) 
no conjunto de tokens de sincronização para o não terminal A. Se pularmos 
tokens até que um elemento de SEGUINTE(A) seja visto e removermos A da 
pilha, é provável que a análise sintática possa continuar. 
2. Não é suficiente usar SEGUINTE(A) como o conjunto de sincronização para A. 
Por exemplo, se os pontos-e-vírgulas terminarem os enunciados, como em C, 
então as palavras-chave que iniciam os enunciados não devem aparecer no 
conjunto SEGUINTE do não-terminal que gera expressões. Um ponto-e-vírgula 
ausente após uma atribuição pode conseqüentemente resultar na omissão da 
palavra chave que inicia o próximo enunciado. Freqüentemente, existe uma 
estrutura hierárquica nas construções da linguagem; por exemplo, as 
expressões aparecem dentro de enunciados, que figuram dentro de blocos e 
assim por diante. Podemos adicionar ao conjunto de sincronização de uma 
construção mais baixa os símbolos que começam as construções mais altas. 
Por exemplo, poderíamos adicionar palavras-chave que iniciam comandos aos 
conjuntos de sincronização para os não-terminais que geram expressões. 
3. Se adicionarmos os símbolos em PRIMEIRO(A) ao conjunto de sincronização 
para o não terminal A, pode ser possível retornar a análise a partir de A, se um 
símbolo em PRIMEIRO(A) figurar na entrada. 
4. Se um não terminal puder gerar a cadeia vazia, então a produção que deriva Є 
pode ser usada como default. Agindo-se assim, pode-se postergar a detecção 
de algum erro, mas não se pode fazer com que um erro seja perdido. Esse 
enfoque reduz o número de não terminais que tenham de ser considerados 
durante a recuperação de erros. 
5. Se um terminal ao topo da pilha não puder ser reconhecido, uma idéia simples 
é a de removê-lo, emitir uma mensagem informando da remoção e prosseguir 
a análise sintática. Com efeito, este enfoque faz com que o conjunto de 
sincronização de um token consista em todos os demais tokens. 
 12 
6 ANÁLISE SINTÁTICA BOTTOM-UP 
 
A análise sintática bottom-up é conhecida como análise de empilhar e reduzir. A 
análise gramatical de empilhar e reduzir tenta construiruma árvore gramatical para 
uma cadeia de entrada começando pelas folhas (o fundo) e trabalhando árvore acima 
em direção à raiz (o topo). Podemos pensar neste processo como o de “reduzir” uma 
cadeia w ao símbolo de partida de uma gramática. A cada passo de redução, uma 
subcadeia particular, que reconheça o lado direito de uma produção, é substituída pelo 
símbolo à esquerda daquela produção e, se a subcadeia tiver sido escolhida 
corretamente a cada passo, uma derivação mais à direita terá sido rastreada na ordem 
inversa. 
 
Exemplo: 
 
Considerando a gramática 
 
SaABe 
AAbc | b 
B d 
 
A sentença abbcde pode ser reduzida a S pelos seguintes passos: 
 
Aabbcde 
aAbcde 
aAde 
aABe 
S 
 
Podemos esquadrinhar abbcde procurando por uma subcadeia que reconheça o lado 
direito de alguma produção. As subcadeias b e d se qualificam. Vamos escolher o b 
mais à esquerda e substituí-lo por A, o lado esquerdo da produção Ab; obtemos 
dessa forma a cadeia aAbcde. Agora as subcadeias Abc, b e d reconhecem o lado 
direito de alguma produção. Apesar de b ser a subcadeia mais à esquerda que 
reconheça o lado direito de alguma produção, escolhemos substituir a subcadeia Abc 
por A, o lado esquerdo da produção AAbc. Obtemos agora aAde. Com a 
substituição de d por B, o lado esquerdo da produção Bd, obtemos aABe. Podemos 
agora substituir toda esta cadeia por S. Conseqüentemente, através de uma 
 13 
seqüência de quatro reduções, estamos capacitados a reduzir abbcde a S. Essas 
reduções, de fato, rastreiam a seguinte derivação mais à direita, na ordem reversa: 
 
S  aABe  aAde  aAbcde  abbcde 
 
7 HANDLES 
 
Informalmente, um handle é uma subcadeia que reconhece o lado direito de uma 
produção e cuja redução ao não terminal do lado esquerdo da produção representa 
um passo ao longo do percurso de uma derivação mais à direita. Em muitos casos, a 
subcadeia β mais à esquerda que reconhece o lado direito de uma produção A β 
não é um handle, porque uma redução pela produção A β produz uma cadeia que 
não pode ser reduzida ao símbolo de partida. 
 
7.1 A Poda do Handle 
 
Uma derivação mais à esquerda na ordem inversa pode ser obtida “podando-se os 
handles”. Ou seja, começamos pela primeira cadeia de terminais w que desejamos 
decompor. Se w for uma sentença da gramática em questão, então w=yn, onde yn é a 
enésima forma sentencial à direita de alguma derivação mais à direita ainda 
desconhecida. 
 
Para reconstruir esta derivação na ordem inversa, localizamos o handle βn em yn e 
substituímos βn pelo lado direito de alguma produção An  βn de modo a obtermos a 
enésima menos uma forma sentencial à direita yn-1. 
 
Repetimos, em seguida, esse processo. Isto é, localizamos o handle Βn-1 em yn-1 e o 
reduzimos de forma a obter a forma sentencial à direita yn-2. Continuando esse 
processo, produzimos uma forma sentencial à direita consistindo somente no símbolo 
de partida S e então paramos e anunciamos o término com sucesso da análise 
sintática. O reverso da seqüência de produções usadas nas reduções é uma derivação 
mais à direita para a cadeia de entrada. 
 
8 IMPLEMENTAÇÃO DE PILHA DA ANÁLISE SINTÁTICA 
DE EMPILHAR E REDUZIR 
 
Existem dois problemas que precisam ser resolvidos se estivermos dispostos a 
analisar sintaticamente através da poda de handles. O primeiro é o de localizar a 
 14 
subcadeia a ser reduzida numa forma sentencial à direita e o segundo é o de 
determinar que produção escolher no caso de existir mais de uma produção com 
aquela subcadeia no lado direito. 
 
Uma forma conveniente de implementar um analisador sintático de empilhar e reduzir 
é usar uma pilha para guardar os símbolos gramaticais e um buffer de entrada para a 
cadeia w a ser decomposta. Usamos $ para marcar o fundo da pilha e também o final 
à direita da entrada. Inicialmente, a pilha está vazia e a cadeia w está à entrada como 
segue 
 
Pilha Entrada 
$ w$ 
 
O analisador sintático opera empilhando zero ou mais símbolos (na pilha) até que um 
handle β surja no topo da pilha. Reduz, então, β para o lado esquerdo da produção 
apropriada. Repete este ciclo até que tenha detectado um erro ou que a pilha 
contenha o símbolo de partida e a entrada esteja vazia: 
 
Pilha Entrada 
$S $ 
 
Após entrar nesta configuração, pára e anuncia o término com sucesso da análise 
sintática. 
 
8.1 Prefixos Viáveis 
 
Os prefixos de uma forma sentencial à direita que podem figurar na pilha deu m 
analisador sintático de empilhar e reduzir são chamados de prefixos viáveis. Uma 
definição equivalente de um prefixo viável é a de ser um prefixo de uma forma 
sentencial à direita, o qual não se estende para além do limite à direita do handle mais 
à direita, daquela forma sentencial. Por esta definição é sempre possível adicionar 
símbolos terminais ao final de um prefixo viável de modo a obter uma forma sentencial 
à direita. Por conseguinte, não há aparentemente erro na medida em que a porção da 
entrada enxergada até um dado ponto possa ser reduzida a um prefixo viável. 
 
 
 
 
 15 
9 ANÁLISE SINTÁTICA DE PRECEDÊNCIA DE OPERADORES 
 
A mais ampla classe de gramáticas, para a qual os analisadores sintáticos de empilhar 
e reduzir podem ser construídos com sucesso são as gramáticas LR. Entretanto, para 
uma pequena, porém importante classe de gramáticas, podemos facilmente construir 
manualmente eficientes analisadores sintáticos de empilhar e reduzir. Essas 
gramáticas possuem a propriedade (dentre outras exigências essenciais) de que 
nenhum lado direito de produção seja Є, ou tenha dois não terminais adjacentes. Uma 
gramática com a última propriedade é chamada de uma gramática de operadores. 
 
Exemplo: 
 
A seguinte gramática para expressões 
 
E  EAE | (E) | -E |id 
A  + | - | * | / | ↑ 
 
Não é uma gramática de operadores porque o lado direito EAE possui dois (de fato 
três) não terminais consecutivos. Entretanto, se substituirmos A por cada uma de suas 
alternativas, obtemos a seguinte gramática de operadores: 
 
E  E + E | E –E | E * E| E / E | E ↑ E | (E) | -E | id 
 
Descrevemos agora uma técnica de análise sintática fácil de implementar chamada de 
análise sintática de precedência de operadores. Historicamente, esta técnica foi 
primeiramente descrita como uma manipulação sobre tokens sem qualquer referência 
a uma gramática subjacente. De fato, uma vez que tenhamos terminado de construir 
um analisador sintático de precedência de operadores a partir de uma gramática, 
podemos ignorar esta última usando os não terminais na pilha apenas como 
marcadores de lugar para os atributos associados aos não terminais. 
 
Como uma técnica geral de análise sintática, a de precedência de operadores possui 
uma série de desvantagens. Por exemplo, é difícil tratar os tokens como o sinal de 
menos, que possui duas diferentes precedências (dependendo de ser unário ou 
binário). Sobretudo, uma vez que o relacionamento entre a gramática para a 
linguagem analisada e o analisador sintático de precedência de operadores é tênue, 
não se pode estar sempre certo de que o analisador aceite exatamente a linguagem 
 16 
desejada. Finalmente, somente uma pequena classe de gramáticas pode ser 
decomposta usando as técnicas de precedência de operadores. 
 
Apesar de tudo, em virtude de sua simplicidade, numerosos compiladores usando as 
técnicas de análise sintática de precedência de operadores têm sido construídos com 
sucesso. Freqüentemente, esses analisadores são de descendência recursiva. 
Analisadores sintáticos de precedência de operadores tem sido construídosaté 
mesmo para linguagens inteiras. 
 
10 ANALISADORES SINTÁTICOS LR 
 
Uma técnica eficiente de análise sintática bottom-up, que pode ser usada para 
decompor uma ampla classe de gramáticas livres de contexto é chamada análise 
sintática LR(k); o”L” significa varredura da entrada da esquerda para a direita (left-to-
right), o “R”, construir uma derivação mais à direita ao contrário (right)most derivation) 
e o k, o número de símbolos de entrada de lookahead que são usados ao se tomar 
decisões na análise sintática. Quando (k) for omitido, k é assumido ser 1. A técnica de 
análise sintática LR é atrativa por uma série de razões. 
 
 Analisadores sintáticos LR podem ser elaborados para reconhecer virtualmente 
todas as construções de linguagens de programação para as quais as 
gramáticas livres de contexto podem ser escritas. 
 O método de decomposição LR é o mais geral dentre os métodos sem 
retrocesso de empilhar e reduzir conhecidos e ainda pode ser implementado 
tão eficientemente quanto os demais métodos de empilhar e reduzir, . 
 A classe de gramáticas que podem ser decompostas usando-se os métodos 
LR é um superconjunto próprio da classe de gramáticas que podem ser 
decompostas usando-se analisadores sintáticos preditivos. 
 Um analisador sintático LR pode detectar um erro sintático tão cedo quanto 
possível numa varredura da entrada da esquerda para a direita. 
 
A principal desvantagem deste método está em ser muito trabalhoso construir um 
analisador sintático LR manualmente para uma gramática típica de linguagem de 
programação. Necessita-se em geral de uma ferramenta especializada – um gerador 
de analisadores LR. Felizmente, muitos de tais geradores estão disponíveis. Com um 
tal gerador, podemos escrever uma gramática livre de contexto e usá-lo para produzir 
automaticamente um analisador sintático para a mesma. Se a gramática contiver 
ambigüidades ou outras construções que sejam difíceis de decompor, numa varredura 
 17 
da entrada da esquerda para a direita, o gerador de analisadores pode localizá-las e 
informar ao projetista do compilador de suas ocorrências. 
 
10.1 O Algoritmo de Análise Sintática LR 
 
Consiste em uma entrada, uma saída, uma pilha, um programa diretor e uma tabela 
sintática que possui duas partes (ação e desvio). O programa diretor é o mesmo para 
todos os três tipos de analisadores LR; somente a tabela sintática muda de um 
analisador para o outro. O programa de análise sintática lê os caracteres provenientes 
de um buffer de entrada, um de cada vez. Usa uma pilha para armazenar as cadeias 
sob a forma s0X1s1X2s2...Xmsm onde sm está ao topo. Cada Xi é um símbolo gramatical 
e cada si, um símbolo chamado de estado. Cada estado sumariza a informação 
contida na pilha abaixo do mesmo e a combinação do símbolo do estado no topo da 
pilha e o símbolo corrente de entrada é usada para indexar a tabela sintática e 
determinar a decisão de empilhar ou reduzir durante a análise. Numa implementação, 
os símbolos gramaticais não precisam figurar na pilha; entretanto, iremos sempre 
incluí-los em nossas discussões, a fim de auxiliar a explicação do comportamento de 
uma analisador sintático LR. 
 
A tabela sintática consiste em duas partes, uma unção de ações sintáticas, ação, e 
uma função de desvio, desvio. O programa diretor do analisador LR se comporta como 
se segue. Determina sm, o estado correntemente no topo da pilha, e ai, o símbolo 
corrente de entrada. Consulta, então ação[sm,ai], a entrada da tabela de ações 
sintáticas para o estada sm e a entrada ai, que pode ter um dos seguintes valores: 
 
1. empilhar s, onde s é um estado, 
2. reduzir através da produção gramatical A  β, 
3. aceitar, e 
4. erro. 
 
A função desvio toma um estado e um símbolo gramatical como argumentos e produz 
um estado como saída. Veremos que a função desvio de uma tabela sintática, 
construída a partir de uma gramática G, usando os métodos SLR, LR canônico ou 
LALR, é a função de transição de um autômato finito determinístico que reconhece os 
prefixos viáveis de G. Relembremos que os prefixos viáveis de G são aqueles das 
formas sentenciais à direita que podem aparecer na pilha de um analisador sintático 
de empilhar e reduzir, porque os mesmos não se estendem para depois do handle 
 18 
mais à direita. O estado inicial deste AFD é o estado inicialmente colocado no topo da 
pilha do analisador sintático LR. 
 
Uma configuração de um analisador sintático LR é um par cujo primeiro componente é 
o conteúdo da pilha e cujo segundo componente é a entrada ainda não consumida: 
 
(s0X1S1x2S2...Xmsm,aiai+1...an$) 
 
Esta configuração representa a forma sentencial à direita 
 
X1X2...Xmaiai+1...an 
 
Essencialmente da mesma maneira que um analisador de empilhar e reduzir faria: 
somente a presença dos estados na pilha é inovadora. 
 
O próprio movimento do analisador é determinado pela leitura de ai, o símbolo 
corrente da entrada e de sm, o estado no topo d pilha, e pela consulta à entrada da 
tabela de ações, ação[sm,a i]. As configurações resultantes após cada um dos quatro 
tipos de movimentos são como se segue: 
 
1. Se ação [sm,a i]=empilhar s, o analisador executa um movimento e empilhar, 
entrando na configuração 
 
(s0X1s1X 2s2...Xmsm,ais,ai+1...an$) 
 
Aqui, o analisador sintático empilhou tanto o símbolo corrente de entrada como o 
próximo estado s, que é dado por ação[sm,a i]; ai+1 se torna o símbolo corrente da 
entrada. 
 
2. Se ação[sm,a i]=reduzir A  β, o analisador executa um movimento de redução, 
entrando na configuração 
(s0X1s1X 2s2...Xm-rsm-r,As,ai ai+1...an$) 
 
onde s=desvio[sm-r,A] e r é o comprimento de β, o lado direito da produção. Aqui o 
analisador sintático remove primeiro 2r símbolos para fora da pilha (r símbolos de 
estados e r símbolos gramaticais), expondo o estado sm-r. Em seguida, empilha tanto 
A, o lado esquerdo da produção, quanto s, a entrada para desvio[sm-r,A]. Para os 
analisadores sintáticos LR que iremos construir, Xm-r+1... Xm, a seqüência de símbolos 
 19 
gramaticais removidos da pilha irá sempre reconhecer β, o lado direito da produção 
redutora. 
 
A saída de um analisador sintático LR é gerada após um movimento de redução, 
através da execução de uma ação semântica associada à produção redutora. Para o 
momento, assumiremos que a saída consista somente na impressão da produção 
redutora. 
 
3. Se ação[sm,a i]=aceitar, a análise sintática está completa. 
4. Se ação[sm,a i]=erro, o analisador sintático descobriu um erro e chama um 
procedimento de recuperação de erros.