¿Cuál es un buen recurso para comenzar a escribir un lenguaje de programación, que no está libre de contexto?

Question

Estoy buscando escribir un lenguaje de programación para divertirme, sin embargo, la mayor parte del recurso que he visto es para escribir un lenguaje libre de contexto, sin embargo, deseo escribir un lenguaje que, como python, utilice sangría, lo que a mi entender significa no puede estar libre de contexto

Answer 1

No conozco ningún tutorial/guía, pero podría intentar buscar en la fuente tinypy, es una implementación muy pequeña de un lenguaje similar al de python.

Answer 2

Es posible que desee leer este ensayo bastante bien escrito sobre el análisis de Python, Python: Myths about Indentation.

Si bien no he intentado escribir un analizador sintáctico sin contexto usando algo como yacc, creo que es posible usar un lector condicional para devolver los tokens de cambio de sangría como se describe en la url.

Por cierto, aquí es la gramática oficial del pitón python.org: http://www.python.org/doc/current/ref/grammar.txt

Answer 3

El uso de la sangría en un idioma no significa necesariamente que la gramática de la lengua no puede estar libre de contexto. Es decir. la sangría determinará en qué alcance existe una declaración. Una declaración seguirá siendo una declaración sin importar en qué ámbito esté definida (el alcance a menudo puede ser manejado por una parte diferente del compilador/intérprete, generalmente durante un análisis semántico).

