Compiladores Analise Sintática LL Discentes

UNIVERSIDADE ZAMBEZE Faculdade de Ciências e Tecnologia Engenharia Informática 3ºAno-Laboral

Compiladores Analise Sintática LL

Discentes:  Carlitos João Fainda Chitsumba  Cesar António Samuge Fijamo  Josué Tiago Mazive Júnior

Docente: Eng. Amilcar Borrás Gonsález

Beira Agosto 2015

Resumo Neste presente trabalho tem como fulcro o desenvolvimento de um gerador de analisadores sintáticos do tipo top-down para gramáticas LL com entrada gráfica da gramática, bem como uma comparação do mesmo com outros geradores em uso no mercado. Como resultado foi obtido um gerador totalmente funcional, e foi mostrado como ele é superior aos outros analisadores. São descritos detalhes da implementação e foi elaborado um manual de uso do sistema implementado em Java independente de ambientes de programação. Palavras-Chave: Analisador Sintático, Gramática, LL(1), Compilador, Gerador de Analisadores Sintáticos.

I

Abstract In this present work has as its main goal the development a parser generator using top-down syntax analysis for LL grammars. Its input is a graph grammar. A comparison with available parser generators is also presented. As a result a fully executable generator, and the fact that it is superior to the other generators was demonstrated. This work contains details of the implementation, and presents a user's manual of the system, which was implemented in Java. The system is independent of programming environments. Keywords: Syntax Analyzer, Grammar, LL(1), Compiler, Parser Generator.

II

Indice Resumo ............................................................................................................................................ I Abstract .......................................................................................................................................... II Introdução ..................................................................................................................................... 1 Análise sintática ............................................................................................................................ 2 Tipos de analisadores sintáticos .................................................................................................. 3 Existem três tipos básicos: .............................................................................................................. 3 Determinismo .......................................................................................................................... 3 Tratamento de erros ..................................................................................................................... 4 Fases para a detenção de erros ........................................................................................................ 4 Fase do tratamento do erro é a sua recuperação ............................................................................. 4 Analisador sintático LL ................................................................................................................ 5 Caso geral ................................................................................................................................ 7 Exemplo ................................................................................................................................... 7 Procedimento de análise .......................................................................................................... 8 Gramáticas LL (k) ..................................................................................................................... 11 Fatoração à esquerda ............................................................................................................. 11 Conclusão ..................................................................................................................................... 12 Bibliografia .................................................................................................................................. 13

