Análise lexical - Lexical analysis

Em ciência da computação , análise lexical , lexing ou tokenização é o processo de conversão de uma sequência de caracteres (como em um programa de computador ou página da web ) em uma sequência de tokens ( strings com um significado atribuído e, portanto, identificado). Um programa que executa análise lexical pode ser denominado lexer , tokenizer ou scanner , embora scanner também seja um termo para o primeiro estágio de um lexer. Um lexer geralmente é combinado com um analisador , que juntos analisam a sintaxe de linguagens de programação , páginas da web e assim por diante.

Formulários

Um lexer forma a primeira fase de um frontend de compilador no processamento moderno. A análise geralmente ocorre em uma passagem.

Em linguagens mais antigas, como ALGOL , o estágio inicial era, em vez disso , a reconstrução da linha , que desmontava e removia espaços em branco e comentários (e tinha analisadores sem scanner, sem lexer separado). Essas etapas agora são realizadas como parte do lexer.

Lexers e analisadores são mais frequentemente usados ​​para compiladores, mas podem ser usados ​​para outras ferramentas de linguagem de computador, como prettyprinters ou linters . Lexing pode ser dividido em dois estágios: a varredura , que segmenta a string de entrada em unidades sintáticas chamadas lexemas e as categoriza em classes de token; e a avaliação , que converte lexemas em valores processados.

Os lexers são geralmente bastante simples, com a maior parte da complexidade transferida para as fases do analisador ou da análise semântica , e muitas vezes podem ser gerados por um gerador de lexers , principalmente lex ou derivados. No entanto, lexers às vezes podem incluir alguma complexidade, como processamento de estrutura de frase para tornar a entrada mais fácil e simplificar o analisador, e podem ser escritos parcial ou totalmente à mão, seja para suportar mais recursos ou para desempenho.

A análise lexical também é um estágio inicial importante no processamento da linguagem natural , onde o texto ou as ondas sonoras são segmentadas em palavras e outras unidades. Isso requer uma variedade de decisões que não são totalmente padronizadas, e o número de tokens produzidos varia para sequências como "1/2", "cadeira", "não posso", "e / ou", "1/1 / 2010 "," 2x4 "," ..., "e muitos outros. Isso contrasta com a análise lexical para linguagens de programação e similares, onde regras exatas são comumente definidas e conhecidas.

Lexeme

Um lexema é uma sequência de caracteres no programa de origem que corresponde ao padrão de um token e é identificado pelo analisador léxico como uma instância desse token.

Alguns autores chamam isso de "token", usando "token" de forma intercambiável para representar a string que está sendo tokenizada e a estrutura de dados do token resultante da colocação dessa string no processo de tokenização .

A palavra lexema em ciência da computação é definida de forma diferente de lexema em lingüística. Um lexema em ciência da computação corresponde aproximadamente a uma palavra em linguística (não deve ser confundida com uma palavra em arquitetura de computador ), embora em alguns casos possa ser mais semelhante a um morfema .

Símbolo

Um token léxico ou simplesmente token é uma string com um significado atribuído e, portanto, identificado. Ele é estruturado como um par que consiste em um nome de token e um valor de token opcional . O nome do token é uma categoria de unidade lexical. Nomes de tokens comuns são

  • identificador : nomes que o programador escolhe;
  • palavra - chave : nomes já na linguagem de programação;
  • separador (também conhecido como pontuação): caracteres de pontuação e delimitadores emparelhados;
  • operador : símbolos que operam em argumentos e produzem resultados;
  • literal : literais numéricos, lógicos, textuais, de referência;
  • comentário : linha, bloco (Depende do compilador se o compilador implementar comentários como tokens, caso contrário, ele será removido).
