robot_lexer.js

class ParsingError extends SyntaxError {
  constructor(message, line, column) {
    super(`line ${line + 1}, column ${column + 1}: ${message}`);

    this.name = "ParsingError";
    this.line = line;
    this.column = column;
  }
}

class UnknownTokenError extends ParsingError {
  constructor(line, column) {
    super(`unknown token`, line, column);

    this.name = "UnknownTokenError";
  }
}

class UnexpectedTokenError extends ParsingError {
  constructor(line, column, expectedTokenType, actualTokenType) {
    if (actualTokenType) {
      super(`expected "${expectedTokenType}" but "${actualTokenType}" reached`, line, column);
    } else {
      actualTokenType = expectedTokenType;
      expectedTokenType = undefined;

      super(`unexpected token "${actualTokenType}"`, line, column);
    }

    this.name = "UnexpectedTokenError";
    this.expectedTokenType = expectedTokenType;
    this.actualTokenType = actualTokenType;
  }
}

class UnableToParseAnExpressionError extends ParsingError {
  constructor(line, column, tokenType) {
    super(`unable to parse an expression with "${tokenType}" token type`, line, column);

    this.name = "UnableToParseAnExpressionError";
    this.tokenType = tokenType;
  }
}

class UnknownKeywordError extends ParsingError {
  constructor(line, column, keyword) {
    super(`unknown keyword "${keyword}"`, line, column);

    this.name = "UnknownKeywordError";
    this.keyword = keyword;
  }
}

class UnexpectedEndOfInputError extends SyntaxError {
  constructor() {
    super(`unexpected end of input`);

    this.name = "UnexpectedEndOfInputError";
  }
}

class UnexpectedWhileEndOfInputError extends UnexpectedEndOfInputError {
  constructor(line, column) {
    super();

    this.message = `unable to parse body for a "while" loop statement at position ${line+1}:${column+1}: unexpected end of input reached`

    this.name = "UnexpectedWhileEndOfInputError";
    this.line = line;
    this.column = column;
  }
}

class UnexpectedIfEndOfInputError extends UnexpectedEndOfInputError {
  constructor(line, column, blockTokenType) {
    super();

    this.message = `unable to parse body for an "${blockTokenType}" statement at position ${line+1}:${column+1}: unexpected end of input reached`

    this.name = "UnexpectedIfEndOfInputError";
    this.line = line;
    this.column = column;
    this.blockTokenType = blockTokenType;
  }
}

const TokenType = {
  EndOfInput: 'END_OF_INPUT',
  Comment: 'COMMENT',
  Newline: 'NEW_LINE',

  StartLoop: 'START_LOOP',
  EndLoop: 'END_LOOP',
  While: 'WHILE',

  Not: 'NOT',
  And: 'AND',
  Or: 'OR',

  CheckTop: 'CHECK_TOP',
  CheckBottom: 'CHECK_BOTTOM',
  CheckLeft: 'CHECK_LEFT',
  CheckRight: 'CHECK_RIGHT',
  CheckLiteral: 'CHECK_LITERAL',

  MoveUp: 'MOVE_UP',
  MoveDown: 'MOVE_DOWN',
  MoveLeft: 'MOVE_LEFT',
  MoveRight: 'MOVE_RIGHT',

  Fill: 'FILL',

  If: 'IF',
  Else: 'ELSE',
  Then: 'THEN',
  End: 'END',

  OpenParen: 'OPEN_PAREN',
  CloseParen: 'CLOSE_PAREN',
};

const keywordsTypes = {
  'нц': TokenType.StartLoop,
  'кц': TokenType.EndLoop,

  'пока': TokenType.While,

  'не': TokenType.Not,
  'и': TokenType.And,
  'или': TokenType.Or,

  'сверху': TokenType.CheckTop,
  'снизу': TokenType.CheckBottom,
  'слева': TokenType.CheckLeft,
  'справа': TokenType.CheckRight,
  'свободно': TokenType.CheckLiteral,

  'вверх': TokenType.MoveUp,
  'вниз': TokenType.MoveDown,
  'влево': TokenType.MoveLeft,
  'вправо': TokenType.MoveRight,

  'закрасить': TokenType.Fill,

  'если': TokenType.If,
  'иначе': TokenType.Else,
  'то': TokenType.Then,
  'все': TokenType.End,
  'всё': TokenType.End,
};