Introdução O presente trabalho que tem como tema de investigação Analise Sintática LL, a abordagem revela que o número de linguagens de programação de computadores em uso é vasto. Variando de propósitos gerais a altamente especializadas, elas estão presentes em quase todas as áreas da computação. Portanto há enumeras linguagens gerais de programação nomeadamente como Fortran, Pascal, C e Java, mas também há muitas linguagens usadas em aplicações de domínios específicos. Para que uma linguagem de programação seja executada ou interpretada por um computador, é preciso ter um programa tradutor de um programa escrito nessa linguagem para outra linguagem, que pode ser interpretada ou, no caso de a segunda ser uma linguagem de máquina, executada pelo computador. Uma parte essencial dos compiladores é o analisador sintático, que pode orientar toda a compilação quando a linguagem é descrita por uma gramática formal. Portanto o trabalho tem como o Objetivo geral: apresentar um analisador sintáticos que aceita uma descrição gráfica da gramática da linguagem a ser compilada, denominado "GGLL" (de Gerador de analisadores sintáticos para Gramáticas Gráficas LL(1)'), realizar uma implementação desse gerador na linguagem de programação Java com uma arquitetura orientada a objetos, independente de ambientes de programação, compará-lo com outros geradores de analisadores sintáticos.

1

Análise sintática Análise Sintática é a segunda fase da compilação, conhecida como parsing que analisa uma sequência de entrada para determinar sua estrutura gramatical segundo uma determinada gramatica formal. Em ciência da computação ou em Informática, análise sintática é o processo de analisar uma sequência de entrada (lida de um arquivo de computador ou do teclado) para determinar sua estrutura gramatical segundo uma determinada gramática formal. Essa análise faz parte de um compilador, junto com a análise léxica e análise semântica. Exemplo da análise Sintática de uma expressão matemática

Análise sintática transforma um texto na entrada em uma estrutura de dados, em geral uma árvore, o que é conveniente para processamento posterior, alem de capturar a hierarquia implícita desta entrada. O analisador sintático é a parte central de um compilador orientado pela sintaxe (gramática) da linguagem que ele compila, além disso, verifica se um programa-fonte é válido ou não do ponto de vista sintático. O analisador sintático recebe do analisador léxico uma cadeia de tokens representando o programa-fonte, verifica se essa cadeia de tokens pertence à linguagem gerada pela gramática e estabelece a estrutura gramatical dessa cadeia, controlando assim toda a compilação. O analisador deve ser projetado para emitir mensagens para quaisquer erros de sintaxe encontrados no programa-fonte de forma inteligível e também para contornar esses erros a fim de continuar processando o restante do programa A análise sintática transforma um texto na entrada em uma estrutura de dados, em geral uma árvore, o que é conveniente para processamento posterior e captura a hierarquia implícita desta entrada. Através da análise léxica é obtido um grupo de tokens, para que o analisador sintático use um conjunto de regras para construir uma árvore sintática da estrutura. A tarefa do analisador sintático (um algoritmo, programa de computador ou componente de software que se preze a realizar uma análise sintática) é essencialmente a de determinar se uma entrada de dados pode ser derivada de um símbolo inicial com as regras de uma gramática formal.

2

Tipos de analisadores sintáticos

Existem dois tipos básicos:

Métodos Descendente (top-down) ou Analise Sintatica LL- que constrói a árvore gramatical do topo (raiz) para o fundo (folhas), é um analisador que pode iniciar com o símbolo inicial e tentar transformá-lo na entrada de dados. Intuitivamente, o analisador inicia dos maiores elementos e os quebra em elementos menores. Essa estratégia constrói as árvores de derivação de cima para baixo, isto é, parte do símbolo inicial e vai aplicando as produções até chegar à cadeia a ser reconhecida.

Método Ascendente (bottom-up) ou Analise Sintática LR - que constroem arvore gramatica do fundo (folha) para o topo(raiz ),é um analisador que pode iniciar com uma entrada de dados e tentar reescrevê-la até o símbolo inicial. Intuitivamente, o analisador tentar localizar os elementos mais básicos, e então elementos maiores que contêm os elementos mais básicos, e assim por diante. Essa estratégia constrói as árvores de derivação de baixo para cima, isto é, parte da cadeia de entrada e vai fazendo reconhecimento sintático usando exclusivamente as cadeias intermediárias e os lados direitos completos das produções da gramática, substituindo os símbolos correspondentes nas cadeias intermediárias, até chegar ao símbolo inicial desta.

Determinismo Analisadores sintáticos são determinísticos se sempre souberem que ação tomar independentemente da entrada de texto. Este comportamento é desejado e esperado na compilação de uma linguagem de programação.

3

Tratamento de erros Fases para a detenção de erros 1) Detectar o local no programa em que ocorreu o erro, pois existe uma chance do erro ter ocorrido alguns tokens antes: Uma estratégia é imprimir a linha ilegal com apontador para a posição em que o erro foi detectado; 2) Apresentação de uma mensagem de erro Fase do tratamento do erro é a sua recuperação 1) O analisador não deve encerrar o programa quando detectar o primeiro erro, já que podem ocorrer outros erros depois; 2) Se existir um razoável prognóstico de que o erro realmente foi, uma compreensível mensagem de diagnóstico informativo é também incluída; por exemplo: “ponto-e-vírgula ausente nesta posição”.

4

