Bonjour Je vous présente une traduction amateur d'un guide pour implémenter votre langage de programmation JavaScript - PL Tutorial .

Du traducteur

Nous allons créer notre propre langage de programmation - langage λ (dans l'original - λanguage). Dans le processus de création, nous utiliserons de nombreuses techniques intéressantes, telles que la descente récursive, le style de transfert de contrôle et les techniques d'optimisation de base. Deux versions de l'interpréteur seront créées - les interprètes standard et CPS, le trans-compilateur en JavaScript.

L'auteur de l'original est Mihai Bazon , l'auteur de la célèbre bibliothèque UglifyJS (un outil pour minimiser et formater le code JS).

Entrée

Si vous avez déjà écrit votre compilateur ou interprète, il n'y aura rien de nouveau pour vous. Mais si vous utilisez des expressions régulières pour analyser quelque chose qui ressemble à un langage de programmation, lisez la section sur l' analyse . Écrivons du code avec moins de bugs!

L'article est divisé en parties dans l'ordre «du simple au complexe». Je ne vous recommande pas d'ignorer certaines parties de l'article, à moins que vous ne compreniez bien le sujet. Vous pouvez toujours revenir en arrière si vous ne comprenez pas quelque chose.

Qu'allons-nous apprendre:

• Qu'est-ce qu'un analyseur et comment l'écrire.
• Comment écrire un interprète.
• La suite du transfert et pourquoi c'est important.
• Écriture d'un compilateur (trans).
• Style de transfert de continuation.
• Quelques techniques de base d'optimisation de code.
• Exemples de nouveautés dans notre langage λ par rapport à JavaScript.

Parallèlement à cela, je montrerai pourquoi Lisp est un excellent langage de programmation. Cependant, la langue sur laquelle nous travaillons n'est pas le lisp. Il a une syntaxe plus riche (une notation infixe classique que tout le monde connaît), quelque chose comme Scheme (sauf les macros). Bon ou pas, mais les macros sont la principale caractéristique de Lisp - quelque chose que les autres langues (à l'exception des dialectes Lisp) ne peuvent pas faire aussi bien que lui. (Oui, je connais SweetJS ... proche, mais pas ça.)

Mais d'abord, introduisons notre langage de programmation.

langue λ

Avant de faire quoi que ce soit, nous devons avoir une image claire de ce que nous voulons faire. Ce serait bien d'écrire une description de la grammaire du langage, mais je vais vous faciliter la tâche - écrivez un exemple de programme simple, alors voici quelques exemples du langage λ:

#   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); 

Conclusion:

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

Le langage ressemble à JavaScript, mais dans l'ensemble il ne l'est pas. Premièrement, il n'y a pas de déclarations, seulement des expressions. Une expression doit renvoyer une valeur et peut être utilisée n'importe où dans une autre expression. Les points-virgules sont nécessaires pour séparer les expressions dans une "séquence" d'expressions. Les accolades { et } créent une séquence qui est elle-même une expression, et sa valeur est la dernière valeur de la séquence. Le programme suivant est correct:

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

Les fonctions sont créées à l'aide des mots clés lambda ou λ . Après cela, entre parenthèses se trouve une liste (éventuellement vide) de noms d'arguments, séparés par des virgules. Le corps d'une fonction est une expression, mais peut être enfermé dans une séquence {...} . Il convient également de noter qu'il n'y a pas de mot-clé return . La fonction renvoie la valeur de la dernière expression.

En outre, aucune var . Pour ajouter une variable, vous pouvez utiliser ce que les programmeurs JavaScript appellent IIFE . Utilisez lambda , déclarez les variables comme arguments. Pour les variables, la portée est une fonction et les fonctions sont des fermetures, comme en JavaScript [env. traduction: jusqu'à ES6.].

Même if c'est une expression. JavaScript utilise l'opérateur ternaire pour ce faire:

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

Le mot clé then est facultatif si la branche est une séquence ( {...} ), comme vous pouvez le voir ci-dessus. Dans un autre cas, c'est nécessaire. else utilisé si une branche alternative est présente. Et encore une fois, then et else prenez l'expression comme corps, mais vous pouvez combiner plusieurs expressions en une seule en utilisant {...} . Si else absent et que la condition est false , alors le résultat de tout if est false . Il convient de noter que false est un mot-clé représentant une valeur qui est la seule fausse valeur dans un langage λ:

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

affichera OK si et seulement si le résultat de foo() pas false . De plus, il y a le mot-clé true , mais absolument tout ce qui n'est pas false (en JavaScript, l'opérateur === ) sera considéré comme true dans les branches (y compris le nombre 0 et la chaîne vide "" ).

