Hola Le presento una traducción amateur de una guía para implementar su lenguaje de programación JavaScript: PL Tutorial .

Del traductor

Crearemos nuestro propio lenguaje de programación - lenguaje λ (en el idioma original - λ). En el proceso de creación, utilizaremos muchas técnicas interesantes, como el descenso recursivo, el estilo de transferencia de control y las técnicas básicas de optimización. Se crearán dos versiones del intérprete: los intérpretes regulares y los de CPS, el transcompilador en JavaScript.

El autor del original es Mihai Bazon , autor de la famosa biblioteca UglifyJS (una herramienta para minimizar y formatear el código JS).

Entrada

Si alguna vez ha escrito su compilador o intérprete, entonces no habrá nada nuevo para usted. Pero si usa expresiones regulares para analizar algo que se parece a un lenguaje de programación, lea la sección sobre análisis . ¡Escribamos código con menos errores!

El artículo está dividido en partes en el orden "de simple a complejo". No recomiendo que omita partes del artículo, a menos que comprenda bien el tema. Siempre puedes regresar si no entiendes algo.

¿Qué vamos a aprender?

• Qué es un analizador sintáctico y cómo escribirlo.
• Cómo escribir un intérprete.
• La secuela de la transferencia y por qué es importante.
• Escribir un compilador (trans).
• Estilo de transferencia de continuación.
• Algunas técnicas básicas de optimización de código.
• Ejemplos de novedades en nuestro lenguaje λ en comparación con JavaScript.

Junto con esto, mostraré por qué Lisp es un gran lenguaje de programación. Sin embargo, el lenguaje en el que estamos trabajando no es Lisp. Tiene una sintaxis más rica (una notación infija clásica que todos conocen), algo así como Scheme (excepto las macros). Bueno o no, pero las macros son la característica principal de Lisp, algo que otros lenguajes (excepto los dialectos de Lisp) no pueden hacer tan bien como lo hacen. (Sí, sé sobre SweetJS ... cerca, pero no eso).

Pero primero, presentemos nuestro lenguaje de programación.

idioma λ

Antes de hacer algo, debemos tener una idea clara de lo que queremos hacer. Sería bueno escribir una descripción de la gramática del lenguaje, pero lo haré más fácil: escriba un ejemplo de un programa simple, así que aquí hay algunos ejemplos del lenguaje λ:

#   println("Hello World!"); println(2 + 3 * 4); #       `lambda`  `λ` fib = lambda (n) if n < 2 then n else fib(n - 1) + fib(n - 2); println(fib(15)); print-range = λ(a, b) # `λ`     ,   `lambda` if a <= b then { # `then`  ,      print(a); if a + 1 <= b { print(", "); print-range(a + 1, b); } else println(""); #   }; print-range(1, 5); 

Conclusión

 Hello World! 14 610 1, 2, 3, 4, 5 

