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

que es python y para que sirve (12)

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

¿Has leído Aho, Sethi, Ullman: "Compiladores: principios, técnicas y herramientas"? Es un libro de referencia de lenguaje clásico.

/Alano

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

El 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 de 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, los lenguajes sensibles al contexto son un poco más difíciles de imaginar en cualquier sentido preciso y, por lo tanto, son menos comunes. Incluso Ruby y Scala realmente no cuentan, 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 sensible al contexto, son muy estrictas para expresar tales conceptos fácilmente.

Es posible que desee leer este ensayo bastante bien escrito sobre el análisis de Python, Python: Mitos sobre la sangría .

Si bien no he intentado escribir un analizador sintáctico sin contexto que use 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, esta es la gramática oficial de python de python.org: http://www.python.org/doc/current/ref/grammar.txt

Le recomendaría que escriba su 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 hacia abajo escrito a mano, puede implementar prácticamente las reglas que quiera, donde quiera. 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. Puedes agregar un poco de no determinismo donde lo necesites con relativamente poco impacto en el resto del analizador,

Además, como usted mismo está diseñando el lenguaje, debe asumir que su diseño va a 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.

Diría que los generadores de analizadores son solo una buena opción si:

Nunca planeas escribir un IDE nunca,
El lenguaje tiene una sintaxis muy simple, o
Necesita un analizador extremadamente rápido y está de acuerdo con una mala experiencia del usuario

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

Primero me familiarizaría con el problema al leer algo de la literatura disponible sobre el tema. El clásico libro de compiladores de Aho et. Alabama. puede ser pesado en las matemáticas y comp, pero un texto mucho más accesible es el de Construyamos un compilador 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 un 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 el ensamblador 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 quiere seguir el ejemplo, al menos necesitará Turbo Pascal 5.5 y un ensamblador y emulador de 68K . El texto sigue siendo relevante hoy y usar 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.

Si nunca antes has escrito un analizador, comienza con algo simple. 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 a 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.

Usar sangrías en un idioma no significa necesariamente que la gramática del idioma 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 eso, 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 utilizando antlr ( http://www.pragprog.com/titles/tpantlr/the-definitive-antlr-reference ). Hay documentación bastante buena y muchas gramáticas de ejemplo.

Una gramática libre de 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, ¿T * x 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).

El espacio en blanco 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).

Si realmente vas a criticar el diseño e implementación del lenguaje, es posible que desees agregar lo siguiente a tu biblioteca:

Lenguaje de programación Pragmática, Scott et al.
Conceptos de diseño en lenguajes de programación, Turbak et al.
Diseño moderno del compilador, Grune et al. (Yo sacrílegamente prefiero esto a "El Libro del Dragón" por Aho et al.)

Presentaciones más suaves como:

El tutorial de Crenshaw (como lo sugiere @ ''Jonas Gorauskas'' aquí)
La referencia ANTLR definitiva de Parr
El reciente trabajo de Martin Fowler sobre DSL

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

"Sin contexto" 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, los siguientes dos programas C son válidos según la gramática libre de contexto de C, pero uno falla rápidamente durante la verificación de contexto:

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álida, pero en contexto puede 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.

Todo lo que se puede 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 lenguajes dependientes del espacio en blanco como Python hacen que su gramática libre de contexto sea menos útil y, por lo tanto, requieren una verificación más sensible al contexto 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.