c# - example - mano codificando un analizador

remarks c#

Question

Para todos los gurús de compilación, quiero escribir un analizador sintáctico de descenso recursivo y quiero hacerlo con solo código. Sin generar lexers y analizadores sintácticos de otra gramática y no me digan que lea el libro de dragones, eventualmente llegaré a eso.

Quiero profundizar en los detalles sobre la implementación de un Lexer y un analizador sintáctico para un lenguaje razonablemente simple, por ejemplo, CSS. Y quiero hacer esto bien.

Esto probablemente termine siendo una serie de preguntas, pero en este momento estoy empezando con un lexer. Las reglas de tokenización para CSS se pueden encontrar here .

Encuentro mi código de escritura automática así (espero que puedas inferir el resto de este fragmento):

public CssToken ReadNext()
{
    int val;
    while ((val = _reader.Read()) != -1)
    {
        var c = (char)val;
        switch (_stack.Top)
        {
            case ParserState.Init:
                if (c == '' '')
                {
                    continue; // ignore
                }
                else if (c == ''.'')
                {
                    _stack.Transition(ParserState.SubIdent, ParserState.Init);
                }
                break;

            case ParserState.SubIdent:
                if (c == ''-'')
                {
                    _token.Append(c);
                }
                _stack.Transition(ParserState.SubNMBegin);
                break;

¿Como se llama esto? y ¿qué tan lejos estoy de algo razonable, bien entendido? Estoy tratando de equilibrar algo que sea justo en términos de eficiencia y fácil de usar, usar una pila para implementar algún tipo de máquina de estado funciona bastante bien, pero no estoy seguro de cómo continuar así.

Lo que tengo es un flujo de entrada, desde el cual puedo leer 1 carácter a la vez. No hago ningún look en este momento, simplemente leo el personaje y luego, dependiendo del estado actual, trato de hacer algo con eso.

Realmente me gustaría entrar en la mentalidad de escribir fragmentos de código reutilizables. Este método de Transition actualmente significa hacerlo, mostrará el estado actual de la pila y luego empujará los argumentos en orden inverso. De esta forma, cuando escribo Transition(ParserState.SubIdent, ParserState.Init) , se "llamará" a una sub Sub rutina que, cuando se complete, volverá al estado Init .

El analizador se implementará de la misma manera, actualmente, tener todo en un único método grande como este me permite devolver fácilmente un token cuando lo encuentro, pero también me obliga a mantener todo en un solo método. ¿Hay una buena manera de dividir estas reglas de tokenización en métodos separados?

Answer 1

Lo que estás escribiendo se llama autómata pushdown. Esto usualmente es más poder que lo que necesita para escribir un lexer, es ciertamente excesivo si está escribiendo un lexer para un lenguaje moderno como CSS. Un analizador descendente recursivo está cerca del poder de un autómata pushdown, pero los analizadores descendentes recursivos son mucho más fáciles de escribir y comprender. La mayoría de los generadores de analizadores generan autómatas pushdown.

Los Lexers casi siempre se escriben como máquinas de estado finito, es decir, como su código, excepto para deshacerse del objeto "pila". Las máquinas de estados finitos están estrechamente relacionadas con las expresiones regulares (en realidad, son probablemente equivalentes entre sí). Al diseñar un analizador de este tipo, uno generalmente comienza con las expresiones regulares y las usa para crear un autómata finito determinista, con algún código adicional en las transiciones para registrar el comienzo y el final de cada token.

Hay herramientas para hacer esto. La herramienta lex y sus descendientes son bien conocidos y se han traducido a muchos idiomas. El toolchain ANTLR también tiene un componente lexer. Mi herramienta preferida es ragel en plataformas que lo soportan. La mayoría de las veces, le resulta poco útil escribir un lexer a mano, y el código generado por estas herramientas probablemente sea más rápido y más confiable.

Si desea escribir su propio lexer a mano, los buenos a menudo se ven más o menos así:

function readToken() // note: returns only one token each time
    while !eof
        c = peekChar()
        if c in A-Za-z
            return readIdentifier()
        else if c in 0-9
            return readInteger()
        else if c in '' /n/r/t/v/f''
            nextChar()
        ...
    return EOF

function readIdentifier()
    ident = ""
    while !eof
        c = nextChar()
        if c in A-Za-z0-9
            ident.append(c)
        else
            return Token(Identifier, ident)
            // or maybe...
            return Identifier(ident)

Luego puede escribir su analizador sintáctico como un analizador de descenso recursivo. No intente combinar las etapas lexer / analizador en una sola, esto lleva a un desorden total de código. (Según el autor de Parsec, es más lento, también).

Answer 2

Necesita escribir su propio analizador de descenso recursivo de su BNF / EBNF. Tuve que escribir el mío recientemente y esta página fue de mucha ayuda. No estoy seguro de a qué te refieres con "con solo código". ¿Quiere decir que quiere saber cómo escribir su propio analizador recursivo?

Si quieres hacer eso, primero necesitas tener tu gramática. Una vez que tenga su EBNF / BNF en su lugar, el analizador se puede escribir con bastante facilidad.

Lo primero que hice cuando escribí mi analizador, fue leer todo y luego tokenizar el texto. Así que esencialmente terminé con una matriz de tokens que traté como una pila. Para reducir la verborrea / sobrecarga de sacar un valor de una pila y luego volver a presionarlo si no lo requiere, puede tener un método de peek que simplemente devuelve el valor superior en la pila sin abrirlo.

ACTUALIZAR

En base a su comentario, tuve que escribir un analizador sintáctico de descenso recursivo en Javascript desde cero. Puedes echar un vistazo al analizador here . Solo busca la función de constraints . Escribí mi propia función tokenize para tokenizar la entrada también. También escribí otra función de conveniencia ( peek , que mencioné antes). El analizador analiza de acuerdo con el EBNF here .

Esto me llevó un poco de tiempo averiguarlo porque han pasado años desde que escribí un analizador sintáctico (¡la última vez que escribí fue en la escuela!), Pero créanme, una vez que lo obtienen, lo obtienen . Espero que mi ejemplo te lleve más lejos en tu camino.

OTRA ACTUALIZACIÓN

También me di cuenta de que mi ejemplo puede no ser el que usted desea porque podría utilizar un analizador de desplazamiento-reducción. Usted mencionó que en este momento está tratando de escribir un tokenizador. En mi caso, escribí mi propio tokenizer en Javascript. Probablemente no sea robusto, pero fue suficiente para mis necesidades.

 function tokenize(options) {
            var str = options.str;
            var delimiters = options.delimiters.split("");
            var returnDelimiters = options.returnDelimiters || false;
            var returnEmptyTokens = options.returnEmptyTokens || false;
            var tokens = new Array();
            var lastTokenIndex = 0;

            for(var i = 0; i < str.length; i++) {
                if(exists(delimiters, str[i])) {
                    var token = str.substring(lastTokenIndex, i);

                    if(token.length == 0) {
                        if(returnEmptyTokens) {
                            tokens.push(token);
                        }
                    }

                    else {
                        tokens.push(token);
                    }

                    if(returnDelimiters) {
                        tokens.push(str[i]);
                    }

                    lastTokenIndex = i + 1;
                }
            }

            if(lastTokenIndex < str.length) {
                var token = str.substring(lastTokenIndex, str.length);
                token = token.replace(/^/s+/, "").replace(//s+$/, "");

                if(token.length == 0) {
                    if(returnEmptyTokens) {
                        tokens.push(token);
                    }
                }

                else {
                    tokens.push(token);
                }
            }

            return tokens;
        }

Según tu código, parece que estás leyendo, tokenizando y analizando al mismo tiempo, supongo que eso es lo que hace un analizador de desplazamiento-reducción. El flujo de lo que tengo es tokenize primero para construir la pila de tokens, y luego enviar los tokens a través del analizador de descenso recursivo.

Answer 3

Parece que quieres implementar un analizador "shift-reduce" , donde construyes explícitamente una pila de tokens. La alternativa habitual es un analizador de "descenso recursivo", en el que las llamadas a profundidad de procedimiento crean la misma pila de tokens con sus propias variables locales, en la pila de hardware real.

En shift-reduce, el término "reducir" se refiere a la operación realizada en la pila de tokens mantenida explícitamente. Por ejemplo, si la parte superior de la pila se ha convertido en Term, Operator, Term entonces se puede aplicar una regla de reducción que resulte en Expression como un reemplazo para el patrón. Las reglas de reducción están codificadas explícitamente en una estructura de datos utilizada por el analizador shift-reduce; como resultado, todas las reglas de reducción se pueden encontrar en el mismo lugar del código fuente.

El enfoque shift-reduce ofrece algunos beneficios en comparación con el descenso recursivo. En un nivel subjetivo, mi opinión es que shift-reduce es más fácil de leer y mantener que el descenso recursivo. Más objetivamente, shift-reduce permite mensajes de error más informativos del analizador cuando se produce un token inesperado.

Específicamente, debido a que el analizador shift-reduce tiene una codificación explícita de reglas para hacer "reducciones", el analizador sintáctico se extiende fácilmente para articular qué tipos de tokens podrían haber seguido legalmente. (por ej., "; esperado"). Una implementación de descenso recursivo no se puede extender fácilmente para hacer lo mismo.

Un gran libro sobre ambos tipos de analizador, y las concesiones en la implementación de diferentes tipos de cambio-reducción es "Introducción a la construcción del compilador", por Thomas W. Parsons .

Shift-reduce a veces se denomina análisis "ascendente" y el descendente recursivo a veces se denomina análisis "descendente". En la analogía utilizada, los nodos compuestos con la precedencia más alta (por ejemplo, "factores" en la expresión de multiplicación) se consideran "en la parte inferior" del análisis sintáctico. Esto está de acuerdo con la misma analogía utilizada en "descenso" de "descenso recursivo".

Answer 4

Si quiere usar el analizador para manejar expresiones no bien formadas, realmente quiere un analizador de descenso recursivo. Es mucho más fácil hacer que el manejo de errores y los informes sean utilizables.

Para la literatura, recomendaría algunos de los viejos trabajos de Niklaus Wirth. Él sabe cómo escribir. Algoritmos + Estructuras de datos = Los programas son los que utilicé, pero puede encontrar su compilación en línea.

Answer 5

Si vas a codificar manualmente todo desde cero definitivamente consideraría ir con un analizador decente recursivo. En tu publicación, en realidad no estás diciendo lo que harás con la secuencia de tokens una vez que hayas analizado la fuente.

Algunas cosas que recomendaría obtener un control sobre
1. Buen diseño para su escáner / lexer, esto es lo que se convertirá en tokens de su código fuente para su analizador.
2. Lo siguiente es el analizador, si tiene un buen ebnf para el idioma de origen, el analizador generalmente se puede traducir bastante bien en un analizador decente recursivo.
3. Otra estructura de datos que realmente necesitará para entender es la tabla de símbolos. Esto puede ser tan simple como una tabla hash o tan compleja como una estructura de árbol que puede representar estructuras de registro complejas, etc. Creo que para CSS podría estar en algún lugar entre los dos.
4. Y finalmente quieres lidiar con la generación de código. Tienes muchas opciones aquí. Para un intérprete, puede simplemente interpretar sobre la marcha mientras analiza el código. Un mejor enfoque podría ser generar un for de i-code para el que luego pueda escribir un iterpreter, y más tarde incluso un compilador. Por supuesto, para la plataforma .NET puede generar directamente IL (probablemente no aplicable para CSS :))


En cuanto a las referencias, supongo que no estás pesado en la teoría profunda y no te culpo. Un buen punto de partida para obtener lo básico sin código complejo, si no te importa el Pascal, es el de Jack Crenshaw, "Construyamos un compilador".
http://compilers.iecc.com/crenshaw/
Buena suerte, estoy seguro de que disfrutarás de este proyecto.