Baixe o app para aproveitar ainda mais
Prévia do material em texto
DESCRIÇÃO Funcionamento do analisador sintático, Caracterização das Gramáticas Livres de Contexto e Ambíguas, Análise dos algoritmos ascendentes e descendentes. PROPÓSITO Apresentar as características da Análise Sintática, a estrutura funcional do analisador, as formas de os implementar e as especificações das gramáticas, para que este passo da compilação seja realizado corretamente. OBJETIVOS MÓDULO 1 Descrever o analisador sintático e o tratamento de erros MÓDULO 2 Identificar as características das Gramáticas Livres de Contexto e Ambíguas e suas produções MÓDULO 3 Classificar o funcionamento dos algoritmos ascendentes e descendentes MÓDULO 4 Classificar as formas de projetar analisadores sintáticos e a utilização de programas que os geram INTRODUÇÃO Na etapa de Análise da Compilação, o seu segundo passo é a Análise Sintática. O analisador sintático é o componente do compilador responsável por, a partir dos tokens gerados pela Análise Léxica, verificar se as expressões de entrada são sentenças válidas na gramática da linguagem-fonte, gerando uma árvore sintática que é repassada para o analisador semântico visando à continuidade da compilação. Neste tema, apresentaremos as características do analisador sintático, as técnicas que emprega e as formas de o implementar. Além disso, veremos as características das gramáticas que balizam o seu funcionamento. MÓDULO 1 Descrever o analisador sintático e o tratamento de erros A ANÁLISE SINTÁTICA A Análise Sintática é o segundo passo da etapa de Análise da Compilação, ela recebe do analisador léxico uma lista de tokens, os processa e passa uma árvore de sintaxe à Análise Semântica (Figura 1). Figura 1 ‒ Passo da Análise Sintática. Fonte: O Autor, 2020. O analisador sintático (AS), também chamado de parser, tem como principal objetivo verificar se os tokens gerados no passo de Análise Léxica formam uma sentença (estrutura sintática) aceita na gramática que especifica a linguagem-fonte. Mas o que queremos dizer com estrutura sintática aceita? Veja o seguinte exemplo: EXEMPLO A3 := 6 + B Esta expressão geraria os seguintes tokens: LEXEMA TIPO VALOR A ID A 3 NumInt 3 = ATRIB Atribuição 6 NumInt 6 + OpArit Soma B ID B Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Do ponto de vista léxico, está tudo correto. Porém, se a gramática especificar que um identificador (Id), por exemplo, A3 e B, somente pode ser formado por letras e que antes de uma atribuição (atrib) somente pode vir um identificador, a expressão não corresponde a uma sentença correta do ponto de vista da sintaxe da linguagem, e será gerado um erro. RELAÇÃO COM O ANALISADOR LÉXICO (AL) OU SCANNER Os passos de Análises Léxica e Sintática são intimamente associados. Apesar de academicamente eles serem vistos como sequenciais, ou seja, o scanner gera toda a sequência de tokens e os passa para o parser, na maior parte dos compiladores reais eles não funcionam desta forma. Na verdade, o AS não necessita de todos os tokens terem sido estabelecidos para fazer o seu trabalho. Na maioria dos casos, é possível construir a árvore de sintaxe de parte do programa examinando apenas um pequeno número de tokens de cada vez. Devido a isso, eles normalmente funcionam em conjunto com o parser, comandando todo o processo de análise e acionando o analisador léxico pedindo um novo token sempre que necessitar (função pedetoken()). Já o scanner deve manter controle de que partes já foram processadas do programa-fonte. (Figura 2). Figura 2 ‒ Relação analisador sintático e léxico. Fonte: O Autor, 2020. VOCÊ SABIA Este tipo de funcionamento tem origem nas limitações que os computadores antigos possuíam, pois sua pouca memória era insuficiente para armazenar toda a sequência de tokens do programa-fonte, bem como toda a árvore sintática gerada. Devido a estas limitações, o parser pedia a geração do token, criava árvores parciais e as passava para o analisador semântico já gerando a representação intermediária. Assim, após a geração da representação intermediária, a parte da árvore que havia sido gerada podia ser descartada, e o processo prosseguia pedindo novos tokens, gerando uma nova árvore, uma nova parte da representação intermediária, e assim, sucessivamente. Este tipo de funcionamento de um compilador denomina-se tradução dirigida pela sintaxe. Atualmente, com o aumento do poder computacional, vários compiladores geram a árvore toda antes de passar para a Análise Semântica, pois esta muitas vezes se beneficia da ter a árvore toda, mas a relação scanner/parser continua, normalmente, da forma tradicional. Conforme vimos, a partir do conjunto de sentenças válidas, o parser deve gerar a árvore de sintaxe, mas o que vem a ser exatamente uma árvore de sintaxe? ÁRVORES DE SINTAXE A árvore de sintaxe nada mais é que a estrutura de dados denominada árvore, onde a raiz fica no topo (Figura 3) e a partir da qual toda a estrutura se origina. Cada um dos nós pode ou não ter filho. Os que possuem filhos estão abaixo ligados por um arco ou aresta. Já os nós sem filhos são chamados folhas e aparecem na “ponta” da árvore. Figura 3 ‒ Estrutura de dados árvore. Fonte: O Autor, 2020. Imagine o seguinte comando: Se <cond> Então <C1> Senão <C2> O comando SE possui as seguintes partes: A condição. O(s) comando(s) a ser(em) executado(s) se o resultado do teste for verdadeiro. O(s) comando(s) a ser(em) executado(s) se o resultado do teste for falso. Quando o compilador encontra o SE, ele necessita acessar estas partes todas para poder gerar o código executável do comando, por isso não basta identificar os tokens – ele precisa montar uma estrutura sintática para o comando. A árvore que representaria o SE seria a da Figura 4. Figura 4 ‒ Árvore do SE. Fonte: O Autor, 2020. A árvore representa o seguinte: Comece com a raiz se é um SE. Teste a condição no filho à esquerda. Se o resultado for: Verdadeiro, siga pelo então. Falso, siga pelo senão. COMENTÁRIO Entretanto, a árvore da Figura 4 está incompleta, pois a condição e os comandos do então e do senão possuem estruturas que também precisam ser representadas na árvore, porém num tipo diferente: A árvore de expressão. ÁRVORE DE EXPRESSÃO Este tipo de árvore é construído para representar expressões aritméticas, lógicas ou de comparação. Uma expressão é composta por operadores que designam a operação que será realizada e operandos, que são os valores ou expressões que irão interagir na operação. Devido a estas características, uma árvore de expressão possui uma estrutura de representação diferente da árvore de sintaxe de um comando, já que os operadores são nós internos (possuem filhos) e os valores são as folhas das árvores. Considere a seguinte expressão: 2 + 3 Atenção! Para visualização completa da equação utilize a rolagem horizontal Sua árvore seria: Onde: O operador é +. Os operandos são 2 e 3. Vejamos um exemplo um pouco mais complexo. Considere a expressão (2 + 3) * 7, cuja árvore seria: Neste tipo de árvore, o percurso é das folhas para a raiz. Então, a interpretação seria: Pegue os operandos 2 e 3. Realize a soma. Pegue como operandos agora o resultado da soma e 7. Realize a multiplicação. Note que, pela forma como a árvore foi construída, ela representa a ordem de execução das operações, não necessitando dos parênteses como acontece quando representamos a expressão como uma expressão matemática. Normalmente, as operações em expressões são binárias, ou seja, possuem dois operandos. Algumas poucas expressões podem ser unárias com o Não lógico ou negativar um número. Devido a estas características, árvores de expressão são do tipo binário, ou seja, um nó pode ter 0, 1 ou no máximo dois filhos. CONSTRUINDO A ÁRVORE COMPLETA DO COMANDO SE Voltando ao nosso comando SE, imagine o seguinte trecho de código: Se (x > 2) Então y = (x - 2) * 7; Senão y = x + 2 * 5; Neste comando, podemosobservar o seguinte: A condição é verificar se X é maior que dois (x > 2). O comando do então é a atribuição a Y do resultado de (x - 2) * 7. O comando do senão é a atribuição a Y do resultado de x + 2 * 5. A estrutura da árvore deste comando é construída a partir da árvore da Figura 4, substituindo Cond, Então e Senão pelas árvores de expressão correspondentes, conforme você pode ver na Figura 5. Figura 5 ‒ Árvore sintática completa do SE. Fonte: O Autor, 2020. TRATAMENTO DE ERROS Se todo programa fosse escrito sem erros, o projeto do compilador seria muito simplificado. COMENTÁRIO Mormente, muitos erros ocorrem, e um bom compilador deve ajudar o programador a corrigir o seu código provendo mensagens de erros que sejam compreensíveis. Em verdade, as linguagens de programação não são projetadas tendo os erros em mente, já que elas não especificam em seus padrões como os tratar. Esta tarefa acaba ficando a cargo do projeto do compilador, gerando maior dificuldade na recuperação das incorreções dos programas. Os programas podem conter erros em múltiplos níveis, por exemplo: LÉXICOS Como colocar um símbolo não existente na linguagem. SINTÁTICOS Como uma expressão que abre um parêntese, mas não o fecha. SEMÂNTICOS Como um operador aritmético aplicado a um valor de string. LÓGICOS Como colocar um programa em loop infinito. A maior parte dos erros é detectada durante a Análise Sintática, pois, em sua maioria, são expostos quando o fluxo de tokens é validado a partir da gramática de linguagem e a cadeia não gera uma sentença válida. Outro fator que contribui para isso é a eficiência dos modernos javascript:void(0) javascript:void(0) javascript:void(0) javascript:void(0) algoritmos de AS nesta detecção. Sendo que fazer a detecção semântica ou lógica é muito mais difícil. As metas para o tratamento de erros pelo parser são: Deve relatar de forma clara e acurada os erros encontrados. A recuperação de cada erro deve ser rápida, de forma a não impactar a detecção de um novo erro. Não deve retardar de forma significativa a análise de programas sem erros. Estas metas, apesar de parecerem simples, são, na realidade, difíceis de serem implementadas, mas felizmente os erros mais comuns são simples e podem ser tratados de forma relativamente direta. ATENÇÃO A maior dificuldade é que um erro, muitas vezes, ocorre bem antes no código em relação ao ponto onde foi detectado, fazendo com que o mecanismo de tratamento tenha que “adivinhar” o que o programador pretendia fazer. Devido a isto, os algoritmos de parser, sejam LL ou LR, tentam detectá-los tão cedo quanto possível. Para tal, usam o conceito de prefixo viável, que consiste em considerar que ocorreu um erro assim que percebem que determinado token não irá corresponder a uma sentença válida. Para tornar o assunto mais claro, vejamos os aspectos obtidos por Ripley e Druseikis (1978), que realizaram uma pesquisa em um conjunto de programas escrito na linguagem Pascal por estudantes da área de TI. Eles descobriram que os erros ocorrem com uma frequência relativamente baixa, já que 60% dos programas não continham erros. Dos restantes, 80% possuíam apenas 1 erro e 13% dois erros, sendo que 90% eram erros triviais que afetavam apenas um token. Dos erros, 60% eram de pontuação, 20% de operandos e operadores, 15% de palavras-chave e os 5% restantes de outros tipos, sendo que, dos erros de pontuação, a maioria era em torno do uso incorreto do ponto e vírgula, por exemplo: Trocar o ponto e vírgula por vírgula na linha de argumentos de uma função Certo - funcao exemplo (i: inteiro; j:inteiro): Errado - funcao exemplo (i: inteiro, j:inteiro): Colocar um ponto e vírgula antes de um senão Certo – se a> b entao a := a - 5 senao b := b + 10; Errado - se a> b entao a := a + 5; senao b := b + 10; Não colocar um ponto e vírgula obrigatório Certo - Programa exemplo; Errado - Programa exemplo Deixar de colocar os dois pontos na atribuição Certo – A:= 8; Errado – A = 8; ATENÇÃO Os exemplos estão em pseudocódigo com sintaxe similar à linguagem Pascal. Vários dos erros decorrem também das diferenças entre as linguagens que usam os mesmos símbolos, mas com significados diferentes, o que confunde os programadores, como acontece com o “=”, que em C é atribuição e em Pascal comparador de igualdade, já que nesta linguagem a atribuição é “:=”. A maior parte dos compiladores lidam com esses tipos de erro sem dificuldade. Emitem um alerta e prosseguem a análise, porém, outros tipos de erros, como deixar de marcar o início ou fim de um bloco de instruções, podem ser de tratamento mais complexo. Considere o seguinte trecho de código: Se a > b entao a:= a -5 senao b:= b +10; c:= b + a; Da forma como está escrito, o senão corresponde apenas ao comando b:= b+10; e a opção da atribuição a “c” sempre irá ocorrer. Porém, se desejássemos que isso fosse parte do senão, teríamos que abrir e fechar um bloco no senão. Este seria um erro que o tratamento não conseguiria detectar. O código correto neste caso seria: Se a > b entao a:= a - 5 senao inicio b:= b +10; c:= b + a; fim; O compilador deve reportar a presença de erro informando no mínimo o local no programa- fonte onde ele foi detectado, já que existe uma boa chance de o erro ser na verdade em um token anterior. Veja este exemplo a partir de um comando SQL: Fonte: O Autor. Uma estratégia comumente usada é imprimir a linha ilegal marcando o local onde o erro foi gerado, com uma mensagem apontando, sempre que possível, o tipo do erro, por exemplo, a falta de ponto e vírgula. No exemplo acima, foi informado que não tem uma tabela especificada. Fonte: O Autor. Mas você pode dizer que está ali o nome da tabela CURSO. O que acontece é que o ponto e vírgula antes do from faz o SGBD entender que o comando acabou ali, ou seja, o erro foi gerado por um token anterior ao from. Se retirarmos o ponto e vírgula, o comando funciona. Feita a detecção, como o compilador se recupera para poder continuar a análise? RESPOSTA Existem várias estratégias, a ideia principal é que o parser volte a um estado que permita que continue o processamento da lista de tokens sem que novos erros sem sentido sejam gerados. Como assim erros sem sentido? Observe o seguinte código: Programa exemplo Var a,b,c: inteiro; Inicio a:=10; b:= 5; Se a > b entao a:= a -5 senao b:= b +10; c:= b + a; Fim; Note que falta o ponto e vírgula após o nome do programa. O correto seria: Programa exemplo; Se o compilador não atentar para este fato, pode gerar erro em todas as outras linhas, que seriam indevidos, já que o restante do programa está correto. Outro exemplo seria, se ao declarar uma variável, ocorresse um erro sintático. Ele prosseguiria na análise e não seriam gerados novos erros sintáticos, mas no próximo passo ocorreria um erro na Análise Semântica, já que a variável não teria sido criada na tabela de símbolos. Se ocorrem muitos erros logo no início da Análise Sintática, pode ser melhor abortar o processo. Imagine a seguinte situação: Um compilador C recebe como entrada um programa- fonte em Pascal. Melhor abortar logo. As estratégias mais utilizadas de recuperação para o parser são: MODALIDADE DO DESESPERO É o método mais simples de implementar. Ao descobrir um erro, o parser descarta os símbolos de entrada, um de cada vez, até encontrar um token que pertença ao conjunto de tokens de sincronização. Tokens de sincronização são usualmente os delimitadores de comando ou blocos de comando, tais como “;” “,” “}” ou “fim”, e que possuem um papel claro no programa-fonte. Este tipo de correção normalmente pula uma parte considerável da entrada sem verificar. Tem como vantagens a simplicidade e o fato de não ficar em loop infinito, o que pode ocorrer com outros métodos. RECUPERAÇÃO DE FRASES Ao detectar um erro, o parser pode corrigir a entrada restante, ou seja, substituir um prefixo da entrada por alguma cadeia que permitaque ele siga em frente. Um exemplo deste tipo de recuperação seria substituir uma vírgula entre os parâmetros de uma função por um ponto e vírgula. Originalmente desenvolvido para a Análise Descendente, tem como principal desvantagem a dificuldade em lidar com erros que efetivamente ocorreram antes do ponto de detecção. REGRAS DE PRODUÇÃO PARA ERRO Quando se tem de antemão uma boa ideia dos erros mais comuns que podem ser cometidos ao se escrever o programa-fonte em uma determinada linguagem, a sua gramática poderia ser expandida com as produções que gerassem construções ilegais. A partir daí, ela pode ser utilizada para construir um parser que gere diagnósticos apropriados para indicar o reconhecimento das construções ilegais ocorridas na lista de tokens de entrada. CORREÇÃO GLOBAL O ideal é que um compilador faça o mínimo de mudanças no programa-fonte ao processar uma cadeia inválida. Existem algoritmos que determinam a menor quantidade de mudanças a partir de uma cadeia de entrada incorreta X e uma Gramática G. Estes algoritmos construirão uma árvore gramatical para outra cadeia Y que seja derivada de X e atenda a G. Estes métodos infelizmente são custosos em termos de memória e tempo de processamento e raramente utilizados na prática. ATENÇÃO Cabe observar que atualmente, com a substituição dos antigos computadores de grande porte, a compilação passou a ser uma atividade tipicamente interativa. Desta forma, interromper o processo no momento da ocorrência do erro se tornou menos problemático e permite que a correção seja realizada imediatamente, como acontece na interpretação, o que facilita a correção dos programas e a construção dos compiladores em relação à recuperação de erros. No vídeo a seguir, você verá a construção de uma árvore sintática e as formas ascendente e descendente. VERIFICANDO O APRENDIZADO 1. DURANTE A REALIZAÇÃO DA ANÁLISE, PODEM SER DETECTADOS ERROS. EM PRINCÍPIO, O PARSER NÃO DEVE ABORTAR A ANÁLISE, DEVE REPORTAR O ERRO E REALIZAR SUA RECUPERAÇÃO. EXISTEM DIVERSAS FORMAS DE REALIZAR O TRATAMENTO DE ERRO. QUANDO A GRAMÁTICA DE LINGUAGEM-FONTE JÁ PREVÊ O QUE FAZER PARA OS ERROS MAIS COMUNS, PODEMOS UTILIZAR O MÉTODO DE TRATAMENTO: A) Modalidade do desespero B) Recuperação de frases C) Correção global D) Regras de produção para erro E) Recuperação sintática 2. ÁRVORES DE SINTAXE SÃO O PRODUTO DO PARSER E SERVEM PARA REPRESENTAR A FORMA DE EXECUÇÃO DE UM COMANDO. OBSERVE A FIGURA ABAIXO E INDIQUE A OPÇÃO QUE APRESENTA O COMANDO QUE A PRODUZ. A) Se X <= Z Entao Y = X * 2 + 7 Senao Y = X * Z - 5 B) Se X < Z Entao Y = X * 2 + 7 Senao Y = X * (Z – 5) C) Se X <= Z Entao Y = X * 2 + 7 Senao Y = X * (Z – 5) D) Se X <= Z Entao Y = X * (2 + 7) Senao Y = X * Z – 5 E) Se X <= Z Entao Y = X * (Z - 5) Senao Y = X * 2 + 7 GABARITO 1. Durante a realização da análise, podem ser detectados erros. Em princípio, o parser não deve abortar a análise, deve reportar o erro e realizar sua recuperação. Existem diversas formas de realizar o tratamento de erro. Quando a gramática de linguagem- fonte já prevê o que fazer para os erros mais comuns, podemos utilizar o método de tratamento: A alternativa "D " está correta. As quatro respostas correspondem a métodos de recuperação de erro. A modalidade desespero corresponde a descartar todos os símbolos até ser encontrado um token que permita a sincronização. A recuperação de frases tenta corrigir a entrada substituindo os símbolos que geraram erros por alguma outra cadeia que permita prosseguir com a análise. A correção global visa a analisar o código-fonte minimizando a quantidade de mudanças para fazer a recuperação. As regras de produção para erro utilizam as produções especificadas na gramática para a correção de erros. 2. Árvores de sintaxe são o produto do parser e servem para representar a forma de execução de um comando. Observe a figura abaixo e indique a opção que apresenta o comando que a produz. A alternativa "C " está correta. Se observarmos a árvore, podemos notar que, no ramo do então, a multiplicação é realizada antes da soma e, no ramo do senão, a soma é realizada antes. Desta forma, analisando as opções, temos que: Na opção A, não existem parênteses no senão e, assim, a multiplicação deveria ser realizada antes. Na opção B, embora o senão esteja correto, o teste da condição está errado: consta < e é <=. A opção C está correta. Na opção D, os parênteses estão no então e não no senão, portanto a soma seria realizada antes de multiplicação no então e depois no senão. MÓDULO 2 Identificar as características das Gramáticas Livres de Contexto e Ambíguas e suas produções GRAMÁTICAS LIVRES DE CONTEXTO As linguagens de programação são um tipo de linguagem como outra qualquer, sendo compostas de símbolos, o seu alfabeto, e de suas regras de escrita, a sua gramática. Dentre os vários tipos de linguagem, as livres de contexto são as mais adequadas para a especificação de linguagens de programação, pois, apesar de as linguagens regulares poderem definir de forma muito eficiente os aspectos léxicos, não possuem expressividade suficiente para definir as regras de escrita da linguagem, ou seja, sua sintaxe. ATENÇÃO Desta forma, as linguagens livres de contexto e as respectivas Gramáticas Livres de Contexto (GLC) vão especificar os padrões que serão utilizados na verificação da sintaxe do programa- fonte. Uma Gramática Livre de Contexto G funciona para especificar formalmente as regras da linguagem e possui em sua especificação quatro componentes: O CONJUNTO DE SÍMBOLOS TERMINAIS T Que representam os símbolos que aparecem na linguagem. O CONJUNTO DE VARIÁVEIS OU SÍMBOLOS NÃO TERMINAIS V Que são símbolos auxiliares durante as substituições. O CONJUNTO DE PRODUÇÕES P Que nos permitem gerar cadeias ou sentenças da linguagem que está sendo analisada. O SÍMBOLO INICIAL S Sendo que este símbolo S deve ser um dos símbolos variáveis (S ∈ V). Antes de continuarmos, vamos estabelecer alguns conceitos básicos que são muito importantes para o entendimento de nosso tema. SÍMBOLOS TERMINAIS SÍMBOLOS NÃO TERMINAIS REGRAS DE PRODUÇÃO FORMA SENTENCIAL E SENTENÇA SÍMBOLOS TERMINAIS São símbolos na especificação da gramática que não possuem regras que os modifiquem. Por exemplo, na seguinte gramática abaixo, 0 e 1 são símbolos terminais. S pode se tornar 0S0 S pode se tornar 1S1 S pode se tornar 1 S pode se tornar 0 S pode se tornar vazio SÍMBOLOS NÃO TERMINAIS São aqueles que pelas regras da gramática podem ser substituídos por outros, ou seja, seriam como variáveis. No exemplo da gramática acima, S é um não terminal. FORMA SENTENCIAL E SENTENÇA Especificam os lexemas que podem ser substituídos por outros. Estas regras podem ser representadas de várias formas, mas em nossos exemplos, usaremos uma notação que deriva da teoria dos conjuntos, por exemplo, a gramática: S pode se tornar 0S0 S pode se tornar 1S1 S pode se tornar 1 S pode se tornar 0 S pode se tornar vazio Poderia ser representada da seguinte forma: S → 0S0 S → 1S1 S → 0 S → 1 S → Ɛ Onde do lado esquerdo temos um símbolo não terminal ligado por uma seta (→) à produção que o pode substituir. Observação: Ɛ representa vazio. FORMA SENTENCIAL E SENTENÇA Sentença - É uma sequência de símbolos terminais. Forma Sentencial – Sequência de símbolos terminais e variáveis (símbolos não terminais). Ela pode ter apenas símbolos terminais, apenas variáveis ou uma mistura dos dois, o que implica que uma sentença é sempre uma forma sentencial, mas nem toda forma sentencial é uma sentença. Por exemplo, considerando a gramática com que temos feito os nossos exemplos, que valida se um número binário possui as seguintes características: Se o número tiver uma quantidade par de dígitos, a primeira metade deve ser o “espelho“ da segunda metade, por exemplo 011110 – note que a primeira metade é 011, logo a segunda deve ser 110. Se o número tiver uma quantidade ímparde dígitos, o digito do meio deve ser separado e os dígitos antes dele devem ser espelho dos dígitos posteriores, por exemplo 0110110 – o dígito do meio é 0, os anteriores 011 e os posteriores 110. As sequências 010, 0110, 000, 111,1001 constituem sentenças. Já 0S0, 1S1 são formas sentenciais que não são sentenças. DERIVAÇÕES A derivação de uma gramática é a sequência de formas sentenciais tal que: A primeira forma é apenas o símbolo inicial da gramática. A última forma é sempre uma sentença. As formas intermediárias podem ser obtidas pela substituição de um único símbolo não terminal pelo lado direito de uma das produções. EXEMPLOS EXEMPLO 1 Considerando nossa gramática de números binários, considere a seguinte derivação: S ⟹ 1 Esta derivação possui duas formas sentenciais que são sempre separadas pelo símbolo ⟹ O símbolo inicial da gramática S. 1 que é uma sentença. A derivação mostra que a cadeia é uma sentença da linguagem. Vejamos passo a passo: Temos a primeira forma sentencial, que é o símbolo inicial da gramática, no caso S. Utilizando a quarta produção, substituímos S por 1, criando a segunda forma sentencial, que no caso também é uma sentença e, portanto, a última forma da sequência, já que não existem mais substituições que possam ser realizadas. EXEMPLO 2 Vejamos um exemplo um pouco mais complexo. Você deseja validar se 00 pertence à gramática. Para isso, a seguinte derivação seria gerada e validaria a cadeia: S ⟹ 0S0 ⟹ 00 Inicialmente, temos a forma sentencial correspondente ao símbolo inicial S. A seguir, utilizando a primeira produção, o substituímos por 0S0, que também é uma forma sentencial, mas não uma sentença, pois possui uma variável. Por último, utilizando a produção 5, substituímos S por vazio, gerando a sentença 00. EXEMPLO 3 Um último exemplo, agora você deseja validar a cadeia 01110. S ⟹ 0S0 ⟹ 01S10 ⟹ 01110 Inicialmente, temos a forma sentencial correspondente ao símbolo inicial S. A seguir, utilizando a primeira produção, o substituímos por 0S0, que também é uma forma sentencial, mas não uma sentença, pois possui uma variável. O próximo passo é, utilizando a produção 2, substituir S por 1S1, e a cadeia fica então 01S10, que também é uma forma sentencial, mas não uma sentença, pois possui uma variável. Por último, utilizando a produção 4, substituímos S por 1 gerando a sentença 01110 e validando a entrada. ÁRVORE DE DERIVAÇÃO Outra forma de representar as derivações é usar árvores de derivação, em vez da sequência linear. ATENÇÃO Árvores de derivação são similares a árvores de sintaxe, mas possuem mais elementos referentes às produções da gramática, inclusive das variáveis utilizadas, para balizar o funcionamento do parser. Numa árvore de derivação, as folhas são os símbolos terminais, e os nós internos são as variáveis. Um nó de variável V vai ter como filhos na árvore os símbolos pelos quais é substituído na derivação. Utilizando nosso último exemplo S ⟹ 0S0 ⟹ 01S10 ⟹ 01110, a árvore seria a da Figura 6: Figura 6 ‒ Árvore de derivação. Fonte: O Autor, 2020. DERIVAÇÕES MAIS À ESQUERDA E MAIS À DIREITA Quando, ao fazermos a derivação, substituímos a variável mais à esquerda, ela é chamada derivação à esquerda. Se substituirmos a da direita, ela se chama derivação à direita. Considere a seguinte gramática: S → 0TS S → 0 T → S1T T → SS T → 10 Os terminais são 0 e 1, e os não terminais S e T, sendo o símbolo inicial S. A figura 7 mostra a árvore de derivação, com os nós numerados para facilitar a explicação, que seria gerada a partir da gramática. Figura 7 ‒ Árvore de derivação. Fonte: O Autor, 2020. Note o seguinte: Os nós 1, 3, 4, 5 e 7 são interiores e possuem símbolos não terminais. Os nós 2, 6, 8, 9, 10 e 11 são folhas e possuem os símbolos terminais que formam uma sentença. Os filhos do nó 1 (2, 3 e 4) correspondem a uma produção da gramática S → 0TS. O mesmo acontece com: O nó 3 - T → S1T. Os nós 4 e 5 - S → 0. O nó 7 - T → 10. A partir da árvore, a sentença gerada seria percorrendo as folhas da esquerda para a direita, ou seja, a sequência seria 2, 9, 6, 10, 11 e 8, sendo a sentença 001100. COMENTÁRIO Se tivesse sido utilizada uma derivação mais à esquerda para a árvore, a ordem seria: S ⟹ 0TS ⟹ 0S1TS ⟹ 001TS ⟹ 00110S ⟹ 001100 Já uma derivação mais à direita produziria a seguinte sequência: S ⟹ 0TS ⟹ 0T0 ⟹ 0S1T0⟹0S11000 ⟹ 001100 Mas a sentença final seria a mesma. VALIDANDO TOKENS DE UM PROGRAMA Até agora, temos trabalhado com uma gramática bem distante das situações de uma linguagem de programação. Vamos nos aproximar da realidade. Considere uma gramática que realiza a soma ou subtração de dois inteiros. Inicialmente, teríamos que definir através de expressões regulares o que é um número e os operadores, por exemplo: int → D D* D → [0-9] + → + - → - A seguir, vamos definir o conjunto das produções válidas: PRODUÇÃO REGRA E → E + E 1 E → E- E 2 E → int 3 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Este conjunto de regras poderia ser representado como uma sentença da seguinte forma: E →E +E | E -E | int Pois bem, a partir destas regras, vamos validar a expressão 125 + 79. Intuitivamente, podemos perceber que, pela aplicação da regra 3 duas vezes e da regra 1, a sentença é válida na gramática, mas vamos passo a passo. A primeira coisa que temos que notar é que a Análise Sintática ocorre a partir dos tokens, ou seja, o analisador léxico passaria a seguinte lista de tokens: TOKEN LEXEMA Int 125 + + Int 79 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Desta forma, a sentença a ser analisada pelo parser seria int + int. PASSO 1 PASSO 2 PASSO 3 PASSO 1 Aplicando a Regra 3 uma primeira vez, substituímos um dos int por E, e a expressão fica E + int. PASSO 2 Aplicando a Regra 3 uma segunda vez, substituímos o outro int por E, e a expressão fica E + E. PASSO 3 Aplicando a Regra 1, substituímos E + E por E. Como chegamos ao final da análise e obtivemos o símbolo inicial, a expressão existe na linguagem, ou, em outras palavras, o comando está sintaticamente correto. Esta forma que apresentamos foi ascendente. Outra forma de fazer seria descendente, com os seguintes passos: PASSO 1 Aplicando a Regra 1, substituímos E por E + E. PASSO 2 Aplicando a Regra 3 uma primeira vez, substituímos um dos E por int, e a expressão fica E + int. PASSO 3 Aplicando a Regra 3 uma segunda vez, substituímos o outro E por int, e a expressão fica int + int. Que corresponde à expressão avaliada. Observe que, na realidade, as duas formas produzem a mesma árvore de derivação (Figura 8a) e de sintaxe (Figura 8b), a primeira forma a partir das folhas e a segunda a partir da raiz. javascript:void(0) javascript:void(0) javascript:void(0) Figura 8 ‒ Árvores geradas. Fonte: O Autor, 2020. Vejamos agora exemplos mais complexos. EXEMPLO Considere que agora nossa gramática irá se referir a todas as operações aritméticas entre dois inteiros, mais o uso de parênteses. Vejamos a sua especificação: int → D D* D → [0-9] + → + - → - * → * / → / ( → ( ) → ) Conjunto de produções: PRODUÇÃO REGRA E → E + E 1 E → E - E 2 E → E * E 3 E → E / E 4 E → (E) 5 E → int 6 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Temos agora os acréscimos de dois operadores, * e /, mais a pontuação pelos parênteses. A gramática ainda poderia ser representada da seguinte forma: E →E +E | E -E | E *E | E/E | (E) | int Estas produções especificam que uma expressão pode ser: Uma operação aritmética (Regra 1 a 4). Uma expressão entre parênteses (Regra 5). Um número inteiro (Regra 6). Considere agora as seguintes expressões: (60 + 40) / 5 Que seria entregue pelo Scanner como (int + int) / int. Vamos fazer então a derivação: Pela aplicação da Regra 6, três vezes a estrutura sentencial se torna (E + E) / E Pela aplicação da Regra 1, temos: (E) / E Pelaaplicação da Regra 5, temos: E / E Pela aplicação da Regra 4, temos: E O comando está correto. (60 + 40)5 Que seria entregue pelo Scanner como (int + int ) int Pela aplicação da Regra 6, três vezes a estrutura sentencial se torna: (E + E)E Pela aplicação da Regra 1, temos: (E)E Pela aplicação da Regra 5, temos: EE Como não existe regra que gere a produção EE, o comando está errado! GRAMÁTICAS AMBÍGUAS Determinadas gramáticas podem permitir a derivação de mais de uma árvore para a mesma expressão. São as Gramáticas Ambíguas. ATENÇÃO Este tipo de gramática é um problema para os compiladores, pois significa que, dependendo do contexto, uma das árvores geradas será correta e a outra não. Considere agora esta expressão: 60 + 40 / 5 Atenção! Para visualização completa da equação utilize a rolagem horizontal O parser receberia do scanner a seguinte expressão int + int / int. Vamos validar a expressão considerando as seguintes regras: PRODUÇÃO REGRA E → E + E 1 E → E - E 2 E → E * E 3 E → E / E 4 E → (E) 5 E → int 6 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Pela aplicação da Regra 6, três vezes a estrutura sentencial se torna E + E / E Pela aplicação da Regra 1, temos E / E Pela aplicação da Regra 4, temos E Validou, mas existe outra sequência que também valida: Pela aplicação da Regra 6, três vezes a estrutura sentencial se torna E + E / E Pela aplicação da Regra 4, temos E + E Pela aplicação da Regra 1, temos E Note que temos uma situação de ambiguidade, pois as sequências gerariam árvores diferentes (Figura 9): Figura 9 ‒ Árvores sintáticas geradas pela ambiguidade. Fonte: O Autor, 2020. COMENTÁRIO Para você, pode parecer estranha a árvore que realiza a soma primeiro, pois aprendemos nos bancos escolares que a divisão tem precedência. O que acontece é que a gramática da forma que foi especificada não mostra esta precedência. Para acabar com a ambiguidade, temos que estender a nossa gramática, de forma a deixar explícita a existência das precedências. Uma possível solução seria: int → D D* D → [0-9] + → + - → - * → * / → / ( → ( ) → ) Conjunto de produções: PRODUÇÃO REGRA E → E + T 1 E → E - T 2 E → T 3 T → T * F 4 T → T / F 5 T → F 6 F → int 7 F → (E) 8 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal A gramática possui agora 3 símbolos variáveis que representam: E – Soma e subtração (precedência mais baixa). T – Multiplicação e divisão (precedência intermediária). F – Números e expressões entre parênteses (precedência mais alta). Esta gramática permite apenas gerar uma árvore de derivação (Figura 10), pois não é mais ambígua. Figura 10 ‒ Árvores derivação gerada. Fonte: O Autor, 2020. No vídeo a seguir, você encontrará um exemplo de uma Gramática Ambígua, os problemas que podem ocorrer e a vantagem de empregar uma Gramática Livre de Contexto (GLC). VERIFICANDO O APRENDIZADO 1. AS DERIVAÇÕES RESULTANTES DAS PRODUÇÕES DE UMA GRAMÁTICA PODEM SER DESCRITAS DE FORMA LINEAR OU EM FORMA DE ÁRVORE DE DERIVAÇÃO. CONSIDERE A ÁRVORE DE DERIVAÇÃO ABAIXO: SABENDO-SE QUE AS PRODUÇÕES DA GRAMATICA SÃO E →E +E | E -E | INT E QUE FOI REALIZADA UMA DERIVAÇÃO MAIS À DIREITA DESCENDENTE, ESCOLHA A OPÇÃO QUE MOSTRA A REPRESENTAÇÃO CORRETA NA FORMA LINEAR: A) E ⟹ E E ⟹ E + E ⟹ E + int ⟹ int + int B) E ⟹ E E ⟹ E + E ⟹ int + E ⟹ int + intS5 C) E ⟹ E + E ⟹ int + E ⟹ int + int D) E ⟹ E + E ⟹ E + int ⟹ int + int E) E ⟹ int E ⟹ int + E ⟹ int + intS5 2. GRAMÁTICAS LIVRES DE CONTEXTO SÃO DEFINIDAS PELA LISTA DE SÍMBOLOS TERMINAIS, DE SÍMBOLOS NÃO TERMINAIS, PELO SÍMBOLO INICIAL E PELAS PRODUÇÕES. CONSIDERE A GRAMÁTICA ABAIXO: S → 0S0 S → 1S1 S → 0 S → 1 S → Ɛ A PARTIR DE SUA ANÁLISE, ESCOLHA A OPÇÃO ABAIXO QUE CORRESPONDE A UMA SENTENÇA: A) 0S1 B) 0001110 C) SS0 D) 110S E) 010 GABARITO 1. As derivações resultantes das produções de uma gramática podem ser descritas de forma linear ou em forma de árvore de derivação. Considere a árvore de derivação abaixo: Sabendo-se que as produções da gramatica são E →E +E | E -E | int e que foi realizada uma derivação mais à direita descendente, escolha a opção que mostra a representação correta na forma linear: A alternativa "D " está correta. Como vamos operar de forma descendente, começamos com a raiz com o símbolo inicial da gramática equivalente a E. A seguir, expandimos E utilizando a segunda produção equivalente a E ⟹ E + E. Como estamos utilizando derivação mais à direita, expandimos o E mais à direita por int. Ficando então E ⟹ E + E ⟹ E + int E, finalmente, expandimos o último E ficando como E ⟹ E + E ⟹ E + int ⟹ int + int 2. Gramáticas Livres de Contexto são definidas pela lista de símbolos terminais, de símbolos não terminais, pelo símbolo inicial e pelas produções. Considere a gramática abaixo: S → 0S0 S → 1S1 S → 0 S → 1 S → Ɛ A partir de sua análise, escolha a opção abaixo que corresponde a uma sentença: A alternativa "B " está correta. Os símbolos terminais da gramática são 0 e 1 e o não terminal S. Estruturas formadas por símbolos terminais e não terminais que pertençam à gramática correspondem a formas sentenciais. Formas sentenciais que possuem apenas símbolos terminais formam as sentenças. Portanto, a resposta é 0001110. MÓDULO 3 Classificar o funcionamento dos algoritmos ascendentes e descendentes MÉTODOS DE IMPLEMENTAÇÃO Os analisadores sintáticos podem utilizar os seguintes métodos para sua implementação: MÉTODOS UNIVERSAIS Que podem tratar qualquer gramática. Apesar de lidarem com qualquer tipo de gramática, são ineficientes e, portanto, não utilizados em compiladores comerciais. MÉTODOS DESCENDENTES (TOP-DOWN OU PARSER LL) Que buscam construir a árvore de derivação a partir da raiz para as folhas e que trabalham como gramática LL. MÉTODOS ASCENDENTES (BOTTOM-UP OU PARSER LR) Que tratam gramáticas LR e constroem a árvore de derivação das folhas para a raiz. ATENÇÃO Os dois últimos métodos varrem a entrada da esquerda para a direita e são amplamente utilizados tanto em implementações manuais, que normalmente empregam métodos descendentes, quanto por geradores de analisadores sintáticos, mormente métodos ascendentes. ALGORITMOS DE ANÁLISE SINTÁTICA ASCENDENTES Estes algoritmos são chamados também Análise Sintática LR e constroem a árvore de sintaxe das folhas para a raiz. Ele começa sua análise com uma entrada de tokens e tenta reescrever a árvore até o símbolo inicial. Na realidade, ele tenta localizar os símbolos mais básicos e, a partir destes, elementos maiores que enquadrem os mais básicos, e assim, sucessivamente. ATENÇÃO Se ao final da análise for obtida uma árvore de sintaxe válida pela gramática da linguagem, ou seja, o símbolo inicial está na raiz e nos rótulos das folhas, temos a cadeia de entrada, formando, desta forma, uma sentença da linguagem, e ela é passada para o próximo passo da compilação. Se isto não for possível, a cadeia não pertence à linguagem especificada pela gramática. Este processo de construção das folhas para a raiz é chamado redução, já que a cada passo se tenta reduzir uma cadeia de tokens (ou subcadeia) ao seu símbolo de origem, seguindo sucessivamente até ser atingido o símbolo inicial da gramática. O funcionamento geral é apresentado a seguir: Toma-se uma determinada sequência de tokens S. Procura-se por uma subcadeia S que possa ser substituída pelo seu símbolo de origem R na gramática. Repetir o passo (2) até que R = símbolo inicial da gramática. Se isso não for possível, S não pertence à gramática. Vejamos um exemplo: Considere a seguinte gramática: PRODUÇÃO REGRA E → E + T | T 1 T → T * F | F 2 F → x | y | z | (E) 3 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Verificando se a cadeia x + y * z pertence à linguagem. PASSO 1 PASSO 2 PASSO 3 PASSO 4 PASSO 5 PASSO 6 PASSO 7 PASSO 8 PASSO 1 Substituir o x por F utilizandoa regra 3. x + y * z ⟹ F + y * z Em termos de árvore seria: PASSO 2 Aplicar a regra 2 a F. F + y * z ⟹ T + y * z A árvore fica então: PASSO 3 Aplicar a regra 1 a T. T + y * z ⟹ E + y * z A árvore fica então: Note que x já foi reduzido ao símbolo inicial E. PASSO 4 Substituir o y por F utilizando a regra 3. T + y * z ⟹ E + F * z A árvore fica então: PASSO 5 Aplicar a regra 2 a F. E + F * z ⟹ E + T * z A árvore fica então: PASSO 6 Aplicar a regra 3 a z, substituindo-o por F. E + T * z ⟹ E + T * F A árvore fica então: PASSO 7 Aplicar a regra 2 e substituir a multiplicação por T. E + T * F ⟹ E + T A árvore fica então: PASSO 8 Aplicar a regra 1 à soma substituído por ET. E + T ⟹ E A árvore fica então: ALGORITMOS DE ANÁLISE SINTÁTICA DESCENDENTES (ASD) Neste tipo de algoritmo, a Análise Sintática parte da raiz da árvore em direção às folhas, ou seja, a partir do símbolo inicial da gramática, procura substituir os símbolos não terminais de forma a obter nas folhas a cadeia desejada. Também conhecida como Análise LL (do inglês left left) , ela lê a entrada de texto da esquerda para a direita, e produz uma derivação mais à esquerda. O que significa que, observando apenas o primeiro símbolo da cadeia, o algoritmo decide qual regra de derivação deve utilizar. Funcionamento geral: 1 Faz a leitura de uma cadeia β e do símbolo inicial da gramática S. 2 Busca-se uma regra que permita derivar ou pelo menos se aproximar de β. 3 Repete-se o passo 2 até que a cadeia não tenha mais símbolos não terminais. 4 Compara-se a cadeia obtida com β; se for igual à derivação, foi bem-sucedida. Se forem diferentes, significa que a cadeia analisada não pertence à linguagem. Vejamos um exemplo. Considere a seguinte gramática: S→cTd T→ a Se a sequência de tokens for cad, a construção seria da seguinte forma: Criar a árvore com o símbolo inicial na raiz, no caso S: A partir desta árvore, deriva-se a primeira produção expandindo-se S. A seguir, expande-se T, o que origina a árvore representada na figura. ATENÇÃO Note que a lista de tokens cad aparece nas folhas da esquerda para a direita, o que quer dizer que são válidas na gramática. ANALISADORES DESCENDENTES COM RETROCESSO Neste tipo de implementação de ASD, se ao se fazer uma avaliação ocorrer um erro e ainda houver como continuar a análise, o processo retrocede ao último estado válido e reinicia a expansão. A utilização do retrocesso permite que um conjunto maior de GLCs sejam analisadas, entretanto apresenta algumas desvantagens que derivam da natureza não determinística do método: A análise é mais demorada. A recuperação de erros é mais difícil. Pode gerar problemas para a Análise Semântica e posterior geração de código. ATENÇÃO DETERMINISMO Analisadores sintáticos são determinísticos se sempre souberem que ação tomar, independentemente da entrada de texto. Vejamos o funcionamento deste método. Considere a seguinte gramática: S → xTz T → xy | y Para a cadeia de entrada xyz, temos a seguinte sequência de análise: 1 – Inicialmente, é criada a árvore com o símbolo inicial da gramática na raiz, e a entrada não é processada. 2 – A seguir, S é expandido pela primeira produção, e o apontador da entrada é posicionado no primeiro símbolo da cadeia. 3 - É feita a comparação da folha mais à esquerda com o símbolo apontado na entrada. 4 - Como a folha mais à esquerda possui o mesmo terminal da cadeia, o símbolo é consumido, e o apontador avança para o próximo símbolo. 5 - Como a próxima folha é um não terminal (T), faz-se a sua expansão. Como existem duas produções possíveis, xy ou y, vamos utilizar a primeira. 6 - Faz-se a comparação da folha mais à esquerda ainda não processada com o símbolo apontado na cadeia de entrada. 7 - Como a folha em análise possui um símbolo terminal e ele não é igual ao símbolo da entrada, ocorreu uma falha. Ocorre, então, o retrocesso, eliminando a última expansão. 8 - Como ainda existe uma produção que pode ser utilizada para expandir T, ela é realizada. Se não houvesse mais produções para fazer a expansão de T, o ASD deveria retornar um erro e fazer o seu tratamento. 9 - Faz-se a comparação da folha mais à esquerda ainda não processada com o símbolo apontado na cadeia de entrada. 10 - Como a folha em processamento possui o mesmo terminal da cadeia, o símbolo é consumido e o apontador avança para o próximo símbolo. 11 - Como a próxima folha a ser processada possui um símbolo terminal, ele é comparado com o símbolo apontado na entrada. 12 - Como a folha em processamento possui o mesmo terminal da cadeia, o símbolo é consumido. Como a cadeia de entrada acabou e todos os tokens foram reconhecidos, a cadeia é aceita, pois pertence à gramática. RESUMINDO Este exemplo nos mostra que: A construção da árvore ocorre na raiz para as folhas, utilizando o símbolo inicial na raiz. À medida que símbolos não terminais são encontrados, eles são expandidos. Se a expansão de um não terminal gerar um símbolo terminal que não tem correspondência com a cadeia de entrada, ocorre o retrocesso, o que implica realizar tentativas e erros até encontrar a produção correta. Símbolos terminais são consumidos, ou seja, retirados da entrada quando correspondem a uma produção correta na gramática. Se ao final não for gerada uma sentença correta nas folhas, será reportado um erro. O sistema é não determinístico, pois mais de uma produção pode ter que ser testada para um mesmo símbolo não terminal. A quantidade de derivações cresce de forma exponencial em função do tamanho da cadeia de entrada e do número de produções da gramática. ANALISADORES DESCENDENTES PREDITIVOS O uso do retrocesso gera, como vimos, várias desvantagens. Uma forma de evitar o seu uso é criar um analisador preditivo. Neste tipo de analisador, a ideia é descobrir qual construção utilizar, evitando, assim, o retrocesso. COMENTÁRIO Imagine: Se no exemplo do ASD com retrocesso, no passo 5, tivéssemos utilizado a produção T → y em vez da produção T → xy, não teriam ocorrido o erro e o retrocesso. Fica a questão: Então, como o ASD consegue “prever” a produção a ser utilizada? RESPOSTA Inicialmente, o que você deve entender é que nem toda gramática pode ser analisada por este tipo de ASD. É necessário que ela permita que, ao olhar o primeiro símbolo da cadeia de entrada, possa se determinar qual produção deve ser utilizada. Veja que a gramática do último exemplo não permitia isto. Para tal, a gramática deve ter as seguintes características: NÃO PODE TER RECURSÃO À ESQUERDA O lado direito das produções deve começar com terminais. javascript:void(0) DEVE ESTAR FATORADA Para cada símbolo não terminal, deve existir apenas uma regra que comece com o mesmo terminal. Este tipo de gramática é chamado de LL(1) (Left to Right - Leftmost derivation 1) , que significa que a cadeia é lida da esquerda para a direita, fazendo uma derivação mais à esquerda, e que é utilizado o símbolo à frente, daí o 1, para determinar que produção utilizar na expansão. O conjunto de símbolos à frente que são analisados para determinar a produção denomina-se lookahead. Vejamos um exemplo. Considere a seguinte gramática: E → +EE Produção 1 E → *EE Produção 2 E → a Produção 3 E → b Produção 4 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Note que ela obedece a todas as regras, pois todas as produções começam com um símbolo terminal e não existem duas produções que começam com o mesmo símbolo. Considere agora que queremos avaliar a seguinte expressão “+ a * ba”. javascript:void(0) Inicialmente, criamos a árvore com o símbolo inicial na raiz e, ao fazermos a análise do primeiro símbolo (+), notamos que temos que aplicar a produção 1. Após a expansão da raiz, analisamos o próximo símbolo a. Ele indica que temos que aplicar a produção 3 na expansão do segundo E. Apósa expansão, o próximo símbolo * indica que temos que aplicar a produção 2 na expansão do terceiro E. Após a expansão, o próximo símbolo b indica que temos que aplicar a produção 4 na expansão do quarto E. Após a expansão, o próximo símbolo a indica que temos que aplicar a produção 3 na expansão do quinto E. Finalmente, chegamos ao final da análise e verificamos que a sentença gerada corresponde a uma construção válida na gramática. Note que, neste tipo de ASD, nunca irá ocorrer retrocesso, e seu funcionamento é bem mais rápido que o anterior, pois não existe tentativa e erro. COMENTÁRIO Um fato que você deve ter achado estranho é a forma da notação utilizada + a * ba em vez de a + b * a, que utilizamos normalmente. Esta notação é chamada de polonesa. Ela foi utilizada no exemplo para podermos definir a gramática como LL(1), pois, se utilizássemos a notação normal, a produção 1, por exemplo, seria E → E + E, que começaria com um não terminal, ou seja, teríamos uma recursão à esquerda. Neste vídeo, você encontrará exemplos de analisadores descendentes. VERIFICANDO O APRENDIZADO 1. PARSERS PODEM SER IMPLEMENTADOS COM ALGORITMOS ASCENDENTES OU DESCENDENTES. DENTRE OS DESCENDENTES, TEMOS O PREDITIVO. QUANTO A ESTE ALGORITMO EM RELAÇÃO À GRAMÁTICA ABAIXO, PODEMOS AFIRMAR QUE: S → (L) S → A L : → L , S L → S A) Ela pode ser analisada por estar fatorada. B) Ela pode ser analisada por ser LL(1). C) Ela não pode ser analisada por não estar fatorada. D) Ela pode ser analisada por ter recursão à esquerda. E) Ela não pode ser analisada por ter recursão à esquerda. 2. DURANTE O PROCESSO DE ANÁLISE, O PARSER, A PARTIR DAS PRODUÇÕES DA GRAMÁTICA E DA CADEIA DE ENTRADA, GERA ÁRVORES DE DERIVAÇÃO QUE REPRESENTAM A FORMA DE SER EXECUTADO O COMANDO QUE CONSTA NA ENTRADA. CONSIDERE A SEGUINTE GRAMÁTICA: E → E + T|T T → T * F | F F → INT |(E) DURANTE A ANÁLISE DA EXPRESSÃO INT * INT – INT, EM DETERMINADO PONTO FOI GERADA A SEGUINTE ÁRVORE INTERMEDIÁRIA: COM BASE NA ÁRVORE, NA GRAMÁTICA E NA EXPRESSÃO, PODEMOS AFIRMAR QUE: A) O analisador é descendente preditivo. B) O analisador é descendente com retrocesso. C) O analisador é descendente sem retrocesso. D) O analisador é ascendente. E) O analisador é ascendente com retrocesso. GABARITO 1. Parsers podem ser implementados com algoritmos ascendentes ou descendentes. Dentre os descendentes, temos o preditivo. Quanto a este algoritmo em relação à gramática abaixo, podemos afirmar que: S → (L) S → a L : → L , S L → S A alternativa "E " está correta. Analisadores sintáticos preditivos exigem que a gramática não tenha recursão à esquerda e esteja fatorada, o que equivale a ser LL(1). A gramática proposta possui recursão à esquerda, pois a terceira produção – L : → L, S – provoca esta situação. 2. Durante o processo de análise, o parser, a partir das produções da gramática e da cadeia de entrada, gera árvores de derivação que representam a forma de ser executado o comando que consta na entrada. Considere a seguinte gramática: E → E + T|T T → T * F | F F → int |(E) Durante a análise da expressão int * int – int, em determinado ponto foi gerada a seguinte árvore intermediária: Com base na árvore, na gramática e na expressão, podemos afirmar que: A alternativa "D " está correta. Todo método descendente começa criando a raiz com o símbolo inicial da gramática, que no caso é E. Como a árvore intermediária não possui E na raiz, ela tem que estar sendo construída a partir das folhas, portanto o analisador é ascendente. MÓDULO 4 Classificar as formas de projetar analisadores sintáticos e a utilização de programas que os geram IMPLEMENTAÇÃO DO ANALISADOR SINTÁTICO ASCENDENTE Em sua implementação, um algoritmo ascendente vai trabalhar com um autômato de pilha e vai necessitar de: Um buffer onde ficam armazenados os tokens de entrada. Uma pilha onde é feito o controle dos tokens processados. Uma tabela que indica a transição de estados a ser realizada. Uma tabela de regras gramaticais a serem aplicadas no token de entrada com as ações a serem realizadas. A base de funcionamento do algoritmo são duas ações – Reduzir e deslocar (em inglês, shift reduce) . REDUÇÃO Compreende substituir uma produção (a parte à direita da gramática) pela parte à esquerda. Por exemplo, na regra E → E + E, se tivermos a expressão E + E, iremos substituí-la por E. DESLOCAMENTO Corresponde a varrer a entrada colocando o token atual na pilha e lendo o próximo. Por exemplo, se tivermos na entrada id + int e for feito o deslocamento, id irá para o topo da pilha e será processado o +. Para um melhor entendimento, vamos a um exemplo: Considere a seguinte gramática referente à soma de números inteiros binários: E → E + E E → int E a expressão int + int O primeiro fator a ser identificado são os handles, que são uma subcadeia de caracteres que correspondem a uma produção, ou seja, ao lado direito de uma regra da gramática. No caso de nosso exemplo, os handles são “E + E” e “int”. Para cada um destes handles, a produção redutora é: HANDLE PRODUÇÃO SIGNIFICADO Redução Int E → int Substituir int por E 1 E + E E → E + E Substituir E + E por E 2 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Outro símbolo importante no processamento é o $, que identifica o final tanto da pilha quanto da cadeia de entrada. A próxima estrutura é a criação da tabela de regras de ação que possui basicamente a seguinte lógica, com base nos símbolos da pilha e na entrada: PILHA ENTRADA AÇÃO SIGNIFICADO $ Diferente de $ Deslocar Ler o próximo símbolo e colocá- lo na pilha Corresponde a uma produção Indiferente Reduzir Aplicar a regra de redução, retirar o símbolo da pilha e substituí-lo pela redução Não corresponde a uma produção Diferente de $ Deslocar Ler o próximo símbolo e colocá- lo na pilha $ $ Aceitar A expressão existe na gramática Símbolo diferente do inicial $ Erro Realizar tratamento de erro Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal No caso específico de nosso exemplo, a tabela seria: PILHA ENTRADA AÇÃO REGRA $ Diferente de $ Deslocar 1 Int Indiferente Reduzir 2 E + E Indiferente Reduzir 3 + Diferente de $ Deslocar 4 E Indiferente Deslocar 5 $ $ Aceitar 6 Diferente de $ $ Erro 7 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal PASSO 1 Na inicialização, colocamos na pilha o símbolo $ para identificar o seu final e na entrada também acrescentamos o mesmo símbolo ao final da expressão que está sendo analisada. Ficamos, então, da seguinte forma: PASSO 2 Aplicando a regra 1, lemos o próximo símbolo e o empilhamos retirando-o da entrada: PASSO 3 Lemos o primeiro elemento da pilha e verificamos se é uma produção: PASSO 4 No caso, int é uma produção. Aplicamos, então, a redução 1 e o substituímos por E, salvando E na pilha: PASSO 5 Retiramos novamente o primeiro símbolo da pilha e vamos analisar se é uma produção: Como E não é uma produção, a pilha está vazia e temos símbolos na entrada, salvamos ‘E’ na pilha e aplicamos a regra 1. Lemos o próximo símbolo na entrada colocando-o na pilha: PASSO 6 Retiramos novamente o primeiro símbolo da pilha e vamos analisar se é uma produção: Como ‘+’ não é uma produção e ainda temos símbolos na pilha, fazemos uma nova leitura para a análise: Como ‘E + ‘não é uma produção, a pilha está vazia e temos símbolos na entrada, salvamos E na pilha. Aplicamos a regra 1 e lemos o próximo símbolo na entrada colocando-o na pilha: PASSO 7 Lemos o primeiro elemento da pilha e verificamos se é uma produção: Como, no caso, int é uma produção, aplicamos, então, a redução 1 e o substituímos por E, salvando E na pilha: PASSO 8 Lemos novamente o primeiro elemento da pilha e verificamos se é uma produção: Como ‘E’ não é uma produção e temos mais símbolos na pilha, continuamos lendoaté encontrar uma produção ou chegarmos ao final da fila. No caso, achamos uma produção: Como ‘E + E’ é uma produção, aplicamos a redução 2 substituindo por E e salvando E na pilha: PASSO 9 Lemos novamente o primeiro elemento da pilha e verificamos se é uma produção: Como ‘E’ não é uma produção, mas é o símbolo inicial da gramática, e tanto a pilha quanto a entrada estão vazias, significa que ocorreu a aceitação, não havendo erro na expressão. IMPLEMENTAÇÃO DO ANALISADOR SINTÁTICO DESCENDENTE PREDITIVO Dentre as várias formas possíveis de implementar um ASD preditivo, o não recursivo baseado em tabela é a mais comum. Para podermos construir este tipo de parser, precisamos ter algumas condições: A gramática tem que ser LL(1), ou seja, sem recursão à esquerda e fatorada. Construir os conjuntos first e follow, que indicam como escolher a produção a ser aplicada na expansão do símbolo não terminal. Quanto à estrutura, iremos necessitar de: Um buffer de entrada onde $ indica o fim da cadeia de entrada. Um fluxo de saída. Uma pilha cujo fundo é marcado por $ e inicializada com o símbolo da gramática. Uma tabela sintática preditiva. Figura 11 ‒ Estrutura ASD não recursivo preditivo. Fonte: Adaptado de Aho et al, 2008. Observe na Figura 11 que o símbolo no topo da pilha é X, que é o inicial da entrada e que será analisado. A partir desta configuração, vamos ver como funciona este esquema: SE X = $ E A = $ Significa que toda a entrada foi analisada e não ocorreu, desta forma ela é reconhecida. javascript:void(0) SE X = A E <> $ Desempilha X e avança de um símbolo na entrada. SE X É NÃO TERMINAL Consulta a tabela sintática M e procura a produção a ser aplicada. Se não existir produção para X em M, ou seja, a entrada é vazia, retorna um erro. Se contém uma produção, por exemplo, X :: = UVW, então substitui na pilha X por UVW (U no topo). CONSTRUÇÃO DOS CONJUNTOS FIRST E FOLLOW Vejamos agora como construir os conjuntos First e Follow. Para tal, considere a seguinte gramática: S→ cAa A→ cB | B B→ bcB| ε Lembrando que ε significa produção vazia. CONJUNTO FIRST O conjunto First é composto pelos símbolos terminais que podem iniciar (que podem aparecer mais à esquerda) das sentenças derivadas de uma forma sentencial ou de suas sequências derivadas. Para o criar, utilizamos uma função First(α), tal que α representa uma forma sentencial, que retorna o conjunto de First da forma sentencial. javascript:void(0) javascript:void(0) Para isso, temos algumas regras: Se α = ε ou α → ε então ε pertence ao conjunto First. Se α é um terminal, então ele próprio pertence ao conjunto First. Se α é um não terminal, então todos os terminais de todas as suas produções pertencem ao conjunto First. Para maior clareza, vejamos como iremos derivar o conjunto First dos não terminais em nossa gramática. Primeiramente criamos uma tabela com uma linha para cada um dos não terminais da gramática com o seu conjunto First Vazio: Não Terminal First S ∅ A ∅ B ∅ Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Muito bem. Começamos observando que, em S→ cAa, temos um terminal c na primeira posição; portanto, c pertence a First(S): Não Terminal First S {c} A ∅ B ∅ Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Tratemos agora o A. Como ele tem duas produções, mas somente a primeira tem um terminal c, este pertence ao conjunto de A: Não Terminal First S {c} A {c} B ∅ Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Vamos agora tratar o B. Com ele, há duas produções que atendem às regras, que são bc e ε. E as duas entram em seu conjunto First: Não Terminal First S {c} A {c} B {b, ε } Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Agora, temos que rever se S ou A herdam algo. Como a única produção de S é iniciada por terminal, não existe nada a ser reprocessado; porém, A tem uma produção do tipo A→ B. Portanto, First(A) = First(A) ∪ First(B), e a tabela final fica sendo então: Não Terminal First S {c} A { b, c, ε } B {b, ε } Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal CONJUNTO FOLLOW O conjunto Follow(X) é definido como sendo composto pelos símbolos terminais que podem aparecer imediatamente após X. As regras gerais para produção do conjunto Follow são: Se um símbolo X é o não terminal mais à direita de alguma forma sentencial, então $ estará no conjunto. Se X é o símbolo inicial da gramática, $ será o seu conjunto Follow. Se existir produção na forma V→ cST, então tudo em First(T), exceto vazio(Ɛ), está em Follow(S). Se existir produção do tipo A → aB ou produção A → aBC onde First(C) contém ɛ, inclua Follow(A) em Follow(B). Vejamos um exemplo continuando com nossa gramática: S→ cAa A→ cB | B B→ bcB| ε E seu conjunto First: Não Terminal First S {c} A { b, c, ε } B {b, ε } Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Comecemos analisando S. Como ele é o símbolo inicial da gramática, terá como Follow $: Não Terminal Follow S {$} A ∅ B ∅ Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Analisando as possibilidades do símbolo A, que pela produção cAa após A pode vir o símbolo A, sendo esta a única produção onde ele aparece à direita: Não Terminal Follow S {$} A {a} B ∅ Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Analisando o símbolo B, ele aparece à direita em 3 produções: A→ cB A→ B Pelas regras, a primeira produção faz com que Follow(B) receba Follow(A): Não Terminal Follow S {$} A {a} B {a} Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal ATENÇÃO No conjunto Follow nunca aparece ɛ TABELA SINTÁTICA De posse desses conjuntos, podemos construir a tabela sintática para o nosso exemplo: Isto feito, podemos fazer um exemplo passo a passo da análise da expressão “cbca”. 1. Inicializamos a pilha com o símbolo inicial da gramática S e posicionamos a leitura no primeiro símbolo da entrada “c”: 2. Como o símbolo no topo de pilha é S e a entrada c, fazemos a expansão de S retirando-o da pilha e o substituindo por cAa: 3. Como o símbolo no topo de pilha é c e a entrada c, fazemos o casamento dos símbolos, desempilhamos c e avançamos o ponteiro de entrada: 4. Como agora o símbolo no topo da pilha é A e o da entrada b, fazemos a expansão de A obedecendo a tabela sintática: 5. Após a expansão no topo de pilha, temos B, e na entrada b, pela tabela, devemos fazer uma nova expansão, substituindo B na pilha por bcB: 6. Agora, tanto na pilha como na entrada, temos b; portanto, fazemos o casamento entre eles, desempilhamos b e avançamos o ponteiro da entrada: 7. Como novamente temos no topo da pilha e na entrada o mesmo símbolo, fazemos o casamento, desempilhamos e avançamos o ponteiro: 8. Como no topo da pilha temos B e na entrada a consultamos a tabela, e observamos que devemos fazer uma expansão vazia, então retiramos B da pilha: 9. Como novamente temos no topo da pilha e na entrada o mesmo símbolo, fazemos o casamento, desempilhamos e avançamos o ponteiro: 10. Como agora temos $ tanto na pilha como na entrada, indicando que as duas estão vazias, isto significa que a análise foi bem-sucedida e a sentença aceita. Assista, agora, o emprego do software GALS. VERIFICANDO O APRENDIZADO 1. DURANTE A PREPARAÇÃO PARA A CRIAÇÃO DA TABELA SINTÁTICA DE UM ANALISADOR DESCENDENTE PREDITIVO, TEMOS QUE DEFINIR OS CONJUNTOS FOLLOW E FIRST QUE MOSTRAM, RESPECTIVAMENTE, OS TERMINAIS QUE PODEM SEGUIR UM DETERMINADO SÍMBOLO E OS TERMINAIS QUE APARECEM MAIS À DIREITA EM UMA FORMA SENTENCIAL. NO PROCESSAMENTO DE UMA DETERMINADA GRAMÁTICA, FORAM ESTABELECIDOS OS CONJUNTOS FOLLOW MOSTRADOS NA TABELA ABAIXO: NÃO TERMINAL FOLLOW S {$} A {A, Ɛ} B {A} � ATENÇÃO! PARA VISUALIZAÇÃOCOMPLETA DA TABELA UTILIZE A ROLAGEM HORIZONTALCOMO BASE NESTES CONJUNTOS, PODEMOS AFIRMAR QUE: I. HOUVE UM ERRO NO PROCESSAMENTO. PORQUE II. NO CONJUNTO FOLLOW NÃO PODE APARECER $. QUANTO ÀS AFIRMATIVAS ACIMA, PODEMOS AFIRMAR QUE: A) As duas estão erradas. B) As duas estão corretas. C) Somente a primeira está correta. D) Somente a segunda está correta. E) A segunda é uma justificativa da primeira. 2. A IMPLEMENTAÇÃO DE UM ANALISADOR SINTÁTICO ENVOLVE, NORMALMENTE, UM BUFFER COM A CADEIA DE ENTRADA E UMA PILHA, ONDE SÃO ARMAZENADOS OS SÍMBOLOS EM PROCESSAMENTO. ANALISANDO AS OPÇÕES, DIGA QUAL A SITUAÇÃO QUE INDICA QUE OCORREU UM ERRO NO PROCESSAMENTO DA CADEIA. A) A) B) B) C) C) D) D) E) E) GABARITO 1. Durante a preparação para a criação da tabela sintática de um analisador descendente preditivo, temos que definir os conjuntos Follow e First que mostram, respectivamente, os terminais que podem seguir um determinado símbolo e os terminais que aparecem mais à direita em uma forma sentencial. No processamento de uma determinada gramática, foram estabelecidos os conjuntos Follow mostrados na tabela abaixo: Não Terminal Follow S {$} A {a, Ɛ} B {a} � Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal Como base nestes conjuntos, podemos afirmar que: I. Houve um erro no processamento. porque II. No conjunto Follow não pode aparecer $. Quanto às afirmativas acima, podemos afirmar que: A alternativa "C " está correta. O símbolo de final de entrada $ sempre irá aparecer no conjunto Follow, portanto a segunda afirmativa está errada. A primeira afirmativa está correta porque a produção vazia Ɛ nunca pode aparecer no conjunto Follow. 2. A implementação de um analisador sintático envolve, normalmente, um buffer com a cadeia de entrada e uma pilha, onde são armazenados os símbolos em processamento. Analisando as opções, diga qual a situação que indica que ocorreu um erro no processamento da cadeia. A alternativa "A " está correta. A opção A está correta, pois, se ao atingirmos o final da pilha ainda existem símbolos diferentes de $ na entrada, fica caracterizado que a sentença não pertence à gramática. As opções B e C mostram uma situação intermediária da análise ou ainda temos símbolos tanto na pilha como na entrada. A opção D mostra a situação de aceitação da entrada, pois, tanto a pilha como a entrada estão vazias, e está errada, já que identificadores aceitam letras que sejam maiúsculas ou minúsculas da forma que a especificação foi realizada. A opção E mostra uma situação errada, porque ainda há dados a serem analisados e a pilha está vazia. CONCLUSÃO CONSIDERAÇÕES FINAIS Ao longo deste tema, fizemos uma viagem pelos conceitos relacionados à Análise Sintática. Iniciamos estudando o que é o analisador sintático, o que é uma árvore de sintaxe e como construí-la e o tratamento de erro. No módulo 2, tratamos de Gramáticas Livres de Contexto e Ambíguas. A seguir, tratamos dos tipos de algoritmos, ascendentes ou descendentes, que podem ser utilizados pelos parser e suas principais características. Finalmente, no módulo 4, estudamos especificamente a construção de analisadores sintáticos, suas funções básicas, o uso da pilha e, no GALS, vimos como configurar a sua criação automática. AVALIAÇÃO DO TEMA: REFERÊNCIAS AHO, A. V. et al. Compiladores: Princípios, técnicas e ferramentas. 2. ed. São Paulo: Pearson, 2008. COOPER, K. D.; TORCZON, L. Construindo Compiladores. 2. ed. Rio de Janeiro: Elsevier, 2014. LOUDEN, K. C. Compiladores: Princípios e práticas. São Paulo: Cengage Learning, 2004. RIPLEY, G.; DRUSEIKIS, F. A Statistical Analysis of Syntax Errors. In: J. Computer Languages, v. 3, Issue 4, USA, 1978. pp. 227-240. SANTOS, P. R.; LANGLOIS, T. Compiladores: Da teoria à prática. Rio de Janeiro: LTC, 2018. TANENBAUM, A. S. Organização Estruturada de Computadores. 5. ed. São Paulo: Pearson, 2006. EXPLORE+ Para saber mais sobre os assuntos tratados neste tema, leia: SConceitos de linguagens de programação, Robert Sebesta, 11ª edição, 2018. CONTEUDISTA Sidney Nicolau Venturi Filho CURRÍCULO LATTES javascript:void(0);
Compartilhar