Prepare-se para as provas
Estude fácil! Tem muito documento disponível na Docsity
Ganhe pontos para baixar
Ganhe pontos ajudando outros esrudantes ou compre um plano Premium
Guias e Dicas
Prepare-se para as provas
Estude fácil! Tem muito documento disponível na Docsity
Encontrar documentos
Prepare-se para as provas com trabalhos de outros alunos como você, aqui na Docsity
Pesquisar documentos Store
Os melhores documentos à venda: Trabalhos de alunos formados
Videoaulas
Prepare-se com as videoaulas e exercícios resolvidos criados a partir da grade da sua Universidade
QuizNEW
Responda perguntas de provas passadas e avalie sua preparação.
Ganhe pontos para baixar
Ganhe pontos ajudando outros esrudantes ou compre um plano Premium
Comunidade
Pergunte à comunidade
Peça ajuda à comunidade e tire suas dúvidas relacionadas ao estudo
Ranking universidades
Descubra as melhores universidades em seu país de acordo com os usuários da Docsity
Guias grátis
Os eBooks que salvam estudantes!
Baixe gratuitamente nossos guias de estudo, métodos para diminuir a ansiedade, dicas de TCC preparadas pelos professores da Docsity
Compiladores - Análise Léxica, Manuais, Projetos, Pesquisas de Engenharia Informática
Análise Léxica, Bufferização, Erros léxicos, Recuperação de erros léxicos, Especificação de Tokens, Reconhecimento de Tokens, Projeto de Analisador Léxico, Enfoques de Implementação e Projeto de Analisador Léxico.
Tipologia: Manuais, Projetos, Pesquisas
Antes de 2010
1 / 45
Documentos relacionados
Pré-visualização parcial do texto
Baixe Compiladores - Análise Léxica e outras Manuais, Projetos, Pesquisas em PDF para Engenharia Informática, somente na Docsity! Análise Léxica Análise Léxica Papel do analisador léxico: ler o arquivo fonte em busca de unidades significativas (os tokens) instanciadas por lexemas ou átomos. Também denominado de scanner, porque varre o arquivo de entrada eliminando comentários e caracteres indesejáveis ao agrupar caracteres com um papel bem definido. Análise Léxica q Um mesmo token pode ser produzido por várias cadeias de entradas. q Tal conjunto de cadeias é descrito por uma regra denominada padrão, associada a tais tokens. q O padrão reconhece as cadeias de tal conjunto, ou seja, reconhece os lexemas que são padrão de um token. Análise Léxica q Usualmente os padrões são convenções determinadas pela linguagem para formação de classes de tokens. lidentificadores: letra seguida por letras ou dígitos. lliteral: cadeias de caracteres delimitadas por aspas. lnum: qualquer constante numérica. Análise Léxica q Os tokens usualmente são conhecidos pelo seu lexema(seqüência de caracteres que compõe um único token) e atributos adicionais. q Os tokens podem ser entregues ao parser como tuplas na forma <a, b, ..., n> assim a entrada: a = b + 3 q poderia gerar as tuplas: <id,a> <=, > <id, b> <num, 3> q note que alguns tokens não necessitam atributos adicionais. Análise Léxica Quais os tokens que podem ser reconhecidos em uma linguagem de programação como C ? palavras reservadas if else while do identificadores operadores relacionais < > <= >= == != operadores aritméticos + * / - operadores lógicos && || & | ! operador de atribuição = delimitadores ; , caracteres especiais ( ) [ ] { } Análise Léxica Quais os tokens que podem ser reconhecidos em uma linguagem de marcação como HTML ? Tags <html> <body> <table>... Comentários <!-- ... --> Conteúdos Página de teste… Especiais &eaccute; Análise Léxica Lexemas podem ter atributos como número da linha em que se encontra no código fonte e o valor de uma constante numérica ou um literal. Normalmente utiliza-se um único atributo que é um apontador para a Tabela de Símbolos que armazena essas informações em registros. Bufferização Trata de técnicas para percorrer arquivos de entrada quando estes forem muito grandes e não houver memória suficiente. Quando a memória for suficiente o arquivo pode ser aberto e percorrido diretamente. Normalmente utiliza-se um esquema de pares de buffers. Bufferização Em alguns momentos pode ser necessário que o analisador léxico precise examinar alguns caracteres a frente de um token antes de o reconhecer. O movimento para frente e para trás no arquivo fonte pode consumir um certo tempo. Para tornar o analisador léxico mais rápido podem ser utilizados buffers em memória principal. Bufferização qÉ muito conveniente que a entrada seja buferizada, i.e., que a leitura da entrada seja fisicamente efetuada em blocos enquanto que logicamente o analisador léxico consome apenas um caractere por vez. qA buferização facilita os procedimentos de devolução de caracteres. Recuperação de erros léxicos qAções possíveis: (1) remoção de sucessivos caracteres até o reconhecimento de um token válido (modalidade pânico). (2) inserção de um caractere ausente. (3) substituição de um caractere incorreto por outro correto. (4) transposição de caracteres adjacentes. Recuperação de erros léxicos qTais estratégias poderiam ser aplicadas dentro de um escopo limitado(denominado erros de distância mínima). While (a<100) {fi(a==b) break else a++;} ... q Estas transformações seriam computadas na tentativa de obtenção de um programa sintaticamente correto (o que não significa um programa correto, daí o limitado número de compiladores experimentais que usam tais técnicas). Especificação de Tokens Tokens são padrões que podem ser especificados através de expressões regulares. Um alfabeto determina o conjunto de caracteres válidos para a formação de cadeias, sentenças ou palavras. Cadeias são seqüências finitas de caracteres. Algumas operações podem ser aplicadas a alfabetos para ajudar na definição de cadeias: concatenação, união e fechamento. Especificação de Tokens Expressões regulares podem receber um nome (definição regular), formando o token de um analisador léxico. Algumas convenções podem facilitar a formação de definições regulares 1. Uma ou mais ocorrência (+) 2. Zero ou mais ocorrências (*) 3. Zero ou uma ocorrência (?) 4. Classe de caracteres [a-z]= a|b|...|z Especificação de Tokens São definições regulares letra → [A-Z]|[a-z] dígito → [0−9] dígitos → dígito dígito* identificador → letra[letra|dígito]* fração_opc → .dígitos|ε exp_opc → E[+|-|ε]dígitos|ε num → dígitos fração_opc exp_opc delim → branco|tabulação|avanço de linha Reconhecimento de Tokens Tokens podem ser reconhecidos através de autômatos finitos onde o estado final dispara o reconhecimento de um token específico e/ou um procedimento específico (inserir na tabela de símbolo, por exemplo). Normalmente cria-se um diagrama de transição para representar o reconhecimento de tokens. Projeto de Analisador Léxico 1. Definir o alfabeto 2. Listar os tokens necessários 3. Especificar os tokens por meio de definições regulares 4. Montar os autômatos para reconhecer os tokens 5. Implementar o analisador léxico Projeto de Analisador Léxico EXERCÍCIO – Projetar um analisador léxico para uma calculadora simples com números naturais e reais e operações básicas (soma, subtração, multiplicação e divisão) Enfoques de Implementação qExistem 3 enfoques básicos para construção de um analisador léxico: lUtilizar um gerador automático de analisadores léxicos (tal como o compilador LEX, que gera um analisador a partir de uma especificação). lEscrever um analisador léxico usando uma linguagem de programação convencional que disponha de certas facilidades de E/S. lEscrever um analisador léxico usando linguagem de montagem. Projeto de Analisador Léxico Que símbolo usar como separador de casas decimais? A calculadora usa representação monetária? A calculadora aceita espaços entre os operandos e operadores? O projetista é quem decide sobre as características desejáveis do compilador ou interpretador. Para a maioria das linguagens de programação existem algumas convenções que devem ser respeitadas. 1. Definição do Alfabeto Σ= {0,1,2,3,4,5,6,7,8,9,.,(,),+,-,*,/,\b} OBS.: projetista deve considerar TODOS os símbolos que são necessários para formar os padrões 2. Listagem dos tokens OPSOMA: operador de soma OPSUB: operador de subtração OPMUL: operador de multiplicação OPDIV: operador de divisão AP: abre parênteses FP: fecha parênteses NUM: número natural/real OBS.: projetista deve considerar tokens especiais e cuidar para que cada token seja uma unidade significativa para o problema 5. Implementar o analisador léxico Existem duas formas básicas para implementar os autômatos: usando a tabela de transição de estados ou diretamente em código Qual é a mais eficiente? Por que ? ESTILO DE IMPLEMENTAÇÃO DO LÉXICO " Cada token listado é codificado em um número natural " Deve haver uma variável para controlar o estado corrente do autômato e outro para indicar o estado de partida do autômato em uso " Uma função falhar é usada para desviar o estado corrente para um outro autômato no caso de um estado não reconhecer uma letra ESTILO DE IMPLEMENTAÇÃO DO LÉXICO Cada estado é analisado individualmente em uma estrutura do tipo switch…case 10 2 letra letra dígito Σ - letra - digito Reconhece ID
Documentos
Videoaulas
perguntas
Copyright © 2024 Ladybird Srl - Via Leonardo da Vinci 16, 10126, Torino, Italy - VAT 10816460017 - All rights reserved