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 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 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
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”.

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.


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.
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:

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:
Criamos um estado inicial e um final (de retorno).
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 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:
Se X=A=$, o analisador pára e anuncia o término com sucesso da análise sintática.
Se X=a≠$, o analisador sintático remove X da pilha e avança o apontador da entrada para o próximo símbolo.
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á 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:
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 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.
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 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.

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 lado esquerdo da produção Bàd, obtemos aABe. Podemos agora substituir toda esta cadeia por S. Conseqüentemente, através de uma 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 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.


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. Freqüentemente, 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 ambigüidades 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:

empilhar s, onde s é um estado,
reduzir através da produção gramatical A à β,
aceitar, e
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:
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.
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 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.
Se ação[sm,a i]=aceitar, a análise sintática está completa.
Se ação[sm,a i]=erro, o analisador sintático descobriu um erro e chama um procedimento de recuperação de erros.