Analisador sintático LL Um analisador sintático LL é um algoritmo de análise sintática para um sub-conjunto de gramáticas livre de contexto. Ele é dito um analisador sintático descendente (top-down) pois tenta deduzir as produções da gramática a partir do nó raiz. Ele lê a entrada de texto da esquerda para a direita, e produz uma derivação mais à esquerda (por isso LL, do termo em inglês left-left). As gramáticas que podem ser analisadas sintaticamente usando esse tipo de analisador são chamadas gramáticas LL. Outro termo usado é analisador sintático LL (𝑥), no qual refere-se à quantidade de tokens posteriores ao símbolo atual (ainda não consumidos da entrada) que são usados para tomar decisões na análise. Se tal analisador sintático existe para uma dada gramática, e pode analisar sentenças nessa gramática sem o uso de backtracking, então essa gramática é chamada gramática LL (𝑥). Dessas gramáticas com análise posterior, as gramáticas LL (1) são as mais populares, pela necessidade de verificar somente o token posterior para a análise. Linguagens mal desenvolvidas tipicamente possuem gramáticas com um valor alto de 𝑥, e necessitam de bastante esforço computacional para serem analisadas. Método que visa a encontrar uma derivação mais á esquerda para uma cadeia de entrada procurando construir uma árvore gramatical a partir da raiz criando nós em pré-ordem; Sua forma geral é denominado análise gramatical descendente recursiva que pode envolver retrocesso; Quando não há retrocesso denomina-se analise sintática preditiva (muito conveniente para linguagens de programação); O retrocesso é exigido no próximo exemplo, e sugere-se uma forma de controlar a entrada quando o mesmo ocorrer.

5

E a cadeia de entrada 𝒘 = 𝒄𝒂𝒅. Para construir uma árvore gramatical para esta cadeia, de cima para baixo, criamos inicialmente uma árvore constituindo de um único nó rotulado 𝑺. O apontador da entrada aponta para 𝒄, o primeiro símbolo de 𝒘 . Em seguida, usa-se a primeira produção para 𝑺 a fim de expandir a árvore. A folha mais à esquerda, rotulada 𝒄, reconhece o primeiro símbolo de 𝒘 e, por conseguinte, avança-se o apontador da entrada para 𝒂, o segundo símbolo de 𝒘, e considera-se a próxima folha, rotulada 𝑨. Em seguida, expande-se 𝑨 usando a sua primeira alternativa. Tem-se agora um reconhecimento para o segundo símbolo da entrada e, consequentemente, avança-se para o apontador da entrada para 𝒅, o terceiro símbolo da entrada, e compara-se 𝒅 com a próxima folha, rotulada 𝒃. Como 𝒃 não é igual a 𝒅, reporta-se uma falha e retorna-se a 𝑨 a fim de verificar se existe uma outra alternativa que não tenhamos tentado ainda, mas que poderia produzir um reconhecimento. Ao ira-se de volta para 𝑨, precisa-se restabelecer o apontador da entrada para a posição 2, aquela que o mesmo detinha quando passou-se pela primeira vez por 𝑨, o que significa que o procedimento para 𝑨 precisa armazenar o apontador da entrada numa variável local. Tenta-se agora a segunda alternativa de 𝑨 a fim de obter a árvore. A folha a reconhece o segundo símbolo de 𝒘 e a folha 𝒅 o terceiro. Uma vez que produzimos uma árvore gramatical para 𝒘, 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 tenta-se expandir 𝑨, pode eventualmente encontrar de novo tentando expandir 𝑨 sem ter consumido nenhum símbolo da entrada.

6

Caso geral O analisador sintático trabalha em cadeias de texto de uma determinada gramática formal, e consiste de :   

Um buffer de entrada ; Uma pilha na qual são armazenados os símbolos da gramática ainda não analisados; Uma tabela análise que indica se qual regra gramatical a ser aplicada dados os símbolos no topo da pilha e o próximo token de entrada.

Quando o analisador é iniciado, a pilha já contém dois símbolos: [S, $] No qual $ é um terminador especial para indicar o fim da pilha e o fim da entrada de dados, e S é o símbolo de entrada da gramática. O analisador sintático irá tentar reescrever o conteúdo da pilha para o que ele interpreta da entrada de texto. Entretanto, ele somente mantém na pilha o que ainda deve ser reescrito. Exemplo A gramática abaixo será usada para o exemplo a seguir. Ela trata expressões matemáticas, no qual são aceitas somas entre uns: (1) S → F (2) S → ( S + F ) (3) F → 1 Deve-se analisar sintaticamente a seguinte entrada: (1 + 1) Tabela de análise ( )1+$ S2-1- F- -3- -