Exemplos de valores de token
Nome do token Valores de token de amostra
identificador x, color,UP
palavra-chave if, ,whilereturn
separador }, (,;
operador +, ,<=
literal true, ,6.02e23"music"
Comente /* Retrieves user data */, // must be negative

Considere esta expressão na linguagem de programação C :

x = a + b * 2;

A análise lexical desta expressão produz a seguinte sequência de tokens:

[(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)]

Um nome simbólico é o que pode ser denominado uma classe gramatical em linguística.

Gramática lexical

A especificação de uma linguagem de programação geralmente inclui um conjunto de regras, a gramática lexical , que define a sintaxe lexical. A sintaxe lexical é geralmente uma linguagem regular , com as regras gramaticais consistindo em expressões regulares ; eles definem o conjunto de possíveis sequências de caracteres (lexemas) de um token. Um lexer reconhece strings e, para cada tipo de string encontrado, o programa lexical executa uma ação, basicamente produzindo um token.

Duas categorias lexicais comuns importantes são espaço em branco e comentários . Estes também são definidos na gramática e processados ​​pelo lexer, mas podem ser descartados (não produzindo nenhum tokens) e considerados não significativos , no máximo separando dois tokens (como em em if xvez de ifx). Existem duas exceções importantes para isso. Primeiro, em linguagens de regra fora do lado que delimitam blocos com recuo, o espaço em branco inicial é significativo, pois determina a estrutura do bloco e geralmente é tratado no nível do lexer; veja a estrutura da frase , abaixo. Em segundo lugar, em alguns usos de lexers, comentários e espaços em branco devem ser preservados - por exemplo, um prettyprinter também precisa produzir os comentários e algumas ferramentas de depuração podem fornecer mensagens ao programador mostrando o código-fonte original. Na década de 1960, principalmente para ALGOL , espaços em branco e comentários foram eliminados como parte da fase de reconstrução da linha (a fase inicial do frontend do compilador ), mas essa fase separada foi eliminada e agora são gerenciados pelo lexer.

Tokenização

Tokenização é o processo de demarcar e possivelmente classificar seções de uma string de caracteres de entrada. Os tokens resultantes são então passados ​​para alguma outra forma de processamento. O processo pode ser considerado uma subtarefa de análise de entrada.

Por exemplo, na string de texto :

The quick brown fox jumps over the lazy dog

a string não é segmentada implicitamente em espaços, como faria um falante de um idioma natural . A entrada bruta, os 43 caracteres, deve ser explicitamente dividida em 9 tokens com um determinado delimitador de espaço (ou seja, correspondendo à string " "ou expressão regular /\s{1}/ ).

Os tokens podem ser representados em XML ,

<sentence>
  <word>The</word>
  <word>quick</word>
  <word>brown</word>
  <word>fox</word>
  <word>jumps</word>
  <word>over</word>
  <word>the</word>
  <word>lazy</word>
  <word>dog</word>
</sentence>

ou como uma expressão s ,

(sentence
  (word The)
  (word quick)
  (word brown)
  (word fox)
  (word jumps)
  (word over)
  (word the)
  (word lazy)
  (word dog))

Quando uma classe de token representa mais de um lexema possível, o lexer geralmente salva informações suficientes para reproduzir o lexema original, para que possa ser usado na análise semântica . O analisador normalmente recupera essas informações do lexer e as armazena na árvore de sintaxe abstrata . Isso é necessário para evitar a perda de informações no caso em que os números também podem ser identificadores válidos.

Os tokens são identificados com base nas regras específicas do lexer. Alguns métodos usados ​​para identificar tokens incluem: expressões regulares , sequências específicas de caracteres denominadas flag , caracteres de separação específicos denominados delimitadores e definição explícita por um dicionário. Caracteres especiais, incluindo caracteres de pontuação, são comumente usados ​​por lexers para identificar tokens devido ao seu uso natural em linguagens escritas e de programação.

Os tokens são frequentemente categorizados por conteúdo de caractere ou por contexto no fluxo de dados. As categorias são definidas pelas regras do lexer. As categorias geralmente envolvem elementos gramaticais da linguagem usada no fluxo de dados. Linguagens de programação geralmente categorizam tokens como identificadores, operadores, símbolos de agrupamento ou por tipo de dados . As linguagens escritas comumente categorizam os tokens como substantivos, verbos, adjetivos ou pontuação. As categorias são usadas para pós-processamento dos tokens pelo analisador ou por outras funções no programa.

Um analisador léxico geralmente não faz nada com combinações de tokens, uma tarefa deixada para um analisador . Por exemplo, um analisador léxico típico reconhece parênteses como tokens, mas não faz nada para garantir que cada "(" corresponda a um ")".

Quando um lexer alimenta tokens para o analisador, a representação usada é normalmente uma lista enumerada de representações de número. Por exemplo, "Identificador" é representado por 0, "Operador de atribuição" com 1, "Operador de adição" com 2 etc.

Os tokens são geralmente definidos por expressões regulares , que são entendidas por um gerador de analisador lexical, como lex . O analisador léxico (gerado automaticamente por uma ferramenta como lex, ou feito à mão) lê em um fluxo de caracteres, identifica os lexemas no fluxo e os categoriza em tokens. Isso é denominado tokenização . Se o lexer encontrar um token inválido, ele relatará um erro.

A seguir a tokenização está a análise . A partir daí, os dados interpretados podem ser carregados em estruturas de dados para uso geral, interpretação ou compilação .

Scanner

O primeiro estágio, o scanner , geralmente é baseado em uma máquina de estado finito (FSM). Ele codificou informações sobre as possíveis sequências de caracteres que podem estar contidas em qualquer um dos tokens que ele manipula (instâncias individuais dessas sequências de caracteres são chamadas de lexemas ). Por exemplo, um lexema inteiro pode conter qualquer sequência de caracteres de dígitos numéricos . Em muitos casos, o primeiro caractere sem espaço em branco pode ser usado para deduzir o tipo de token que se segue e os caracteres de entrada subsequentes são processados ​​um de cada vez até atingir um caractere que não está no conjunto de caracteres aceitável para esse token (este é denominado a regra de mastigação máxima , ou combinação mais longa ). Em alguns idiomas, as regras de criação de lexemas são mais complexas e podem envolver o retrocesso de caracteres lidos anteriormente. Por exemplo, em C, um caractere 'L' não é suficiente para distinguir entre um identificador que começa com 'L' e um literal de string de caractere largo.

Avaliador

Um lexema , entretanto, é apenas uma string de caracteres conhecidos por serem de um certo tipo (por exemplo, uma string literal, uma sequência de letras). Para construir um token, o analisador léxico precisa de um segundo estágio, o avaliador , que percorre os caracteres do lexema para produzir um valor . O tipo do lexema combinado com seu valor é o que constitui um token, que pode ser fornecido a um analisador. Alguns tokens, como parênteses, não têm realmente valores e, portanto, a função do avaliador para eles não pode retornar nada: apenas o tipo é necessário. Da mesma forma, às vezes os avaliadores podem suprimir um lexema inteiramente, ocultando-o do analisador, o que é útil para espaços em branco e comentários. Os avaliadores de identificadores são geralmente simples (literalmente representando o identificador), mas podem incluir alguns desmontagem . Os avaliadores para literais inteiros podem passar a string adiante (adiando a avaliação para a fase de análise semântica), ou podem realizar avaliações eles próprios, que podem estar envolvidos para diferentes bases ou números de ponto flutuante. Para um literal de string entre aspas simples, o avaliador precisa remover apenas as aspas, mas o avaliador de um literal de string de escape incorpora um lexer, que não escapa das sequências de escape.

Por exemplo, no código-fonte de um programa de computador, a string

net_worth_future = (assets liabilities);

pode ser convertido no seguinte fluxo de token léxico; o espaço em branco é suprimido e os caracteres especiais não têm valor:

IDENTIFIER net_worth_future
EQUALS
OPEN_PARENTHESIS
IDENTIFIER assets
MINUS
IDENTIFIER liabilities
CLOSE_PARENTHESIS
SEMICOLON

Devido a restrições de licenciamento de analisadores existentes, pode ser necessário escrever um lexer manualmente. Isso é prático se a lista de tokens for pequena, mas, em geral, lexers são gerados por ferramentas automatizadas. Essas ferramentas geralmente aceitam expressões regulares que descrevem os tokens permitidos no fluxo de entrada. Cada expressão regular está associada a uma regra de produção na gramática lexical da linguagem de programação que avalia os lexemas que correspondem à expressão regular. Essas ferramentas podem gerar código-fonte que pode ser compilado e executado ou construir uma tabela de transição de estado para uma máquina de estado finito (que é conectada ao código de modelo para compilar e executar).

As expressões regulares representam de forma compacta os padrões que os caracteres nos lexemas podem seguir. Por exemplo, para um idioma baseado em inglês , um token IDENTIFICADOR pode ser qualquer caractere alfabético inglês ou um sublinhado, seguido por qualquer número de instâncias de caracteres alfanuméricos ASCII e / ou sublinhados. Isso pode ser representado de forma compacta pela string [a-zA-Z_][a-zA-Z_0-9]*. Isso significa "qualquer caractere az, AZ ou _, seguido por 0 ou mais de az, AZ, _ ou 0-9".

Expressões regulares e as máquinas de estado finito que geram não são poderosas o suficiente para lidar com padrões recursivos, como " n parênteses de abertura, seguido por uma instrução, seguido por n parênteses de fechamento." Eles são incapazes de manter a contagem e verificar se n é o mesmo em ambos os lados, a menos que exista um conjunto finito de valores permitidos para n . É necessário um analisador completo para reconhecer esses padrões em toda sua generalidade. Um analisador pode colocar parênteses em uma pilha e então tentar retirá-los e ver se a pilha está vazia no final (veja o exemplo no livro Estrutura e Interpretação de Programas de Computador ).

Obstáculos

Normalmente, a tokenização ocorre no nível da palavra. No entanto, às vezes é difícil definir o que significa uma "palavra". Muitas vezes, um tokenizer depende de heurísticas simples, por exemplo:

  • Pontuação e espaços em branco podem ou não ser incluídos na lista de tokens resultante.
  • Todas as sequências contíguas de caracteres alfabéticos fazem parte de um token; da mesma forma com os números.
  • Os tokens são separados por caracteres de espaço em branco , como espaço ou quebra de linha, ou por caracteres de pontuação.

Em linguagens que usam espaços entre palavras (como a maioria que usa o alfabeto latino e a maioria das linguagens de programação), essa abordagem é bastante direta. No entanto, mesmo aqui há muitos casos extremos, como contrações , palavras hifenizadas , emoticons e construções maiores, como URIs (que, para alguns fins, podem contar como tokens únicos). Um exemplo clássico é "baseado em Nova York", que um tokenizer ingênuo pode quebrar no espaço, embora a melhor quebra seja (indiscutivelmente) no hífen.

A tokenização é particularmente difícil para idiomas escritos em scriptio continua que não exibem limites de palavras, como grego antigo , chinês ou tailandês . Linguagens aglutinativas , como o coreano, também tornam as tarefas de tokenização complicadas.

Algumas maneiras de resolver os problemas mais difíceis incluem desenvolver heurísticas mais complexas, consultar uma tabela de casos especiais comuns ou ajustar os tokens a um modelo de linguagem que identifica colocações em uma etapa de processamento posterior.

Gerador Lexer

Lexers geralmente são gerados por um gerador de lexer , análogo aos geradores de analisador , e essas ferramentas geralmente vêm juntas. O mais estabelecido é o lex , emparelhado com o gerador de analisador yacc , ou melhor, algumas de suas muitas reimplementações, como flex (geralmente emparelhado com GNU Bison ). Esses geradores são uma forma de linguagem específica de domínio , recebendo uma especificação lexical - geralmente expressões regulares com alguma marcação - e emitindo um lexer.

Essas ferramentas geram um desenvolvimento muito rápido, o que é muito importante no início do desenvolvimento, tanto para obter um lexer funcional quanto porque a especificação de uma linguagem pode ser alterada com frequência. Além disso, eles geralmente fornecem recursos avançados, como pré e pós-condições que são difíceis de programar manualmente. No entanto, um lexer gerado automaticamente pode carecer de flexibilidade e, portanto, pode exigir alguma modificação manual ou um lexer totalmente escrito manualmente.

O desempenho do Lexer é uma preocupação e a otimização vale a pena, ainda mais em linguagens estáveis ​​em que o lexer é executado com frequência (como C ou HTML). Os lexers gerados por lex / flex são razoavelmente rápidos, mas melhorias de duas a três vezes são possíveis usando geradores mais ajustados. Os lexers escritos à mão às vezes são usados, mas os geradores de lexers modernos produzem lexers mais rápidos do que a maioria dos codificados à mão. A família de geradores lex / flex usa uma abordagem baseada em tabela que é muito menos eficiente do que a abordagem diretamente codificada. Com a última abordagem, o gerador produz um mecanismo que salta diretamente para estados de acompanhamento por meio de instruções goto. Ferramentas como o re2c provaram produzir motores duas a três vezes mais rápidos do que os motores flex. Em geral, é difícil escrever analisadores à mão que funcionam melhor do que os motores gerados por essas últimas ferramentas.

Estrutura da frase

A análise lexical segmenta principalmente o fluxo de entrada de personagens em tokens, simplesmente agrupando os personagens em pedaços e categorizando-os. No entanto, o lexing pode ser significativamente mais complexo; mais simplesmente, lexers podem omitir tokens ou inserir tokens adicionados. A omissão de tokens, principalmente espaços em branco e comentários, é muito comum, quando não são necessários para o compilador. Menos comumente, tokens adicionados podem ser inseridos. Isso é feito principalmente para agrupar tokens em instruções , ou instruções em blocos, para simplificar o analisador.

Continuação de linha

A continuação de linha é um recurso de algumas linguagens em que uma nova linha é normalmente um terminador de instrução. Na maioria das vezes, terminar uma linha com uma barra invertida (imediatamente seguida por uma nova linha ) resulta na continuação da linha - a linha seguinte é unida à linha anterior. Isso geralmente é feito no lexer: a barra invertida e a nova linha são descartadas, em vez de a nova linha ser tokenizada. Os exemplos incluem bash , outros scripts de shell e Python.

Inserção de ponto e vírgula

Muitas linguagens usam o ponto-e-vírgula como terminador de instrução. Na maioria das vezes, isso é obrigatório, mas em alguns idiomas o ponto-e-vírgula é opcional em muitos contextos. Isso é feito principalmente no nível do lexer, onde o lexer gera um ponto-e-vírgula no fluxo de token, apesar de não estar presente no fluxo de caractere de entrada, e é denominado inserção de ponto- e- vírgula ou inserção automática de ponto-e-vírgula . Nestes casos, os pontos-e-vírgulas fazem parte da gramática da frase formal do idioma, mas podem não ser encontrados no texto de entrada, pois podem ser inseridos pelo lexer. Os pontos-e-vírgulas opcionais ou outros terminadores ou separadores às vezes também são tratados no nível do analisador, principalmente no caso de vírgulas ou pontos-e- vírgulas à direita .

A inserção de ponto-e-vírgula é uma característica da BCPL e de seu descendente distante Go , embora esteja ausente em B ou C. A inserção de ponto-e-vírgula está presente no JavaScript , embora as regras sejam um tanto complexas e muito criticadas; para evitar bugs, alguns recomendam sempre o uso de ponto-e-vírgula, enquanto outros usam ponto-e-vírgula inicial, denominado ponto-e-vírgula defensivo , no início de declarações potencialmente ambíguas.

A inserção de ponto-e-vírgula (em linguagens com instruções terminadas em ponto-e-vírgula) e continuação de linha (em linguagens com instruções terminadas em nova linha) podem ser vistas como complementares: a inserção de ponto-e-vírgula adiciona um token, embora as novas linhas geralmente não gerem tokens, enquanto a continuação de linha impede um token de ser gerado, mesmo que novas linhas geralmente fazer gerar fichas.

Regra de impedimento

A regra de desvio (blocos determinados por recuo) pode ser implementada no lexer, como em Python , em que aumentar o recuo resulta no lexer emitindo um token INDENT e diminuindo os resultados de recuo no lexer emitindo um token DEDENT. Esses tokens correspondem à chave de abertura {e de fechamento }em linguagens que usam chaves para blocos e significa que a gramática da frase não depende se chaves ou recuo são usados. Isso requer que o lexer mantenha o estado, ou seja, o nível de indentação atual, e assim pode detectar mudanças no indentação quando isso muda e, portanto, a gramática lexical não é livre de contexto : INDENT – DEDENT depende da informação contextual do nível de indentação anterior.

Lexing sensível ao contexto

Geralmente as gramáticas lexicais são livres de contexto, ou quase isso, e, portanto, não exigem olhar para trás ou para frente, ou retrocesso, o que permite uma implementação simples, limpa e eficiente. Isso também permite a comunicação unilateral simples do lexer para o analisador, sem a necessidade de qualquer fluxo de informações de volta para o lexer.

Existem exceções, no entanto. Exemplos simples incluem: inserção de ponto-e-vírgula no Go, que requer a verificação de um token; concatenação de literais de string consecutivos em Python, que requer a retenção de um token em um buffer antes de emiti-lo (para ver se o próximo token é outro literal de string); e a regra off-side em Python, que requer a manutenção de uma contagem do nível de indentação (na verdade, uma pilha de cada nível de indentação). Todos esses exemplos requerem apenas contexto léxico e, embora complicem um pouco um lexer, são invisíveis para o analisador e as fases posteriores.

Um exemplo mais complexo é o hack lexer em C, onde a classe de token de uma sequência de caracteres não pode ser determinada até a fase de análise semântica, uma vez que nomes de typedef e nomes de variáveis ​​são lexicamente idênticos, mas constituem classes de token diferentes. Assim, no hack, o lexer chama o analisador semântico (digamos, tabela de símbolos) e verifica se a sequência requer um nome de typedef. Nesse caso, as informações devem fluir de volta não apenas do analisador, mas do analisador semântico de volta ao lexer, o que complica o design.

Veja também

Referências

Fontes

  • Compilando com C # e Java , Pat Terry, 2005, ISBN  032126360X
  • Algoritmos + estruturas de dados = programas , Niklaus Wirth, 1975, ISBN  0-13-022418-9
  • Compiler Construction , Niklaus Wirth, 1996, ISBN  0-201-40353-6
  • Sebesta, RW (2006). Conceitos de linguagens de programação (sétima edição) pp. 177. Boston: Pearson / Addison-Wesley.

links externos