El lenguaje se parece a JavaScript, pero en general no lo es. En primer lugar, no hay declaraciones, solo expresiones. Una expresión debe devolver un valor y puede usarse en cualquier lugar de otra expresión. Se necesitan punto y coma para separar las expresiones en una "secuencia" de expresiones. Las llaves { y } crean una secuencia que es en sí misma una expresión, y su valor es el último valor de la secuencia. El siguiente programa es correcto:

 a = { fib(10); #    ,      fib(15) #        }; print(a); #  610 

Las funciones se crean usando las palabras clave lambda o λ . Después de eso, entre paréntesis hay una lista (posiblemente vacía) de nombres de argumentos, separados por comas. El cuerpo de una función es una expresión, pero se puede encerrar en una secuencia {...} . También vale la pena señalar que no hay una palabra clave de return . La función devuelve el valor de la última expresión.

Además, no var . Para agregar una variable, puede usar lo que los programadores de JavaScript llaman IIFE . Use lambda , declare variables como argumentos. Para las variables, el alcance es una función, y las funciones son cierres, como en JavaScript [aprox. traducción: hasta ES6.].

Incluso if es una expresión. JavaScript utiliza el operador ternario para hacer esto:

 a = foo() ? bar() : baz(); // JavaScript a = if foo() then bar() else baz(); # λ 

La palabra clave then es opcional si la rama es una secuencia ( {...} ), como puede ver arriba. En otro caso, es necesario. else usa si hay una rama alternativa presente. Y nuevamente, then y de lo else tome la expresión como el cuerpo, pero puede combinar varias expresiones en una usando {...} . Si else y la condición es false , entonces el resultado de todo if es false . Vale la pena señalar que false es una palabra clave que representa un valor que es el único valor falso en un idioma λ:

 if foo() then print("OK"); 

generará OK si y solo si el resultado de foo() no foo() false . Además, existe la palabra clave true , pero absolutamente todo lo que no sea false (en JavaScript, el operador === ) se considerará true en las ramas (incluido el número 0 y la cadena vacía "" ).

Tenga en cuenta que no hay necesidad de paréntesis alrededor de la expresión en if . Si los agrega, no será un error, porque ( comienza la expresión, pero son superfluos.

El programa completo se puede analizar incluso si está rodeado de paréntesis, por lo que debe agregar ; después de cada expresión La última expresión es una excepción.

Genial, este es nuestro pequeño lenguaje λ. El no es perfecto. La sintaxis se ve hermosa, pero tiene fallas. Faltan muchas características, como objetos y matrices. No les prestamos atención, ya que no son básicos para nuestro lenguaje de programación.

A continuación, escribiremos un analizador para nuestro idioma.

Conversión de código a AST

Crear un analizador es una tarea difícil. En esencia, debe tomar un fragmento de código y convertirlo en un AST (árbol de sintaxis abstracta). AST es una representación estructurada de un programa en memoria, abstracta porque no contiene información completa sobre el código, solo semántica. Descripción AST está en una parte separada.

Por ejemplo, tenemos el siguiente código:

 sum = lambda(a, b) { a + b; }; print(sum(1, 2)); 

Nuestro analizador generará un árbol como un objeto JavaScript:

 { type: "prog", prog: [ //  : { type: "assign", operator: "=", left: { type: "var", value: "sum" }, right: { type: "lambda", vars: [ "a", "b" ], body: { //     "prog",  ,  //     ,  //     . type: "binary", operator: "+", left: { type: "var", value: "a" }, right: { type: "var", value: "b" } } } }, //  : { type: "call", func: { type: "var", value: "print" }, args: [{ type: "call", func: { type: "var", value: "sum" }, args: [ { type: "num", value: 1 }, { type: "num", value: 2 } ] }] } ] } 

La principal dificultad para crear un analizador es la dificultad de organizar correctamente el código. El analizador debería funcionar a un nivel más alto que leer caracteres de una cadena. Algunas pautas para reducir la complejidad del código:

• Escribe muchas características pequeñas. En cada función, haz una cosa y hazlo bien.
• No intente utilizar expresiones regulares para analizar. Simplemente no funcionan. Pueden ser útiles en el analizador léxico , pero, por simplicidad, no los utilizaremos.
• No trates de adivinar. Cuando no esté seguro de cómo analizar algo, inicie una excepción que contenga la ubicación del error (fila y columna).

Para mantener el código más simple, lo dividiremos en tres partes, que a su vez se dividen en muchas funciones pequeñas:

• Secuencia de personajes
• Flujo de tokens (tokens)
• Analizador

Secuencia de personajes

Esta es la parte más fácil. Crearemos un objeto continuo que representará las operaciones de lectura secuencial de caracteres de una cadena. Contiene cuatro funciones:

• peek() : devuelve el siguiente carácter sin extraerlo de la secuencia.
• next() : devuelve el siguiente carácter, extrayéndolo de la secuencia.
• eof() : devuelve true si no hay más caracteres en la secuencia.
• croak(msg) : arroja una excepción que contiene el mensaje ( msg ) y la posición actual en la secuencia.

La última función es necesaria para que pueda simplemente lanzar una excepción que contenga la ubicación del error.

Aquí está el código completo para este objeto (llamémoslo InputStream ). Es lo suficientemente pequeño como para que no tenga problemas con él:

 function InputStream(input) { var pos = 0, line = 1, col = 0; return { next : next, peek : peek, eof : eof, croak : croak, }; function next() { var ch = input.charAt(pos++); if (ch == "\n") line++, col = 0; else col++; return ch; } function peek() { return input.charAt(pos); } function eof() { return peek() == ""; } function croak(msg) { throw new Error(msg + " (" + line + ":" + col + ")"); } } 

Tenga en cuenta que este no es un objeto ordinario (que se crea a través de new ). Para obtener este objeto, necesita: var stream = InputStream(string) .

A continuación, escribiremos el siguiente nivel de abstracción: flujo de tokens (tokens) .

Flujo de tokens (tokens)

El tokenizer (lexer) usa una secuencia de caracteres y devuelve un objeto con la misma interfaz, pero los valores de retorno de las funciones peek() / next() serán tokens. Un token es un tipo con dos propiedades: type , value . Aquí hay algunos ejemplos de tokens:

 { type: "punc", value: "(" } // . : , ,     . . { type: "num", value: 5 } //  { type: "str", value: "Hello World!" } //  { type: "kw", value: "lambda" } //   { type: "var", value: "a" } //  { type: "op", value: "!=" } //  

Los espacios en blanco (espacio, tabulación, saltos de línea) y los comentarios simplemente se omiten.

Para escribir un tokenizador, debemos analizar más de cerca nuestro idioma. La idea es notar que dependiendo del carácter actual ( input.peek() ) podemos decidir qué token leer:

• Primero, omita los espacios en blanco.
• Si input.eof() , devuelve null .
• Si es un carácter # , salte todos los caracteres al final de la línea (y devuelva el siguiente token).
• Si esto es una comilla, entonces lea la cadena.
• Si este es un número, entonces lea el número.
• Si es una letra, leemos la palabra y devolvemos el identificador o la palabra clave.
• Si este es uno de los caracteres especiales, devuelve el token correspondiente.
• Si este es uno de los símbolos del operador, devuelva el token correspondiente.
• Si nada de lo anterior aplica, entonces lanza una excepción usando input.croak() .

Tendremos la función read_next , la función principal del tokenizer:

 function read_next() { read_while(is_whitespace); if (input.eof()) return null; var ch = input.peek(); if (ch == "#") { skip_comment(); return read_next(); } if (ch == '"') return read_string(); if (is_digit(ch)) return read_number(); if (is_id_start(ch)) return read_ident(); if (is_punc(ch)) return { type : "punc", value : input.next() }; if (is_op_char(ch)) return { type : "op", value : read_while(is_op_char) }; input.croak("Can't handle character: " + ch); } 

Aquí puede ver muchas funciones adicionales que devuelven diferentes tipos de tokens, como read_string() , read_number() , etc. ... Se colocan en funciones separadas, para que el código se vea más simple y hermoso.

Además, es interesante que no eliminemos todos los símbolos a la vez: cada vez que el analizador solicite el próximo token, leeremos un token. Si ocurre algún tipo de error, ni siquiera leeremos todos los caracteres.

read_ident() leerá todos los caracteres de una fila que pueden ser parte del identificador ( is_id() ). El identificador debe comenzar con la letra, λ o _ , y puede contener los mismos caracteres, números o cualquiera de: ?!-<>= . De ello se deduce que foo-bar no se leerá como tres tokens, sino como uno (token var ). ¿Es esto necesario para poder definir funciones con nombres como is-pair? o string>= (lo siento, este es Lisper en mí).

Además, read_ident() verificará si hay un identificador en la lista de palabras clave conocidas, y si está allí, se devolverá un kw -token en lugar de un var -token.

Creo que el código habla por sí mismo, así que aquí hay un tokenizer listo para nuestro idioma:

 function TokenStream(input) { var current = null; var keywords = " if then else lambda λ true false "; return { next : next, peek : peek, eof : eof, croak : input.croak }; function is_keyword(x) { return keywords.indexOf(" " + x + " ") >= 0; } function is_digit(ch) { return /[0-9]/i.test(ch); } function is_id_start(ch) { return /[a-zλ_]/i.test(ch); } function is_id(ch) { return is_id_start(ch) || "?!-<>=0123456789".indexOf(ch) >= 0; } function is_op_char(ch) { return "+-*/%=&|<>!".indexOf(ch) >= 0; } function is_punc(ch) { return ",;(){}[]".indexOf(ch) >= 0; } function is_whitespace(ch) { return " \t\n".indexOf(ch) >= 0; } function read_while(predicate) { var str = ""; while (!input.eof() && predicate(input.peek())) str += input.next(); return str; } function read_number() { var has_dot = false; var number = read_while(function(ch){ if (ch == ".") { if (has_dot) return false; has_dot = true; return true; } return is_digit(ch); }); return { type: "num", value: parseFloat(number) }; } function read_ident() { var id = read_while(is_id); return { type : is_keyword(id) ? "kw" : "var", value : id }; } function read_escaped(end) { var escaped = false, str = ""; input.next(); while (!input.eof()) { var ch = input.next(); if (escaped) { str += ch; escaped = false; } else if (ch == "\\") { escaped = true; } else if (ch == end) { break; } else { str += ch; } } return str; } function read_string() { return { type: "str", value: read_escaped('"') }; } function skip_comment() { read_while(function(ch){ return ch != "\n" }); input.next(); } function read_next() { read_while(is_whitespace); if (input.eof()) return null; var ch = input.peek(); if (ch == "#") { skip_comment(); return read_next(); } if (ch == '"') return read_string(); if (is_digit(ch)) return read_number(); if (is_id_start(ch)) return read_ident(); if (is_punc(ch)) return { type : "punc", value : input.next() }; if (is_op_char(ch)) return { type : "op", value : read_while(is_op_char) }; input.croak("Can't handle character: " + ch); } function peek() { return current || (current = read_next()); } function next() { var tok = current; current = null; return tok || read_next(); } function eof() { return peek() == null; } } 

• La función next() no siempre llama a read_next() , porque puede haber un token que se haya leído antes (usando la función peek() ). Para esto, tenemos una variable current que contiene el token actual.
• Solo se admiten números decimales en notación regular (1E5, 0x, etc. no son compatibles). Pero si quisiéramos agregar su soporte, solo cambiaríamos read_number() .
• A diferencia de JavaScript, los únicos caracteres que no se pueden escapar de una cadena son las comillas y la barra invertida. Las líneas pueden contener saltos de línea, pestañas y cualquier otra cosa. No interpretamos combinaciones estándar como \n , \t , etc. ... Es muy fácil rehacer ( read_string() ).

Ahora tenemos herramientas poderosas para escribir fácilmente un analizador , pero primero recomendaría mirar la descripción de AST .

Descripción AST

Como se indicó anteriormente, el analizador creará una estructura que muestra la semántica del programa. AST consta de nodos. Cada nodo es un objeto JavaScript normal que tiene una propiedad de type que determina el tipo de nodo, así como información adicional que depende del tipo.

 123.5 

 { type: "num", value: 123.5 } 

 "Hello World" 

 { type: "str", value: "Hello World!" } 

 true false 

 { type: "bool", value: true } { type: "bool", value: false } 

 foo 

 { type: "var", value: "foo" } 

 lambda (x) 10 #  λ (x) 10 

 { type: "lambda", vars: [ "x" ], body: { type: "num", value: 10 } } 

 foo(a, 1) 

 { "type": "call", "func": { "type": "var", "value": "foo" }, "args": [ { "type": "var", "value": "a" }, { "type": "num", "value": 1 } ] } 

 if foo then bar else baz 

 { "type": "if", "cond": { "type": "var", "value": "foo" }, "then": { "type": "var", "value": "bar" }, "else": { "type": "var", "value": "baz" } } 

 if foo then bar 

 { "type": "if", "cond": { "type": "var", "value": "foo" }, "then": { "type": "var", "value": "bar" } } 

 a = 10 

 { "type": "assign", "operator": "=", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 10 } } 

 x + y * z 

 { "type": "binary", "operator": "+", "left": { "type": "var", "value": "x" }, "right": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "y" }, "right": { "type": "var", "value": "z" } } } 

 { a = 5; b = a * 2; a + b; } 

 { "type": "prog", "prog": [ { "type": "assign", "operator": "=", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 5 } }, { "type": "assign", "operator": "=", "left": { "type": "var", "value": "b" }, "right": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 2 } } }, { "type": "binary", "operator": "+", "left": { "type": "var", "value": "a" }, "right": { "type": "var", "value": "b" } } ] } 

 let (a = 10, b = a * 10) { a + b; } 

 { "type": "let", "vars": [ { "name": "a", "def": { "type": "num", "value": 10 } }, { "name": "b", "def": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 10 } } } ], "body": { "type": "binary", "operator": "+", "left": { "type": "var", "value": "a" }, "right": { "type": "var", "value": "b" } } } 

