Análise Sintática de Programas

Prévia do material em texto

Análise Sintática de Programas 
1 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 
ambiguidades 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 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 
frequentemente 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 frequentemente 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 
Frequentemente, 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 
subsequentes. 
– 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 frequentemente 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”. 
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ânticosespú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. 
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 frequentemente. 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. 
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, consequentemente, 
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: 
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. 
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 pilhaquando 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 ambiguidade 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 sequê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 para e anuncia o término com sucesso da análise sintática. 
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 consequentemente 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á 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 ideia 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: 
• 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. 
• 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 consequentemente resultar na omissão da palavra chave que 
inicia o próximo enunciado. Frequentemente, 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. 
• 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. 
• 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. 
• Se um terminal ao topo da pilha não puder ser reconhecido, uma ideia 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. 
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 construir uma á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 ladoesquerdo da produção Bàd, obtemos aABe. Podemos agora substituir toda esta cadeia por 
S. Consequentemente, através de uma sequê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 sequê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 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, para 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. 
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 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. Frequentemente, 
esses analisadores são de descendência recursiva. Analisadores sintáticos de precedência de 
operadores tem sido construídos até 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 
ambiguidades ou outras construções que sejam difíceis de decompor, numa varredura 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 
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 sequência de símbolos 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. 
Autoria: Elisson Oliveira Lima