function ru(tokenType) {
  switch (tokenType) {
    case TokenType.EndOfInput:
      return "конец текста программы";
    case TokenType.Comment:
      return "комментарий";
    case TokenType.Newline:
      return "перевод строки";
    case TokenType.OpenParen:
      return "(";
    case TokenType.CloseParen:
      return ")";
  }

  return Object.keys(keywordsTypes).find(key => keywordsTypes[key] === tokenType);
}

function l10n(e) {
  let line = e.line;
  let column = e.column;

  let prefix = `ошибка на строке ${line+1} в столбце ${column+1}: `;

  if (e instanceof UnknownTokenError) {
    return prefix + "неизвестный токен";
  }

  if (e instanceof UnexpectedTokenError) {
    if (!this.expectedTokenType) {
      return prefix + `получен неожиданный токен "${ru(e.actualTokenType)}"`;
    }

    return prefix + `ожидался токен "${ru(e.actualTokenType)}" но был получен "${ru(e.actualTokenType)}"`;
  }

  if (e instanceof UnableToParseAnExpressionError) {
    return prefix + `невозможно обработать выражение "${ru(e.tokenType)}"`;
  }

  if (e instanceof UnknownKeywordError) {
    return prefix + `неизвестное ключевое слово "${e.keyword}"`;
  }

  if (e instanceof UnexpectedWhileEndOfInputError) {
    return `для цикла "пока" на позиции ${line+1}:${column+1} не найдено окончание цикла "кц"`;
  }

  if (e instanceof UnexpectedIfEndOfInputError) {
    return `для условия "${ru(e.blockTokenType)}" на позиции ${line+1}:${column+1} не найден конец блока, а именно токены "все" или "иначе"`;
  }

  return undefined;
}

class Token {
  constructor(type, value, line, column) {
    this.type = type;
    this.value = value;
    this.line = line;
    this.column = column;
  }

  toString() {
    return '<' + this.type + ', ' + this.value + ', ' + this.line + ':' + this.column + '>';
  }
};

function isHashtag(ch) {
  return ch == '#';
};

function isNewline(ch) {
  return ch == '\n' || ch == '\r';
};

function isWhitespace(ch) {
  return ch == ' ' || ch == '	';
};

function isAlphaRU(ch) {
  return (ch >= 'а' && ch <= 'я') ||
    (ch >= 'А' && ch <= 'Я');
}

function isParen(ch) {
  return ch == '(' || ch == ')';
}

class Lexer {
  constructor(text) {
    this.pos = 0;
    this.text = text;
    this.token = undefined;
    this.line = 0;
    this.column = 0;
  }

  skipWS() {
    while (this.pos < this.text.length && isWhitespace(this.text.charAt(this.pos))) {
      this.pos++;
      this.column++;
    }
  }

  nextToken() {
    this.skipWS();

    if (this.pos >= this.text.length) {
      this.token = new Token(TokenType.EndOfInput);

      return;
    }

    let ch = this.text.charAt(this.pos);

    if (isNewline(ch)) {
      this.token = this.processNewline();

      return;
    }

    if (isHashtag(ch)) {
      this.token = this.processComment();

      return;
    }

    if (isParen(ch)) {
      this.token = this.processParen();

      return;
    }

    if (isAlphaRU(ch)) {
      this.token = this.processIdentifier();

      return;
    }

    throw new UnknownTokenError(this.line, this.column);
  }

  processNewline() {
    let ch = this.text.charAt(this.pos);

    let line = this.line;
    let column = this.column;

    this.pos++;
    this.line++;
    this.column = 0;

    return new Token(TokenType.Newline, ch, line, column);
  }

