Creando un analizador (Parte I)

Question

Estoy haciendo mi propio lenguaje de programación basado en JavaScript (sí, es una locura, pero es solo para aprender ... ¿quizás?). Bien, estoy leyendo acerca de los analizadores y el primer paso es convertir el código fuente de fichas, como:

if(x > 5) 
    return true; 

Tokenizer a:

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 por eso por un tiempo En mi programa de análisis es aún mejor (o no?) Y traducir a ella (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 manera mejor o peor que la forma original ? Tenga en cuenta que mi código será leído y compilado (traducido a otro idioma, como PHP), en lugar de 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

Generalmente, desea separar las funciones del tokeniser (también llamado lexer) de otras etapas de su compilador o intérprete. La razón de esto es la modularidad básica: cada pase consume un tipo de cosas (por ejemplo, caracteres) y produce otro (por ejemplo, tokens).

Has convertido tus personajes en tokens. Ahora quiere convertir su lista plana de tokens a expresiones anidadas significativas, y esto es lo que convencionalmente se llama , que analiza. Para un lenguaje parecido a JavaScript, debe consultar recursive descent parsing. Para analizar expresiones con operadores de infijo de diferentes niveles de precedencia, Pratt parsing es muy útil, y puede recurrir al análisis ordinario de descenso recursivo para casos especiales.

Solo para darle un ejemplo más concreto basado en su caso, supongo que puede escribir dos funciones: accept(token) y expect(token), que prueban el siguiente token en la transmisión que ha creado. Hará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 Pythonish para una función 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 da lo que se llama un árbol de sintaxis abstracta (AST) de su programa, que luego se puede manipular (optimización y análisis), salida (compilación), o correr (interpretación).

Answer 2

¿Es mi manera mejor o peor que el forma original? Tenga en cuenta que mi código será leído y compilado (traducido a otro idioma, como PHP), en lugar de interpretado todo el tiempo.

¿Cuál es la forma original de ? Hay muchas formas diferentes de implementar idiomas. Creo que el tuyo está bien, de hecho, una vez intenté construir un lenguaje que tradujera a C#, el hack programming language. Muchos compiladores de lenguaje traducen a un lenguaje intermedio, es bastante común.

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

Después de tokenizar, necesita analizar él. Utilice un buen marco lexer/analizador, como el 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 maneras de analizar el código, generalmente confío en recursive descent parsing.

Lo siguiente que debes hacer es 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 quieres, intenté hacerlo en mi proyecto, pero era 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 he sugerido anteriormente, utilice herramientas para hacerlo. Hay muchos marcos analizadores analíticos bien documentados.Para obtener más información, puede intentar preguntarle a algunas personas que conocen estas cosas. @DeadMG, en el Lounge C++ está construyendo un lenguaje de programación llamado "Ancho". Puede intentar consultarlo.

Answer 3

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

• lexer (aka. Tokenizer)
• analizador (aka. Gramática)

El tokenizer dividirá los datos de entrada en tokens. El analizador solo operará en la "secuencia" del token y construirá la estructura.

Tu pregunta parece estar centrada 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 de hacerlo de la misma manera que la mayoría de las otras herramientas/marco: mantenga los pasos separados.

Para su primera solución: Me tokenize su ejemplo como este:

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 palabras clave no se puede utilizar como nombres de métodos, nombres de variables y así sucesivamente. Esto se refleja ya en el nivel de tokenizador (T_KEYWORD_IF, T_KEYWORD_RET, T_KEYWORD_TRUE).

El siguiente nivel tomaría esta corriente y - mediante la aplicación de una gramática formal - construiría alguna estructura de datos (a menudo llamado AST - sintaxis abstracta del árbol), 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) 

Implementación del analizador con la mano generalmente lo hacen algunos marcos.La implementación de algo así a mano y de manera eficiente se hace generalmente en una universidad en la mayor parte de un semestre. Entonces deberías usar algún tipo de marco.

La entrada para un marco de gramática es generalmente una gramática formal en algún tipo de BNF. Su parte "if" puede verse así:

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ; 

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

BinaryExpression: LeftOperand BinaryOperator RightOperand; 

.... 

Eso solo para que se haga una idea. Analizar un lenguaje del mundo real como Javascript correctamente no es una tarea fácil. Pero divertido.