Procurando uma definição clara do que são um "tokenizer", "analisador" e "lexers" e como eles se relacionam e são usados?

151

Estou procurando uma definição clara do que são um "tokenizer", "analisador" e "lexer" e como eles estão relacionados entre si (por exemplo, um analisador usa um tokenizador ou vice-versa)? Eu preciso criar um programa passará por arquivos de origem c / h para extrair declarações e definições de dados.

Eu tenho procurado exemplos e posso encontrar algumas informações, mas realmente estou lutando para entender os conceitos subjacentes, como regras gramaticais, analisar árvores e analisar a árvore abstrata de sintaxe e como elas se inter-relacionam. Eventualmente, esses conceitos precisam ser armazenados em um programa real, mas 1) como eles se parecem, 2) existem implementações comuns.

Eu estive pesquisando a Wikipedia sobre esses tópicos e programas como Lex e Yacc, mas nunca tendo passado por uma classe de compilador (EE major), acho difícil entender completamente o que está acontecendo.

parsing lexer tokenize lordhog
fonte

Respostas:

166

Um tokenizador divide um fluxo de texto em tokens, geralmente procurando espaços em branco (tabulações, espaços, novas linhas).

Um lexer é basicamente um tokenizador, mas geralmente anexa contexto extra aos tokens - esse token é um número, esse token é uma cadeia de caracteres literal, esse outro token é um operador de igualdade.

Um analisador pega o fluxo de tokens do lexer e o transforma em uma árvore de sintaxe abstrata que representa o (geralmente) programa representado pelo texto original.

A última vez que verifiquei, o melhor livro sobre o assunto foi "Compiladores: Princípios, Técnicas e Ferramentas", geralmente conhecido como "O Livro do Dragão".

Roger Lipscombe
fonte
8
Sem dúvida, "O Livro do Dragão" é um bom livro, mas exige que o leitor tenha uma boa base em CS. Um livro com apelo mais prático seria "Writing Compilers and Intpreters", de Ronald Mak, "Modern Compiler Implementation", Andrew Appel; "Construção de Compiladores", Niklaus Wirth; "Compilando com C # e Java" e "Compiladores e geradores de compiladores: uma introdução ao C ++", de Pat Terry; e, é claro, "The Definitive ANTLR Reference" de Terrence Parr.
Andre Artus
5
Só para ter certeza, não estou ignorando sua recomendação. "The Dragon Book" foi meu primeiro livro sobre tecnologia de compiladores, mas foi difícil em comparação com, digamos, o livro de Wirth, que é um livro que você pode ler em poucas horas. Naquela época, eu tinha poucas opções, pois era o único livro em que eu conseguia colocar minhas mãos (em 1991, antes da Amazon e da WWW). Eu tinha isso e uma coleção de arquivos de texto produzidos por Jack W. Crenshaw chamado "Vamos construir um compilador" (obrigado Jack!). Este ainda é o livro para obter uma compreensão mais completa dos princípios, mas a maioria dos programadores só precisa de uma introdução pragmática.
Andre Artus
10
Eu não concordaria que um analisador / por definição / produz uma árvore de sintaxe abstrata. Os analisadores podem produzir todos os tipos de saídas diferentes. Por exemplo, é comum que um analisador produza uma sequência de chamadas para alguma interface do construtor - consulte o Padrão do Construtor no livro de padrões do Gang of Four. O ponto principal é que o analisador analisa uma sequência de tokens para determinar se a sequência está ou não em conformidade com alguma gramática (geralmente sem contexto) e pode produzir alguma saída com base na estrutura gramatical da sequência.
Theodore Norvell
2
"Vamos construir um compilador" está aqui: compilers.iecc.com/crenshaw . Eu encontrei o link a partir daqui: prog21.dadgum.com/30.html
Roger Lipscombe
1
@Pithkos: se essas são as únicas restrições, tudo o que você disse é que a função recebe uma entrada em um domínio não identificado (matemático) e produz e produz em outro domínio não nomeado, por exemplo, F (X) -> Y Praticamente isso significa você só pode chamar isso de "função". Se você insistir que o domínio de X é <StreamOfCharacter, Grammar> e o domínio de Y é Tree com a propriedade que reflete a forma da gramática, então F (X, G) -> T seria algo que eu chamaria de analisador. Freqüentemente, curry F com relação a G porque G não muda com frequência, então F [G] (X) -> T é o que você geralmente vê como um analisador.
Ira Baxter
18