  processParen() {
    let ch = this.text.charAt(this.pos);
    let typ = ch == '(' ? TokenType.OpenParen : TokenType.CloseParen;

    let line = this.line;
    let column = this.column;

    this.pos++;
    this.column++;

    return new Token(typ, ch, line, column);
  }

  processComment() {
    this.pos++;
    this.column++;

    let end = this.pos;
    while (end < this.text.length && !isNewline(this.text.charAt(end))) {
      end++;
    }

    let s = this.text.substring(this.pos, end);

    let line = this.line;
    let column = this.column;

    this.pos = end;
    this.column += s.length;

    return new Token(TokenType.Comment, s, line, column);
  }

  processIdentifier() {
    let end = this.pos;
    while (end < this.text.length && isAlphaRU(this.text.charAt(end))) {
      end++;
    }

    let s = this.text.substring(this.pos, end);

    let typ = this.recognizeIdentifierType(s);

    let line = this.line;
    let column = this.column;

    this.pos = end;
    this.column += s.length;

    return new Token(typ, s, line, column);
  }


  recognizeIdentifierType(s) {
    let typ = keywordsTypes[s];

    if (!typ) {
      throw new UnknownKeywordError(this.line, this.column, s);
    }

    return typ;
  }

  print() {
    let s = this.text.substring(this.pos);
    console.log(s);
  }
};

// IfStmt = "если" Condition "то" ExpressionList "все"
// Condition = AndCond { "или" AndCond }
// AndCond = BoolCond { "и" BoolCond }
// BoolCond = "не" BoolCond | "(" Condition ")" | CheckStmt
// test 0 && 0 || 1

// WhileStmt = "нц" "пока" Condition NewLine ExpressionList "кц"

class Parser {
  constructor(lexer) {
    this.lexer = lexer;
  }

  nextToken() {
    this.lexer.nextToken();
    this.token = this.lexer.token;
  }

  parse() {
    this.nextToken();

    return this.parseBlock(TokenType.EndOfInput);
  };

  parseBlock(...terminationTypes) {
    if (terminationTypes.length == 0) {
      throw new Error('terminationTypes must have at least 1 parameter');
    }

    let blockStmt = new Block();

    while (!this.acceptOneOf(...terminationTypes) && !this.accept(TokenType.EndOfInput)) {
      let node = this.parseExpression();

      blockStmt.add(node);

      this.nextToken();
    }

    if (this.accept(TokenType.EndOfInput) && terminationTypes[0] != TokenType.EndOfInput) {
      throw new UnexpectedEndOfInputError();
    }

    return blockStmt;
  }

  parseExpression() {
    if (this.acceptsMove()) {
      return this.parseMove();
    }

    if (this.accept(TokenType.Fill)) {
      return this.parseFill()
    }

    if (this.accept(TokenType.If)) {
      return this.parseIfStmt();
    }

    if (this.accept(TokenType.StartLoop)) {
      return this.parseLoop();
    }

    if (this.accept(TokenType.Comment)) {
      return this.parseComment();
    }

    throw new UnableToParseAnExpressionError(this.token.line, this.token.column, this.token.type);
  }

  parseFill() {
    return new Fill();
  }

  parseComment() {
    return new Comment(this.token.value);
  }

  discardNewlines() {
    while (this.token.type === TokenType.Newline) {
      this.nextToken();
    }
  }

  accept(tokenType) {
    if (tokenType !== TokenType.Newline) {
      this.discardNewlines();
    }

    if (tokenType !== TokenType.EndOfInput && this.token.type === Token.EndOfInput) {
      return false;
    }

    return this.token.type === tokenType;
  }

  expect(tokenType) {
    if (tokenType !== TokenType.Newline) {
      this.discardNewlines();
    }

    let line = this.token.line;
    let column = this.token.column;

    if (tokenType !== TokenType.EndOfInput && this.token.type === TokenType.EndOfInput) {
      throw new UnexpectedTokenError(line, column, tokenType, TokenType.EndOfInput);
    }

    if (this.token.type !== tokenType) {
      throw new UnexpectedTokenError(line, column, tokenType, this.token.type);
    }

    this.nextToken();
  }

