Análise Sintática Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife ‹#› Contatos Prof. Guilherme Alexandre Monteiro Reinaldo Apelido: Alexandre Cordel E-mail/gtalk: [email protected] [email protected] Site: http://www.alexandrecordel.com.br/fbv Celular: (81) 9801-1878 Etapas da Compilação Análise Léxica Análise Sintática Front-End (Análise) Analise Semântica Geração de Código Intermediário Geração de Código Final Back-End (Síntese) 3 Análise Sintática Alguns autores consideram que a análise sintática envolve tudo que diz respeito à verificação do formato do código fonte •Inclui a análise léxica como subfase •Visão mais coerente, porém o livro texto que usamos tem outra visão... 4 Análise Sintática Entenderemos análise sintática como sendo apenas a segunda fase dessa verificação de formato: • “É a fase que analisa os tokens para descobrir a estrutura gramatical do código fonte” • Também chamada “Reconhecimento” (Parsing) • Porém, um nome melhor seria “Análise Gramatical” 5 Gramáticas Livres de Contexto Gramáticas São usadas para organizar os tokens em “frases” de sentido lógico Definem regras de formação recursivas expressão → CTE_INT | ID | expressão + expressão 7 Gramáticas As gramáticas livres de contexto possuem quatro elementos: •Símbolos terminais •Símbolos não-terminais •Símbolo inicial •Produções! ou Regras de Produção! 8 Gramáticas Elementos das gramáticas livres de contexto: •Símbolos terminais: - Símbolos assumidos como atômicos, indivisíveis - Em compiladores, são os tokens (int, +, -, /, identificador, valores literais, etc) •Símbolos não-terminais: - Usados para organizar os tokens em “frases” - Representam elementos abstratos do programa (expressões, termos, etc) 9 Gramáticas Elementos das gramáticas livres de contexto: • Símbolo inicial: - Não-terminal a partir do qual são derivadas “cadeias” de símbolos terminais - Geralmente é um não-terminal chamado programa • Produções: - São as regras de formação - Definem as “frases” de terminais válidas na linguagem 10 Notações Notação formal típica •Símbolo não-terminal: letras maiúscula (E, T) •Símbolo terminal: letras minúsculas, sinais, etc. (x,i) E → | T → | T T + E x i 11 Notações Notação da Gramática BNF (Backus Naur Form) •Símbolo não-terminal delimitado por “<“ e “>” <expressao> ::= <termo> | <termo> "+" <expressao> <termo> ::= "x" | "i" 12 Notações Notações EBNF (existem várias versões) •Não-terminais sem delimitadores •BNF + operadores de expressões regulares expressao = termo {"+" termo}* termo = "x" | "i" 13 Notações Notações que usaremos • Formal: para mostrar conceitos mais teóricos • BNF e EBNF: para os exemplos práticos - Tokens aparecerão literalmente se forem simples - Ex.: sinais: “(”, “+”, “;” - palavras-chave: “int”, “for”, “public”, etc. - Tokens com várias opções de casamento aparecerão em maiúscula (ex.: identificadores, valores literais) 14 Gramáticas A partir do símbolo inicial, podemos derivar (gerar) as cadeias (palavras) de terminais que são válidas na linguagem 15 Derivação Seja a gramática BNF anterior • Derivar a cadeia “i+i+x” <expressao> <termo> + <expressao> i + <expressao> i + <termo> + <expressao> i + i + <expressao> i + i + <termo> i + i + x • Consideremos que esta é uma derivação mais à esquerda 16 Derivação Seja a gramática BNF mostrada antes •Agora a Derivação mais à direita da cadeia “i+i+x” <expressao> <termo> + <expressao> <termo> + <termo> + <expressao> <termo> + <termo> + <termo> <termo> + <termo> + x <termo> + i + x i + i + x 17 Derivação O processo de derivação consiste em substituir cada ocorrência de um não-terminal pelo lado direito (corpo) de alguma de suas produções • Derivação mais à esquerda: substituir sempre o nãoterminal mais à esquerda • Derivação mais à direita: análogo A derivação pára quando sobrarem apenas terminais e o resultado é a cadeia 18 Árvore de Derivação A árvore dos exemplos anteriores expressao termo i + expressao termo + expressao i termo a cadeia gerada pode ser percebida nas folhas, analisando-as da esquerda para a direita 19 x Árvore de Derivação A mesma árvore reorganizada expressao termo expressao termo expressao termo i + i + a seqüência de terminais (cadeia) gerada x 20 Árvore de Derivação Mostra de maneira estática as produções aplicadas • Não diferencia se foi uma derivação mais à esquerda ou mais à direita que gerou a cadeia Forma • Tem o símbolo inicial como raiz: - (expressão) • Não-terminais formam nós intermediários: - (expressões e termos) • As folhas são os terminais (tokens) da cadeia: - (i, +, x) 21 Gramáticas Ambíguas Uma gramática é dita ambígua se ela puder gerar duas árvores de derivação distintas para uma mesma cadeia Veremos uma gramática equivalente à anterior, porém ambígua... 22 Gramáticas Ambíguas Exemplo <expressao> ::= <expressao> "+" <expressao> | "x" | "i" •Mostrar duas árvores de derivação para “i+i+x” 23 Exercício As gramaticas a seguir são ambíguas? E -> | | | E + E E * E (E) a S -> | | E -> if E then S if E then S else S s e 24 Exercício É ambígua já que existem duas derivações mais à esquerda para a cadeia a + a + a: A -> A + A | A − A | a 25 Gramáticas Ambíguas Gramáticas ambíguas são, em geral, inadequadas para uso em compiladores •Dificultam a construção do analisador sintático Em alguns casos, são usadas gramáticas ambíguas junto com restrições adicionais •Exemplo: precedência e associatividade 26 Análise Sintática Vimos que gramáticas são formalismos que geram cadeias Em compiladores, não vamos gerar uma cadeia, mas já temos a cadeia de terminais (ou seja, de tokens) pronta... Diante disso, qual seria a função do analisador sintático? 27 Introdução à Análise Sintática Análise Sintática O objetivo •Descobrir como uma sequência de tokens pode ser gerada pela gramática da linguagem Em outras palavras •Entrada: sequência de tokens •Saída: árvore 29 Análise Sintática O módulo de software responsável por essa etapa pode ser chamado de •Analisador sintático ou parser (reconhecedor) Existem duas estratégias algorítmicas que podem ser adotadas •Bottom-up / ascendente •Top-down / descendente 30 Análise Sintática Usaremos a seguinte gramática não-ambígua para ilustrar, a seguir, as duas estratégias de análise sintática <expressao> ::= <termo> | <termo> "+" <expressao> <termo> ::= "x" | "i" 31 Análise Top-down Parte da raiz (símbolo inicial) e tenta criar a árvore de cima para baixo Recursivamente testa se a cadeia de tokens (lida da esquerda para a direita) pode ser gerada pelas produções de cada não-terminal O processo de construção da árvore lembra uma derivação mais à esquerda da cadeia 32 Análise Top-down O parser vai ter que escolher uma produção adequada para o símbolo inicial <expressao> expressao ? i + i + 33 x Análise Top-down Sabe-se que ambas as produções iniciam com <termo>, variando o restante expressao ? termo ? i + i + 34 x Análise Top-down Ao ler o token “i”, o parser identifica que é gerado por <termo>, mas falta decidir o resto... expressao ? termo i + i + 35 x Análise Top-down A descoberta do “+” faz o parser decidir a produção adequada expressao termo expressao ? i + i + 36 x Análise Top-down Processo similar acontece após a leitura dos dois tokens seguintes expressao termo expressao termo expressao ? i + i + 37 x Análise Top-down Porém, no último token, <expressão> vai ter apenas <termo> e o parser encerra no EOF (fim de arquivo) expressao termo expressao termo expressao termo i + i + 38 x EOF Análise Bottom-up Parte das folhas (tokens) e tenta crescer a árvore até a raiz (símbolo inicial) Para isso, compara a sequência de símbolos do lado direito (ou corpo) das produções para tentar criar um ramo da árvore Diz-se que a sequência é “reduzida” ao nãoterminal do lado esquerdo da produção39 Análise Bottom-up Tenta crescer a árvore usando o corpo das produções, até chegar ao símbolo inicial expressao i + i + 40 x Análise Bottom-up O token “i” é reduzido ao não-terminal <termo>, devido à produção <termo> ::= “i” expressao termo i + i + 41 x Análise Bottom-up O parser lê o token “+”, mas ainda não pode fazer uma redução expressao termo i + i + 42 x Análise Bottom-up Mais uma redução ao não-terminal <termo> expressao termo i termo + i + 43 x Análise Bottom-up Apenas continua a leitura expressao termo i termo + i + 44 x Análise Bottom-up Nova redução ao não-terminal <termo> expressao termo i termo + i termo + 45 x Análise Bottom-up Como acabaram-se os tokens, o último <termo> só pode ser gerado diretamente por <expressao>, então reduz expressao expressao termo i termo + i termo + 46 x EOF Análise Bottom-up Agora, a subcadeia “<termo>+<expressao>” pode ser reduzida para <expressao> expressao expressão expressão termo i termo + i termo + 47 x Análise Bottom-up Outra redução, usando a mesma produção expressao expressao expressao termo i termo + i termo + 48 x Exercício Realizar a análise bottom-up da seguinte gramática para a cadeia “a + a * a”: E E T T F F -> -> -> -> -> -> E + T T T * F F E a 49 Resposta 50 Top-down x Bottom-up A análise sintática top-down é mais fácil de entender e de implementar, porém a bottomup é mais poderosa (aplicável em mais linguagens) Uso principal das duas estratégias • Bottom-up: usada pelos melhores geradores semiautomáticos de parsers • Top-down: melhor técnica para implementar manualmente 51 Top-down x Bottom-up Chama-se gramática LL àquela que permite a construção de um parser top-down (descendente) para reconhecê-la Chama-se gramática LR àquela que permite a construção de um parser bottom-up (ascendente) para reconhecê-la 52 Análise Sintática Além de construir a árvore, outras atribuições importantes do analisador sintático são: •Reportar erros, o que deve ser feito de maneira clara para permitir ao usuário corrigir o problema •Recuperar-se de erros automaticamente (pouco uso em compiladores comerciais) 53 Análise Sintática Na verdade, a análise sintática não precisa construir a árvore durante o reconhecimento Só é necessário construir a árvore se a análise sintática for separada das etapas seguintes Em todo caso, o parser vai funcionar como se estivesse descobrindo a árvore que seria gerada pela gramática para os tokens dados 54 Conceitos Conceitos Veremos alguns conceitos adicionais ligados à fase de análise sintática • Árvore sintática • Sintaxe abstrata • Precedência e associatividade • Sintaxe concreta 56 Árvore Sintática É quase igual à árvore de derivação, porém é organizada de maneira mais “racional” Cada nó interior é uma construção da linguagem ou um operador Cada nó filho é uma parte significativa da construção ou um operando • São descartados: pontuação, parênteses, etc. 57 Árvore Sintática Gramática para os exemplos a seguir expressao ::= | | | | | | expressao + expressao expressao - expressao expressao * expressao expressao / expressao ( expressao ) IDENTIFICADOR INTEIRO_LITERAL 58 Árvore de Derivação Árvore de derivação de “x*(i+i)” expressao expressao x * expressao ( expressao expressao + ) expressao i i 59 Árvore Sintática Árvore sintática de “x*(i+i)” produto var x soma var var i i 60 Sintaxe Abstrata É comum uma linguagem ser especificada por meio de uma gramática de sintaxe abstrata •Em geral, é ambígua •Porém, mais simples de entender Para resolver as ambiguidades, a especificação precisa definir restrições adicionais 61 Sintaxe Abstrata Um exemplo seria a gramática mostrada antes expressao ::= | | | expressao + expressao expressao * expressao ( expressao ) INTEIRO_LITERAL É comum assumir associatividade à esquerda e precedência maior para a multiplicação 62 Associatividade Associatividade diz como será aplicada uma mesma operação binária quando há vários operandos • Exemplo: como interpretar a + b + c + d + e ? • Se o operador for associativo à esquerda: ((((a + b) + c) + d) + e) • Se o operador for associativo à direita: (a + (b + (c + (d + e)))) 63 Precedência Precedência diz qual operação binária será aplicada primeiro houver operadores diferentes • Exemplo: como interpretar a + b * c + d * e ? • Se o operador * tiver maior precedência: ((a + (b * c)) + (d * e)) • Se o operador + tiver maior precedência: (((a + b) * (c + d)) * e) 64 Sintaxe Concreta Por outro lado, a gramática tal como ela foi usada para implementar o parser é chamada de sintaxe concreta •Geralmente não tem ambigüidades •Mais fácil de implementar Específica da implementação •Cada compilador (de uma mesma linguagem) pode criar uma implementação diferente 65 Sintaxe Concreta Exemplo de sintaxe concreta correspondente à gramática de expressões anterior expressao ::= termo + expressao | termo termo ::= fator * termo | fator fator ::= ( expressao ) | INTEIRO_LITERAL 66 Tratando Ambiguidades Tratando Ambiguidades Veremos como tratar gramáticas ambíguas (sintaxe abstrata), de modo a prepará-la para ser usada em um parser (sintaxe concreta) Veremos como tratar dois tipos de ambiguidades: •Ambiguidade do “else” •Ambiguidade de expressões 68 Tratando Ambiguidades A seguinte de definição de comando apresenta ambigüidade cmd ::= if ( expr ) cmd else cmd | if ( expr ) cmd | outro expr ::= x Exemplo: “if (x) if (x) outro else outro” •A qual “if” está ligado o “else”? 69 Tratando Ambiguidades O mais comum é considerar que o “else” casa com o “if” aberto mais próximo Geralmente, a definição anterior funciona bem com as técnicas que vamos aprender Mas, caso seja desejado, é possível remover essa ambiguidade... 70 Tratando Ambiguidades A estratégia é classificar os comandos em comandos incompletos (ou abertos) e completos Comandos completos (matched) • if-else • todos os outros Comandos incompletos ou abertos (open) • if (sem else) • if-else com um comando incompleto após o71else Tratando Ambiguidades Solução cmd ::= matched-cmd | open-cmd matched-cmd ::= | if ( expr ) matched-cmd else matched-cmd | outro open-cmd ::= | if ( expr ) cmd | if ( expr ) matched-cmd else open-cmd 72 Tratando Ambiguidades Como mostrado, a gramática abaixo é ambígua, mas essa ambiguidade pode ser resolvida com regras de precedência e associatividade expressao ::= | | | | | | expressao + expressao expressao - expressao expressao * expressao expressao / expressao expressao ^ expressao ( expressao ) INTEIRO_LITERAL Como incluir essas regras na própria gramática? 73 Tratando Ambiguidades Criar um não-terminal para cada nível de precedência •Chamaremos de: exprA, exprB, exprC... No último nível (máxima precedência) ficam apenas expressões não binárias 74 Tratando Ambiguidades O não-terminal de cada nível tem uma produção para cada operador do nível Os operandos serão •o não-terminal do nível atual, para outras operações do mesmo nível •e o não-terminal do próximo nível (nível de maior precedência) 75 Tratando Ambiguidades Na produção para os operadores, a posição do não-terminal do nível atual indica o tipo de associatividade do operador • Se estiver à esquerda: associativo à esquerda • Se estiver à direita: associativo à direita Para tratar o caso de não haver nenhuma operação do nível, deve haver uma produção de substituição para o próximo nível 76 Tratando Ambiguidades No exemplo anterior, vamos assumir três níveis para os operadores binários • As demais expressões formam um quarto nível Ordenados da menor para a maior precedência: • adição e subtração, associativos à esquerda - exprA • multiplicação e divisão, assoc. à esquerda - exprB • exponenciação, assoc. à direita - exprC 77 Tratando Ambiguidades Resultado expressao ::= exprA exprA ::= exprA + exprB | exprA - exprB | exprB associativos à esquerda ... 78 Tratando Ambiguidades Resultado (continuação) exprB ::= exprB * exprC | exprB / exprC | exprC associativos à esquerda exprC ::= exprD ^ exprC | exprD associativo à direita exprD ::= ( expressao ) | INTEIRO_LITERAL 79 Bibliografia AHO, A., LAM, M. S., SETHI, R., ULLMAN, J. D., Compiladores: princípios, técnicas e ferramentas. Ed. Addison Wesley. 2a Edição, 2008 (Capítulo 4) 80