Notez qu'il n'y a pas besoin de parenthèses autour de l'expression dans if . Si vous les ajoutez, ce ne sera pas une erreur, car ( l'expression commence, mais elles sont juste superflues.

L'ensemble du programme peut être analysé même s'il est entouré de parenthèses, vous devez donc ajouter ; après chaque expression. La dernière expression est une exception.

Génial, c'est notre petit langage λ. Il n'est pas parfait. La syntaxe est magnifique, mais elle a des défauts. Il existe de nombreuses fonctionnalités manquantes, telles que des objets et des tableaux. Nous n'y prêtons pas attention, car ils ne sont pas basiques pour notre langage de programmation.

Ensuite, nous allons écrire un analyseur pour notre langue.

Conversion de code en AST

La création d'un analyseur est une tâche difficile. En substance, il devrait prendre un morceau de code et le transformer en AST (arbre de syntaxe abstraite). AST est une représentation structurée d'un programme en mémoire, abstraite car elle ne contient pas d'informations complètes sur le code, seulement la sémantique. Description AST est dans une pièce séparée.

Par exemple, nous avons le code suivant:

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

Notre analyseur va générer un arbre en tant qu'objet 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 principale difficulté de création d'un analyseur est la difficulté à bien organiser le code. L'analyseur doit fonctionner à un niveau supérieur à la lecture de caractères dans une chaîne. Quelques conseils pour réduire la complexité du code:

• Écrivez beaucoup de petites fonctionnalités. Dans chaque fonction, faites une chose et faites-la bien.
• N'essayez pas d'utiliser des expressions régulières pour l'analyse. Ils ne fonctionnent tout simplement pas. Ils peuvent être utiles dans l' analyseur lexical , mais, pour simplifier, nous ne les utiliserons pas.
• N'essayez pas de deviner. Lorsque vous ne savez pas comment analyser quelque chose, lancez une exception contenant l'emplacement de l'erreur (ligne et colonne).

Pour garder le code plus simple, nous allons le diviser en trois parties, qui à leur tour sont divisées en de nombreuses petites fonctions:

• Flux de caractères
• Flux de jetons (jetons)
• Analyseur

Flux de caractères

C'est la partie la plus simple. Nous allons créer un objet stream qui représentera les opérations de lecture séquentielle des caractères d'une chaîne. Il contient quatre fonctions:

• peek() - renvoie le caractère suivant sans l'extraire du flux.
• next() - renvoie le caractère suivant, en l'extrayant du flux.
• eof() - retourne true s'il n'y a plus de caractères dans le flux.
• croak(msg) - lève une exception contenant le message ( msg ) et la position actuelle dans le flux.

La dernière fonction est nécessaire pour que vous puissiez simplement lever une exception contenant l'emplacement de l'erreur.

Voici le code complet de cet objet (appelons-le InputStream ). Il est assez petit pour ne pas avoir de problèmes avec:

 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 + ")"); } } 

Veuillez noter que ce n'est pas un objet ordinaire (qui est créé via new ). Pour obtenir cet objet, vous avez besoin de: var stream = InputStream(string) .

Ensuite, nous écrirons le niveau d'abstraction suivant: Flux de jetons (jetons) .

Flux de jetons (jetons)

Le tokenizer (lexer) utilise un flux de caractères et renvoie un objet avec la même interface, mais les valeurs de retour des fonctions peek() / next() seront des jetons. Un jeton est un type avec deux propriétés: type , value . Voici quelques exemples de jetons:

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

Les espaces (espace, tabulation, sauts de ligne) et les commentaires sont simplement ignorés.