Exemplo:

int x = 1;

Um lexer ou tokeniser dividirá isso em tokens 'int', 'x', '=', '1', ';'.

Um analisador pegará esses tokens e os usará para entender de alguma maneira:

  • nós temos uma declaração
  • é uma definição de um número inteiro
  • o número inteiro é chamado 'x'
  • 'x' deve ser inicializado com o valor 1
Gra
fonte
9
Um lexer notará que "int", "=" e ";" são tokens sem significado adicional, que "x" é um nome identificador ou algo assim, valor "x" e "1" é um número inteiro ou número, valor "1". Um tokenizador não fará necessariamente isso.
23715 David Thornley
5

Eu diria que um lexer e um tokenizer são basicamente a mesma coisa, e eles esmagam o texto em suas partes componentes (os 'tokens'). O analisador interpreta os tokens usando uma gramática.

Eu não ficaria muito preocupado com o uso terminológico preciso - as pessoas costumam usar 'análise' para descrever qualquer ação de interpretação de um pedaço de texto.

Will Dean
fonte
1
Com os analisadores PEG, a distinção entre tokenizer e analisador é ainda menos clara.
Andre Artus
0

( adicionando às respostas dadas )

  • O tokenizador também removerá quaisquer comentários e retornará apenas os tokens para o Lexer.
  • A Lexer também definirá escopos para esses tokens (variáveis ​​/ funções)
  • O analisador criará a estrutura de código / programa
mcha
fonte
1
Olá @ downvoter, você pode explicar por que realmente fez o voto negativo?
precisa saber é o seguinte
1
Não sou a favor do voto negativo, mas acho que o voto negativo pode ter sido porque sua resposta não parece correta. Um tokenizador pode remover ruídos (geralmente espaço em branco, mas talvez também comentários), mas geralmente não alimenta o lexer. Um lexer baseado em DFA irá tokenizar e identificar o que são tokens (por exemplo, um número, uma sequência, um identificador, mas também um espaço em branco ou um comentário), mas não poderá ser escopo desses, pois isso exigiria a árvore de sintaxe que é posteriormente construída por o analisador.
Lucero
1) Não entendo sua aparente distinção entre "lexer" e "tokenizer". Criei analisadores para mais de 50 idiomas e nunca tive dois mecanismos separados que dividem o texto de origem em átomos; portanto, para mim, esses são apenas sinônimos. 2) Se você estiver compilando, remover comentários e espaços em branco faz sentido no lexer. Se você estiver criando ferramentas de transformação de fonte a fonte, não poderá perder comentários porque elas devem reaparecer no texto transformado. Portanto, SEMPRE remover comentários está errado; podemos discutir sobre como se consegue preservar o espaço em branco. ...
Ira Baxter
1
... [As ferramentas que construo (veja minha biografia) capturam ambas com fidelidade adequada para reproduzi-las no código transformado; vamos além e capturamos o formato dos átomos, incluindo coisas estranhas, como as aspas usadas nas cadeias de caracteres e a contagem inicial de números zero e raiz / número, tudo isso para evitar que o usuário rejeite o resultado transformado. Então, o que você perdeu não só é fazer lexers não necessariamente tira informação, mas na verdade eles podem precisar de informações de captura acima e além o token matéria]. ....
Ira Baxter
... 3) Os Lexers definem apenas "escopos" em analisadores irremediavelmente desajeitados, que têm dificuldade em lidar com ambiguidades sintáticas. Os analisadores C e C ++ são o exemplo canônico; consulte minha discussão em stackoverflow.com/a/1004737/120163 ). Não é preciso fazer dessa maneira (feia). Portanto, acho sua resposta simplesmente equivocada.
Ira Baxter