Guest User

TinyExpressionParser.cpp

a guest
Nov 4th, 2015
205
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×