parsing - programacion - parse tree

Construyendo un analizador(Parte I)

Question

Estoy creando mi propio lenguaje de programación basado en javascript (sí, es una locura, pero es solo para aprender ... ¿quizás? ). Bueno, estoy leyendo sobre analizadores y el primer paso es convertir el código fuente en tokens, como:

if(x > 5)
  return true;

Tokenizer para:

T_IF          "if"
T_LPAREN      "("
T_IDENTIFIER  "x"
T_GT          ">"
T_NUMBER      "5"
T_RPAREN      ")"
T_IDENTIFIER  "return"
T_TRUE        "true"
T_TERMINATOR  ";"

No sé si mi lógica es correcta para eso por un tiempo. En mi analizador es aún mejor ( o no? ) Y se traduce a él (sí, matriz multidimensional):

T_IF             "if"
  T_EXPRESSION     ...
    T_IDENTIFIER     "x"
    T_GT             ">"
    T_NUMBER         "5"
  T_CLOSURE        ...
    T_IDENTIFIER     "return"
    T_TRUE           "true"

Tengo algunas dudas:

1. ¿Es mi camino mejor o peor que el original ? Tenga en cuenta que mi código será leído y compilado (traducido a otro idioma, como PHP), en lugar de ser interpretado todo el tiempo.
2. Después de tokenizer, ¿qué necesito hacer exactamente? Estoy realmente perdido en este pase!
3. ¿Hay algún buen tutorial para aprender cómo puedo hacerlo?

Bueno, es eso. ¡Adiós!

Answer 1

¿Es mi camino mejor o peor que el original ? Tenga en cuenta que mi código se leerá y compilará (se traducirá a otro idioma, como PHP), en lugar de interpretarlo todo el tiempo.

¿Cuál es la forma original ? Hay muchas maneras diferentes de implementar idiomas. Creo que el tuyo está bien, en realidad, una vez intenté crear un lenguaje que tradujera a C #, el lenguaje de programación hack . Muchos compiladores de idiomas se traducen a un idioma intermedio, es bastante común.

Después de tokenizer, ¿qué necesito hacer exactamente? Estoy realmente perdido en este pase!

Después de tokenizing, necesitas analizarlo . Use un buen marco lexer / parser, como Boost.Spirit , o Coco, o lo que sea. Hay cientos de ellos. O puede implementar su propio lexer, pero eso requiere tiempo y recursos. Hay muchas formas de analizar el código, generalmente confío en el análisis de descenso recursivo .

A continuación tienes que hacer la generación de código. Esa es la parte más difícil en mi opinión. También hay herramientas para eso, pero puedes hacerlo manualmente si lo deseas. Traté de hacerlo en mi proyecto, pero fue bastante básico y con errores, hay algunos códigos útiles here y here .

¿Hay algún buen tutorial para aprender cómo puedo hacerlo?

Como sugerí anteriormente, use herramientas para hacerlo. Hay una gran cantidad de marcos analizadores bastante bien documentados. Para más información, puedes intentar preguntar a algunas personas que saben sobre esto. @DeadMG, en el Lounge C ++ está construyendo un lenguaje de programación llamado "Wide". Puedes intentar consultarle.

Answer 2

En general, desea separar las funciones del tokeniser (también denominado lexer ) de otras etapas de su compilador o intérprete. La razón de esto es la modularidad básica: cada paso consume un tipo de cosa (por ejemplo, personajes) y produce otra (por ejemplo, tokens).

Así que has convertido tus personajes en tokens. Ahora desea convertir su lista plana de tokens en expresiones anidadas significativas, y esto es lo que tradicionalmente se llama análisis . Para un lenguaje similar a JavaScript, debe buscar en el análisis de descenso recursivo . Para analizar expresiones con operadores de infijo de diferentes niveles de precedencia, el análisis de Pratt es muy útil, y puede recurrir al análisis de descenso recursivo ordinario para casos especiales.

Solo para darle un ejemplo más concreto basado en su caso, asumiré que puede escribir dos funciones: accept(token) y expect(token) , que prueban el siguiente token en la secuencia que ha creado. Realizarás una función para cada tipo de declaración o expresión en la gramática de tu idioma. Aquí está el pseudocódigo de Pythonish para una función de statement() , por ejemplo:

def statement():

  if accept("if"):
    x = expression()
    y = statement()
    return IfStatement(x, y)

  elif accept("return"):
    x = expression()
    return ReturnStatement(x)

  elif accept("{")
    xs = []
    while True:
      xs.append(statement())
      if not accept(";"):
        break
    expect("}")
    return Block(xs)

  else:
    error("Invalid statement!")

Esto le proporciona lo que se denomina un árbol de sintaxis abstracta (AST) de su programa, que luego puede manipular (optimización y análisis), salida (compilación) o ejecución (interpretación).

Answer 3

La mayoría de los kits de herramientas dividen el proceso completo en dos partes separadas

• lexer (aka. tokenizer)
• analizador (también conocido como gramática)

El tokenizador dividirá los datos de entrada en tokens. El analizador solo funcionará en el "flujo" del token y construirá la estructura.

Tu pregunta parece estar enfocada en el tokenizador. Pero su segunda solución combina el analizador gramatical y el tokenizador en un solo paso. En teoría, esto también es posible, pero para un principiante es mucho más fácil hacerlo de la misma manera que la mayoría de las otras herramientas / marco: mantener los pasos separados.

A tu primera solución: tokenizaría tu ejemplo así:

T_KEYWORD_IF   "if"
T_LPAREN       "("
T_IDENTIFIER   "x"
T_GT           ">"
T_LITARAL      "5"
T_RPAREN       ")"
T_KEYWORD_RET  "return"
T_KEYWORD_TRUE "true"
T_TERMINATOR   ";"

En la mayoría de los idiomas, las palabras clave no se pueden usar como nombres de métodos, nombres de variables, etc. Esto se refleja ya en el nivel del tokenizador ( T_KEYWORD_IF , T_KEYWORD_RET , T_KEYWORD_TRUE ).

El siguiente nivel tomaría esta corriente y, al aplicar una gramática formal, construiría una estructura de datos (a menudo llamada AST - Árbol de sintaxis abstracta) que podría tener este aspecto:

IfStatement:
    Expression:
        BinaryOperator:
            Operator:     T_GT
            LeftOperand: 
               IdentifierExpression:
                   "x"
            RightOperand:
                LiteralExpression
                    5
    IfBlock
        ReturnStatement
            ReturnExpression
                LiteralExpression
                    "true"
    ElseBlock (empty)

La implementación del analizador a mano generalmente se realiza mediante algunos marcos. La implementación de algo así a mano y de manera eficiente generalmente se realiza en una universidad en la mayor parte del semestre. Así que realmente deberías usar algún tipo de marco.

La entrada para un marco de análisis de gramática es generalmente una gramática formal en algún tipo de BNF . Tu parte "si" podría verse así:

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ;

Expression: LiteralExpression | BinaryExpression | IdentifierExpression | ... ;

BinaryExpression: LeftOperand BinaryOperator RightOperand;

....

Eso es solo para tener la idea. Analizar un lenguaje del mundo real como Javascript correctamente no es una tarea fácil. Pero gracioso.