Análise Sintática Ascendente e Construção de Analisadores LR1

Unidade II COMPILADORES E COMPUTABILIDADE Prof Leandro Fernandes Roteiro Análise sintática ascendente Analisadores LR1 Análise semântica Gramática de atributos Tabela de símbolos Geração de código Linguagens intermediárias Tradução dirigida pela sintaxe Otimizações Assemblers ligadores e carregadores Análise sintática ascendente analisadores LR1 O nome LR1 indica que A cadeia de entrada é examinada da esquerda para a direita lefttoright isto é do início para o fim do arquivo O analisador procura construir uma derivação direta rightmost invertida Tornase invertida para que a entrada possa ser examinada do início para o fim Considerase apenas o 1o símbolo do restante da entrada Análise sintática ascendente analisadores LR1 Decidimos qual regra A deve ser aplicada encontrando os nós vizinhos rotulados com os símbolos de A redução para A consiste em acrescentálo à árvore como um que agrupe todos os símbolos de como seus nós filhos Considera duas informações O estado atual da análise O símbolo corrente da entrada Uma tabela M codifica as operações a serem realizadas de acordo com o autômato de reconhecimento Construção do analisador Várias possibilidades precisam ser consideradas em um mesmo momento Um item A indica o ponto atual em que se encontra a análise ou seja A regra A foi usada na derivação da cadeia de entrada Os símbolos terminais derivados de já foram encontrados Falta encontrar os símbolos terminais derivados de Um estado do processo de análise é representado por um conjunto de itens Gramática aumentada Suponha a gramática dada a esquerda Acrescentase a nova regra regra 0 para que seja possível a identificação correta da raiz da árvore sintática diferenciando a de outras ocorrências do símbolo inicial 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F a 0 S E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F a Construção do analisador definindo os estados O estado inicial é dado pelo item formado a partir da regra 0 e contém todos os outros itens associados ao fechamento do estado 0 S E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F a Estado 0 S E E E T E T T T F T F F E F a Construção do analisador definindo os estados Os demais estados do autômato são obtidos qual o símbolo esperado para os itens do estado Estado 0 S E E E T E T T T F T F F E F a E T F a Estado 1 S E E E T Estado 2 T F Estado 5 F a Operações do analisador LR1 A tabela do analisador define as ações de Empilhamento shift ocorrerá quando uma transição com um terminal no estado corrente topo da pilha for realizada Redução quando existe um item completo B e se o símbolo da entrada pertencer ao FollowB é feita uma redução pela regra B Os estados correspondentes a devem ser retirados da pilha e o estado qB deve ser empilhado representando B Aceitação quando ocorre a redução pela regra zero Programa sintaticamente correto Tabela do analisador LR1 E T F A 0 1 2 3 4 5 1 6 r0 2 r2 7 r2 r2 3 r4 r4 r4 r4 4 8 2 3 4 5 5 r6 r6 r6 r6 6 9 3 4 5 7 10 4 5 8 6 11 9 r1 7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Analisando a sentença aa Pilha Entrada Regra 0 aa M0 a 5 Empilha a 5 0 a M5 r6 Reduz Fa Desempilha o estado 5 ref símbolo a volta para o estado 0 e empilha 3 ref símbolo F 3 0 a M3 r4 Reduz TF 2 0 a M2 r1 Reduz ET 1 0 a M1 6 Empilha 6 1 0 a M6 a 5 Empilha a 5 6 1 0 M5 r6 Reduz Fa 3 6 1 0 M3 r4 Reduz TF 9 6 1 0 M9 r1 Reduz EET Desempilha os estados 9 6 e 1 ref símbolos ET volta para o estado 0 e empilha 1 ref símbolo E 1 0 M1 r0 Interatividade A respeito dos analisadores sintáticos LR1 não se pode afirmar que a São analisadores redutores estilo shiftreduce ou empilhareduz ascendentes São eficientes e leem a sentença em análise da esquerda para a direita produzindo uma derivação mais à direita ao reverso b Entre as vantagens podese afirmar que são capazes de reconhecer praticamente todas as estruturas sintáticas definidas por GLC c São capazes de descobrir erros sintáticos durante a leitura da sentença em análise d O YACC gera analisadores ascendentes e Os erros são identificados sempre no momento mais tarde isto é na leitura de tokens Resposta A respeito dos analisadores sintáticos LR1 não se pode afirmar que a São analisadores redutores estilo shiftreduce ou empilhareduz ascendentes São eficientes e leem a sentença em análise da esquerda para a direita produzindo uma derivação mais à direita ao reverso b Entre as vantagens podese afirmar que são capazes de reconhecer praticamente todas as estruturas sintáticas definidas por GLC c São capazes de descobrir erros sintáticos durante a leitura da sentença em análise d O YACC gera analisadores ascendentes e Os erros são identificados sempre no momento mais tarde isto é na leitura de tokens Análise semântica 3a etapa do processo de análise Analisador semântico Tabela de símbolos Analisador sintático Árvore sintática Analisador léxico Tokens Tarefas da análise semântica É responsável por três tarefas Construir a descrição interna dos tipos e das estruturas de dados definidos no programa do usuário Armazenar na tabela símbolos as informações sobre os identificadores de constante tipos variáveis procedimentos parâmetros e funções que são usados no programa Verificar o programa quanto a erros semânticos erros dependentes de contexto e checagens de tipos com base nas informações contidas na tabela de símbolos O componente semântico Verificar a utilização adequada dos identificadores Análise contextual declarações prévias de variáveis escopo de uso etc Checagem de tipos e compatibilidade Essas tarefas estão além do domínio da sintaxe Gram Livres de Contexto GLC Aumenta a GLC e completa a definição do que são programas válidos A análise ocorre em dois aspectos Semântica estática Semântica de tempo de execução O componente semântico semântica estática Conjunto de restrições que determinam se programas sintaticamente corretos são válidos As atividades compreendidas são A checagem de tipos A análise de escopo de declarações A verificação da quantidade e dos tipos dos parâmetros em subrotinas Pode ser especificada formalmente por uma gramática de atributos O componente semântico semântica de tempo de execução É usada para especificar o que o programa faz isto é a relação do programafonte objeto estático com a sua execução dinâmica Exemplo L goto L if i0 KI 10 Importante para a geração de código Geralmente é especificada de modo informal mas é possível o uso de formalismos tais com as gramáticas de atributos dentre outros Gramática de atributos É uma gramática livre de contexto estendida para fornecer sensitividade ao contexto através de atributos ligados a terminais e não terminais Um atributo é qualquer propriedade de uma construção da linguagem 1 D T L Lin Ttipo 2 T int Ttipo inteiro 3 T float Ttipo real 4 L L1 id L1in Lin incluirTSidtoken Lin 5 L id incluirTSidtoken Lin Calculando os atributos Com base na árvore sintática explícita Ad hoc comandada pelo parser Podem ser calculados tanto durante a compilação quanto na execução Exemplos Tipo de dado de uma variável compilação Valor de uma expressão execução exceto expressões que tratem de constantes Endereço do início do código objeto de um procedimento compilação Declaração de objeto no contexto compilação para linguagens que exigem declaração prévia Tabela de símbolos Armazena as informações sobre todos os identificadores do código fonte Captura a sensitividade ao contexto e as ações executadas no decorrer do programa Está atrelada a todas as etapas da compilação sendo a estrutura principal do processo Fundamental para Realizar a análise semântica A geração de código Operações inserção e busca envolvendo a tabela de símbolos Podem ser implementadas como Chamadas na gramática de atributos L L1 id if buscaTSid false incluirTSid Ltipo else ERROJá declarado Diretamente na análise sintática Inserção quando analisa declarações de variáveis subrotinas parâmetros Busca em atribuições expressões chamadas de subrotinas ou qualquer outro uso de um identificador em um bloco de comandos Interatividade Analise as mensagens de erro a seguir I Identificador já declarado no escopo atual II Identificador de tipo esperado III Quantidade de parâmetros incompatível com a função IV Função ou variável não definida lado esquerdo de atribuições Quais destes são de natureza semântica a Apenas o item I b Itens I e II c Itens I III e IV d Itens I II e IV e Itens I II III e IV Resposta Analise as mensagens de erro a seguir I Identificador já declarado no escopo atual II Identificador de tipo esperado III Quantidade de parâmetros incompatível com a função IV Função ou variável não definida lado esquerdo de atribuições Quais destes são de natureza semântica a Apenas o item I b Itens I e II c Itens I III e IV d Itens I II e IV e Itens I II III e IV Geração de código enfim a tradução efetivamente Corresponde à 1a etapa do processo de síntese modelo de análise e síntese Em geral ocorre em duas fases Tradução da estrutura construída na análise sintática para um código em linguagem intermediária usualmente independente do processador Tradução do código em linguagem intermediária para a linguagem simbólica do processadoralvo Produção do código binário é realizada por outro programa montador Código intermediário Há várias formas de representação de código intermediário sendo as mais comuns Árvore e grafo de sintaxe Notações pósfixadas e préfixadas Representações linearizadas Código de três endereços Quádruplas ou triplas Instruções assembler HIR MIR e LIR High Medium e Low Intermediate Representation Código intermediário árvore e grafo de sintaxe A árvore de sintaxe mostra a estrutura hierárquica de um programa fonte O grafo de sintaxe inclui simplificações da árvore de sintaxe Exemplo a b c b c b c b c a b c a Código intermediário código de três endereços Cada instrução terá no máximo três variáveis dois operandos e o resultado Formato independente e fácil de traduzir para linguagem simbólica de qualquer processador Expressões complexas devem ser decompostas em várias expressões Necessitam de variáveis temporárias Exemplos de instruções A B op C A op B A B goto L if A oprel B goto L Código intermediário código de três endereços Exemplo a b c d Quádruplas Triplas Op Arg1 Arg2 Res 1 c d t1 2 b t1 a Op Arg1 Arg2 1 c d 2 b 1 3 a 2 Geração de código tradução dirigida pela sintaxe Construída a partir do mecanismo empregado na verificação de tipos isto é uma gramática de atributos Adicionamse regras que permitam a geração de código intermediário simultaneamente a ações semânticas S id E geracodidvalor Evalor E E1 E2 Eval geratemp geracodEval E1val E2val E E1 E2 Eval geratemp geracodEval E1val E2val E E1 Eval E1val E id Eval idval Interatividade Analise as seguintes afirmativas I A geração de código intermediário torna o compilador mais portável mas a otimização é mais difícil por estar longe do código alvo II O problema de gerar código ótimo é indecidível Geralmente são usadas técnicas heurísticas que na maior parte do tempo geram bom código III São exemplos de código intermediário as notações préfixas pósfixas e o código de três endereços Podese afirmar ser correta a alternativa a Item I b Item II c Itens I e II d Itens II e III e Itens I II e III Resposta Analise as seguintes afirmativas I A geração de código intermediário torna o compilador mais portável mas a otimização é mais difícil por estar longe do código alvo II O problema de gerar código ótimo é indecidível Geralmente são usadas técnicas heurísticas que na maior parte do tempo geram bom código III São exemplos de código intermediário as notações préfixas pósfixas e o código de três endereços Podese afirmar ser correta a alternativa a Item I b Item II c Itens I e II d Itens II e III e Itens I II e III Montadores ligadores linkers e carregadores loaders Compilador Montador Ligador Carregador 00101 11010 00101 obj 00101 11010 00101 obj 00101 11010 00101 obj 00101 11010 00101 exe RAM mov ax add bx load x interm Montadores assemblers As funções da montagem compreendem Substituir os mnemônicos pelos opcodes do conjunto de instruções do processador Determinar de maneira absoluta ou relativa termos do valor do registrador Program Counter o endereço de destino dos rótulos Reservar espaço para dados de acordo com o tipo associado a cada variável Gerar constantes em memória para variáveis e constantes determinando o valor associado ao modo de endereçamento do operando Assemblers montadores Programa em linguagem de alto nível Programa em linguagem de montagem assembly Programa em linguagem de máquina Rótulo Mnemônico Oper End Opcod Oper int abc INPUT N1 00 12 13 reada INPUT N2 02 12 14 readb LOAD N1 04 10 13 c a b ADD N2 06 01 14 writec STORE N3 08 11 15 OUTPUT N3 10 13 15 STOP 12 14 N1 SPACE 13 N2 SPACE 14 N3 SPACE 15 Formato do arquivo objeto Dado pela identificação de tipo tamanho do código e eventualmente o arquivo de origem Cabeçalho Contém as instruções e os dados em formato binário Código gerado Contém as posições no código em que ocorrerão mudanças quando for definida a posição de carregamento Relocação Lista de símbolos globais definidos no módulo e símbolos externos que devem vir de outros módulos Tabela de símbolos Contém referências para o código fonte ex número de linha e nomes de identificadores Depuração Ligadores linkers Reunir os vários módulos objetos obtidos da tradução dos vários arquivos fontes em um único programa o módulo absoluto de carga Deve ser capaz de resolver referências cruzadas endereços dados pelos módulos devem ser atualizados problema de relocação Quando existe um procedimento A que chama a um procedimento B o endereço absoluto de B só é conhecido após a ligação problema de referência externa Tarefas do linker Construir uma tabela com todos os módulos objetos e seus respectivos comprimentos Atribuir um endereço de carga a cada módulo objeto Relocar todas as instruções que contêm um endereço adicionando uma constante de relocação endereço inicial de cada módulo Encontrar todas as instruções que referenciam outros procedimentos e inserir nelas o endereço absoluto dos mesmos Carregador loader Copiar um programa para a memória principal e preparar sua execução Atividades Verificar se o programa existe Avaliar a quantidade de memória necessária e solicitála ao SO Copiar o conteúdo do arquivo código para a memória Ajustar os endereços do código executável de acordo com a posição base de carregamento Tipos de carregadores absolutos relocador e dinâmico Tipos de carregadores Absoluto considera que programa é carregado sempre no mesmo endereço Relocador se a carga do programa na posição X da memória adiciona X a cada uma das referências do programa Dinâmico em situações de swapping pois os processos não necessariamente retornam à mesma posição Executa relocação no momento em que a posição for referenciada Os endereços devem ser relativos ao início do módulo na memória Interatividade Analise as afirmativas I Os montadores assemblers realizam a conversão de programas em linguagem de montagem para a linguagem de máquina II Um editor de ligação ou ligador linker permite combinar módulos montados separadamente em um único programa III A função principal de um programa carregador loader é permitir a edição de um programa em linguagem de alto nível Está correta a alternativa a Item I b Item III c Itens I e II d Itens II e III e Todos os itens estão corretos Resposta Analise as afirmativas I Os montadores assemblers realizam a conversão de programas em linguagem de montagem para a linguagem de máquina II Um editor de ligação ou ligador linker permite combinar módulos montados separadamente em um único programa III A função principal de um programa carregador loader é permitir a edição de um programa em linguagem de alto nível Está correta a alternativa a Item I b Item III c Itens I e II d Itens II e III e Todos os itens estão corretos ATÉ A PRÓXIMA