  parseLoop() {
    let line = this.token.line;
    let column = this.token.column;

    this.expect(TokenType.StartLoop);
    this.expect(TokenType.While);

    let whileStmt = new While();

    whileStmt.condition = this.parseCondition();

    try {
      whileStmt.body = this.parseBlock(TokenType.EndLoop);
    } catch (e) {
      if (e instanceof UnexpectedEndOfInputError) {
        throw new UnexpectedWhileEndOfInputError(line, column);
      }

      throw e;
    }

    this.expect(TokenType.EndLoop);

    return whileStmt;
  }

  parseIfStmt() {
    let line = this.token.line;
    let column = this.token.column;

    this.expect(TokenType.If);

    let ifStmt = new If();

    ifStmt.condition = this.parseCondition();

    this.expect(TokenType.Then);

    try {
      ifStmt.thenBranch = this.parseBlock(TokenType.End, TokenType.Else);
    } catch (e) {
      if (e instanceof UnexpectedEndOfInputError) {
        throw new UnexpectedIfEndOfInputError(line, column, TokenType.If);
      }

      throw e;
    }

    if (this.accept(TokenType.Else)) {
      let line = this.token.line;
      let column = this.token.column;
      this.expect(TokenType.Else);

      try {
        ifStmt.elseBranch = this.parseBlock(TokenType.End);
      } catch (e) {
        if (e instanceof UnexpectedEndOfInputError) {
          throw new UnexpectedIfEndOfInputError(line, column, TokenType.Else);
        }

        throw e;
      }

    }

    this.expect(TokenType.End);

    return ifStmt;
  }

  acceptsMove() {
    return this.accept(TokenType.MoveUp) || this.accept(TokenType.MoveDown) ||
      this.accept(TokenType.MoveLeft) || this.accept(TokenType.MoveRight);
  };

  parseMove() {
    switch (this.token.type) {
      case TokenType.MoveUp:
        return new Move('up');
      case TokenType.MoveDown:
        return new Move('down');
      case TokenType.MoveLeft:
        return new Move('left');
      case TokenType.MoveRight:
        return new Move('right');
    }
  };

  acceptsCheck() {
    return this.accept(TokenType.CheckTop) || this.accept(TokenType.CheckBottom) ||
      this.accept(TokenType.CheckLeft) || this.accept(TokenType.CheckRight);
  };

  acceptOneOf(...tokenTypes) {
    if (tokenTypes.indexOf(TokenType.Newline) < 0) {
      this.discardNewlines();
    }

    let type = this.token.type;

    if (type === TokenType.EndOfInput) {
      return false;
    }

    return tokenTypes.indexOf(type) >= 0;
  }

  parseCondition() {
    let lst = this.parseAndCond();

    while (this.accept(TokenType.Or)) {
      this.expect(TokenType.Or);

      let rst = this.parseAndCond();

      lst = new Or(lst, rst);
    }

    return lst;
  }

  parseAndCond() {
    let lst = this.parseBoolCond();

    while (this.accept(TokenType.And)) {
      this.expect(TokenType.And);

      let rst = this.parseBoolCond();

      lst = new And(lst, rst);
    }

    return lst;
  }

  parseBoolCond() {
    if (!this.acceptOneOf(TokenType.Not, TokenType.OpenParen,
        TokenType.CheckTop, TokenType.CheckBottom, TokenType.CheckLeft, TokenType.CheckRight)) {
      throw new UnexpectedTokenError(this.token.line, this.token.column, this.token.type);
    }

    if (this.accept(TokenType.Not)) {
      this.expect(TokenType.Not);

      let node = this.parseBoolCond();

      return new Not(node);
    }

    if (this.accept(TokenType.OpenParen)) {
      this.expect(TokenType.OpenParen);

      let node = this.parseCondition();

      this.expect(TokenType.CloseParen);

      return node;
    }

    return this.parseCheckStmt()
  }

