Olá Apresento a você uma tradução amadora de um guia para implementar sua linguagem de programação JavaScript - PL Tutorial .

Do tradutor

Criaremos nossa própria linguagem de programação - linguagem λ (no original - linguagem λ ). No processo de criação, usaremos muitas técnicas interessantes, como descida recursiva, estilo de transferência de controle e técnicas básicas de otimização. Serão criadas duas versões do intérprete - o regular e o CPS, o transcompilador em JavaScript.

O autor do original é Mihai Bazon , o autor da famosa biblioteca UglifyJS (uma ferramenta para minimizar e formatar o código JS).

Entrada

Se você já escreveu seu compilador ou intérprete, não haverá novidades para você. Mas se você usar expressões regulares para analisar algo que se parece com uma linguagem de programação, leia a seção sobre análise . Vamos escrever código com menos bugs!

O artigo está dividido em partes na ordem “do simples ao complexo”. Não recomendo que você pule partes do artigo, a menos que entenda bem o tópico. Você sempre pode voltar se não entender alguma coisa.

O que vamos aprender:

• O que é um analisador e como escrevê-lo.
• Como escrever um intérprete.
• A sequela da transferência e por que isso importa.
• Escrevendo um compilador (trans).
• Estilo de transferência de continuação.
• Algumas técnicas básicas de otimização de código.
• Exemplos do que há de novo em nossa linguagem λ em comparação ao JavaScript.

Junto com isso, mostrarei por que o Lisp é uma ótima linguagem de programação. No entanto, o idioma em que estamos trabalhando não é o Lisp. Possui uma sintaxe mais rica (uma notação clássica de infixo que todo mundo conhece), algo como Scheme (exceto macros). Bom ou não, mas as macros são a principal característica do Lisp - algo que outros idiomas (exceto os dialetos Lisp) não podem fazer tão bem quanto fazem. (Sim, eu sei sobre o SweetJS ... perto, mas não isso.)

Mas primeiro, vamos apresentar nossa linguagem de programação.

idioma λ

Antes de fazer qualquer coisa, precisamos ter uma imagem clara do que queremos fazer. Seria bom escrever uma descrição da gramática da linguagem, mas eu vou facilitar - escreva um exemplo de um programa simples, então aqui estão alguns exemplos da linguagem λ:

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

Conclusão:

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

A linguagem é semelhante ao JavaScript, mas no geral não é. Em primeiro lugar, não há declarações, apenas expressões. Uma expressão deve retornar um valor e pode ser usada em qualquer lugar em outra expressão. É necessário ponto e vírgula para separar expressões em uma "sequência" de expressões. Os chavetas { e } criam uma sequência que é uma expressão em si, e seu valor é o último valor da sequência. O seguinte programa está correto:

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

As funções são criadas usando as palavras-chave lambda ou λ . Depois disso, entre parênteses há uma lista (possivelmente vazia) de nomes de argumentos, separados por vírgulas. O corpo de uma função é uma expressão, mas pode ser incluído em uma sequência {...} . Também é importante notar que não há palavra-chave de return . A função retorna o valor da última expressão.

Além disso, não há var . Para adicionar uma variável, você pode usar o que os programadores de JavaScript chamam de IIFE . Use lambda , declare variáveis ​​como argumentos. Para variáveis, o escopo é uma função e as funções são encerramentos, como no JavaScript [aprox. tradução: até ES6.].

Mesmo if seja uma expressão. JavaScript usa o operador ternário para fazer isso:

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

A palavra then chave then é opcional se o ramo for uma sequência ( {...} ), como você pode ver acima. Em outro caso, é necessário. else usado se um ramo alternativo estiver presente. E, novamente, then e else pegue a expressão como corpo, mas você pode combinar várias expressões em uma usando {...} . Se else ausente e a condição for false , o resultado de tudo if é false . Vale notar que false é uma palavra-chave que representa um valor que é o único valor falso em um idioma λ:

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

produzirá OK se e somente se o resultado de foo() não foo() false . Além disso, existe a palavra-chave true , mas absolutamente tudo o que não é false (em JavaScript, o operador === ) será considerado true nas ramificações (incluindo o número 0 e a string vazia "" ).

Observe que não há necessidade de parênteses em torno da expressão em if . Se você adicioná-los, não será um erro, porque ( a expressão começa, mas eles são apenas supérfluos.

O programa inteiro pode ser analisado, mesmo que esteja entre parênteses, portanto, você deve adicionar ; após cada expressão. A última expressão é uma exceção.

Ótimo, esta é a nossa pequena linguagem λ. Ele não é perfeito. A sintaxe está linda, mas tem falhas. Existem muitos recursos ausentes, como objetos e matrizes. Não prestamos atenção a eles, pois eles não são básicos para a nossa linguagem de programação.

Em seguida, escreveremos um analisador para o nosso idioma.

Conversão de código para AST

Criar um analisador é uma tarefa difícil. Em essência, ele deve pegar um pedaço de código e transformá-lo em um AST (árvore de sintaxe abstrata). O AST é uma representação estruturada de um programa na memória, abstrato porque não contém informações completas sobre o código, apenas semântica. Descrição AST está em uma parte separada.

Por exemplo, temos o seguinte código:

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

Nosso analisador irá gerar uma árvore como um 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 } ] }] } ] } 

