SHARE
TWEET

TinyExpressionParser.cpp

a guest Nov 4th, 2015 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <assert.h>
  2. #include <stdint.h>
  3. #include <vector>
  4. #include <setjmp.h>
  5. #include <stdio.h>
  6.  
  7. typedef char token_e;
  8.  
  9. namespace {
  10. // return the precedence of an operator
  11. int op_prec(token_e o) {
  12.     switch (o) {
  13.     case ('&'): return  1;
  14.     case ('+'):
  15.     case ('-'): return  2;
  16.     case ('*'):
  17.     case ('/'): return  3;
  18.     default:    return  0;
  19.     }
  20. }
  21.  
  22. // return true if token is an operator
  23. bool is_op(token_e o) {
  24.     return op_prec(o) != 0;
  25. }
  26.  
  27. // return true if token is a variable identifier
  28. bool is_var(token_e o) {
  29.     return (o>='A' && o<='Z') || (o>='a' && o<='z');
  30. }
  31.  
  32. // return true if token is a numeric literal
  33. bool is_num(token_e o) {
  34.     return (o>='0' && o<='9');
  35. }
  36. } // namespace {}
  37.  
  38. struct parser_t {
  39.  
  40.     std::vector<token_e> op_;
  41.     const char * s_;
  42.     jmp_buf error_buf;
  43.  
  44.     void error() {
  45.         longjmp (error_buf, 1);
  46.     }
  47.  
  48.     parser_t(const char * stream)
  49.         : op_()
  50.         , s_(stream)
  51.     {}
  52.  
  53.     char found_op () { return (is_op  (*s_)) ? *(s_++) : 0; }
  54.     char found_var() { return (is_var (*s_)) ? *(s_++) : 0; }
  55.     char found_num() { return (is_num (*s_)) ? *(s_++) : 0; }
  56.  
  57.     // check for specific token in the token stream
  58.     bool found(char ch) {
  59.         if (*s_ == ch) {
  60.             s_++;
  61.             return true;
  62.         }
  63.         return false;
  64.     }
  65.  
  66.     // unconditionally expect a token in the token stream
  67.     void expect(char ch) {
  68.         if (*(s_++) != ch) {
  69.             printf ("\nexpected '%c'\n", ch);
  70.             error ();
  71.         }
  72.     }
  73.  
  74.     // ---- ---- ---- ---- ---- ---- ---- ---- <expression parser>
  75.  
  76.     void pop_op() {
  77.         assert(op_.size() > 0);
  78.         token_e t = op_.back();
  79.         putchar (t);
  80.         op_.pop_back();
  81.     }
  82.  
  83.     void push_op(uint32_t tide, token_e tok) {
  84.         while (op_.size() > tide) {
  85.             if (op_prec (op_.back ()) > op_prec (tok))
  86.                 pop_op ();
  87.             else
  88.                 break;
  89.         }
  90.         op_.push_back(tok);
  91.     }
  92.  
  93.     void pop_all_op(uint32_t tide) {
  94.         while (op_.size() > tide)
  95.             pop_op();
  96.     }
  97.  
  98.     void parse_lhs(uint32_t tide) {
  99.         // parenthesis
  100.         if (found('(')) {
  101.             parse_expr ();
  102.             expect (')');
  103.         }
  104.         // identifier
  105.         else if (char var = found_var()) {
  106.             // identifier name
  107.             putchar (var);
  108.             // index an object
  109.             while (found('.')) {
  110.                 if (char ix = found_var()) {
  111.                     putchar (ix);
  112.                     putchar ('@');
  113.                 }
  114.                 else {
  115.                     printf ("\nexpecting identifier, got '%c'\n", *s_);
  116.                     error ();
  117.                 }
  118.             }
  119.             // function call
  120.             if (found('(')) {
  121.                 //
  122.                 uint32_t num_args = 0;
  123.                 // argument list
  124.                 if (!found(')')) {
  125.                     do {
  126.                         ++num_args;
  127.                         parse_expr();
  128.                     } while (found(','));
  129.                     expect (')');
  130.                 }
  131.                 // call instruction
  132.                 printf("<%d>",-num_args);
  133.             }
  134.         }
  135.         // numeric literal
  136.         else if (char num = found_num()) {
  137.             putchar (num);
  138.         }
  139.         // unexpected token
  140.         else {
  141.             printf ("\nunexpected token '%c'\n", *s_);
  142.             error ();
  143.         }
  144.     }
  145.  
  146.     // parse an expression with extended control
  147.     void parse_expr_ex(uint32_t tide) {
  148.         bool unary_not = found ('!');
  149.         parse_lhs(tide);
  150.         if (unary_not) {
  151.             // logical not instruction
  152.             putchar('!');
  153.         }
  154.         if (char op = found_op()) {
  155.             push_op (tide, op);
  156.             parse_expr_ex(tide);
  157.         }
  158.     }
  159.  
  160.     // parse a full expression
  161.     void parse_expr() {
  162.         uint32_t tide = op_.size();
  163.         parse_expr_ex(tide);
  164.         pop_all_op(tide);
  165.     }
  166.  
  167.     // ---- ---- ---- ---- ---- ---- ---- ---- </expression parser>
  168.  
  169.     // parse root
  170.     void parse() {
  171.         if (!setjmp(error_buf)) {
  172.             parse_expr ();
  173.         } else {
  174.             printf ("unable to parse\n");
  175.         }
  176.     }
  177. };
  178.  
  179. // supported operators:
  180. //      &       and
  181. //      + -     add sub
  182. //      * /     mul div
  183. //      !       unary not
  184. // example input:
  185. //      A+B*C*(0-3)
  186. //      A&!B
  187. //      2+A(B,C+1)
  188. int main() {
  189.     char buffer[1024];
  190.     // little REPL loop
  191.     for (;;) {
  192.         printf ("expr: ");
  193.         fgets(buffer, sizeof(buffer), stdin);
  194.         if (buffer[0] == '\0')
  195.             break;
  196.         parser_t parser(buffer);
  197.         printf ("post: ");
  198.         parser.parse();
  199.         printf ("\n\n");
  200.     }
  201.     return 0;
  202. }
RAW Paste Data
Top