Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "tparser.h"
Toshihiro Shimizu 890ddd
#include "tgrammar.h"
Toshihiro Shimizu 890ddd
#include "ttokenizer.h"
Toshihiro Shimizu 890ddd
#include "tutil.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include <iostream></iostream>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
namespace TSyntax {
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
// RunningPattern
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class RunningPattern {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  std::vector<token> m_tokens;</token>
Shinya Kitaoka 120a6e
  const Pattern *m_pattern;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  RunningPattern(const Pattern *pattern) : m_pattern(pattern) {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  int getPriority() const { return m_pattern->getPriority(); }
Shinya Kitaoka 120a6e
  bool isFinished(const Token &token) const {
Shinya Kitaoka 120a6e
    return m_pattern->isFinished(m_tokens, token);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  bool isComplete(const Token &token) const {
Shinya Kitaoka 120a6e
    return m_pattern->isComplete(m_tokens, token);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  bool expressionExpected() const {
Shinya Kitaoka 120a6e
    return m_pattern->expressionExpected(m_tokens);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  bool matchToken(const Token &token) const {
Shinya Kitaoka 120a6e
    return m_pattern->matchToken(m_tokens, token);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  void advance() {
Shinya Kitaoka 120a6e
    assert(!isFinished(Token()));
Shinya Kitaoka 120a6e
    m_tokens.push_back(Token());
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  void advance(const Token &token) {
Shinya Kitaoka 120a6e
    assert(!isFinished(token));
Shinya Kitaoka 120a6e
    m_tokens.push_back(token);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  TokenType getTokenType(const Token &token) const {
Shinya Kitaoka 120a6e
    return m_pattern->getTokenType(m_tokens, token);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void createNode(Calculator *calc, std::vector<calculatornode *=""> &stack) {</calculatornode>
Shinya Kitaoka 120a6e
    m_pattern->createNode(calc, stack, m_tokens);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
// Parser::Imp
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class Parser::Imp {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  const Grammar *m_grammar;
Shinya Kitaoka 120a6e
  Tokenizer m_tokenizer;
Shinya Kitaoka 120a6e
  std::string m_errorString;
Shinya Kitaoka 120a6e
  bool m_isValid;
Shinya Kitaoka 120a6e
  Calculator *m_calculator;
Shinya Kitaoka 120a6e
  std::vector<runningpattern> m_patternStack;</runningpattern>
Shinya Kitaoka 120a6e
  std::vector<calculatornode *=""> m_nodeStack;</calculatornode>
Shinya Kitaoka 120a6e
  std::vector<syntaxtoken> m_syntaxTokens;</syntaxtoken>
Shinya Kitaoka 120a6e
  Grammar::Position m_position;
Shinya Kitaoka 120a6e
  // Pattern *m_lastPattern;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  Imp(const Grammar *grammar)
Shinya Kitaoka 120a6e
      : m_grammar(grammar)
Shinya Kitaoka 120a6e
      , m_errorString("")
Shinya Kitaoka 120a6e
      , m_isValid(false)
Shinya Kitaoka 120a6e
      , m_calculator(0)
Shinya Kitaoka 120a6e
      , m_position(Grammar::ExpressionStart) {}
Shinya Kitaoka 120a6e
  ~Imp() {
Shinya Kitaoka 120a6e
    clearPointerContainer(m_nodeStack);
Shinya Kitaoka 120a6e
    delete m_calculator;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void pushSyntaxToken(TokenType type);
Shinya Kitaoka 120a6e
  bool parseExpression(bool checkOnly);
Shinya Kitaoka 120a6e
  void flushPatterns(int minPriority, int minIndex, bool checkOnly);
Shinya Kitaoka 120a6e
  bool checkSyntax(std::vector<syntaxtoken> &tokens);</syntaxtoken>
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
// Parser
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
Parser::Parser(const Grammar *grammar) : m_imp(new Imp(grammar)) {}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
Parser::~Parser() {}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void Parser::Imp::flushPatterns(int minPriority, int minIndex, bool checkOnly) {
Shinya Kitaoka 120a6e
  while ((int)m_patternStack.size() > minIndex &&
Shinya Kitaoka 120a6e
         m_patternStack.back().getPriority() >= minPriority) {
Shinya Kitaoka 120a6e
    if (!checkOnly) m_patternStack.back().createNode(m_calculator, m_nodeStack);
Shinya Kitaoka 120a6e
    m_patternStack.pop_back();
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void Parser::Imp::pushSyntaxToken(TokenType type) {
Shinya Kitaoka 120a6e
  SyntaxToken syntaxToken;
Shinya Kitaoka 120a6e
  Token token          = m_tokenizer.getToken();
Shinya Kitaoka 120a6e
  syntaxToken.m_pos    = token.getPos();
Shinya Kitaoka 120a6e
  syntaxToken.m_length = token.getPos1() - token.getPos() + 1;
Shinya Kitaoka 120a6e
  syntaxToken.m_type   = type;
Shinya Kitaoka 120a6e
  m_syntaxTokens.push_back(syntaxToken);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
bool Parser::Imp::parseExpression(bool checkOnly) {
Shinya Kitaoka 120a6e
  if (!m_grammar) return false;
Shinya Kitaoka 120a6e
  int stackMinIndex          = m_patternStack.size();
Shinya Kitaoka 120a6e
  int count                  = 0;
Shinya Kitaoka 120a6e
  Grammar::Position position = Grammar::ExpressionStart;
Shinya Kitaoka 120a6e
  m_position                 = position;
Shinya Kitaoka 120a6e
  // warning: parseExpression() is called recursively. m_position is used after
Shinya Kitaoka 120a6e
  // parseExpression()
Shinya Kitaoka 120a6e
  // for diagnostic and suggestions. position is used in the actual parsing
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  bool expressionExpected = true;
Shinya Kitaoka 120a6e
  while (!m_tokenizer.eos()) {
Shinya Kitaoka 120a6e
    // token, position -> pattern
Shinya Kitaoka 120a6e
    const Pattern *pattern =
Shinya Kitaoka 120a6e
        m_grammar->getPattern(position, m_tokenizer.getToken());
Shinya Kitaoka 120a6e
    if (!pattern) {
Shinya Kitaoka 120a6e
      // no pattern found for the next token
Shinya Kitaoka 120a6e
      if (position == Grammar::ExpressionEnd) {
Shinya Kitaoka 120a6e
        // already found an expression
Shinya Kitaoka 120a6e
        flushPatterns(-1, stackMinIndex, checkOnly);
Shinya Kitaoka 120a6e
        return true;
Shinya Kitaoka 120a6e
      } else {
Shinya Kitaoka 120a6e
        // syntax error : expression not found
Shinya Kitaoka 120a6e
        if (checkOnly) pushSyntaxToken(UnexpectedToken);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        m_errorString = "Unexpected token";
Shinya Kitaoka 120a6e
        return false;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    // pattern found: start scanning it
Shinya Kitaoka 120a6e
    RunningPattern runningPattern(pattern);
Shinya Kitaoka 120a6e
    if (position ==
Shinya Kitaoka 120a6e
        Grammar::ExpressionEnd)  // patterns of the form "<expr> ...."</expr>
Shinya Kitaoka 120a6e
      runningPattern.advance();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // eat the first token
Shinya Kitaoka 120a6e
    if (checkOnly)
Shinya Kitaoka 120a6e
      pushSyntaxToken(runningPattern.getTokenType(m_tokenizer.getToken()));
Shinya Kitaoka 120a6e
    runningPattern.advance(m_tokenizer.getToken());
Shinya Kitaoka 120a6e
    m_tokenizer.nextToken();
Shinya Kitaoka 120a6e
    expressionExpected = false;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    while (!runningPattern.isFinished(m_tokenizer.getToken())) {
Shinya Kitaoka 120a6e
      if (runningPattern.expressionExpected()) {
Shinya Kitaoka 120a6e
        // expression expected
Shinya Kitaoka 120a6e
        runningPattern.advance();
Shinya Kitaoka 120a6e
        if (runningPattern.isFinished(m_tokenizer.getToken())) {
Shinya Kitaoka 120a6e
          // pattern ended with an expression
Shinya Kitaoka 120a6e
          expressionExpected = true;
Shinya Kitaoka 120a6e
          break;
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
        // parse a sub expression
Shinya Kitaoka 120a6e
        if (!parseExpression(checkOnly)) {
Shinya Kitaoka 120a6e
          return false;
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
      } else {
Shinya Kitaoka 120a6e
        // "terminal" expected
Shinya Kitaoka 120a6e
        if (m_tokenizer.eos()) {
Shinya Kitaoka 120a6e
          // EOS
Shinya Kitaoka 120a6e
          if (runningPattern.isComplete(Token())) break;
Shinya Kitaoka 120a6e
          if (checkOnly) pushSyntaxToken(Eos);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
          m_errorString = "Uncompleted syntax";
Shinya Kitaoka 120a6e
          return false;
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
        if (!runningPattern.matchToken(m_tokenizer.getToken())) {
Shinya Kitaoka 120a6e
          // token mismatch
Shinya Kitaoka 120a6e
          if (runningPattern.isComplete(m_tokenizer.getToken())) break;
Shinya Kitaoka 120a6e
          if (checkOnly) pushSyntaxToken(Mismatch);
Shinya Kitaoka 120a6e
          m_errorString = "Syntax error";
Shinya Kitaoka 120a6e
          return false;
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
        // token matched
Shinya Kitaoka 120a6e
        if (checkOnly)
Shinya Kitaoka 120a6e
          pushSyntaxToken(runningPattern.getTokenType(m_tokenizer.getToken()));
Shinya Kitaoka 120a6e
        runningPattern.advance(m_tokenizer.getToken());
Shinya Kitaoka 120a6e
        m_tokenizer.nextToken();
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // pattern ended
Shinya Kitaoka 120a6e
    if (expressionExpected) {
Shinya Kitaoka 120a6e
      // pattern terminated with an expression
Shinya Kitaoka 120a6e
      if (position == Grammar::ExpressionEnd) {
Shinya Kitaoka 120a6e
        // "E op . E"
Shinya Kitaoka 120a6e
        flushPatterns(runningPattern.getPriority(), stackMinIndex, checkOnly);
Shinya Kitaoka 120a6e
        m_patternStack.push_back(runningPattern);
Shinya Kitaoka 120a6e
      } else {
Shinya Kitaoka 120a6e
        // "op . E"
Shinya Kitaoka 120a6e
        m_patternStack.push_back(runningPattern);
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
      m_position = position = Grammar::ExpressionStart;
Shinya Kitaoka 120a6e
    } else {
Shinya Kitaoka 120a6e
      // pattern terminates with a keyword
Shinya Kitaoka 120a6e
      if (position == Grammar::ExpressionEnd) {
Shinya Kitaoka 120a6e
        // "E op ."
Shinya Kitaoka 120a6e
        flushPatterns(runningPattern.getPriority(), stackMinIndex, checkOnly);
Shinya Kitaoka 120a6e
      } else {
Shinya Kitaoka 120a6e
        // "leaf .", "f(E) .", "(E) ."
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
      if (!checkOnly) runningPattern.createNode(m_calculator, m_nodeStack);
Shinya Kitaoka 120a6e
      count++;
Shinya Kitaoka 120a6e
      m_position = position = Grammar::ExpressionEnd;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  if (count == 0 || expressionExpected) {
Shinya Kitaoka 120a6e
    m_errorString = "Expression expected";
Shinya Kitaoka 120a6e
    return false;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  flushPatterns(-1, stackMinIndex, checkOnly);
Shinya Kitaoka 120a6e
  return true;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
Calculator *Parser::parse(std::string text) {
Shinya Kitaoka 120a6e
  m_imp->m_tokenizer.setBuffer(text);
Shinya Kitaoka 120a6e
  clearPointerContainer(m_imp->m_nodeStack);
Shinya Kitaoka 120a6e
  m_imp->m_errorString = "";
Shinya Kitaoka 120a6e
  m_imp->m_isValid     = false;
Shinya Kitaoka 120a6e
  m_imp->m_calculator  = new Calculator();
Shinya Kitaoka 120a6e
  bool ret             = m_imp->parseExpression(false);
Shinya Kitaoka 120a6e
  if (ret && !m_imp->m_nodeStack.empty()) {
Shinya Kitaoka 120a6e
    m_imp->m_calculator->setRootNode(m_imp->m_nodeStack.back());
Shinya Kitaoka 120a6e
    m_imp->m_nodeStack.pop_back();
Shinya Kitaoka 120a6e
    m_imp->m_isValid = true;
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    delete m_imp->m_calculator;
Shinya Kitaoka 120a6e
    m_imp->m_calculator = 0;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  clearPointerContainer(m_imp->m_nodeStack);
Shinya Kitaoka 120a6e
  Calculator *calculator = m_imp->m_calculator;
Shinya Kitaoka 120a6e
  m_imp->m_calculator    = 0;
Shinya Kitaoka 120a6e
  return calculator;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
Parser::SyntaxStatus Parser::checkSyntax(std::vector<syntaxtoken> &tokens,</syntaxtoken>
Shinya Kitaoka 120a6e
                                         std::string text) {
Shinya Kitaoka 120a6e
  m_imp->m_tokenizer.setBuffer(text);
Shinya Kitaoka 120a6e
  if (m_imp->m_tokenizer.eos()) return Incomplete;
Shinya Kitaoka 120a6e
  bool ret = m_imp->parseExpression(true);
Shinya Kitaoka 120a6e
  tokens   = m_imp->m_syntaxTokens;
Shinya Kitaoka 120a6e
  if (ret && m_imp->m_tokenizer.eos()) return Correct;
Shinya Kitaoka 120a6e
  if (tokens.empty()) return Incomplete;
Shinya Kitaoka 120a6e
  SyntaxToken &lastToken = tokens.back();
Shinya Kitaoka 120a6e
  if (lastToken.m_type == Eos) return Incomplete;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  int k = lastToken.m_pos + lastToken.m_length;
Shinya Kitaoka 120a6e
  if (k >= (int)text.length()) {
Shinya Kitaoka 120a6e
    if (lastToken.m_type < Unknown) {
Shinya Kitaoka 120a6e
      lastToken.m_type = Unknown;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    return ExtraIgnored;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  SyntaxToken extraIgnored;
Shinya Kitaoka 120a6e
  extraIgnored.m_type   = Unknown;
Shinya Kitaoka 120a6e
  extraIgnored.m_pos    = k;
Shinya Kitaoka 120a6e
  extraIgnored.m_length = text.length() - k;
Shinya Kitaoka 120a6e
  tokens.push_back(extraIgnored);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return Error;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void Parser::getSuggestions(Grammar::Suggestions &suggestions,
Shinya Kitaoka 120a6e
                            std::string text) {
Shinya Kitaoka 120a6e
  std::vector<syntaxtoken> tokens;</syntaxtoken>
Shinya Kitaoka 120a6e
  Parser::SyntaxStatus status = checkSyntax(tokens, text);
Shinya Kitaoka 120a6e
  suggestions.clear();
Shinya Kitaoka 120a6e
  if (status == Correct || status == Incomplete || status == ExtraIgnored)
Shinya Kitaoka 120a6e
    m_imp->m_grammar->getSuggestions(suggestions, m_imp->m_position);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
std::string Parser::getCurrentPatternString(std::string text) {
Shinya Kitaoka 120a6e
  return "ohime";
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
bool Parser::isValid() const { return m_imp->m_isValid; }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
std::string Parser::getText() const { return m_imp->m_tokenizer.getBuffer(); }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
std::string Parser::getError() const { return m_imp->m_errorString; }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
std::pair<int, int=""> Parser::getErrorPos() const {</int,>
Shinya Kitaoka 120a6e
  if (m_imp->m_errorString == "") return std::make_pair(0, -1);
Shinya Kitaoka 120a6e
  Token token = m_imp->m_tokenizer.getToken();
Shinya Kitaoka 120a6e
  return std::make_pair(token.getPos(), token.getPos1());
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
}  // namespace TSyntax