parsing - hecho - que es bison

¿Existe una alternativa para flex/bison que se pueda usar en sistemas integrados de 8 bits?

Question

Estoy escribiendo un pequeño intérprete para un lenguaje BASIC simple como un ejercicio en un microcontrolador AVR en C usando la cadena de herramientas avr-gcc. Sin embargo, me pregunto si hay alguna herramienta de código abierto que me ayude a escribir el analizador y el analizador.

Si escribiera esto para ejecutar en mi caja de Linux, podría usar flex / bison. Ahora que me restringí a una plataforma de 8 bits, ¿tengo que hacerlo todo a mano o no?

Answer 1

En lugar de reinventar la rueda, eche un vistazo a LUA: www.lua.org . Es un lenguaje interpretativo destinado a ser incorporado en otro software y utilizado en sistemas de pequeña escala, como sistemas integrados. Sintaxis de procedimiento incorporada, árbol de análisis sintáctico, lógica de control, matemática y soporte de variables: no es necesario reinventar algo que miles de otros ya han depurado y utilizado. Y es extensible, lo que significa que puede agregar a la gramática agregando sus propias funciones en C.

Answer 2

GCC puede realizar compilaciones cruzadas en una variedad de plataformas, pero ejecuta flex y bison en la plataforma en la que ejecuta el compilador. Simplemente escupieron el código C que luego compila el compilador. Pruébelo para ver qué tan grande es realmente el ejecutable resultante. Tenga en cuenta que tienen bibliotecas de tiempo de ejecución ( libfl.a etc.) que también tendrá que realizar una compilación cruzada para su destino.

Answer 3

Implementé un analizador para un lenguaje de comandos sencillo para ATmega328p . Este chip tiene una ROM de 32k y solo 2k de RAM. La RAM es definitivamente la limitación más importante: si todavía no estás vinculado a un chip en particular, elige uno con la mayor cantidad de RAM posible. Esto hará tu vida mucho más fácil.

Al principio consideré usar flex / bison. Decidí no utilizar esta opción por dos razones principales:

• Por defecto, Flex & Bison depende de algunas funciones de biblioteca estándar (especialmente para E / S) que no están disponibles o que no funcionan igual en avr-libc. Estoy bastante seguro de que hay soluciones alternativas compatibles, pero este es un esfuerzo adicional que deberá tener en cuenta.
• AVR tiene una arquitectura de Harvard . C no está diseñado para dar cuenta de esto, por lo que incluso las variables constantes se cargan en la memoria RAM de forma predeterminada . Debe usar macros / funciones especiales para almacenar y acceder a los datos en flash y EEPROM . Flex & Bison crea algunas tablas de búsqueda relativamente grandes, y éstas consumirán tu RAM bastante rápido. A menos que me equivoque (lo cual es bastante posible), tendrá que editar la fuente de salida para aprovechar las interfaces especiales de Flash y EEPROM.

Después de rechazar Flex & Bison, fui en busca de otras herramientas de generador. Aquí hay algunos que consideré:

• LEMON
• Ragel
• re2c

También es posible que desee echar un vistazo a la comparación de Wikipedia .

Finalmente, terminé codificando a mano tanto el lector como el analizador.

Para el análisis utilicé un analizador de descenso recursivo. Creo que Ira Baxter ya ha hecho un trabajo adecuado para cubrir este tema, y ​​hay muchos tutoriales en línea.

Para mi lector, escribí expresiones regulares para todos mis terminales, diagramamos la máquina de estado equivalente, y la implementamos como una función gigante usando goto para saltar entre estados. Esto fue tedioso, pero los resultados funcionaron de maravilla. Como un aparte, goto es una gran herramienta para implementar máquinas de estado: todos sus estados pueden tener etiquetas claras al lado del código relevante, no hay llamadas a funciones ni variables generales de estado, y es lo más rápido que puede obtener. C realmente no tiene una mejor construcción para construir máquinas de estado estático.

Algo en lo que pensar: los lexers son solo una especialización de analizadores sintácticos. La mayor diferencia es que las gramáticas regulares suelen ser suficientes para el análisis léxico, mientras que la mayoría de los lenguajes de programación tienen (principalmente) gramáticas libres de contexto. Por lo tanto, realmente no hay nada que te impida implementar un lector lexer como un analizador de descenso recursivo o utilizar un generador de analizador para escribir un lector de texto. Simplemente no es tan conveniente como usar una herramienta más especializada.

