Guest User

LALR

a guest
Dec 16th, 2012
316
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.63 KB | None | 0 0
  1. #include <cctype>
  2. #include <cstdarg>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <iostream>
  6. #include <sstream>
  7. #include <stack>
  8. #include <vector>
  9. #include <string>
  10.  
  11. struct Token{
  12.     enum TokenType{
  13.         null=0,
  14.         END=1,
  15.         INTEGER='0',
  16.         PLUS='+',
  17.         MINUS='-',
  18.         MUL='*',
  19.         DIV='/',
  20.         POW='^',
  21.         LPAREN='(',
  22.         RPAREN=')',
  23.         expr=128
  24.     } type;
  25.     double intValue;
  26.     Token(TokenType type=END):type(type),intValue(0){}
  27.     Token(long val):type(INTEGER),intValue(val){}
  28.     Token(char character){
  29.         this->type=(TokenType)character;
  30.     }
  31. };
  32.  
  33. struct Rule{
  34.     Token reduces_to;
  35.     std::vector<Token> constraints;
  36.     Token lookahead;
  37.     Rule(const Token &to,const Token &la){
  38.         this->reduces_to=to;
  39.         this->lookahead=la;
  40.     }
  41.     bool matches(const std::vector<Token> &stack,const Token &lookahead){
  42.         if (stack.size()<this->constraints.size() ||
  43.                 this->lookahead.type!=Token::null && this->lookahead.type!=lookahead.type)
  44.             return 0;
  45.         const Token *array=&stack[stack.size()-this->constraints.size()];
  46.         for (unsigned a=0,size=this->constraints.size();a<size;a++)
  47.             if (array[a].type!=this->constraints[a].type)
  48.                 return 0;
  49.         return 1;
  50.     }
  51.     Rule operator<<(const Token::TokenType &tt) const{
  52.         Rule ret=*this;
  53.         ret.constraints.push_back(tt);
  54.         return ret;
  55.     }
  56. };
  57.  
  58. class Parser{
  59.     std::stringstream stream;
  60.     std::vector<Token> stack;
  61.     bool result;
  62.     std::vector<Rule> rules;
  63.     Token read(){
  64.         char character;
  65.         while (!this->stream.eof() && isspace(character=this->stream.peek()))
  66.             this->stream.get();
  67.         if (this->stream.eof())
  68.             return Token::END;
  69.         character=this->stream.peek();
  70.         if (isdigit(character)){
  71.             std::string str;
  72.             str.push_back(this->stream.get());
  73.             while (isdigit(this->stream.peek()))
  74.                 str.push_back(this->stream.get());
  75.             long temp=atol(str.c_str());
  76.             return temp;
  77.         }
  78.         return (char)this->stream.get();
  79.     }
  80.     bool reduce(const Token &lookahead){
  81.         long rule_index=-1;
  82.         unsigned max=0;
  83.         for (unsigned a=0;a<this->rules.size();a++){
  84.             if (this->rules[a].matches(this->stack,lookahead) && this->rules[a].constraints.size()>max){
  85.                 rule_index=a;
  86.                 max=this->rules[a].constraints.size();
  87.             }
  88.         }
  89.         if (rule_index<0 || this->rules[rule_index].reduces_to.type==Token::null)
  90.             return 0;
  91.         Rule &rule=this->rules[rule_index];
  92.         Token new_token(rule.reduces_to);
  93.         Token *redex=&this->stack[this->stack.size()-rule.constraints.size()];
  94.         switch (rule_index){
  95.             case 0: //expr <- INTEGER
  96.                 new_token.intValue=redex[0].intValue;
  97.                 break;
  98.             case 1: //expr <- '(' expr ')'
  99.             case 2: //expr <- '+' expr
  100.                 new_token.intValue=redex[1].intValue;
  101.                 break;
  102.             case 3: //expr <- '-' expr
  103.                 new_token.intValue=-redex[1].intValue;
  104.                 break;
  105.             case 4: //impossible
  106.             case 5: //expr <- expr '^' expr
  107.                 new_token.intValue=pow((double)redex[0].intValue,(double)redex[2].intValue);
  108.                 break;
  109.             case 6: //impossible
  110.             case 7: //expr <- expr '*' expr
  111.                 new_token.intValue=redex[0].intValue*redex[2].intValue;
  112.                 break;
  113.             case 8: //impossible
  114.             case 9: //expr <- expr '/' expr
  115.                 new_token.intValue=redex[0].intValue/redex[2].intValue;
  116.                 break;
  117.             case 10: //impossible
  118.             case 11: //impossible
  119.             case 12: //impossible
  120.             case 13: //expr <- expr '+' expr
  121.                 new_token.intValue=redex[0].intValue+redex[2].intValue;
  122.                 break;
  123.             case 14: //impossible
  124.             case 15: //impossible
  125.             case 16: //impossible
  126.             case 17: //expr <- expr '-' expr
  127.                 new_token.intValue=redex[0].intValue-redex[2].intValue;
  128.                 break;
  129.         }
  130.         for (unsigned a=0;a<rule.constraints.size();a++)
  131.             this->stack.pop_back();
  132.         this->stack.push_back(new_token);
  133.         return 1;
  134.     }
  135.     bool run_state(){
  136.         Token next_token=this->read();
  137.         while (this->reduce(next_token));
  138.         switch (next_token.type){
  139.             case Token::END:
  140.                 this->result=(this->stack.size()==1);
  141.                 return 0;
  142.             case Token::INTEGER:
  143.             case Token::PLUS:
  144.             case Token::MINUS:
  145.             case Token::MUL:
  146.             case Token::DIV:
  147.             case Token::RPAREN:
  148.             case Token::LPAREN:
  149.             case Token::POW:
  150.                 this->stack.push_back(next_token);
  151.                 return 1;
  152.             default:
  153.                 this->result=0;
  154.                 return 0;
  155.         }
  156.     }
  157.     void initializeRules(){
  158.         this->rules.clear();
  159.         /*rule 0*/  this->rules.push_back(Rule(Token::expr,Token::null)<<Token::INTEGER);
  160.                    
  161.         /*rule 1*/  this->rules.push_back(Rule(Token::expr,Token::null)<<Token::LPAREN<<Token::expr<<Token::RPAREN);
  162.                    
  163.         /*rule 2*/  this->rules.push_back(Rule(Token::expr,Token::null)<<Token::PLUS<<Token::expr);
  164.         /*rule 3*/  this->rules.push_back(Rule(Token::expr,Token::null)<<Token::MINUS<<Token::expr);
  165.                    
  166.         /*rule 4*/  this->rules.push_back(Rule(Token::null,Token::POW) <<Token::expr<<Token::POW<<Token::expr);
  167.         /*rule 5*/  this->rules.push_back(Rule(Token::expr,Token::null)<<Token::expr<<Token::POW<<Token::expr);
  168.                    
  169.         /*rule 6*/  this->rules.push_back(Rule(Token::null,Token::POW) <<Token::expr<<Token::MUL<<Token::expr);
  170.         /*rule 7*/  this->rules.push_back(Rule(Token::expr,Token::null)<<Token::expr<<Token::MUL<<Token::expr);
  171.                    
  172.         /*rule 8*/  this->rules.push_back(Rule(Token::null,Token::POW) <<Token::expr<<Token::DIV<<Token::expr);
  173.         /*rule 9*/  this->rules.push_back(Rule(Token::expr,Token::null)<<Token::expr<<Token::DIV<<Token::expr);
  174.  
  175.         /*rule 10*/ this->rules.push_back(Rule(Token::null,Token::POW) <<Token::expr<<Token::PLUS<<Token::expr);
  176.         /*rule 11*/ this->rules.push_back(Rule(Token::null,Token::MUL) <<Token::expr<<Token::PLUS<<Token::expr);
  177.         /*rule 12*/ this->rules.push_back(Rule(Token::null,Token::DIV) <<Token::expr<<Token::PLUS<<Token::expr);
  178.         /*rule 13*/ this->rules.push_back(Rule(Token::expr,Token::null)<<Token::expr<<Token::PLUS<<Token::expr);
  179.                    
  180.         /*rule 14*/ this->rules.push_back(Rule(Token::null,Token::POW) <<Token::expr<<Token::MINUS<<Token::expr);
  181.         /*rule 15*/ this->rules.push_back(Rule(Token::null,Token::MUL) <<Token::expr<<Token::MINUS<<Token::expr);
  182.         /*rule 16*/ this->rules.push_back(Rule(Token::null,Token::DIV) <<Token::expr<<Token::MINUS<<Token::expr);
  183.         /*rule 17*/ this->rules.push_back(Rule(Token::expr,Token::null)<<Token::expr<<Token::MINUS<<Token::expr);
  184.     }
  185. public:
  186.     Parser(const std::string &str)
  187.             :stream(str){
  188.         this->result=0;
  189.         this->initializeRules();
  190.     }
  191.     bool eval(double &res){
  192.         while (this->run_state());
  193.         if (this->result)
  194.             res=this->stack.front().intValue;
  195.         else
  196.             this->stack.clear();
  197.         return this->result;
  198.     }
  199. };
  200.  
  201. int main(){
  202.     while (1){
  203.         std::string line;
  204.         std::getline(std::cin,line);
  205.         Parser evaluator(line);
  206.         double res=0;
  207.         std::cout <<(evaluator.eval(res)?"ACCEPT":"ABORT")<<std::endl;
  208.         std::cout <<res<<std::endl;
  209.     }
  210.     return 0;
  211. }
Advertisement
Add Comment
Please, Sign In to add comment