Qual deve ser o tipo de dados dos tokens que um lexer retorna ao seu analisador?

21

Como dito no título, que tipo de dados um lexer deve retornar / fornecer ao analisador? Ao ler o artigo de análise lexical que a Wikipedia possui, afirmou que:

Na ciência da computação, a análise lexical é 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" identificado).

No entanto, em completa contradição com a afirmação acima, quando outra pergunta que fiz em um site diferente ( Revisão do código, se você estiver curioso) foi respondida, a pessoa que respondeu afirmou que:

O lexer geralmente lê a string e a converte em um fluxo ... de lexemes. Os lexemas precisam apenas ser um fluxo de números .

e ele deu esse visual:

nl_output => 256
output    => 257
<string>  => 258

Mais adiante, no artigo, ele mencionou Flexum lexer já existente e disse que escrever "regras" com ele seria mais simples do que escrever um lexer à mão. Ele passou a me dar este exemplo:

Space              [ \r\n\t]
QuotedString       "[^"]*"
%%
nl_output          {return 256;}
output             {return 257;}
{QuotedString}     {return 258;}
{Space}            {/* Ignore */}
.                  {error("Unmatched character");}
%%

Para aprofundar meus conhecimentos e obter mais informações, li o artigo da Wikipedia sobre o Flex . o artigo Flex mostrou que você pode definir um conjunto de regras de sintaxe, com tokens, da seguinte maneira:

digit         [0-9]
letter        [a-zA-Z]

%%
"+"                  { return PLUS;       }
"-"                  { return MINUS;      }
"*"                  { return TIMES;      }
"/"                  { return SLASH;      }
"("                  { return LPAREN;     }
")"                  { return RPAREN;     }
";"                  { return SEMICOLON;  }
","                  { return COMMA;      }
"."                  { return PERIOD;     }
":="                 { return BECOMES;    }
"="                  { return EQL;        }
"<>"                 { return NEQ;        }
"<"                  { return LSS;        }
">"                  { return GTR;        }
"<="                 { return LEQ;        }
">="                 { return GEQ;        }
"begin"              { return BEGINSYM;   }
"call"               { return CALLSYM;    }
"const"              { return CONSTSYM;   }
"do"                 { return DOSYM;      }
"end"                { return ENDSYM;     }
"if"                 { return IFSYM;      }
"odd"                { return ODDSYM;     }
"procedure"          { return PROCSYM;    }
"then"               { return THENSYM;    }
"var"                { return VARSYM;     }
"while"              { return WHILESYM;   }

Parece-me que o Flex lexer está retornando seqüências de palavras-chave \ tokens. Mas poderia estar retornando constantes iguais a determinados números.

Se o lexer retornasse números, como ele leria literais de string? retornar um número é adequado para palavras-chave únicas. Mas como você lida com uma string? O lexer não precisaria converter a string em números binários e, em seguida, o analisador converteria os números novamente em uma string. Parece muito mais lógico (e mais fácil) para o lexer retornar strings e, em seguida, permitir que o analisador converta qualquer literal de string numérico em números reais.

Ou o lexer poderia retornar os dois? Eu tenho tentado escrever um lexer simples em c ++, que permite que você tenha apenas um tipo de retorno para suas funções. Assim, levando-me a fazer minha pergunta.

Para condensar minha pergunta em um parágrafo: Ao escrever um lexer, e assumindo que ele poderia retornar apenas um tipo de dados (strings ou números), qual seria a opção mais lógica?

Christian Dean
fonte
O lexer retorna o que você diz para retornar. Se o seu design solicitar números, ele retornará números. Obviamente, representar literais de strings exigirá um pouco mais do que isso. Veja também É um trabalho da Lexer analisar números e seqüências de caracteres? Observe que os literais de seqüência de caracteres geralmente não são considerados "Elementos da linguagem".
Robert Harvey
@RobertHarvey Então, você converteria a string literal em números binários?
Christian Dean
Pelo que entendi, o objetivo do lexer é pegar os elementos da linguagem (como palavras-chave, operadores e assim por diante) e transformá-los em tokens. Assim, as seqüências de caracteres citadas não interessam ao lexer, porque não são elementos de linguagem. Embora eu nunca tenha escrito um lexer, eu imaginaria que a string citada é simplesmente passada inalterada (incluindo as aspas).
Robert Harvey
Então, o que você está dizendo é que o lexer não lê nem se importa com literais de strings. E assim o analisador deve procurar esses literais de string? Isso é muito confuso.
Christian Dean
Você pode gastar alguns minutos lendo isso: en.wikipedia.org/wiki/Lexical_analysis
Robert Harvey

Respostas:

10

Geralmente, se você estiver processando um idioma através de lexing e análise, terá uma definição de seus tokens lexicais, por exemplo:

NUMBER ::= [0-9]+
ID     ::= [a-Z]+, except for keywords
IF     ::= 'if'
LPAREN ::= '('
RPAREN ::= ')'
COMMA  ::= ','
LBRACE ::= '{'
RBRACE ::= '}'
SEMICOLON ::= ';'
...

e você tem uma gramática para o analisador:

STATEMENT ::= IF LPAREN EXPR RPAREN STATEMENT
            | LBRACE STATEMENT BRACE
            | EXPR SEMICOLON
EXPR      ::= ID
            | NUMBER
            | ID LPAREN EXPRS RPAREN
...

Seu lexer pega o fluxo de entrada e produz um fluxo de tokens. O fluxo de tokens é consumido pelo analisador para produzir uma árvore de análise. Em alguns casos, basta conhecer o tipo do token (por exemplo, LPAREN, RBRACE, FOR), mas em alguns casos, você precisará do valor real associado ao token. Por exemplo, quando você encontrar um token de ID, desejará os caracteres reais que compõem o ID mais tarde, quando estiver tentando descobrir qual identificador está tentando fazer referência.

Então, você normalmente tem algo mais ou menos assim:

enum TokenType {
  NUMBER, ID, IF, LPAREN, RPAREN, ...;
}

class Token {
  TokenType type;
  String value;
}

Portanto, quando o lexer retorna um token, você sabe qual é o tipo (do qual você precisa para a análise) e a sequência de caracteres a partir da qual foi gerado (do qual você precisará mais tarde para interpretar cadeias e literais numéricos, identificadores, etc.) Pode parecer que você está retornando dois valores, já que está retornando um tipo agregado muito simples, mas realmente precisa das duas partes. Afinal, você gostaria de tratar os seguintes programas de maneira diferente:

if (2 > 0) {
  print("2 > 0");
}
if (0 > 2) {
  print("0 > 2");
}

Eles produzem a mesma sequência de tipos de token : SE, LPAREN, NÚMERO, MAIOR_THAN, NÚMERO, RPAREN, LBRACE, ID, LPAREN, STRING, RPAREN, SEMICOLON, RBRACE. Isso significa que eles analisam o mesmo também. Mas quando você estiver realmente fazendo algo com a árvore de análise, você se importará de que o valor do primeiro número seja '2' (ou '0') e que o valor do segundo número seja '0' (ou '2 ') e que o valor da sequência é' 2> 0 '(ou' 0> 2 ').

Joshua Taylor
fonte
Entendo muito do que você está dizendo, mas como isso será String valuepreenchido? será preenchido com uma string ou um número? E também, como eu definiria o Stringtipo?
Christian Dean
1
@ Mr.Python No caso mais simples, é apenas a sequência de caracteres que corresponde à produção lexical. Portanto, se você ver foo (23, "bar") , obterá os tokens [ID, "foo"], [LPAREN ", ((]] [[NUMBER," 23 "], [COMMA", " ], [STRING, "" 23 ""], [RPAREN, ")"] . Preservar essa informação pode ser importante. Ou você pode adotar outra abordagem e fazer com que o valor tenha um tipo de união que possa ser uma sequência ou número, etc., e escolher o tipo de valor correto com base no tipo de token que você possui (por exemplo, quando o tipo de token é NUMBER , use value.num e, quando for STRING, use value.str).
21716 Joshua Taylor
@MrPython "E também, como eu definiria o tipo String?" Eu estava escrevendo a partir de uma mentalidade Java-ish. Se você estiver trabalhando em C ++, poderá usar o tipo de string do C ++ ou, se estiver trabalhando em C, poderá usar um caractere *. O ponto é que, associado a um token, você tem o valor correspondente ou o texto que pode ser interpretado para produzir o valor.
21416 Joshua Taylor
1
@ ollydbg23 é uma opção, e não é irracional, mas torna o sistema menos consistente internamente. Por exemplo, se você quiser o valor da última cidade que analisou, precisará verificar explicitamente um valor nulo e, em seguida, usar uma pesquisa inversa de token para string para descobrir qual teria sido a string. Além disso, é um acoplamento mais apertado entre o lexer e o analisador; haverá mais código a ser atualizado se o LPAREN puder corresponder a seqüências diferentes ou múltiplas.
Joshua Taylor
2
@ ollydbg23 Um caso seria um pseudo-minificador simples. É fácil de fazer parse(inputStream).forEach(token -> print(token.string); print(' '))(ou seja, basta imprimir os valores da string dos tokens, separados por espaço). Isso é bem rápido. E mesmo que o LPAREN possa surgir apenas de "(", isso pode ser uma cadeia constante na memória, incluir uma referência a ele no token pode não ser mais caro do que incluir a referência nula. Em geral, prefiro escrever código que não me torna um caso especial de código
Joshua Taylor
6

Como dito no título, que tipo de dados um lexer deve retornar / fornecer ao analisador?

"Token", obviamente. Um lexer produz um fluxo de tokens, portanto, ele deve retornar um fluxo de tokens .

Ele mencionou o Flex, um lexer já existente, e disse que escrever 'regras' com ele seria mais simples do que escrever um lexer manualmente.

Os lexers gerados por máquina têm a vantagem de gerá-los rapidamente, o que é particularmente útil se você acha que sua gramática lexical vai mudar muito. Eles têm a desvantagem de que você geralmente não tem muita flexibilidade nas suas opções de implementação.