7

Procedimento de análise O analisador sintático primeiro lê o terminal da entrada de texto, e o S da pilha. Da tabela é indicado que deve-se aplicar a regra 2, isto é, reescrever S para (𝑺 + 𝑭 ) na pilha e escrever o número dessa regra na saída de dados. No próximo passo é removido o numero da entrada de dados e da pilha. Agora o analisador verifica o terminal 1 na entrada de texto então aplica a regra 1 e então a regra 3 da gramática, e escreve seus números na saída de dados. Nos próximos dois passos o analisador sintático lê o 1 e o + da entrada de dados e os compara aos valores da pilha. Como são iguais, eles são removidos da pilha. Nos próximos três passos o 𝑭 será substituído da pilha por 1, e o número 3 (a regra gramatical) será escrita na saída de dados. Por fim, o analisador termina com $ tanto na pilha quanto na entrada de dados. Nesse caso será retornado que a cadeia de caracteres de entrada foi aceita, e na saída de dados está a lista de regras usadas na análise. Como pode ser visto no exemplo, o analisador sintático LL realiza três tipos de passos dependendo do conteúdo do topo da pilha, seja não-terminal, terminal ou $: 





Se o topo é não terminal então ele verifica a tabela de análise, com base do valor não terminal e o símbolo na entrada de dados, qual regra da gramática deve ser usada. O número da regra é escrito na saída de dados. Se a tabela de análise indica que não há regra programada, é retornado um erro. Se o topo é terminal então ele compara o símbolo na entrada com o símbolo do topo da pilha, e se são iguais ambos são removidos. Se eles não são iguais é retornado um erro de sintaxe. Se o topo é $ e na entrada de dados também existe um $ então ele retorna sucesso de análise, senão erro de sintaxe. Parecido com o tratamento para um topo terminal, note que nesse caso o algoritmo é terminado em ambos os casos.

Esses três passos são repetidos até o algoritmo parar, seja com sucesso ou com erro.

8

Exemplo:

Ao processo de voltar atras no reconhecimento e tentar produções alternativas dá-se o nome de retrocesso ou backtracking; Tal processo é ineficiente, pois leva á repetição da leitura de partes da sentença de entrada e, por isso, em geral, não é usado no reconhecimento de linguagens de programação: 



Como o reconhecimento é geralmente, acompanhado da execução de ações semânticas (por exemplo, armazenamento de identificadores na tabela de símbolos),a ocorrência de retrocesso pode levar o analisador sintático a ter que desfazer essas ações; Outra desvantagem dessa classe de analisadores é que, quando ocorre um erro, fica difícil indicar com precisão o local do erro, devido á tentativa de aplicação de produções alternativas.

A análise sintática top-down ou LL 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. Considerando 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. 9

Nesses métodos a análise sintática gera uma árvore sintática de cima para baixo, ou seja, da raiz para as folhas. A principal classe gramatical usada pelos métodos descendentes são as gramáticas LL, do inglês left-to-rigth leftmost derivation, ou seja, reconhecimento da esquerda para direita com derivação mais à esquerda. Um método de análise sintática descendente é o recursive descent ou recursivo descendente, em que se programa um procedimento da linguagem de implementação (que deve ter procedimentos recursivos) para cada não terminal, e o código especifica quais terminais devem ser examinados para escolher cada produção ou para seguir adiante durante a análise do lado direito de uma produção.

Exemplo: dada a gramática G = ({T, F}, {*, id}, T, {T → T * F | F, F → id}), teremos a seguinte árvore de derivação gerada pela análise descendente com a ordem da derivação indicada pelos números entre parenteses. Note-se que depois de substituir T no primeiro passo (1), substitui-se T no segundo passo (2), pois isso corresponde a derivação mais à esquerda (LL).

Árvore de derivação descendente

10