Answer 4

Prueba Boost :: Spirit. Es una biblioteca de solo encabezado que puedes incluir y construir un analizador muy rápido y limpio completamente en C ++. Se utilizan operadores sobrecargados en C ++ en lugar de un archivo de gramática especial.

Answer 5

Puede usar flex / bison en Linux con su gcc nativo para generar el código que luego compilará en forma cruzada con su AVR gcc para el objetivo incrustado.

Answer 6

Si desea una forma fácil de codificar analizadores sintácticos, o si tiene poco espacio, debe codificar manualmente un analizador de descenso recursivo; estos son esencialmente analizadores LL (1). Esto es especialmente efectivo para lenguajes que son tan "simples" como Básicos. (¡Hice varios de estos en los años 70!). La buena noticia es que estos no contienen ningún código de biblioteca; justo lo que escribes

Son muy fáciles de codificar, si ya tienes una gramática. Primero, debes deshacerte de las reglas recursivas de la izquierda (p. Ej., X = XY). Esto generalmente es bastante fácil de hacer, así que lo dejo como ejercicio. (No tiene que hacer esto para las reglas de formación de listas; vea la discusión a continuación).

Entonces, si tiene la regla BNF del formulario:

 X = A B C ;

crea una subrutina para cada elemento en la regla (X, A, B, C) que devuelve un booleano que dice "Vi la construcción de sintaxis correspondiente". Para X, código:

subroutine X()
if ~(A()) return false;
if ~(B()) { error(); return false; }
if ~(C()) { error(); return false; }
// insert semantic action here: generate code, do the work, ....
return true;
end X;

Del mismo modo para A, B, C.

Si un token es un terminal, escriba un código que verifique el flujo de entrada para la cadena de caracteres que compone el terminal. Por ejemplo, para un Número, verifique que la corriente de entrada contenga dígitos y avance el cursor de la corriente de entrada más allá de los dígitos. Esto es especialmente fácil si está analizando un búfer (para BASIC, tiende a obtener una línea a la vez) simplemente avanzando o sin avanzar un puntero de exploración de búfer. Este código es esencialmente la parte más lexer del analizador.

Si su regla BNF es recursiva ... no se preocupe. Simplemente codifique la llamada recursiva. Esto maneja reglas gramaticales como:

T = ''('' T '')'' ;

Esto se puede codificar como:

subroutine T()
if ~(left_paren()) return false;
if ~(T()) { error(); return false; }
if ~(right_paren()) { error(); return false; }
// insert semantic action here: generate code, do the work, ....
return true;
end T;

Si tiene una regla BNF con una alternativa:

 P = Q | R ;

luego codifica P con opciones alternativas:

subroutine P()
if ~(Q)
{if ~(R) return false;
return true;
}
return true;
end P;

A veces te encontrarás con reglas de formación de listas. Estos tienden a ser recursivos, y este caso se maneja fácilmente. Ejemplo:

L = A | L A ;

Puede codificar esto como:

subroutine L()
if ~(A()) then return false;
while (A()) do // loop
return true;
end L;

Puede codificar varios cientos de reglas de gramática en un día o dos de esta manera. Hay más detalles para completar, pero los conceptos básicos aquí deberían ser más que suficientes.

Si tiene poco espacio, puede construir una máquina virtual que implemente estas ideas. Eso es lo que hice en los años 70, cuando 8K palabras de 16 bits era lo que podías obtener.

Si no desea codificar esto a mano, puede automatizarlo con un metacompilador ( Meta II ) que produce esencialmente lo mismo. Se trata de una diversión técnica alucinante que realmente quita todo el trabajo de hacer esto, incluso para grandes gramáticas.

Agosto de 2014:

Recibo muchas solicitudes de "cómo construir un AST con un analizador sintáctico". Para detalles sobre esto, que esencialmente elabora esta respuesta, vea mi otra respuesta SO https://.com/a/25106688/120163

Julio de 2015:

Hay mucha gente que quiere escribir un evaluador de expresiones simple. Puedes hacer esto haciendo el mismo tipo de cosas que sugiere el enlace "AST Builder" arriba; simplemente haga aritmética en lugar de construir nodos de árbol. Aquí hay un evaluador de expresiones hecho de esta manera .