A principal dificuldade na criação de um analisador é a dificuldade em organizar corretamente o código. O analisador deve funcionar em um nível superior ao da leitura de caracteres de uma sequência. Algumas diretrizes para reduzir a complexidade do código:

• Escreva muitos recursos pequenos. Em cada função, faça uma coisa e faça bem.
• Não tente usar expressões regulares para analisar. Eles simplesmente não funcionam. Eles podem ser úteis no analisador lexical , mas, por simplicidade, não os usaremos.
• Não tente adivinhar. Quando você não tiver certeza de como analisar algo, lance uma exceção contendo o local do erro (linha e coluna).

Para manter o código mais simples, vamos dividi-lo em três partes, que por sua vez são divididas em várias funções pequenas:

• Fluxo de caracteres
• Fluxo de token (tokens)
• Analisador

Fluxo de caracteres

Esta é a parte mais fácil. Criaremos um objeto de fluxo que representará as operações de leitura sequencial de caracteres de uma string. Ele contém quatro funções:

• peek() - retorna o próximo caractere sem extraí-lo do fluxo.
• next() - retorna o próximo caractere, extraindo-o do fluxo.
• eof() - retorna true se não houver mais caracteres no fluxo.
• croak(msg) - lança uma exceção contendo a mensagem ( msg ) e a posição atual no fluxo.

A última função é necessária para que você possa simplesmente lançar uma exceção contendo a localização do erro.

Aqui está o código inteiro para esse objeto (vamos chamá-lo de InputStream ). É pequeno o suficiente para que você não tenha problemas com isso:

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

Observe que este não é um objeto comum (criado via new ). Para obter esse objeto, você precisa: var stream = InputStream(string) .

A seguir, escreveremos o seguinte nível de abstração: Fluxo de token (tokens) .

Fluxo de token (tokens)

O tokenizer (lexer) usa um fluxo de caracteres e retorna um objeto com a mesma interface, mas os valores de retorno das funções peek() / next() serão tokens. Um token é um tipo com duas propriedades: type , value . Aqui estão alguns exemplos 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: "!=" } //  

Espaço em branco (espaço, tabulação, quebras de linha) e comentários são simplesmente ignorados.

Para escrever um tokenizer, precisamos dar uma olhada mais de perto no nosso idioma. A idéia é perceber que, dependendo do caractere atual ( input.peek() ), podemos decidir qual token ler:

• Primeiro, pule o espaço em branco.
• Se input.eof() , retorne null .
• Se for um caractere # , pule todos os caracteres para o final da linha (e retorne o próximo token).
• Se for entre aspas, leia a sequência.
• Se este for um número, leia o número.
• Se for uma letra, lemos a palavra e retornamos o identificador ou a palavra-chave.
• Se esse for um dos caracteres especiais, retorne o token correspondente.
• Se este é um dos símbolos dos operadores, retornamos o token correspondente.
• Se nenhuma das opções acima se aplicar, input.croak() uma exceção usando input.croak() .

Teremos a função read_next , a principal função do 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); } 

Aqui você pode ver muitas funções adicionais que retornam tipos diferentes de tokens, como read_string() , read_number() , etc. ... Eles são colocados em funções separadas, para que o código pareça mais simples e bonito.

Além disso, é interessante não removermos todos os símbolos de uma vez: sempre que o analisador solicitar o próximo token, leremos um token. Se algum tipo de erro acontecer, nem leremos todos os personagens.

read_ident() lerá todos os caracteres em uma linha que podem fazer parte do identificador ( is_id() ). O identificador deve começar com a letra, λ ou _ , e pode conter os mesmos caracteres, números ou qualquer um dos seguintes: ?!-<>= . Segue-se que foo-bar não será lido como três tokens, mas como um (token). Isso é necessário para poder definir funções com nomes como is-pair? ou string>= (desculpe, isso é Lisper em mim).

Além disso, read_ident() verificará se há um identificador na lista de palavras-chave conhecidas e, se existir, um token de kw será retornado em vez de um token de var .

Eu acho que o código fala por si, então aqui está um tokenizer pronto para o nosso 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; } } 