Pour écrire un tokenizer, nous devons regarder de plus près notre langue. L'idée est de remarquer qu'en fonction du caractère courant ( input.peek() ) nous pouvons décider quel jeton lire:

• Tout d'abord, ignorez les espaces.
• Si input.eof() , retourne null .
• S'il s'agit d'un caractère # , sautez tous les caractères à la fin de la ligne (et retournez le jeton suivant).
• S'il s'agit d'un guillemet, lisez la chaîne.
• S'il s'agit d'un nombre, lisez-le.
• S'il s'agit d'une lettre, nous lisons le mot et retournons l'identifiant ou le mot-clé.
• S'il s'agit de l'un des caractères spéciaux, renvoyez le jeton correspondant.
• Si c'est l'un des symboles des opérateurs, alors nous retournons le jeton correspondant.
• Si rien de ce qui précède ne s'applique, lancez une exception à l'aide de input.croak() .

Nous aurons la fonction read_next , la fonction principale du 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); } 

Ici, vous pouvez voir de nombreuses fonctions supplémentaires qui renvoient différents types de jetons, tels que read_string() , read_number() , etc ... Ils sont placés dans des fonctions distinctes, de sorte que le code semble plus simple et plus beau.

De plus, il est intéressant de ne pas retirer tous les symboles à la fois: chaque fois que l'analyseur demande le prochain jeton, nous lirons un jeton. Si une erreur se produit, nous ne lirons même pas tous les caractères.

read_ident() lira tous les caractères d'une ligne pouvant faire partie de l'identifiant ( is_id() ). L'identifiant doit commencer par la lettre, λ ou _ , et peut contenir les mêmes caractères, chiffres ou n'importe lequel des éléments suivants: ?!-<>= . Il s'ensuit que foo-bar ne sera pas lu comme trois jetons, mais comme un ( var ). Est-ce nécessaire pour pouvoir définir des fonctions avec des noms tels que is-pair? ou string>= (désolé, c'est Lisper en moi).

De plus, read_ident() vérifiera s'il y a un identifiant dans la liste des mots clés connus, et s'il y est, un kw -token sera retourné au lieu d'un var -token.

Je pense que le code parle de lui-même, alors voici un tokenizer prêt à l'emploi pour notre langue:

 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 fonction next() n'appelle pas toujours read_next() , car il peut y avoir un jeton qui a été lu auparavant (en utilisant la fonction peek() ). Pour cela, nous avons une variable current qui contient le jeton courant.
• Seuls les nombres décimaux sont pris en charge en notation régulière (1E5, 0x, etc. ne sont pas pris en charge). Mais si nous voulions ajouter leur support, nous ne read_number() que read_number() .
• Contrairement à JavaScript, les seuls caractères qui ne peuvent pas être échappés dans une chaîne sont les guillemets et les barres obliques inverses. Les lignes peuvent contenir des sauts de ligne, des tabulations et tout autre élément. Nous n'interprétons pas les combinaisons standard comme \n , \t , etc ... C'est très facile à refaire ( read_string() ).

Nous avons maintenant des outils puissants pour écrire facilement un analyseur , mais je recommanderais d'abord de regarder la description AST .

Description de l'AST

Comme indiqué ci-dessus, l'analyseur va construire une structure qui montre la sémantique du programme. AST se compose de nœuds. Chaque nœud est un objet JavaScript standard qui possède une propriété type qui détermine le type du nœud, ainsi que des informations supplémentaires qui dépendent du type.

 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" } } } 

Analyseur

L'analyseur va construire l'arborescence décrite ci-dessus.

Grâce au travail que nous avons fait dans le tokenizer, l'analyseur fonctionne avec un flux de jetons, au lieu d'un flux de caractères. Il existe encore de nombreuses fonctionnalités supplémentaires pour simplifier la structure. Nous parlerons des principaux. Commençons par une fonction d'analyseur de haut niveau:

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