Analizador

El analizador construirá el árbol descrito anteriormente.

Gracias al trabajo que hicimos en el tokenizer, el analizador funciona con una secuencia de tokens, en lugar de una secuencia de caracteres. Todavía hay muchas características adicionales aquí para simplificar la estructura. Hablaremos de los principales. Comencemos con una función de analizador de alto nivel:

 function parse_lambda() { return { type: "lambda", vars: delimited("(", ")", ",", parse_varname), body: parse_expression() }; } 

Esta función se llamará cuando la palabra clave lambda ya se haya tomado de la secuencia de tokens, por lo que solo tenemos que tomar los nombres de los argumentos. Pero dado que están entre paréntesis y separados por comas, haremos esto usando la función delimited , que toma los siguientes argumentos: start , stop , separator , la función del parser , que analiza cada elemento por separado. En este caso, usamos la función parse_varname , que arroja un error si nota algo que no parece una variable. El cuerpo de la función es una expresión, por lo que lo parse_expression con parse_expression .

La función delimited es el nivel inferior:

 function delimited(start, stop, separator, parser) { var a = [], first = true; skip_punc(start); while (!input.eof()) { if (is_punc(stop)) break; if (first) first = false; else skip_punc(separator); if (is_punc(stop)) break; //      a.push(parser()); } skip_punc(stop); return a; } 

Como puede ver, utiliza aún más funciones: is_punc y skip_punc . El primero devuelve true si el token actual es el signo de puntuación dado (sin extraerlo), mientras que skip_punc verificará si el token actual es el carácter de puntuación dado y lo extraerá (o lanzará una excepción de lo contrario).

La función que analiza todo el programa parece ser la más simple:

 function parse_toplevel() { var prog = []; while (!input.eof()) { prog.push(parse_expression()); if (!input.eof()) skip_punc(";"); } return { type: "prog", prog: prog }; } 

Como solo tenemos expresiones, simplemente llamamos a parse_expression() y leemos las expresiones hasta que leemos todo. Usando skip_punc(";") , lo hacemos ; obligatorio después de cada expresión.

Otro ejemplo simple es parse_if() :

 function parse_if() { skip_kw("if"); var cond = parse_expression(); if (!is_punc("{")) skip_kw("then"); var then = parse_expression(); var ret = { type: "if", cond: cond, then: then }; if (is_kw("else")) { input.next(); ret.else = parse_expression(); } return ret; } 

Ella omite la palabra clave if (lanza una excepción si el token actual no es la palabra clave if ), lee la condición usando parse_expression() . Si el símbolo { no va más allá, entonces se requiere la palabra clave (la sintaxis no se ve muy bien sin ella). Las ramas son solo expresiones, por lo que solo usamos parse_expression() nuevamente para ellas. La rama else es opcional, por lo que primero verificamos la presencia de la palabra clave antes de analizarla.

Con muchas funciones pequeñas, podemos simplificar el código. Escribimos el analizador casi como lo haría si usáramos un lenguaje de alto nivel específicamente para analizar la sintaxis. Todas estas funciones son "recursivas mutuamente", es decir, tenemos parse_atom() , que, dependiendo del token actual, llama a otras funciones. Uno de ellos es parse_if() (llamado cuando el token actual es if ) y a su vez llama a parse_expression() . Pero parse_expression() llama a parse_atom() . No hay recursión infinita porque una de las funciones siempre extrae al menos un token.

Este tipo de método de análisis se llama Método de descenso recursivo y, de hecho, es el más fácil de escribir.

Nivel inferior: parse_atom() y parse_expression()

La función parse_atom() llama a otra función, dependiendo del token actual:

 function parse_atom() { return maybe_call(function(){ if (is_punc("(")) { input.next(); var exp = parse_expression(); skip_punc(")"); return exp; } if (is_punc("{")) return parse_prog(); if (is_kw("if")) return parse_if(); if (is_kw("true") || is_kw("false")) return parse_bool(); if (is_kw("lambda") || is_kw("λ")) { input.next(); return parse_lambda(); } var tok = input.next(); if (tok.type == "var" || tok.type == "num" || tok.type == "str") return tok; unexpected(); }); } 

Cuando ve el paréntesis de apertura, la expresión entre paréntesis debe ir, por lo tanto, omitiendo el paréntesis, la función llama a parse_expression() y espera omitir el paréntesis de cierre después de eso. Si ve algún tipo de palabra clave, llama a la función correspondiente. Si ve una constante o identificador, lo devuelve como está. Y si no aparece nada, llama unexpected() , lo que arroja una excepción.

Cuando ve { , llama a parse_prog para analizar la secuencia de expresiones. Además, parse_prog realiza una optimización simple: si no hay expresiones entre { y } , devuelve false , si solo hay una expresión, solo la devuelve. De lo contrario, se devuelve el nodo prog con una matriz de expresiones.

 //     FALSE   , //     . var FALSE = { type: "bool", value: false }; function parse_prog() { var prog = delimited("{", "}", ";", parse_expression); if (prog.length == 0) return FALSE; if (prog.length == 1) return prog[0]; return { type: "prog", prog: prog }; } 

Y aquí está la función parse_expression() . A diferencia de parse_atom() , analizará tantas expresiones como sea posible usando maybe_binary() :

 function parse_expression() { return maybe_call(function(){ return maybe_binary(parse_atom(), 0); }); } 

Funciones maybe_*

Estas funciones comprueban lo que viene después de la expresión y deciden si ajustar la expresión en su nodo o devolverla como está.

La función maybe_call() es muy simple: obtiene una función que analiza la expresión actual, y si encuentra ( después de la expresión, se envuelve en una call . Observe cómo delimited() es adecuado para analizar una lista de argumentos:

 function maybe_call(expr) { expr = expr(); return is_punc("(") ? parse_call(expr) : expr; } function parse_call(func) { return { type: "call", func: func, args: delimited("(", ")", ",", parse_expression) }; } 

Prioridad del operador

La función maybe_binary(left, my_prec) se usa para combinar expresiones como 1 + 2 * 3 . , , , :

 var PRECEDENCE = { "=": 1, "||": 2, "&&": 3, "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7, "+": 10, "-": 10, "*": 20, "/": 20, "%": 20, }; 

, * "", + , , 1 + 2 * 3 (1 + (2 * 3)) ((1 + 2) * 3) .

, ( read_atom ) maybe_binary() ( ), ( my_prec ). maybe_binary , . , , .

, , , binary , , , (*):

 function maybe_binary(left, my_prec) { var tok = is_op(); if (tok) { var his_prec = PRECEDENCE[tok.value]; if (his_prec > my_prec) { input.next(); var right = maybe_binary(parse_atom(), his_prec) // (*); var binary = { type : tok.value == "=" ? "assign" : "binary", operator : tok.value, left : left, right : right }; return maybe_binary(binary, my_prec); } } return left; } 

, , , maybe_binary , ( my_prec ), , , . - , (, ), .

, , my_prec 0, binary ( assign = ).

, .

 var FALSE = { type: "bool", value: false }; function parse(input) { var PRECEDENCE = { "=": 1, "||": 2, "&&": 3, "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7, "+": 10, "-": 10, "*": 20, "/": 20, "%": 20, }; return parse_toplevel(); function is_punc(ch) { var tok = input.peek(); return tok && tok.type == "punc" && (!ch || tok.value == ch) && tok; } function is_kw(kw) { var tok = input.peek(); return tok && tok.type == "kw" && (!kw || tok.value == kw) && tok; } function is_op(op) { var tok = input.peek(); return tok && tok.type == "op" && (!op || tok.value == op) && tok; } function skip_punc(ch) { if (is_punc(ch)) input.next(); else input.croak("Expecting punctuation: \"" + ch + "\""); } function skip_kw(kw) { if (is_kw(kw)) input.next(); else input.croak("Expecting keyword: \"" + kw + "\""); } function skip_op(op) { if (is_op(op)) input.next(); else input.croak("Expecting operator: \"" + op + "\""); } function unexpected() { input.croak("Unexpected token: " + JSON.stringify(input.peek())); } function maybe_binary(left, my_prec) { var tok = is_op(); if (tok) { var his_prec = PRECEDENCE[tok.value]; if (his_prec > my_prec) { input.next(); return maybe_binary({ type : tok.value == "=" ? "assign" : "binary", operator : tok.value, left : left, right : maybe_binary(parse_atom(), his_prec) }, my_prec); } } return left; } function delimited(start, stop, separator, parser) { var a = [], first = true; skip_punc(start); while (!input.eof()) { if (is_punc(stop)) break; if (first) first = false; else skip_punc(separator); if (is_punc(stop)) break; a.push(parser()); } skip_punc(stop); return a; } function parse_call(func) { return { type: "call", func: func, args: delimited("(", ")", ",", parse_expression), }; } function parse_varname() { var name = input.next(); if (name.type != "var") input.croak("Expecting variable name"); return name.value; } function parse_if() { skip_kw("if"); var cond = parse_expression(); if (!is_punc("{")) skip_kw("then"); var then = parse_expression(); var ret = { type: "if", cond: cond, then: then, }; if (is_kw("else")) { input.next(); ret.else = parse_expression(); } return ret; } function parse_lambda() { return { type: "lambda", vars: delimited("(", ")", ",", parse_varname), body: parse_expression() }; } function parse_bool() { return { type : "bool", value : input.next().value == "true" }; } function maybe_call(expr) { expr = expr(); return is_punc("(") ? parse_call(expr) : expr; } function parse_atom() { return maybe_call(function(){ if (is_punc("(")) { input.next(); var exp = parse_expression(); skip_punc(")"); return exp; } if (is_punc("{")) return parse_prog(); if (is_kw("if")) return parse_if(); if (is_kw("true") || is_kw("false")) return parse_bool(); if (is_kw("lambda") || is_kw("λ")) { input.next(); return parse_lambda(); } var tok = input.next(); if (tok.type == "var" || tok.type == "num" || tok.type == "str") return tok; unexpected(); }); } function parse_toplevel() { var prog = []; while (!input.eof()) { prog.push(parse_expression()); if (!input.eof()) skip_punc(";"); } return { type: "prog", prog: prog }; } function parse_prog() { var prog = delimited("{", "}", ";", parse_expression); if (prog.length == 0) return FALSE; if (prog.length == 1) return prog[0]; return { type: "prog", prog: prog }; } function parse_expression() { return maybe_call(function(){ return maybe_binary(parse_atom(), 0); }); } } 

Marijn Haverbeke, parse-js (Common Lisp), , . , , JS, .

: JavaScript. Parte 2: Intérprete