Dicho esto, un buen recurso es la herramienta antlr (http://www.antlr.org). El autor de la herramienta también ha producido un libro sobre la creación de analizadores para idiomas usando antlr (http://www.pragprog.com/titles/tpantlr/the-definitive-antlr-reference). Hay documentación bastante buena y muchas gramáticas de ejemplo.

Answer 4

El mero hecho de que un idioma utilice una sangría significativa no significa que sea intrínsecamente sensible al contexto. Como ejemplo, Haskell utiliza indentaciones significativas, y (que yo sepa) su gramática no tiene ningún contexto.

Un ejemplo de fuente que requiere una gramática sensible al contexto podría ser este fragmento del Ruby:

my_essay = << END_STR 
This is within the string 
END_STR 

<< self 
    def other_method 
    ... 
    end 
end 

Otro ejemplo sería el modo XML de Scala:

def doSomething() = { 
    val xml = <code>def val <tag/> class</code> 
    xml 
} 

Como regla general, al contexto los lenguajes sensibles son un poco más difíciles de imaginar en cualquier sentido preciso y, por lo tanto, son menos comunes. Incluso Ruby y Scala no cuentan realmente ya que sus características sensibles al contexto abarcan solo un subconjunto menor del idioma. Si yo fuera usted, formularía mi gramática según dicte la inspiración y luego me preocuparía analizar las metodologías en una fecha posterior. Creo que descubrirás que lo que sea que encuentres será naturalmente libre de contexto o muy cercano.

Como nota final, si realmente necesita herramientas de análisis sensibles al contexto, puede probar algunas de las técnicas menos rígidamente formales. Los combinadores de analizadores se utilizan en el análisis sintáctico de Scala. Tienen algunas limitaciones molestas (no lexing), pero no son una mala herramienta. Las herramientas LL (*) como ANTLR también parecen ser más hábiles para expresar escapes de análisis "ad hoc". No intente utilizar Yacc o Bison con una gramática contextual, son muy estrictos para expresar tales conceptos fácilmente.

Answer 5

Yo recomendaría que escribas tu analizador a mano, en cuyo caso tener espacios en blanco significativos no debería presentar ningún problema real.

El principal problema con el uso de un generador de analizador es que es difícil obtener una buena recuperación de errores en el analizador. Si planea implementar un IDE para su idioma, entonces tener una buena recuperación de errores es importante para lograr que cosas como Intellisence funcionen. Intellisence siempre trabaja en constructos sintácticos incompletos, y cuanto mejor sea el analizador para descifrar qué construcción está intentando escribir el usuario, mejor será la experiencia de inteligencia que pueda ofrecer.

Si escribe un analizador de arriba a abajo escrito a mano, puede implementar prácticamente las reglas que desee, donde quiera que desee. Esto es lo que facilita la recuperación de errores. También hará que sea trivial para usted implementar espacios en blanco significativos. Simplemente puede almacenar cuál es el nivel de sangría actual en una variable dentro de su clase de analizador, y puede detener el análisis de bloques cuando encuentra un token en una nueva línea que tiene una posición de columna que es menor que el nivel de sangría actual. Además, es probable que te encuentres con ambigüedades en tu gramática. La mayoría de los lenguajes de "producción" de amplio uso tienen ambigüedades sintácticas. Un buen ejemplo son los genéricos en C# (hay ambigüedades en torno a "<" en un contexto de expresión, puede ser un operador "menor que" o el comienzo de una "lista de argumentos genérica"). En un analizador manuscrito, resolver ambigüedades como esa es trivial. Puede agregar un poco de no determinismo donde lo necesite con un impacto relativamente pequeño en el resto del analizador,

Además, como usted mismo está diseñando el lenguaje, debe suponer que su diseño evolucionará rápidamente. (para algunos idiomas con comités de estándares, como C++, este no es el caso). Realizar cambios en analizadores generados automáticamente para manejar ambigüedades o desarrollar el lenguaje puede requerir una refacturación significativa de la gramática, que puede ser irritante y lenta. Los cambios en los analizadores escritos a mano, particularmente para los analizadores descendentes, suelen estar bastante localizados.

Yo diría que los generadores de analizadores sintácticos sólo son una buena opción si:

1. Nunca se piensa en la escritura de un IDE nunca,
2. El lenguaje tiene realmente sintaxis simple, o
3. Necesita un analizador extremadamente rápido y está de acuerdo con una mala experiencia de usuario

Answer 6

¿Tiene usted d Aho, Sethi, Ullman: "Compiladores: principios, técnicas y herramientas"? Es un libro de referencia de lenguaje clásico.

/Allan

Answer 7

Si usted nunca ha escrito un programa de análisis antes, empezar con algo sencillo. Los analizadores son sorprendentemente sutiles, y usted puede meterse en todo tipo de problemas para escribirlos si nunca ha estudiado la estructura de los lenguajes de programación.

Leer Aho, Sethi y Ullman (es conocido como "El libro del dragón") es un buen plan. A diferencia de otros colaboradores, digo que primero deberías jugar con generadores de analizadores simples como Yacc y Bison, y solo cuando te quemes porque no puedes hacer algo con esa herramienta deberías intentar construir algo con un LL (*) analizador como Antlr.

Answer 8

¿Un lenguaje sensible al contexto? Éste no tiene sangría: Protium (http://www.protiumble.com)

Answer 9

Me gustaría familiarizarme con el problema primero leyendo algo de la literatura disponible sobre el tema. El clásico Compiladores libro de Aho et. Alabama.puede ser pesado en las matemáticas y comp, pero un texto mucho más accesible son los artículos Let's Build a Compiler de Jack Crenshaw. Esta es una serie de artículos que el Sr. Crenshaw escribió a finales de los 80 y es el texto menos apreciado sobre los compiladores jamás escritos. El enfoque es simple y al grano: el Sr. Crenshaw muestra el enfoque "A" que funciona. Puede revisar fácilmente el contenido en el transcurso de unas pocas noches y comprender mucho mejor de qué se trata el compilador. Un par de advertencias son que los ejemplos en el texto están escritos en Turbo Pascal y los compiladores emiten un ensamblador de 68K. Los ejemplos son lo suficientemente fáciles de exportar a un lenguaje de programación más actual y recomiendo Python para eso. Pero si desea seguir a lo largo de los ejemplos que se presentan, al menos necesitará Turbo Pascal 5.5 y a 68K assembler and emulator. El texto sigue siendo relevante hoy y el uso de estas tecnologías antiguas es realmente divertido. Lo recomiendo como primer texto de compiladores. La gran noticia es que los lenguajes como Python y Ruby son de código abierto y puede descargar y estudiar el código fuente C para comprender mejor cómo se hace.

Answer 10

Una gramática sin contexto es, simplemente, una que no requiere una tabla de símbolos para analizar correctamente el código. Una gramática sensible al contexto sí.

El lenguaje de programación D es un ejemplo de gramática libre de contexto. C++ es sensible al contexto. (Por ejemplo, ¿es T * x que declara que x es un puntero a T, o está multiplicando T por x? Solo podemos ver buscando T en la tabla de símbolos para ver si es un tipo o una variable.)

Whitespace no tiene nada que ver con eso.

D usa una gramática libre de contexto para simplificar enormemente el análisis, y para que las herramientas simples puedan analizarlo (como los editores de resaltado de sintaxis).

Answer 11

Si usted está realmente va a tomar un golpe en el diseño y la implementación del lenguaje, es posible que desee añadir lo siguiente a su biblioteca:

• Lenguaje de programación pragmática, Scott et al.
• Conceptos de diseño en lenguajes de programación, Turbak et al.
• Modern Compiler Design, Grune et al. (I sacrílega prefiero esto a "El Dragón libro" escrito por Aho et al.)

Gentler introducciones tales como:

• el tutorial de Crenshaw (como se sugiere por @ 'Jonas Gorauskas' aquí)
• el antlr definitivo de referencia por el trabajo reciente Parr
• Martin Fowler en DSL

también debe considerar su lenguaje de implementación. Esta es una de esas áreas donde los diferentes idiomas ampliamente difieren en lo que facilitan. Debería considerar idiomas como LISP, F #/OCaml y el nuevo idioma de Newspeak, Gilad Bracha.

Answer 12

"Context-free" es un término relativo. La mayoría de los analizadores sin contexto realmente analizan un superconjunto del lenguaje que no tiene contexto y luego verifican el árbol de análisis resultante para ver si es válido.Por ejemplo, las siguientes dos programas en C son válidas según la gramática independiente del contexto de C, pero una falla rápidamente durante contexto de comprobación:

int main() 
{ 
    int i; 
    i = 1; 
    return 0; 
} 

int main() 
{ 
    int i; 
    i = "Hello, world"; 
    return 0; 
} 

libre de contexto, i = "Hello, world"; es una tarea perfectamente válido, pero en el contexto puedes ver que los tipos son todos incorrectos. Si el contexto fuera char* i;, estaría bien. Por lo tanto, el analizador sin contexto no verá nada incorrecto con esa tarea. No es hasta que el compilador comience a verificar los tipos (que dependen del contexto) que detectará el error.

Cualquier cosa que se pueda producir con un teclado se puede analizar como libre de contexto; como mínimo, puede verificar que todos los caracteres utilizados sean válidos (el conjunto de todas las cadenas que contienen solo caracteres Unicode visualizables es una gramática libre de contexto). La única limitación es qué tan útil es tu gramática y cuánto controles contextuales debes hacer en el árbol de análisis resultante.

Los idiomas dependientes del espacio como Python hacen que su gramática sin contexto sea menos útil y por lo tanto requieren más verificación contextual más adelante (mucho de esto se hace en tiempo de ejecución en Python mediante tipado dinámico). Pero aún hay muchas cosas que un analizador sin contexto puede hacer antes de que se necesite una verificación contextual.