Cette fonction sera appelée lorsque le mot-clé lambda a déjà été extrait du flux de jetons, il nous suffit donc de prendre les noms des arguments. Mais comme ils sont entre crochets et séparés par des virgules, nous le ferons en utilisant la fonction delimited , qui prend les arguments suivants: start , stop , separator , la fonction parser , qui analyse chaque élément séparément. Dans ce cas, nous utilisons la fonction parse_varname , qui génère une erreur si elle remarque quelque chose qui ne ressemble pas à une variable. Le corps de la fonction est une expression, nous l'obtenons donc avec parse_expression .

La fonction delimited est de niveau inférieur:

 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; } 

Comme vous pouvez le voir, il utilise encore plus de fonctions: is_punc et skip_punc . La première renvoie true si le jeton actuel est un signe de ponctuation donné (sans l'extraire), tandis que skip_punc vérifie si le jeton actuel est un caractère de ponctuation donné et l'extrait (ou déclenche une exception sinon).

La fonction qui analyse l'ensemble du programme semble être la plus simple:

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

Puisque nous n'avons que des expressions, nous appelons simplement parse_expression() et lisons les expressions jusqu'à ce que nous parse_expression() tout. En utilisant skip_punc(";") , nous faisons ; obligatoire après chaque expression.

Un autre exemple simple est 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; } 

Elle ignore le mot clé if (lève une exception si le jeton actuel n'est pas le mot clé if ), lit la condition à l'aide de parse_expression() . Si le symbole { ne va pas plus loin, alors le mot-clé then est requis (la syntaxe ne semble pas très bonne sans lui). Les branches ne sont que des expressions, nous utilisons parse_expression() nouveau parse_expression() pour elles. La branche else est facultative, nous vérifions donc d'abord la présence du mot-clé avant de l'analyser.

Avec de nombreuses petites fonctions, nous pouvons simplifier le code. Nous avons écrit l'analyseur presque comme il le ferait si nous utilisions un langage de haut niveau spécifiquement pour l'analyse syntaxique. Toutes ces fonctions sont "mutuellement récursives", c'est-à-dire que nous avons parse_atom() , qui, selon le jeton actuel, appelle d'autres fonctions. L'un d'eux est parse_if() (appelé lorsque le jeton actuel est if ) et à son tour appelle parse_expression() . Mais parse_expression() appelle parse_atom() . Il n'y a pas de récursion infinie car l'une des fonctions extrait toujours au moins un jeton.

Ce type de méthode d'analyse est appelé méthode de descente récursive , et en fait, la plus simple à écrire.

Niveau inférieur: parse_atom() et parse_expression()

La fonction parse_atom() appelle une autre fonction, selon le jeton actuel:

 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(); }); } 

Quand elle voit le crochet ouvrant, alors l'expression parenthèse devrait aller, donc, sautant le crochet, la fonction appelle parse_expression() et s'attend à sauter le crochet fermant après cela. Si elle voit une sorte de mot-clé, alors elle appelle la fonction correspondante. Si elle voit une constante ou un identifiant, elle le renvoie tel quel. Et si rien ne se produit, il appelle unexpected() , qui lève une exception.

Quand elle voit { , elle appelle parse_prog pour analyser la séquence d'expressions. De plus, parse_prog fait une optimisation simple: s'il n'y a pas d'expressions entre { et } , alors il retourne false , s'il n'y a qu'une seule expression, alors il ne le retourne que. Sinon, le nœud prog avec un tableau d'expressions est retourné.

 //     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 }; } 

Et voici la fonction parse_expression() . Contrairement à parse_atom() , il analysera autant d'expressions que possible en utilisant peut- maybe_binary() :

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

Fonctions peut- maybe_*

Ces fonctions vérifient ce qui vient après l'expression et décident d'envelopper l'expression dans son nœud ou de la renvoyer telle quelle.

La fonction peut- maybe_call() est très simple: elle obtient une fonction qui analyse l'expression actuelle, et si elle rencontre ( après l'expression, elle s'enveloppe dans un call . Notez comment delimited() convient pour analyser une liste d'arguments:

 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) }; } 

Priorité de l'opérateur

La fonction peut- maybe_binary(left, my_prec) est utilisée pour combiner des expressions telles que 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); }); } } 

Remerciements

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

: JavaScript. Partie 2: interprète