Compiladores e Computabilidade: Conceitos e Processos

Unidade I COMPILADORES E COMPUTABILIDADE Prof Leandro Fernandes Roteiro Contextualização e conceitos básicos O que acontece desde a codificação até a execução de um programa O modelo de análise e síntese Análise léxica a 1ª etapa O emprego das gramáticas regulares e autômatos finitos O processo de análise sintática Tipos de analisadores e recuperação de erros Analisadores descendentes Descendentes recursivos e LL1 Linguagens ferramentas e tradutores gcc javac masm JVM dot NET Browser Visual Studio Eclipse Netbeans Assembly Java HTML PHP CC Linguagem Ferramenta de Apoio Interpre tador Compilador Tradutor Montador Da codificação a execução Código fonte Pré processador Código fonte sem macros Compilador Código em Linguagem de Montagem Montador Código objeto Linker Ligador Código de máquina realocável Loader SO Carregador Código de máquina absoluto Estrutura dinâmica de um compilador cont Compiladores de duas passagens modelo de análise e síntese Interatividade Qual tipo de software tradutor deve ser utilizado para programas em geral quando a velocidade de execução é uma exigência de alta prioridade a Compiladores b Interpretadores c Tradutores híbridos d Macroprocessadores e Interpretadores de macroinstruções Resposta Qual tipo de software tradutor deve ser utilizado para programas em geral quando a velocidade de execução é uma exigência de alta prioridade a Compiladores b Interpretadores c Tradutores híbridos d Macroprocessadores e Interpretadores de macroinstruções Analise léxica tokenização ou scanning Produzir símbolos terminais Ignorar e descartar símbolos irrelevantes espaços em branco caracteres de tabulação caracteres de controle CR e LF Comentários Tokens possuem uma estrutura sintática identif letra letra dígito número dígito dígito if i f igual Por que o analisador léxico não é uma parte do analisador sintático Isso deixaria o analisador sintático mais complicado de ser construído Dificulta a distinção entre palavras reservadas e identificadores Precisaria ser reescrito na forma Por que o analisador léxico não é uma parte do analisador sintático O scanning deve eliminar brancos tabulações fins de linha e comentários Esses caracteres podem ocorrer em qualquer lugar do código levando a gramáticas muito complexas Tokens podem ser descritos por linguagens regulares mais simples e mais eficientes que as gramáticas livres de contexto Usando uma gramática regular para representar lexemas Um gramática é dita regular se suas produções são na forma Ex gramática de nomes Definição alternativa O scanner como um AFD Autômato Finito Determinístico Exemplo para a entrada max 30 Portanto a análise léxica deverá esquadrinhar o código fonte símbolo a símbolo compondo tokens e classificálos eliminar elementos desnecessários ao processo de compilação reconhecer e validar números inteiros e reais reconhecer e validar os elementos utilizados como identificadores prover recursos para que se projete um mecanismo de controle de erros mais amigável interagir com o sistema de arquivos Interatividade Dentre os diferentes tipos de mensagens de erro que podem ser reportados por um compilador quais dentre as apresentadas abaixo são de natureza léxica a Identificador não declarado b Esperado fim de comentário c Esperado símbolo X porém encontrado símbolo Y d Número de parâmetros insuficiente durante a chamada de uma subrotina e Tipo misturado durante uma atribuição Resposta Dentre os diferentes tipos de mensagens de erro que podem ser reportados por um compilador quais dentre as apresentadas abaixo são de natureza léxica a Identificador não declarado b Esperado fim de comentário c Esperado símbolo X porém encontrado símbolo Y d Número de parâmetros insuficiente durante a chamada de uma subrotina e Tipo misturado durante uma atribuição Análise sintática 2ª etapa do processo de análise Analisador Sintático Árvore sintática Tabela de símbolos Analisador Léxico Tokens A análise sintática deve Comprovar que a sequência de tokens cumpre as regras sintáticas da linguagem identificar erros de sintaxe Compor a estrutura hierárquica dos comandos e expressões A B C AB C em Fortran A BC em APL Recuperação de erros de sintaxe Importante não retardar de forma significativa o processamento de programas corretos Especificando a linguagem por meio de Gramáticas Livres de Contexto Gramáticas regulares não podem lidar com estruturas aninhadas ou com recursões centrais Expr Expr Cmd do Cmd while Expr Solução Gramáticas Livres de Contexto Vantagens na utilização de gramáticas especificações sintáticas permite uso de geradores automáticos o processo de construção pode levar à identificação de ambiguidades facilidade em ampliarmodificar a linguagem Tipos de analisadores sintáticos Métodos descendentes Top Down Constroem a árvore sintática de cima para baixo da raiz para as folhas ou seja do símbolo inicial da gramática para a sentença Analisadores descendentes recursivos Analisadores LLk E E T T F a F T a F a E E T T F a F T a F a E E T a F T a a E E T a T a a E a a a Tipos de analisadores sintáticos Métodos ascendentes Bottomup Constroem a árvore sintática de baixo para cima das folhas para a raiz ou seja reduz os símbolo da sentença até alcançar o símbolo inicial da gramática Analisadores LR Analisadores LALR E E T T F a F T a F a E T T F a F T a F a E T F a F T a F a E a F T a F a a F a a Tipos de analisadores sintáticos Tanto em analisadores ascendentes quanto descendentes a entrada sempre é examinada da esquerda para a direita um símbolo por vez Muitos compiladores são dirigidos pela sintaxe parsen driver isto é o analisador sintático chama o analisador léxico Ferramentas para geração automática de analisadores sintáticos baseiamse na gramática Ex Yacc Bison e ANTLR Recuperação de erros Modo Pânico ou Desespero para imediatamente ou descarta símbolos até que seja encontrado um token de sincronização Recuperação de frases tenta realizar uma correção local substituindo alguns elementos que permitam à análise prosseguir Ex substituir uma vírgula inadequada por um ponto e vírgula remover um excedente Recuperação de erros cont Produções de erro aumentase a gramática incluindo regras de forma a acomodar os erros mais comuns Correção global um algoritmo escolhe a sequência mínima de mudanças necessárias para se obter a correção Ex dada uma cadeia x o parser procura árvores gramaticais que permitam transformar x em y cadeia correta com um mínimo de modificações Interatividade Analise o texto Na compilação a análise consiste em três fases Em uma das fases os caracteres ou tokens são agrupados hierarquicamente em coleções aninhadas com significado coletivo Essa fase envolve o agrupamento dos tokens do programa fonte em frases gramaticais que são usadas pelo compilador a fim de sintetizar a saída Usualmente as frases gramaticais do programa fonte são representadas por uma árvore gramatical A fase citada no texto é conhecida como análise a sintática b semântica c léxica d binária e linear Resposta Analise o texto Na compilação a análise consiste em três fases Em uma das fases os caracteres ou tokens são agrupados hierarquicamente em coleções aninhadas com significado coletivo Essa fase envolve o agrupamento dos tokens do programa fonte em frases gramaticais que são usadas pelo compilador a fim de sintetizar a saída Usualmente as frases gramaticais do programa fonte são representadas por uma árvore gramatical A fase citada no texto é conhecida como análise a sintática b semântica c léxica d binária e linear Análise sintática Tarefa dada uma gramática livre de contexto G e uma sentença s o analisador sintático deve verificar se s pertence à linguagem gerada por G O analisador tenta construir a árvore de derivação para s segundo as regras de produção dadas pela gramática G Se esta tarefa for possível o programa é considerado sintaticamente correto O analisador não precisa efetivamente construir a árvore mas sim comprovar que é possível construíla Pode ser emulado utilizandose uma pilha de dados Análise sintática descendente analisadores descendentes recursivos São construídos transcrevendose cada uma das regras de produção da gramática como uma subrotina que será responsável por consumir os tokens da sentença Assim temos para cada símbolo não terminal da regra invocamos a subrotina correspondente e para cada símbolo terminal da regra verificamos se ele ocorre na posição corrente da análise Análise sintática descendente analisadores descendentes recursivos Suponha a gramática abaixo 1 L S 2 S I S I 3 I a L void parseL accept parseS accept void parseS parseI while s acceptIt parseI void parseI switch s case a acceptIt break case parseS break default ERRO 1 2 3 Análise sintática descendente analisadores LL1 O nome LL1 indica que a cadeia de entrada é examinada da esquerda para a direita lefttoright o analisador procura construir uma derivação esquerda leftmost considerase apenas o 1º símbolo do restante da entrada Análise sintática descendente analisadores LL1 Temos de decidir qual regra A deve ser aplicada a um nó rotulado por um não terminal A A expansão de A é feita criando nós filhos rotulados com os símbolos de Considera duas informações o não terminal a ser expandido e o símbolo corrente da entrada Uma tabela M nos fornece a regra a ser utilizada com base nessas duas entradas Essa técnica só pode ser usada para a classe das gramáticas LL1 Analisador LL1 Seja a gramática 1 E T E FirstTE a 2 T F T FirstFT a 3 F E FirstE 4 F a Firsta a 5 E T E FirstTE 6 E FollowE 7 T F T FirstFT 8 T FollowT Analisador LL1 Seja a gramática 1 E T E FirstTE a 2 T F T M E 1 3 F E M E a 1 4 F a 5 E T E 6 E 7 T F T 8 T Analisador LL1 Seja a gramática 1 E T E 2 T F T 3 F E 4 F a 5 E T E 6 E FollowE 7 T F T M E 6 8 T M E 6 Analisador LL1 Seja a gramática 1 E T E 2 T F T 3 F E 4 F a 5 E T E 6 E 7 T F T 8 T a E 1 1 T 2 2 F 3 4 E 5 6 6 T 8 7 8 8 Analisando a sentença aa Pilha Entrada Regra E aa ME a 1 E T E T E aa MT a 2 T F T F T E aa MF a 4 F a a T E aa Verifica a T E a MT 8 T E a ME 5 E T E T E a Verifica T E a MT a 2 T F T F T E a MF a 4 F a a T E a Verifica a T E MT 8 T E ME 6 E Identificando se uma gramática é LL1 1 E E T First ET a 2 E T First T a 3 T T F 4 T F ME 1 e ME a 1 5 F E ME 2 e ME a 2 6 F a A gramática dada acima não é LL1 por causa dos conflitos Podemos descobrir por inspeção As duas características mais óbvias são a possibilidade de fatoração e a recursão à esquerda Interatividade Analise cada uma das afirmações dadas a seguir e indique a que julgar incorreta a Os parsers topdown não têm problemas em relação a gramáticas recursivas à esquerda b Yacc gera parsers bottomup que são mais eficientes c Os parsers bottomup são normalmente gerados por ferramentas d Parsers descendentes recursivos são um exemplo de parser topdown e É relativamente fácil escrever um parser topdown manualmente usando funções recursivas Resposta Analise cada uma das afirmações dadas a seguir e indique a que julgar incorreta a Os parsers topdown não tem problemas em relação a gramáticas recursivas à esquerda b Yacc gera parsers bottomup que são mais eficientes c Os parsers bottomup são normalmente gerados por ferramentas d Parsers descendentes recursivos são um exemplo de parser topdown e É relativamente fácil escrever um parser topdown manualmente usando funções recursivas