  parseCheckStmt() {
    let node = null;

    if (this.accept(TokenType.CheckTop)) {
      this.expect(TokenType.CheckTop);

      node = new Check('top');
    }

    if (this.accept(TokenType.CheckBottom)) {
      this.expect(TokenType.CheckBottom);

      node = new Check('bottom');
    }

    if (this.accept(TokenType.CheckLeft)) {
      this.expect(TokenType.CheckLeft);

      node = new Check('left');
    }

    if (this.accept(TokenType.CheckRight)) {
      this.expect(TokenType.CheckRight);

      node = new Check('right');
    }

    this.expect(TokenType.CheckLiteral);

    return node;
  };
};

class Not {
  constructor(cond) {
    this.cond = cond;
  }

  eval(board) {
    return !this.cond.eval(board);
  }
}

class And {
  constructor(lst, rst) {
    this.lst = lst;
    this.rst = rst;
  }

  eval(board) {
    return this.lst.eval(board) && this.rst.eval(board);
  }
}

class Or {
  constructor(lst, rst) {
    this.lst = lst;
    this.rst = rst;
  }

  eval(board) {
    return this.lst.eval(board) || this.rst.eval(board);
  }
}

class Check {
  constructor(direction) {
    this.direction = direction;
  }

  eval(board) {
    switch (this.direction) {
      case 'top':
        return board.checkTop();
      case 'bottom':
        return board.checkBottom();
      case 'left':
        return board.checkLeft();
      case 'right':
        return board.checkRight();
    }
  }
}

class Move {
  constructor(direction) {
    this.direction = direction;
  }

  eval(board) {
    switch (this.direction) {
      case 'up':
        return board.moveUp();
      case 'down':
        return board.moveDown();
      case 'left':
        return board.moveLeft();
      case 'right':
        return board.moveRight();
    }
  }
}

class Fill {
  constructor() {}

  eval(board) {
    board.fill();
  }
}

class If {
  constructor(condition, thenBranch, elseBranch) {
    this.condition = condition;
    this.thenBranch = thenBranch;
    this.elseBranch = elseBranch;
  }

  eval(board) {
    if (this.condition.eval(board)) {
      this.thenBranch.eval(board);
    } else {
      if (!this.elseBranch) {
        return;
      }

      this.elseBranch.eval(board);
    }
  }
}

class Block {
  constructor(expressions = []) {
    this.expressions = expressions;
  }

  add(expression) {
    this.expressions.push(expression);
  }

  eval(board) {
    let size = this.expressions.length;

    for (let i = 0; i < size; ++i) {
      this.expressions[i].eval(board);
    }
  }
}

class While {
  constructor(condition, body) {
    this.condition = condition;
    this.body = body;
  }

  eval(board) {
    while (this.condition.eval(board) === true) {
      this.body.eval(board);
    }
  }
}

class Comment {
  constructor(value) {
    this.value = value;
  }

  eval(board) {}
}

class Board {
  constructor(grid, row, col) {
    this.grid = grid;
    this.n = grid.length;
    this.m = grid[0].length;
    this.row = row;
    this.col = col;
    this.moveListeners = [];
  }
  
  addMoveListener(listener) {
    this.moveListeners.push(listener);
  }
  
  async fireMoveEvent(cb) {
    for (let i = 0; i < this.moveListeners.length; i++) {
        await this.moveListeners[i](this.grid, this.row, this.col);
    }
  }

  isValid(row, col) {
    let st = row < 0 || row >= this.n || col < 0 || col >= this.m;

    return !st;
  }

  async move(row, col) {
    if (!this.isValid(row, col)) {
      throw new Error(`it's not possible to move to the position (${row},${col}).`);
    }

    this.row = row;
    this.col = col;
    
    await this.fireMoveEvent();
  }

  moveUp() {
    this.move(this.row - 1, this.col);
  }

  moveDown() {
    this.move(this.row + 1, this.col);
  }