• A função next() nem sempre chama read_next() , porque pode haver um token que foi lido antes (usando a função peek() ). Para isso, temos uma variável current que contém o token atual.
• Somente números decimais são suportados em notação regular (1E5, 0x, etc. não são suportados). Mas se quiséssemos adicionar o suporte deles, read_number() apenas read_number() .
• Diferentemente do JavaScript, os únicos caracteres que não podem ser escapados em uma sequência de caracteres são aspas e barra invertida. As linhas podem conter quebras de linha, guias e qualquer outra coisa. Nós não interpretamos combinações padrão como \n , \t , etc. ... É muito fácil refazer ( read_string() ).

Agora, temos ferramentas poderosas para escrever facilmente um analisador , mas primeiro eu recomendaria examinar a descrição do AST .

Descrição AST

Como indicado acima, o analisador criará uma estrutura que mostra a semântica do programa. AST consiste em nós. Cada nó é um objeto JavaScript comum que possui uma propriedade de type que determina o tipo do nó, além de informações adicionais que dependem do 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" } } } 

Analisador

O analisador criará a árvore descrita acima.

Graças ao trabalho que fizemos no tokenizer, o analisador trabalha com um fluxo de tokens, em vez de um fluxo de caracteres. Ainda existem muitos recursos adicionais aqui para simplificar a estrutura. Vamos falar sobre os principais. Vamos começar com uma função de analisador de alto nível:

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

Essa função será chamada quando a palavra-chave lambda já tiver sido retirada do fluxo de token, portanto, apenas precisamos usar os nomes dos argumentos. Mas, como eles estão entre colchetes e separados por vírgulas, faremos isso usando a função delimited , que utiliza os seguintes argumentos: start , stop , separator , a função parser , que analisa cada elemento separadamente. Nesse caso, usamos a função parse_varname , que gera um erro se perceber algo que não se parece com uma variável. O corpo da função é uma expressão, portanto, obtemos isso com parse_expression .

A função delimited é de nível 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 você pode ver, ele usa ainda mais funções: is_punc e skip_punc . O primeiro retornará true se o token atual for um determinado sinal de pontuação (sem extraí-lo), enquanto skip_punc verificará se o token atual é um caractere de pontuação fornecido e o extrairá (ou lançará uma exceção caso contrário).

A função que analisa todo o programa parece ser a mais simples:

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

Como temos apenas expressões, simplesmente chamamos parse_expression() e lemos as expressões até lermos tudo. Usando skip_punc(";") , nós fazemos ; obrigatório após cada expressão.

Outro exemplo simples é 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; } 

Ela pula a palavra-chave if (lança uma exceção se o token atual não if palavra-chave if ), lê a condição usando parse_expression() . Se o símbolo { não for mais longe, a palavra-chave then será necessária (a sintaxe não parece muito boa sem ela). Como ramificações são apenas expressões, usamos apenas parse_expression() novamente para elas. O ramo else é opcional, portanto, primeiro verificamos a presença da palavra-chave antes de analisá-la.

Com muitas funções pequenas, podemos simplificar o código. Escrevemos o analisador quase como se usássemos uma linguagem de alto nível especificamente para analisar a sintaxe. Todas essas funções são "recursivas", ou seja, temos parse_atom() , que, dependendo do token atual, chama outras funções. Um deles é parse_if() (chamado quando o token atual é if ) e, por sua vez, chama parse_expression() . Mas parse_expression() chama parse_atom() . Não há recursão infinita porque uma das funções sempre extrai pelo menos um token.

Esse tipo de método de análise é chamado de Método de Descida Recursiva e, de fato, o mais fácil de escrever.

Nível inferior: parse_atom() e parse_expression()

A função parse_atom() chama outra função, dependendo do token atual:

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

Quando ela vê o colchete de abertura, a expressão entre parênteses deve ir, portanto, pulando o colchete, a função chama parse_expression() e espera pular o colchete de fechamento depois disso. Se ela vir algum tipo de palavra-chave, ela chamará a função correspondente. Se ela vir uma constante ou identificador, retornará como está. E se nada acontecer, chama unexpected() , o que gera uma exceção.

Quando ela vê { , ela chama parse_prog para analisar a sequência de expressões. Além disso, parse_prog faz uma otimização simples: se não houver expressões entre { e } , ele retornará false ; se houver apenas uma expressão, retornará apenas ela. Caso contrário, o nó prog com uma matriz de expressões será retornado.

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

E aqui está a função parse_expression() . Ao contrário de parse_atom() , ele analisará o maior número possível de expressões usando maybe_binary() :

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

Funções maybe_*

Essas funções verificam o que vem após a expressão e decidem se a expressão deve ser quebrada em seu nó ou retornada como está.

A função maybe_call() é muito simples: obtém uma função que analisa a expressão atual e, se encontrar ( após a expressão, ela se envolve em uma call . Observe como delimited() é adequado para analisar uma 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) }; } 

Prioridade do Operador

A função maybe_binary(left, my_prec) é usada para combinar expressões 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