Escribiendo un lexer en C ++

14

¿Cuáles son los buenos recursos sobre cómo escribir un lexer en C ++ (libros, tutoriales, documentos), cuáles son algunas buenas técnicas y prácticas?

He mirado en internet y todos dicen usar un generador lexer como lex. No quiero hacer eso, quiero escribir un lexer a mano.

    
pregunta rightfold 01.01.2012 - 12:00

4 respuestas

6

Tenga en cuenta que cada máquina de estados finitos corresponde a una expresión regular, que corresponde a un programa estructurado que usa las declaraciones if y while .

Entonces, por ejemplo, para reconocer enteros, podría tener la máquina de estado:

0: digit -> 1
1: digit -> 1

o la expresión regular:

digit digit*

o el código estructurado:

if (isdigit(*pc)){
  while(isdigit(*pc)){
    pc++;
  }
}

Personalmente, siempre escribo lexers usando este último, porque en mi humilde opinión no es menos claro, y no hay nada más rápido.

    
respondido por el Mike Dunlavey 01.01.2012 - 15:23
8

Lexers son máquinas de estado finito. Por lo tanto, pueden ser construidos por cualquier biblioteca FSM de propósito general. Para los propósitos de mi propia educación, sin embargo, escribí la mía, usando plantillas de expresión. Aquí está mi 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;
}

Está respaldado por una biblioteca de máquinas de estados finitos basada en iteradores y de seguimiento, que tiene una longitud de ~ 400 líneas. Sin embargo, es fácil ver que todo lo que tenía que hacer era construir operaciones booleanas simples, como and , or y not , y un par de operadores de estilo regex como * para cero o más , eps significa "coincidir con cualquier cosa" y opt significa "coincidir con cualquier cosa pero no la consumes". La biblioteca es totalmente genérica y basada en iteradores. Las cosas de MakeEquality son una prueba simple para la igualdad entre *it y el valor pasado, y MakeRange es una prueba simple de <= >= .

Eventualmente, estoy planeando pasar del backtracking al predictivo.

    
respondido por el DeadMG 01.01.2012 - 12:37
3

En primer lugar, hay diferentes cosas que están sucediendo aquí:

  • dividir la lista de caracteres en tokens
  • reconocer esos tokens (identificando palabras clave, literales, corchetes, ...)
  • verificar una estructura gramatical general

En general, esperamos que un lexer realice los 3 pasos de una sola vez, sin embargo, este último es inherentemente más difícil y hay algunos problemas con la automatización (más sobre esto más adelante).

El lexer más sorprendente que conozco es Boost.Spirit.Qi . Utiliza plantillas de expresión para generar sus expresiones de lexer, y una vez acostumbrado a su sintaxis, el código se siente realmente limpio. Sin embargo, se compila muy lentamente (plantillas pesadas), por lo que es mejor aislar las distintas partes en archivos dedicados para evitar que se vuelvan a compilar cuando no se han tocado.

Hay algunos escollos en el rendimiento, y el autor del compilador Epoch explica cómo consiguió una aceleración de 1000x mediante un análisis e investigación intensivos de cómo funciona Qi en un artículo .

Finalmente, también hay código generado por herramientas externas (Yacc, Bison, ...).

Pero prometí una reseña de lo que estaba mal al automatizar la verificación gramatical.

Si revisa Clang, por ejemplo, se dará cuenta de que en lugar de usar un analizador generado y algo como Boost.Spirit, en lugar de eso, intentaron validar la gramática manualmente utilizando una técnica genérica de análisis de pendientes. Seguramente esto parece al revés?

De hecho, hay una razón muy simple: recuperación de errores .

El ejemplo típico, en C ++:

struct Immediate { } instanceOfImmediate;

struct Foo {}

void bar() {
}

¿Notaste el error? Un punto y coma faltante justo después de la declaración de Foo .

Es un error común, y Clang se recupera perfectamente al darse cuenta de que simplemente falta y que void no es una instancia de Foo sino parte de la siguiente declaración. Esto evita los mensajes de error crípticos difíciles de diagnosticar.

La mayoría de las herramientas automatizadas no tienen ninguna forma (al menos obvia) de especificar los posibles errores y cómo recuperarse de ellos. A menudo, la recuperación requiere un poco de análisis sintáctico, por lo que está lejos de ser evidente.

Por lo tanto, hay una compensación relacionada con el uso de una herramienta automatizada: obtienes tu analizador rápidamente, pero es menos fácil de usar.

    
respondido por el Matthieu M. 01.01.2012 - 14:19
3

Ya que quiere aprender cómo funcionan los lexers, supongo que realmente quiere saber cómo funcionan los generadores de lexer.

Un generador lexer toma una especificación léxica, que es una lista de reglas (pares de token de expresión regular), y genera un lexer. Este lexer resultante puede transformar una cadena de entrada (carácter) en una cadena de token de acuerdo con esta lista de reglas.

El método que se usa más comúnmente consiste principalmente en transformar una expresión regular en un autómata finito determinista (DFA) a través de un autómata no determinista (NFA), más algunos detalles.

Puede encontrar una guía detallada para hacer esta transformación aquí . Tenga en cuenta que no lo he leído, pero se ve bastante bien. Además, casi cualquier libro sobre construcción de compiladores incluirá esta transformación en los primeros capítulos.

Si está interesado en las diapositivas de los cursos sobre el tema, no hay duda de que hay una cantidad infinita de ellos en los cursos sobre construcción de compiladores. Desde mi universidad, puede encontrar estas diapositivas aquí y aquí .

Hay pocas cosas más que no se emplean comúnmente en los lexers ni se tratan en los textos, pero que son bastante útiles, sin embargo:

En primer lugar, el manejo de Unicode es algo no trivial. El problema es que la entrada ASCII tiene solo 8 bits de ancho, lo que significa que puede tener fácilmente una tabla de transición para cada estado en la DFA, ya que solo tienen 256 entradas. Sin embargo, Unicode, con 16 bits de ancho (si usa UTF-16), requiere tablas de 64k para cada entrada en el DFA. Si tienes gramáticas complejas, esto puede comenzar a ocupar bastante espacio. Rellenar estas tablas también comienza a tomar bastante tiempo.

Alternativamente, podrías generar árboles de intervalo. Un árbol de rango puede contener las tuplas ('a', 'z'), ('A', 'Z'), por ejemplo, que es mucho más eficiente en memoria que tener la tabla completa. Si mantiene intervalos no superpuestos, puede usar cualquier árbol binario equilibrado para este propósito. El tiempo de ejecución es lineal en el número de bits que necesita para cada carácter, por lo que O (16) en el caso de Unicode. Sin embargo, en el mejor de los casos, por lo general será un poco menos.

Un problema más es que los lexers generados comúnmente tienen un desempeño cuadrático en el peor de los casos. Aunque este comportamiento en el peor de los casos no se ve con frecuencia, puede morderlo. Si se encuentra con el problema y desea resolverlo, puede encontrar un documento que describe cómo alcanzar el tiempo lineal aquí .

Probablemente querrá poder describir expresiones regulares en forma de cadena, como normalmente aparecen. Sin embargo, el análisis de estas descripciones de expresiones regulares en NFA (o posiblemente una estructura intermedia recursiva primero) es un problema de huevo de gallina. Para analizar las descripciones de expresiones regulares, el algoritmo de Shunting Yard es muy adecuado. Wikipedia parece tener una página extensa en el algoritmo .

    
respondido por el Alex ten Brink 01.01.2012 - 15:12

Lea otras preguntas en las etiquetas