Quale dovrebbe essere il tipo di dati dei token che un lexer restituisce al parser?

Generalmente, se stai elaborando una lingua tramite lexing e analisi, hai una definizione dei token lessicali, ad esempio:

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

e hai una grammatica per il parser:

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

Il tuo lexer prende il flusso di input e produce un flusso di token. Il flusso di token viene utilizzato dal parser per produrre un albero di analisi. In alcuni casi, è sufficiente conoscere il tipo del token (ad esempio, LPAREN, RBRACE, FOR), ma in alcuni casi, è necessario il valore effettivo che è associato al token. Ad esempio, quando incontri un token ID, vorresti i caratteri reali che compongono l'ID in un secondo momento quando stai cercando di capire quale identificatore stai cercando di fare riferimento.

Quindi, in genere hai qualcosa di più o meno come questo:

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

class Token {
  TokenType type;
  String value;
}

Quindi, quando il lexer restituisce un token, sapete di che tipo è (di cui avete bisogno per l'analisi), e la sequenza di caratteri da cui è stato generato (di cui avrete bisogno in seguito per interpretare letterali stringa e numerici , identificatori, ecc.). Potrebbe sembrare che stai restituendo due valori, dal momento che stai restituendo un tipo di aggregazione molto semplice, ma hai davvero bisogno di entrambe le parti. Dopotutto, vorresti trattare i seguenti programmi in modo diverso:

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

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

Produce la stessa sequenza di tipi di token : SE, LPAREN, NUMBER, GREATER_THAN, NUMBER, RPAREN, LBRACE, ID, LPAREN, STRING, RPAREN, SEMICOLON, RBRACE. Ciò significa che anche loro analizzano . Ma quando stai effettivamente facendo qualcosa con l'albero di analisi, ti preoccuperai che il valore del primo numero sia '2' (o '0') e che il valore del secondo numero sia '0' (o '2 '), e che il valore della stringa è' 2 > 0 '(o' 0 > 2 ').

As said in the title, which data type should a lexer return/give the parser?

"Token", ovviamente. Un lexer produce un flusso di token, quindi dovrebbe restituire un flusso di token .

He mentioned Flex, a already existing lexer, and said writing 'rules' with it would be simpler than writing a lexer by hand.

I lexer generati dalle macchine hanno il vantaggio di poterli generare rapidamente, il che è particolarmente utile se pensi che la tua grammatica lessicale cambierà molto. Hanno lo svantaggio che spesso non si ottiene molta flessibilità nelle scelte di implementazione.

Detto questo, a chi importa se è "più semplice"? Scrivere il lexer di solito non è la parte difficile!

When writing a lexer, and assuming that it could only return one data type(strings or numbers), which would be the more logical choice?

Nessuno dei due. Generalmente un lexer ha un'operazione "successiva" che restituisce un token, quindi dovrebbe restituire un token . Un token non è una stringa o un numero. È un token.

L'ultimo lexer che ho scritto era un lexer "full fidelity", nel senso che restituiva un token che monitorava la posizione di tutti gli spazi bianchi e dei commenti (che chiamiamo "trivia") nel programma, così come il token . Nel mio lexer un token è stato definito come:

• Un array di trivia leader
• Un tipo di token
• Una larghezza di token nei caratteri
• Un array di trivia finale

Trivia è stata definita come:

• Un tipo di curiosità - spazio bianco, nuova riga, commento e così via
• Una larghezza trivia nei caratteri

Quindi se avessimo qualcosa di simile

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

che avrebbe lex come quattro token con tipi di token Identifier , Plus , Identifier , Semicolon e larghezza 3, 1, 3, 1. Il primo identificatore ha una serie di trivia che comprende Whitespace con una larghezza di 4 e trivia finale Whitespace con larghezza di 1. La percentuale diPlus non ha trivia e trivia finali che comprendono uno spazio bianco, un commento e una nuova riga. L'identificatore finale ha una trivia principale di un commento e uno spazio, e così via.

Con questo schema ogni carattere nel file viene preso in considerazione nell'output del lexer, che è una proprietà utile da avere per cose come la colorazione della sintassi.

Ovviamente, se non hai bisogno della curiosità, puoi semplicemente fare un token due cose: il tipo e la larghezza.

Potresti notare che il token e il trivia contengono solo la loro larghezza, non la loro posizione assoluta nel codice sorgente. È deliberato. Tale schema ha vantaggi:

• È compatto in memoria e in formato wire
• Abilita il re-lexing sulle modifiche; questo è utile se il lexer è in esecuzione all'interno di un IDE. Cioè, se si rileva una modifica in un token, si esegue il backup del lexer su un paio di token prima della modifica e si avvia nuovamente il lexing fino a quando non si è sincronizzati con il flusso di token precedente. Quando digiti un carattere, la posizione di ogni token dopo quel carattere cambia, ma di solito solo uno o due token cambiano di larghezza, quindi puoi riutilizzare tutto quello stato.
• Gli esatti offset di carattere di ogni token possono essere facilmente ricavati ripetendo il flusso di token e tenendo traccia dell'offset corrente. Una volta ottenuti gli offset dei caratteri esatti, è facile estrarre il testo quando necessario.

Se non ti interessa nessuno di questi scenari, allora un token potrebbe essere rappresentato come un tipo e un offset, piuttosto che un tipo e una larghezza.

Ma la chiave da asporto qui è: la programmazione è l'arte di fare astrazioni utili . Stai manipolando i token, quindi crea un'astrazione utile sui token e poi scegli autonomamente quali sono i dettagli di implementazione sottostanti.

Generalmente, si restituisce una piccola struttura che ha un numero che indica il token (o valore enum per facilità d'uso) e un valore opzionale (stringa, o possibilmente valore generico / basato su modelli). Un altro approccio sarebbe quello di restituire un tipo derivato per elementi che devono trasportare dati aggiuntivi. Entrambe sono leggermente di cattivo gusto, ma sono sufficienti soluzioni per un problema pratico.