Gramáticas LL (k) As gramáticas LL (k) são usadas por métodos descendentes que utilizam k símbolos de look-ahead, ou seja, k símbolos da cadeia de entrada para determinar a produção a ser escolhida durante uma análise, ou uma alternativa de uma sequência de alternativas. Exemplo 1: se 𝑮 = ({𝑺}, {𝒂, 𝒃, 𝒄}, 𝑺, {𝑺 → 𝒂𝑺 | 𝒃𝑺 | 𝒄}), então G é uma gramática 𝑳𝑳(𝟏), pois é necessário verificar um único símbolo da cadeia para determinar a produção a ser escolhida ou se é necessário ler o próximo símbolo de entrada em cada passo da análise. Os passos do reconhecimento da cadeia "𝒂𝒂𝒃𝒄" são 𝒂𝒂𝒃𝒄 ⇐ 𝒂𝒂𝒃𝑺 ⇐ 𝒂𝒂𝑺 ⇐ 𝒂𝑺 ⇐ 𝑺; em cada passo é necessário usar apenas um só símbolo da cadeia intermediária para decidir qual produção deve ser usada, isto é, 𝑺 → 𝒄, 𝑺 → 𝒃𝑺, 𝑺 → 𝒂𝑺 𝒆 𝑺 → 𝒂𝑺 respectivamente. Exemplo 2: se 𝑮 = ( {𝑺}, {𝒂, 𝒃, 𝒄, 𝒅}, 𝑺, { 𝑺 → 𝒂𝒃𝑺 | 𝒂𝒄𝑺 | 𝒅}), então G é uma gramática 𝑳𝑳(𝟐), pois é necessário verificar os dois primeiros símbolos de cada produção para determinar a produção a ser escolhida. De fato, na cadeia "𝒂𝒃𝒅", no primeiro passo depois de 𝒂𝒃𝒅 ⇐ 𝒂𝒃𝑺 é necessário examinar os dois símbolos antes de S para decidir entre 𝑺 → 𝒂𝒃𝑺 ou 𝑺 → 𝒂𝒄𝑺.

Fatoração à esquerda Se, para as produções de um certo não terminal, há várias delas começando à esquerda com o mesmo símbolo terminal, para obter-se gramáticas do tipo LL(1), pode-se utilizar a técnica de factoração à esquerda. Se G é uma gramática com as produções do tipo 𝑷 = {𝑺 → 𝜶𝜷𝟏 | 𝜶𝜷𝟐 | . . . |𝜶𝜷𝒏 } onde 𝜷𝟏 ≠ 𝜷𝟐 ≠ . . . ≠ 𝜷𝒏, então G não é LL(1), mas pode ser transformado em uma gramática equivalente G’ LL(1) com as produções da forma 𝑃 = {𝑆 → 𝛼(𝛽1 | 𝛽2 |. . . | 𝛽𝑛 )}.

11

Conclusão O analisador léxico e o analisador sintático, expandido com as rotinas semânticas programadas pelo implementador formam um compilador completo. O analisador sintático serve para controlar todo o processo de compilação, sendo portanto o cerne de um compilador. Além disso, essa implementação foi comparada com outros sistemas de geradores de analisadores sintáticos a fim de comprovar suas vantagens. Ela também contribui para facilitar a criação, implementação e compreensão de novas linguagens para problemas específicos. Uma das vantagens é a validação da gramática desenhada e a indicação clara dos pontos de erro, com a facilidade de se perceber a causa dos erros e como corrigi-los. Ele ainda possui uma recuperação automática de erros; isso não ocorre nos sistemas baseados em métodos bottom-up e apresenta uma estratégia a mais (busca de delimitadores).

12

Bibliografia PINTO, Tasso Tirapani Silva. GGLL – Um gerador de analisadores sintáticos para gramáticas gráficas LL(1) . Instituto de matemática e estatística da Universidade de São Paulo para obtenção do título de mestre em ciências. São Paulo. Agosto de 2014. BRAGA, G. H. GrView - Um Gerador Gráfico de Analisadores Sintáticos. Usp - Instituto de matemática e estatística. São Paulo, p. 39. 2009. AHO, A. V. et al. Compiladores - Princípios, técnicas e ferramentas. 2ª Edição. ed. São Paulo: Pearson, 2008.

13