  moveLeft() {
    this.move(this.row, this.col - 1);
  }

  moveRight() {
    this.move(this.row, this.col + 1);
  }

  checkTop() {
    let valid = this.isValid(this.row - 1, this.col);

    if (!valid) {
      return false;
    }

    // 1 means the cell has a wall on the top
    let hasWall = this.grid[this.row][this.col][1] === '1';

    return !hasWall;
  }

  checkBottom() {
    let valid = this.isValid(this.row + 1, this.col);

    if (!valid) {
      return false;
    }

    // 3 means the cell has a wall on the bottom
    let hasWall = this.grid[this.row][this.col][3] === '1';

    return !hasWall;
  }

  checkLeft() {
    let valid = this.isValid(this.row, this.col - 1);

    if (!valid) {
      return false;
    }

    // 4 means the cell has a wall on the left
    let hasWall = this.grid[this.row][this.col][4] === '1';

    return !hasWall;
  }

  checkRight() {
    let valid = this.isValid(this.row, this.col + 1);

    if (!valid) {
      return false;
    }

    // 2 means the cell has a wall on the righ
    let hasWall = this.grid[this.row][this.col][2] === '1';

    return !hasWall;
  }

  isFilled(row, col) {
    return this.grid[row][col][0] === '1';
  }

  fill() {
    this.grid[this.row][this.col] = '1' + this.grid[this.row][this.col].substring(1);
  }

  log() {
    console.log(this.grid);
    console.log(this.row, this.col);
  }
}

function sleep(ms) {
    return new Promise(resolve => setTimeout(resolve, ms));
}


// let grid = Array(10).fill().map(() => Array(10).fill('O'));
/* let grid = [
  ['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O', 'O', 'Z', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O', 'O', 'Z', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O', 'O', 'Z', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O', 'O', 'Z', 'O', 'O', 'O'],
  ['O', 'S', 'O', 'O', 'O', 'O', 'Z', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O']
]; */

let grid = [
  ['00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000'],
  ['00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000'],
  ['00000', '00000', '00010', '00010', '00010', '00010', '00000', '00000', '00000', '00000'],
  ['00000', '00000', '01000', '01000', '01000', '01100', '00001', '00000', '00000', '00000'],
  ['00000', '00000', '00000', '00000', '00000', '00100', '00001', '00000', '00000', '00000'],
  ['00000', '00000', '00000', '00000', '00000', '00100', '00001', '00000', '00000', '00000'],
  ['00000', '00000', '00000', '00000', '00000', '00100', '00001', '00000', '00000', '00000'],
  ['00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000'],
  ['00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000'],
  ['00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000', '00000']
];

let text = `
нц пока справа свободно
	вправо
кц

нц пока (не справа свободно) и (сверху свободно)
	закрасить
  вверх
кц

нц пока не сверху свободно
	закрасить
  влево
кц
`


let row = 0,
  col = 0;
for (let i = 0; i < grid.length; ++i) {
  for (let j = 0; j < grid[0].length; ++j) {
    if (grid[i][j].length == 6 && grid[i][j][0] === 'S') {
      row = i;
      col = j;
      grid[i][j] = grid[i][j].substring(1);
    }
  }
}

row = 6;
col = 1;
let board = new Board(grid, row, col);
board.addMoveListener(async (grid, row, col) => {
    return new Promise((resolve, reject) => {
      setTimeout(() => {
          console.log(row, col);
          resolve();
      }, 1000);
    });
});

let lex = new Lexer(text);
let parser = new Parser(lex);

/* let i = 0;
lex.nextToken();
while (lex.token.type !== TokenType.EndOfInput) {
  let t = lex.token;
  console.log(t);
  lex.nextToken();
  i++;
  
  if (i > 1000)
    break;
} */





try {
  let block = parser.parse();
  
  (async () => {
     await block.eval(board);
  })();
} catch (e) {
  let errorMsg = l10n(e);

  if (!errorMsg) {
    throw e;
  }

  console.error(errorMsg);
}