LISP処理系を作る（途中）．

javascriptの勉強も兼ねて（といいつつc like）．とりあえず構文木生成まではいけたと思う．そもそもlispをよくわかってないので合ってるのかなー．

動作

("ABC" [1 2 3 ()])を与えると((65 (66 (67 ()))) (1 (2 (3 (() ())))))みたいになる．

文法

[]リスト表記がある．（(1 (2 (3 ()))と[1 2 3]は等価）

''文字がある．（'a'は97と等価）

""文字列がある．（"abc"は(97 (98 (99 ()))と等価）

BNF

  <Root> := <S Expression>
  <S Expression> := <Atom>|'('<S Expression> <S Expression>')'
  <Atom> := <Nil>|<List>|<String>|<Char>|<Number>|<Id>
  <Nil> := '('')'
  <Number> := <Digit>+
  <String> := '"'(<"以外の任意の1文字>|\<任意の1文字>)*'"'
  <Char> := '''<任意の1文字>'''
  <List> := '['<S Expression>*']'
  <Id> := <()[]"'以外の任意の1文字><任意の1文字>*
  <Digit> := 0|1|2|3|4|5|6|7|8|9

コード

scanが字句解析器？，parserRootが構文解析木？

function scan(input_string) {
  var tokens = new Array()
  for (var i = 0; i < input_string.length; i++) {
    switch(input_string[i]) {
      case '[' :
      case ']' :
      case '(' :
      case ')' :
      case '\\' :
        tokens.unshift(input_string[i]);
        break;
      case '\'' :
        character = '\''
        i++;
        while('\'' != input_string[i]) {
          if(input_string[i] == '\\') i++;
          character += input_string[i++];
        }
        character += '\''
        tokens.unshift(character)
        break;
      case '"' :
        string = '"';
        i++;
        while('"' != input_string[i]) {
          if(input_string[i] == '\\') i++;
          string += input_string[i++];
        }
        string += '"';
        tokens.unshift(string);
        break;
      case ' ' :
      case '\t' :
      case '\n' :
        break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' :
        number = '';
        while('0' <= input_string[i] && input_string[i] <= '9') {
          number += input_string[i++];
        }
        i--;
        tokens.unshift(number);
        break
      default :
        symbol = '';
        while(input_string[i] != '[' &&
              input_string[i] != ']' &&
              input_string[i] != '(' &&
              input_string[i] != ')' &&
              input_string[i] != ' ' &&
              input_string[i] != '\n' &&
              input_string[i] != '\t' &&
              i < input_string.length){
          symbol += input_string[i++];
        }
        i--;
        tokens.unshift(symbol);
        break;
    }
  }
  return tokens;
}

function createNil()
{
  var nil = new Object();
  nil.type = "Nil";
  nil.car = nil;
  nil.cdr = nil;
  return nil;
}

function createNumber(n)
{
  var number = new Object();
  number.value = n;
  number.type = "Number";
  return number;
}

function createList(car, cdr)
{
  var list = new Object();
  list.car = car;
  list.cdr = cdr;
  list.type = "List";
  return list;
}

/*
  <Root> := <S Expression>
  <SExpr> := <Atom>|<List>
  <List> := '('<S Expression> <S Expression>')'
  <Atom> := <Nil>|<Number>|<Symbol>|<Lambda>|<ExtendList>|<String>|<Char>
  <Nil> := '('')'
  <Number> := <Digit>+
  <Symbol> := <()[]"'以外の任意の1文字><任意の1文字>*
  <Lambda> := '\'<S Expression>
  <String> := '"'(<"以外の任意の1文字>|\<任意の1文字>)*'"'
  <Char> := '''<任意の1文字>'''
  <ExtendList> := '['<S Expression>*']'
  <Digit> := 0|1|2|3|4|5|6|7|8|9
*/
function parseRoot(tokens){
  var tree = parseSExpr(tokens);
  if(tokens.pop() == null){
    return tree;
  }else{
    throw 'parse error.'
  }
}

function parseSExpr(tokens){
  var v = tokens.pop();
  if(v == '('){
    var v2 = tokens.pop();
    if(v2 == ')'){
      tokens.push(v2);
      tokens.push(v);
      return parseAtom(tokens);
    }
    tokens.push(v2);
    tokens.push(v);
    return parseList(tokens);
  }else{
    tokens.push(v);
    return parseAtom(tokens);
  }
}

function parseList(tokens){
  var v = tokens.pop();
  var car = parseSExpr(tokens);
  var cdr = parseSExpr(tokens);
  v = tokens.pop();
  if(v != ')'){
    throw 'parse error.'
  }
  return createList(car, cdr);
}

function parseAtom(tokens){
  var v = tokens.pop();
  if(v == '('){
    tokens.push(v);
    return parseNil(tokens);
  }else if(v == '['){
    tokens.push(v);
    return parseExtendList(tokens);
  }else if(v[0] == '"'){
    tokens.push(v);
    return parseString(tokens);
  }else if(v[0] == '\\'){
    tokens.push(v);
    return parseLambda(tokens);
  }else if(v[0] == '\''){
    tokens.push(v);
    return parseChar(tokens);
  }else if('0' <= v[0] && v[0] <= '9'){
    tokens.push(v);
    return parseNumber(tokens);
  }else{
    tokens.push(v);
    return parseSymbol(tokens);
  }
}

function parseNil(tokens){
  tokens.pop();
  tokens.pop();
  return createNil();
}

function parseLambda(tokens){
  var v = tokens.pop();
  var list = parseList(tokens);
  list.type = "Lambda";
  return list;
}

function parseExtendList(tokens){
  var v = tokens.pop();
  return parseExtendList_(tokens);
}

function parseExtendList_(tokens){
  var v = tokens.pop();
  
  if(v != ']'){
    tokens.push(v);
    var car = parseSExprn(tokens);
    var cdr = parseExtendList_(tokens);
    return createList(car, cdr);
  }else{
    return createNil();
  }
}

function parseString(tokens){
  var v = tokens.pop();
  return parseString_(v.slice(1));
}

function parseString_(string){
  if(string[0] != '"'){
    var car = createNumber(string[0].charCodeAt());
    var cdr = parseString_(string.slice(1));
    return createList(car, cdr);
  }else{
    return createNil();
  }
}

function parseChar(tokens){
  var v = tokens.pop();
  return createNumber(v[1].charCodeAt());
}

function parseNumber(tokens){
  var v = tokens.pop();
  return createNumber(parseInt(v));
}

function parseSymbol(tokens){
  var v = tokens.pop();
  var elem = new Object();
  elem.type = "Symbol";
  elem.value = v;
  return elem
}

function reverseSExpr(tree){
  var string;
  if(tree.type == "List"){
    string = "("+reverseSExpr(tree.car)+" "+reverseSExpr(tree.cdr)+")";
  }else if(tree.type == "Lambda"){
    string = "\\("+reverseSExpr(tree.car)+" "+reverseSExpr(tree.cdr)+")";
  }else if(tree.type == "Number"){
    string = tree.value;
  }else if(tree.type == "Symbol"){
    string = tree.value;
  }else{
    string = "()";
  }
  return string;
}


input_string = '("ABC" [1 2 3 ()])';
tokens = scan(input_string);
tree = parseRoot(tokens);
sexpr = reverseSExpr(tree);

console.log(input_string);
console.log(sexpr);