Dito isto, quem se importa se é "mais simples"? Escrever o lexer geralmente não é a parte mais difícil!

Ao escrever um lexer, e assumindo que ele poderia retornar apenas um tipo de dados (strings ou números), qual seria a opção mais lógica?

Nem. Um lexer normalmente tem uma operação "próxima" que retorna um token, portanto, ele deve retornar um token . Um token não é uma sequência ou um número. É um sinal.

O último lexer que escrevi foi um lexer de "fidelidade total", o que significa que ele retornou um token que rastreia a localização de todos os espaços em branco e comentários - que chamamos de "trivialidades" - no programa, bem como o token. No meu lexer, um token foi definido como:

  • Uma variedade de curiosidades importantes
  • Um tipo de token
  • Uma largura de token em caracteres
  • Uma variedade de curiosidades à direita

Curiosidades foi definido como:

  • Uma espécie de trivialidade - espaço em branco, nova linha, comentário e assim por diante
  • Uma largura de trivia em caracteres

Então, se tivéssemos algo como

    foo + /* comment */
/* another comment */ bar;

que seria lex como quatro fichas com tipos simbólicos Identifier, Plus, Identifier, Semicolon, e as larguras de 3, 1, 3, 1. O primeiro identificador tem trivialidades que consiste em líder Whitespacecom uma largura de 4 e de fuga trivialidades Whitespacecom largura de 1. A Plusnão tem trivialidades que conduz e trivialidades finais consistindo em um espaço em branco, um comentário e uma nova linha. O identificador final tem uma trivialidade principal de um comentário e um espaço, e assim por diante.

Com esse esquema, todos os caracteres do arquivo são contabilizados na saída do lexer, que é uma propriedade útil para itens como coloração de sintaxe.

Obviamente, se você não precisa de trivialidades, pode simplesmente fazer um token de duas coisas: o tipo e a largura.

Você pode perceber que o token e as trivialidades contêm apenas suas larguras, não sua posição absoluta no código-fonte. Isso é deliberado. Esse esquema tem vantagens:

  • É compacto em formato de memória e fio
  • Permite refletir novamente em edições; isso é útil se o lexer estiver sendo executado dentro de um IDE. Ou seja, se você detectar uma edição em um token, basta fazer backup do seu lexer em alguns tokens antes da edição e começar a lexing novamente até sincronizar com o fluxo de token anterior. Quando você digita um caractere, a posição de cada token após esse caractere muda, mas geralmente apenas um ou dois tokens mudam de largura, para que você possa reutilizar todo esse estado.
  • As compensações exatas de caracteres de cada token podem ser facilmente derivadas iterando sobre o fluxo de token e acompanhando o deslocamento atual. Depois de ter as compensações exatas dos caracteres, é fácil extrair o texto quando necessário.

Se você não se importa com nenhum desses cenários, um token pode ser representado como um tipo e um deslocamento, em vez de um tipo e uma largura.

Mas o principal argumento aqui é: programação é a arte de fazer abstrações úteis . Você está manipulando tokens; portanto, faça uma abstração útil sobre tokens e depois escolha por si mesmo quais detalhes de implementação estão subjacentes a ele.

Eric Lippert
fonte
3

Geralmente, você retorna uma pequena estrutura que possui um número que significa o token (ou valor da enumeração para facilitar o uso) e um valor opcional (sequência, ou possivelmente valor genérico / modelo). Outra abordagem seria retornar um tipo derivado para elementos que precisam transportar dados extras. Ambos são levemente desagradáveis, mas são soluções suficientes para um problema prático.

Telastyn
fonte
O que você quer dizer com um pouco desagradável ? Eles são maneiras ineficientes de obter valores de string?
Christian Dean
@ Mr. Python - eles levarão a muitas verificações antes do uso no código, o que é ineficiente, mas mais ainda torna o código um pouco mais complexo / frágil.
Telastyn
Eu tenho uma pergunta semelhante ao projetar um lexer em C ++, eu poderia retornar um Token *ou um simplesmente um Token, ou um TokenPtrque é um ponteiro compartilhado da Tokenclasse. Mas também vejo algum lexer retornar apenas um TokenType e armazenar o valor da string ou do número em outras variáveis ​​globais ou estáticas. Outra pergunta é como podemos armazenar as informações de localização. Preciso ter uma estrutura de token que possua os campos TokenType, String e Location? Obrigado.
precisa saber é o seguinte
@ ollydbg23 - qualquer uma dessas coisas pode funcionar. Eu usaria uma estrutura. E para idiomas que não aprendem, você estará usando um gerador de analisador de qualquer maneira.
Telastyn
@Telastyn obrigado pela resposta. Você quer dizer que uma estrutura de token pode ser algo como struct Token {TokenType id; std::string lexeme; int line; int column;}, certo? Para uma função pública do Lexer, como PeekToken(), a função pode retornar um Token *ou TokenPtr. Eu acho que por um tempo, se a função retornar o TokenType, como o Analisador tenta obter as outras informações sobre o Token? Portanto, um ponteiro como o tipo de dados é preferido para retornar dessa função. Algum comentário sobre a minha ideia? Graças
ollydbg23