codificación manual de un analizador

Si vas a codificar todo desde cero, definitivamente consideraría usar un analizador recursivo decente. En su publicación, realmente no está diciendo lo que hará con el flujo de tokens una vez que haya analizado la fuente.

Algunas cosas que recomendaría conseguir una manija en
1. Buen diseño para su escáner/lexer, esto es lo que será tokenizar su código fuente para su analizador.
2. Lo siguiente es el analizador, si tienes un buen ebnf para la fuente idioma el analizador por lo general puede traducir muy bien en un analizador recursivo decente.
3. Otra estructura de datos que realmente necesitará para obtener su cabeza alrededor es la tabla de símbolos. Esto puede ser tan simple como una tabla hash o tan complejo 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, simplemente puede interpretar en la mosca mientras analizas el código. Un mejor enfoque podría ser generar un for de i-code para el que luego se puede escribir un iterpreter, y más tarde incluso un compilador. Por supuesto, para la plataforma. NET podría generar directamente IL (probablemente no aplicable para CSS :))


Para las referencias, deduzco que no eres pesado en la teoría profunda y no te culpo. Un muy buen punto de partida para conseguir lo básico sin complejo, código si no te importa el Pascal es decir, es Jack Crenshaw ' Let's construir un compilador'
http://compilers.iecc.com/crenshaw/
Buena suerte Estoy seguro de que vas a disfrutar de este proyecto.

Necesita escribir su propio Analizador recursivo de Descenso desde su BNF/EBNF. Tuve que escribir mi propio recientemente y esta página fue de mucha ayuda. No estoy seguro de lo que quieres decir con "con solo código". ¿Quieres decir que quieres saber cómo escribir tu propio analizador recursivo?

Si quieres hacer eso, primero necesitas tener tu gramática en su lugar. Una vez que tenga su EBNF/BNF en su lugar, el analizador se puede escribir fácilmente desde él.

Lo primero que hice cuando escribí mi parser, era leer todo y luego tokenizar el texto. Así que esencialmente terminé con una matriz de tokens que traté como una pila. Para reducir la verbosidad / sobrecarga de extraer un valor de una pila y luego empujarlo de nuevo si no lo requiere, puede tener un método peek que simplemente devuelve el valor superior de la pila sin activarlo.

UPDATE

Basado en su comentario, tuve que escribir un analizador de descenso recursivo en Javascript desde cero. Puedes echa un vistazo al analizador aquí. Simplemente busque la función 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 aquí.

Esto me llevó un poco de tiempo averiguarlo porque han pasado años desde que escribí un analizador (la última vez que lo escribí fue en la escuela!), pero créeme, una vez que lo obtienes, lo obtienes. Espero que mi ejemplo consiga su más adelante en su camino.

OTRA ACTUALIZACIÓN

También me di cuenta de que mi ejemplo puede no ser lo que quieres porque podrías ir hacia el uso de un analizador sintáctico shift-reduce. Usted mencionó que en este momento está tratando de escribir un tokenizador. En mi caso, escribí mi propio tokenizador en Javascript. Probablemente no es robusto, pero era 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;
        }

Basado en su código, parece que está leyendo, tokenizando y analizando al mismo tiempo - ¿Asumo que eso es lo que hace un analizador de reducción de cambios? El flujo de lo que tengo es tokenizar primero para construir la pila de tokens, y luego enviar los tokens a través del analizador de descenso recursivo.

Parece que desea implementar un analizador "shift-reduce" , donde construye explícitamente una pila de tokens. La alternativa habitual es un analizador sintáctico de "descenso recursivo", en el que las llamadas a profundidad de procedimiento construyen 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 una regla de reducción se puede aplicar dando como resultado 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 de reducción de cambios trae 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 recursivo-descenso. Más objetivamente, shift-reduce permite más mensajes de error 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 se extiende fácilmente para articular qué tipos de tokens podrían haber seguido legalmente. (por ejemplo, "; 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 compensaciones en la implementación de diferentes tipos de shift-reduce es "Introducción a la construcción del compilador", por Thomas W. Parsons.

Shift-reduce a veces se llama análisis "bottom-up" y recursive-descent a veces se llama análisis "top-down". En la analogía utilizada, los nodos compuestos con mayor precedencia (por ejemplo, "factores" en la expresión de multiplicación) se consideran "en la parte inferior" del análisis. Esto está de acuerdo con la misma analogía utilizada en "descenso" de "descenso recursivo".

Si desea utilizar el analizador también para manejar expresiones no bien formadas, realmente desea un analizador recursivo de descenso. Mucho más fácil de obtener el manejo de errores y los informes utilizables.

Para literatura, recomendaría algunos de los viejos trabajos de Niklaus Wirth. Sabe escribir. Algoritmos + Estructuras de datos = Programas es lo que usé, pero puedes encontrar su Construcción del compilador en línea.