Quali sono le buone risorse su come scrivere un lexer in C ++ (libri, tutorial, documenti), quali sono alcune buone tecniche e pratiche?
Ho guardato su Internet e tutti dicono di usare un generatore di lexer come lex. Non voglio farlo, voglio scrivere un lexer a mano.
Ricorda che ogni macchina a stati finiti corrisponde a un'espressione regolare, che corrisponde a un programma strutturato utilizzando if e while dichiarazioni.
Quindi, ad esempio, per riconoscere gli interi, potresti avere il computer di stato:
0: digit -> 1
1: digit -> 1
o l'espressione regolare:
digit digit*
o il codice strutturato:
if (isdigit(*pc)){
while(isdigit(*pc)){
pc++;
}
}
Personalmente, scrivo sempre i lexer usando quest'ultimo, perché IMHO non è meno chiaro e non c'è niente di più veloce.
I lessici sono macchine a stati finiti. Pertanto, possono essere costruiti da qualsiasi libreria FSM generica. Ai fini della mia educazione, tuttavia, ho scritto il mio, usando modelli di espressioni. Ecco il mio lexer:
static const std::unordered_map<Unicode::String, Wide::Lexer::TokenType> reserved_words(
[]() -> std::unordered_map<Unicode::String, Wide::Lexer::TokenType>
{
// Maps reserved words to TokenType enumerated values
std::unordered_map<Unicode::String, Wide::Lexer::TokenType> result;
// RESERVED WORD
result[L"dynamic_cast"] = Wide::Lexer::TokenType::DynamicCast;
result[L"for"] = Wide::Lexer::TokenType::For;
result[L"while"] = Wide::Lexer::TokenType::While;
result[L"do"] = Wide::Lexer::TokenType::Do;
result[L"continue"] = Wide::Lexer::TokenType::Continue;
result[L"auto"] = Wide::Lexer::TokenType::Auto;
result[L"break"] = Wide::Lexer::TokenType::Break;
result[L"type"] = Wide::Lexer::TokenType::Type;
result[L"switch"] = Wide::Lexer::TokenType::Switch;
result[L"case"] = Wide::Lexer::TokenType::Case;
result[L"default"] = Wide::Lexer::TokenType::Default;
result[L"try"] = Wide::Lexer::TokenType::Try;
result[L"catch"] = Wide::Lexer::TokenType::Catch;
result[L"return"] = Wide::Lexer::TokenType::Return;
result[L"static"] = Wide::Lexer::TokenType::Static;
result[L"if"] = Wide::Lexer::TokenType::If;
result[L"else"] = Wide::Lexer::TokenType::Else;
result[L"decltype"] = Wide::Lexer::TokenType::Decltype;
result[L"partial"] = Wide::Lexer::TokenType::Partial;
result[L"using"] = Wide::Lexer::TokenType::Using;
result[L"true"] = Wide::Lexer::TokenType::True;
result[L"false"] = Wide::Lexer::TokenType::False;
result[L"null"] = Wide::Lexer::TokenType::Null;
result[L"int"] = Wide::Lexer::TokenType::Int;
result[L"long"] = Wide::Lexer::TokenType::Long;
result[L"short"] = Wide::Lexer::TokenType::Short;
result[L"module"] = Wide::Lexer::TokenType::Module;
result[L"dynamic"] = Wide::Lexer::TokenType::Dynamic;
result[L"reinterpret_cast"] = Wide::Lexer::TokenType::ReinterpretCast;
result[L"static_cast"] = Wide::Lexer::TokenType::StaticCast;
result[L"enum"] = Wide::Lexer::TokenType::Enum;
result[L"operator"] = Wide::Lexer::TokenType::Operator;
result[L"throw"] = Wide::Lexer::TokenType::Throw;
result[L"public"] = Wide::Lexer::TokenType::Public;
result[L"private"] = Wide::Lexer::TokenType::Private;
result[L"protected"] = Wide::Lexer::TokenType::Protected;
result[L"friend"] = Wide::Lexer::TokenType::Friend;
result[L"this"] = Wide::Lexer::TokenType::This;
return result;
}()
);
std::vector<Wide::Lexer::Token*> Lexer::Context::operator()(Unicode::String* filename, Memory::Arena& arena) {
Wide::IO::TextInputFileOpenArguments args;
args.encoding = Wide::IO::Encoding::UTF16;
args.mode = Wide::IO::OpenMode::OpenExisting;
args.path = *filename;
auto str = arena.Allocate<Unicode::String>(args().AsString());
const wchar_t* begin = str->c_str();
const wchar_t* end = str->c_str() + str->size();
int line = 1;
int column = 1;
std::vector<Token*> tokens;
// Some variables we'll need for semantic actions
Wide::Lexer::TokenType type;
auto multi_line_comment
= MakeEquality(L'/')
>> MakeEquality(L'*')
>> *( !(MakeEquality(L'*') >> MakeEquality(L'/')) >> eps)
>> eps >> eps;
auto single_line_comment
= MakeEquality(L'/')
>> MakeEquality(L'/')
>> *( !MakeEquality(L'\n') >> eps);
auto punctuation
= MakeEquality(L',')[[&]{ type = Wide::Lexer::TokenType::Comma; }]
|| MakeEquality(L';')[[&]{ type = Wide::Lexer::TokenType::Semicolon; }]
|| MakeEquality(L'~')[[&]{ type = Wide::Lexer::TokenType::BinaryNOT; }]
|| MakeEquality(L'(')[[&]{ type = Wide::Lexer::TokenType::OpenBracket; }]
|| MakeEquality(L')')[[&]{ type = Wide::Lexer::TokenType::CloseBracket; }]
|| MakeEquality(L'[')[[&]{ type = Wide::Lexer::TokenType::OpenSquareBracket; }]
|| MakeEquality(L']')[[&]{ type = Wide::Lexer::TokenType::CloseSquareBracket; }]
|| MakeEquality(L'{')[[&]{ type = Wide::Lexer::TokenType::OpenCurlyBracket; }]
|| MakeEquality(L'}')[[&]{ type = Wide::Lexer::TokenType::CloseCurlyBracket; }]
|| MakeEquality(L'>') >> (
MakeEquality(L'>') >> (
MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::RightShiftEquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::RightShift; }])
|| MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::GreaterThanOrEqualTo; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::GreaterThan; }])
|| MakeEquality(L'<') >> (
MakeEquality(L'<') >> (
MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::LeftShiftEquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::LeftShift; }] )
|| MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::LessThanOrEqualTo; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::LessThan; }])
|| MakeEquality(L'-') >> (
MakeEquality(L'-')[[&]{ type = Wide::Lexer::TokenType::Decrement; }]
|| MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::MinusEquals; }]
|| MakeEquality(L'>')[[&]{ type = Wide::Lexer::TokenType::PointerAccess; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::Minus; }])
|| MakeEquality(L'.')
>> (MakeEquality(L'.') >> MakeEquality(L'.')[[&]{ type = Wide::Lexer::TokenType::Ellipsis; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::Dot; }])
|| MakeEquality(L'+') >> (
MakeEquality(L'+')[[&]{ type = Wide::Lexer::TokenType::Increment; }]
|| MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::PlusEquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::Plus; }])
|| MakeEquality(L'&') >> (
MakeEquality(L'&')[[&]{ type = Wide::Lexer::TokenType::LogicalAnd; }]
|| MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::BinaryANDEquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::BinaryAND; }])
|| MakeEquality(L'|') >> (
MakeEquality(L'|')[[&]{ type = Wide::Lexer::TokenType::LogicalOr; }]
|| MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::BinaryOREquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::BinaryOR; }])
|| MakeEquality(L'*') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::MulEquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::Multiply; }])
|| MakeEquality(L'%') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::ModulusEquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::Modulus; }])
|| MakeEquality(L'=') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::EqualTo; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::Assignment; }])
|| MakeEquality(L'!') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::NotEquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::LogicalNOT; }])
|| MakeEquality(L'/') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::DivEquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::Divide; }])
|| MakeEquality(L'^') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::BinaryXOREquals; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::BinaryXOR; }])
|| MakeEquality(L':') >> (MakeEquality(L'=')[[&]{ type = Wide::Lexer::TokenType::VarAssign; }]
|| opt[[&]{ type = Wide::Lexer::TokenType::Colon; }]);
auto string
= L'"' >> *( L'\' >> MakeEquality(L'"') >> eps || !MakeEquality(L'"') >> eps) >> eps;
auto character
= L'\'' >> *( L'\' >> MakeEquality(L'\'') >> eps || !MakeEquality(L'\'') >> eps);
auto digit
= MakeRange(L'0', L'9');
auto letter
= MakeRange(L'a', L'z') || MakeRange(L'A', L'Z');
auto number
= +digit >> ((L'.' >> +digit) || opt);
auto new_line
= MakeEquality(L'\n')[ [&] { line++; column = 0; } ];
auto whitespace
= MakeEquality(L' ')
|| L'\t'
|| new_line
|| L'\n'
|| L'\r'
|| multi_line_comment
|| single_line_comment;
auto identifier
= (letter || L'_') >> *(letter || digit || (L'_'));
//= *( !(punctuation || string || character || whitespace) >> eps );
bool skip = false;
auto lexer
= whitespace[ [&]{ skip = true; } ] // Do not produce a token for whitespace or comments. Just continue on.
|| punctuation[ [&]{ skip = false; } ] // Type set by individual punctuation
|| string[ [&]{ skip = false; type = Wide::Lexer::TokenType::String; } ]
|| character[ [&]{ skip = false; type = Wide::Lexer::TokenType::Character; } ]
|| number[ [&]{ skip = false; type = Wide::Lexer::TokenType::Number; } ]
|| identifier[ [&]{ skip = false; type = Wide::Lexer::TokenType::Identifier; } ];
auto current = begin;
while(current != end) {
if (!lexer(current, end)) {
throw std::runtime_error("Failed to lex input.");
}
column += (current - begin);
if (skip) {
begin = current;
continue;
}
Token t(begin, current);
t.columnbegin = column - (current - begin);
t.columnend = column;
t.file = filename;
t.line = line;
if (type == Wide::Lexer::TokenType::Identifier) { // check for reserved word
if (reserved_words.find(t.Codepoints()) != reserved_words.end())
t.type = reserved_words.find(t.Codepoints())->second;
else
t.type = Wide::Lexer::TokenType::Identifier;
} else {
t.type = type;
}
begin = current;
tokens.push_back(arena.Allocate<Token>(t));
}
return tokens;
}
È supportato da una libreria di macchine a stati finiti basata su iteratore, con back-tracking, che ha una lunghezza di ~ 400 righe. Tuttavia, è facile vedere che tutto ciò che dovevo fare era costruire semplici operazioni booleane, come and , or e not , e un paio di operatori in stile regex come * per zero o più , eps significa "abbina nulla" e opt significa "abbina tutto ma non consumarlo". La libreria è completamente generica e basata su iteratori. Il materiale MakeEquality è un semplice test per l'uguaglianza tra *it e il valore passato, e MakeRange è un semplice test <= >= .
Alla fine, ho intenzione di passare dal backtracking al predittivo.
Prima di tutto, ci sono diverse cose da fare qui:
Generalmente, ci aspettiamo che un lexer faccia tutti e 3 i passaggi in una volta, tuttavia quest'ultima è intrinsecamente più difficile e ci sono alcuni problemi con l'automazione (ne parleremo più avanti).
Il lessico più sorprendente che conosco è Boost.Spirit.Qi . Utilizza i modelli di espressione per generare le espressioni lessicali e, una volta abituato alla sua sintassi, il codice risulta davvero accurato. Compilare molto lentamente (modelli pesanti), quindi è meglio isolare le varie parti in file dedicati per evitare di ricompilarli quando non sono stati toccati.
Ci sono alcuni trabocchetti nelle prestazioni, e l'autore del compilatore di Epoch spiega come ha ottenuto un aumento di velocità 1000x grazie a profilazione e indagini intensive su come Qi funziona in un articolo .
Infine, ci sono anche codice generato da strumenti esterni (Yacc, Bison, ...).
Ma ho promesso un resoconto su cosa c'era di sbagliato nell'automazione della verifica grammaticale.
Se controlli Clang, ad esempio, ti renderai conto che invece di usare un parser generato e qualcosa come Boost.Spirit, invece, si prefiggono di convalidare manualmente la grammatica usando una tecnica di analisi della discendenza generica. Sicuramente questo sembra arretrato?
In realtà, esiste una ragione molto semplice: ripristino errori .
L'esempio tipico, in C ++:
struct Immediate { } instanceOfImmediate;
struct Foo {}
void bar() {
}
Si noti l'errore? Un punto e virgola mancante a destra dopo la dichiarazione di Foo .
È un errore comune, e Clang si riprende ordinatamente rendendosi conto che è semplicemente mancante e void non è un'istanza di Foo ma parte della prossima dichiarazione. Questo evita di diagnosticare messaggi di errore criptici.
La maggior parte degli strumenti automatici non ha (almeno ovvio) i modi per specificare quei probabili errori e come recuperarli. Spesso il recupero richiede una piccola analisi sintattica quindi è tutt'altro che evidente.
Quindi, c'è un compromesso nell'utilizzo di uno strumento automatico: ottieni rapidamente il parser, ma è meno user-friendly.
Dato che vuoi imparare come funzionano i lexer, presumo che tu voglia veramente sapere come funzionano i generatori di lexer.
Un generatore di lexer prende una specifica lessicale, che è un elenco di regole (coppie di token di espressioni regolari) e genera un lexer. Questo lexer risultante può quindi trasformare una stringa di input (carattere) in una stringa di token in base a questo elenco di regole.
Il metodo più comunemente usato consiste principalmente nel trasformare un'espressione regolare in un automix finito deterministico (DFA) tramite un automa non deterministico (NFA), più alcuni dettagli.
Una guida dettagliata su questa trasformazione può essere trovata qui . Nota che non l'ho letto da solo, ma sembra abbastanza buono. Inoltre, quasi tutti i libri sulla costruzione del compilatore presenteranno questa trasformazione nei primi capitoli.
Se sei interessato alle diapositive delle lezioni sui corsi sull'argomento, non ci sono dubbi su una quantità infinita di loro da corsi sulla costruzione di compilatori. Dalla mia università, puoi trovare tali diapositive qui e here .
Ci sono poche altre cose che non sono comunemente usate nei lexer o trattate nei testi, ma sono comunque molto utili:
In primo luogo, la gestione di Unicode è in qualche modo non banale. Il problema è che l'input ASCII è largo solo 8 bit, il che significa che puoi facilmente avere una tabella di transizione per ogni stato in DFA, perché hanno solo 256 voci. Tuttavia, Unicode, essendo largo 16 bit (se si utilizza UTF-16), richiede 64k tabelle per ogni voce in DFA. Se hai grammatiche complesse, questo potrebbe iniziare a occupare un po 'di spazio. Il riempimento di queste tabelle inizia anche a richiedere un po 'di tempo.
In alternativa, è possibile generare alberi intervallati. Un albero di intervallo può contenere le tuple ('a', 'z'), ('A', 'Z') per esempio, che è molto più efficiente della memoria rispetto alla tabella completa. Se si mantengono intervalli non sovrapposti, è possibile utilizzare qualsiasi albero binario bilanciato per questo scopo. Il tempo di esecuzione è lineare nel numero di bit necessari per ogni carattere, quindi O (16) nel caso Unicode. Tuttavia, nel migliore dei casi, di solito sarà un po 'meno.
Un altro problema è che i lexer generati comunemente hanno in realtà una prestazione quadratica nel caso peggiore. Anche se questo comportamento nel caso peggiore non è comunemente visto, potrebbe morderti. Se incontri il problema e vuoi risolverlo, puoi trovare un articolo che descrive come ottenere il tempo lineare qui .
Probabilmente vorrai essere in grado di descrivere le espressioni regolari in forma di stringa, come normalmente appaiono. Tuttavia, l'analisi di queste descrizioni di espressioni regolari in NFA (o forse prima in una struttura intermedia ricorsiva) è un po 'un problema di uovo di gallina. Per analizzare le descrizioni delle espressioni regolari, l'algoritmo Shunting Yard è molto adatto. Wikipedia sembra avere una pagina estesa su l'algoritmo .