fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4. #include <stdlib.h>
  5.  
  6. #define MAXLEN 256
  7. #define TBLSIZE 65535
  8.  
  9. typedef enum {UNKNOWN, END, INT, ID, ADDSUB, MULDIV, ASSIGN,
  10.     LPAREN, RPAREN, ENDFILE} TokenSet;
  11. typedef enum {MISPAREN, NOTNUMID, NOTFOUND, RUNOUT} ErrorType;
  12.  
  13. typedef struct {
  14.     char name[MAXLEN];
  15.     int val;
  16. } Symbol;
  17.  
  18. typedef struct _Node {
  19.     char lexeme[MAXLEN];
  20.     TokenSet data;
  21.     int val;
  22.     struct _Node *left, *right;
  23. } BTNode;
  24.  
  25. Symbol table[TBLSIZE];
  26. extern Symbol table[TBLSIZE];
  27.  
  28. int r[8][2];
  29. int idx = 0;
  30.  
  31. extern int getval(void);
  32. extern int setval(char *str, int val);
  33. extern int match (TokenSet token);
  34. extern int evaluateTree(BTNode *root);
  35. extern void printPrefix(BTNode *root);
  36. extern void advance(void);
  37. extern void freeTree(BTNode *root);
  38. extern void statement(void);
  39. extern void error(ErrorType errorNum);
  40. extern BTNode* makeNode(TokenSet tok, const char *lexe);
  41. extern BTNode* factor(void);
  42. extern BTNode* term(void);
  43. extern BTNode* term_tail(BTNode *left);
  44. extern BTNode* expr(void);
  45. extern BTNode* expr_tail(BTNode *left);
  46. static TokenSet getToken(void);
  47. static TokenSet lookahead = UNKNOWN;
  48. extern char* getLexeme(void);
  49. static char lexeme[MAXLEN];
  50. int sbcount = 0;
  51. /*
  52.  Something like Python
  53.  >> y = 2
  54.  >> z = 2
  55.  >> x = 3*y + 4/(2*z)
  56.  
  57.  */
  58.  
  59. /*
  60.  the only type: integer
  61.  everything is an expression
  62.  statement   := END | expr END
  63.  expr        := term expr_tail
  64.  expr_tail   := ADDSUB term expr_tail | NIL
  65.  term        := factor term_tail
  66.  term_tail := MULDIV factor term_tail | NIL
  67.  factor      := INT | ADDSUB INT | ADDSUB ID | ID ASSIGN expr | ID | LPAREN expr RPAREN
  68.  */
  69.  
  70. int main() {
  71.     printf(">> ");
  72.     while (1) {
  73.         statement();
  74.     }
  75.     return 0;
  76. }
  77.  
  78. /*statement   := ENDFILE | END | expr END*/
  79. void statement(void) {
  80.     BTNode* retp;
  81.  
  82.     if (match(ENDFILE)) {
  83.         exit(0);
  84.     } else if (match(END)) {
  85.         printf(">> ");
  86.         advance();
  87.     } else {
  88.         retp = expr();
  89.         if (match(END)) {
  90.  
  91.             printf("%d\n", evaluateTree(retp));
  92.             printPrefix(retp); printf("\n");
  93.             freeTree(retp);
  94.  
  95.             printf(">> ");
  96.             advance();
  97.         }
  98.     }
  99. }
  100.  
  101. void advance(void) {
  102.     lookahead = getToken();
  103. }
  104.  
  105. /*  expr        := term expr_tail*/
  106. BTNode* expr(void) {
  107.     BTNode *node;
  108.  
  109.     node = term();
  110.  
  111.     return expr_tail(node);
  112. }
  113. /*  expr_tail   := ADDSUB term expr_tail | NIL*/
  114. BTNode* expr_tail(BTNode *left) {
  115.     BTNode *node;
  116.  
  117.     if (match(ADDSUB)) {
  118.         node = makeNode(ADDSUB, getLexeme());
  119.         advance();
  120.  
  121.         node->left = left;
  122.         node->right = term();
  123.  
  124.         return expr_tail(node);
  125.     }
  126.     else
  127.         return left;
  128. }
  129.  
  130. TokenSet getToken(void) {
  131.     int i;
  132.     char c;
  133.  
  134.     while ((c = fgetc(stdin)) == ' ' || c == '\t');  // ©ø≤§™≈•’¶r§∏
  135.  
  136.     if (isdigit(c)) {
  137.         lexeme[0] = c;
  138.         c = fgetc(stdin);
  139.         i = 1;
  140.         while (isdigit(c) && i < MAXLEN) {
  141.             lexeme[i] = c;
  142.             ++i;
  143.             c = fgetc(stdin);
  144.         }
  145.         ungetc(c, stdin);
  146.         lexeme[i] = '\0';
  147.         return INT;
  148.     } else if (c == '+' || c == '-') {
  149.         lexeme[0] = c;
  150.         lexeme[1] = '\0';
  151.         return ADDSUB;
  152.     } else if (c == '*' || c == '/') {
  153.         lexeme[0] = c;
  154.         lexeme[1] = '\0';
  155.         return MULDIV;
  156.     } else if (c == '\n') {
  157.         lexeme[0] = '\0';
  158.         return END;
  159.     } else if (c == '=') {
  160.         strcpy(lexeme, "=");
  161.         return ASSIGN;
  162.     } else if (c == '(') {
  163.         strcpy(lexeme, "(");
  164.         return LPAREN;
  165.     } else if (c == ')') {
  166.         strcpy(lexeme, ")");
  167.         return RPAREN;
  168.     } else if (isalpha(c) || c == '_') {
  169.         lexeme[0] = c;
  170.         c = fgetc(stdin);
  171.         i = 1;
  172.         while (isalpha(c) || isdigit(c) || c == '_') {
  173.             lexeme[i] = c;
  174.             ++i;
  175.             c = fgetc(stdin);
  176.         }
  177.         ungetc(c, stdin);
  178.         lexeme[i] = '\0';
  179.         return ID;
  180.     } else if (c == EOF)
  181.         return ENDFILE;
  182.     else
  183.         return UNKNOWN;
  184. }
  185.  
  186. int match(TokenSet token) {
  187.     if (lookahead == UNKNOWN) advance();
  188.     return token == lookahead;
  189. }
  190.  
  191. char* getLexeme(void) {
  192.     return lexeme;
  193. }
  194.  
  195. int evaluateTree(BTNode *root) {
  196.     int retval = 0, lv, rv;
  197.     if (root != NULL) {
  198.         switch (root->data) {
  199.             case ID:
  200.                 if (strcmp(root->lexeme, "x") == 0)
  201.                     printf("MOV r%d [0]\n", idx);
  202.                 else if (strcmp(root->lexeme, "y") == 0)
  203.                     printf("MOV r%d [4]\n", idx);
  204.                 else if (strcmp(root->lexeme, "z") == 0)
  205.                     printf("MOV r%d [8]\n", idx);
  206.                 break;
  207.             case INT:
  208.                 retval = root->val;
  209.                 r[idx][0] = root->val;
  210.                 r[idx][1] = -1;
  211.                 printf("MOV r%d %d\n", idx, r[idx][0]);
  212.                 idx++;
  213.                 break;
  214.             case ASSIGN:
  215.                 /*if (strcmp(root->right->lexeme, "x") == 0)
  216.                  printf("MOV [0] r%d\n", idx);
  217.                  else if (strcmp(root->right->lexeme, "y") == 0)
  218.                  printf("MOV [4] r%d\n", idx);
  219.                  else if (strcmp(root->right->lexeme, "z") == 0)
  220.                  printf("MOV [8] r%d\n", idx);*/
  221.  
  222.             case ADDSUB:
  223.                 if (strcmp(root->lexeme, "+") == 0) {
  224.                     //printf("",);
  225.                 }
  226.             case MULDIV:
  227.                 lv = evaluateTree(root->left);
  228.                 rv = evaluateTree(root->right);
  229.                 if (strcmp(root->lexeme, "+") == 0) {
  230.                     retval = lv + rv;
  231.  
  232.                 }
  233.                 else if (strcmp(root->lexeme, "-") == 0) {
  234.                     retval = lv - rv;
  235.  
  236.                 }
  237.                 else if (strcmp(root->lexeme, "*") == 0) {
  238.                     retval = lv * rv;
  239.  
  240.                 }
  241.                 else if (strcmp(root->lexeme, "/") == 0) {
  242.                     retval = lv / rv;
  243.  
  244.                 }
  245.                 else if (strcmp(root->lexeme, "=") == 0) {
  246.                     retval = setval(root->left->lexeme, rv);
  247.  
  248.                 }
  249.                 break;
  250.             default:
  251.                 retval = 0;
  252.         }
  253.     }
  254.     return retval;
  255. }
  256.  
  257.  
  258. /* print a tree by pre-order. */
  259. void printPrefix(BTNode *root) {
  260.     if (root != NULL) {
  261.         printf("%s ", root->lexeme);
  262.         printPrefix(root->left);
  263.         printPrefix(root->right);
  264.     }
  265. }
  266.  
  267. int getval(void) {
  268.     int i, retval, found;
  269.  
  270.     if (match(INT))
  271.         retval = atoi(getLexeme());
  272.     else if (match(ID)) {
  273.         i = 0; found = 0; retval = 0;
  274.         while (i < sbcount && !found) {
  275.             if (strcmp(getLexeme(), table[i].name)==0) {
  276.                 retval = table[i].val;
  277.                 found = 1;
  278.                 break;
  279.             } else
  280.                 i++;
  281.         }
  282.         if (!found) {
  283.             if (sbcount < TBLSIZE) {
  284.                 strcpy(table[sbcount].name, getLexeme());
  285.                 table[sbcount].val = 0;
  286.                 sbcount++;
  287.             } else
  288.                 error(RUNOUT);
  289.         }
  290.     }
  291.     return retval;
  292. }
  293.  
  294. int setval(char *str, int val) {
  295.     int i, retval;
  296.     i = 0;
  297.     while (i < sbcount) {
  298.         if (strcmp(str, table[i].name) == 0) {
  299.             table[i].val = val;
  300.             retval = val;
  301.             break;
  302.         } else
  303.             i++;
  304.     }
  305.     return retval;
  306. }
  307. /* create a node without any child.*/
  308. BTNode* makeNode(TokenSet tok, const char *lexe){
  309.     BTNode *node = (BTNode*) malloc(sizeof(BTNode));
  310.     strcpy(node->lexeme, lexe);
  311.     node->data = tok;
  312.     node->val = 0;
  313.     node->left = NULL;
  314.     node->right = NULL;
  315.     return node;
  316. }
  317. /* clean a tree.*/
  318. void freeTree(BTNode *root) {
  319.     if (root != NULL) {
  320.         freeTree(root->left);
  321.         freeTree(root->right);
  322.         free(root);
  323.     }
  324. }
  325. /*factor := INT | ADDSUB INT | ADDSUB ID | ID ASSIGN expr | ID | LPAREN expr RPAREN*/
  326. BTNode* factor(void) {
  327.     BTNode* retp = NULL;
  328.     char tmpstr[MAXLEN];
  329.  
  330.     if (match(INT)) {
  331.         retp = makeNode(INT, getLexeme());
  332.         retp->val = getval();
  333.         advance();
  334.     } else if (match(ID)) {
  335.         BTNode* left = makeNode(ID, getLexeme());
  336.         left->val = getval();
  337.         strcpy(tmpstr, getLexeme());
  338.         advance();
  339.         if (match(ASSIGN)) {
  340.             retp = makeNode(ASSIGN, getLexeme());
  341.             advance();
  342.             retp->right = expr();
  343.             retp->left = left;
  344.         } else
  345.             retp = left;
  346.     } else if (match(ADDSUB)) {
  347.         strcpy(tmpstr, getLexeme());
  348.         advance();
  349.         if (match(ID) || match(INT)) {
  350.             retp = makeNode(ADDSUB, tmpstr);
  351.             if (match(ID))
  352.                 retp->right = makeNode(ID, getLexeme());
  353.             else
  354.                 retp->right = makeNode(INT, getLexeme());
  355.             retp->right->val = getval();
  356.             retp->left = makeNode(INT, "0");
  357.             retp->left->val = 0;
  358.             advance();
  359.         } else
  360.             error(NOTNUMID);
  361.     } else if (match(LPAREN)) {
  362.         advance();
  363.         retp = expr();
  364.         if (match(RPAREN))
  365.             advance();
  366.         else
  367.             error(MISPAREN);
  368.     } else
  369.         error(NOTNUMID);
  370.     return retp;
  371. }
  372. /*  term        := factor term_tail*/
  373. BTNode* term(void) {
  374.     BTNode *node;
  375.     node = factor();
  376.  
  377.     return term_tail(node);
  378. }
  379. /*term_tail := MULDIV factor term_tail | NIL*/
  380. BTNode* term_tail(BTNode *left) {
  381.     BTNode *node;
  382.  
  383.     if (match(MULDIV)) {
  384.         node = makeNode(MULDIV, getLexeme());
  385.         advance();
  386.  
  387.         node->left = left;
  388.         node->right = factor();
  389.  
  390.         return term_tail(node);
  391.     }
  392.     else
  393.         return left;
  394. }
  395.  
  396. void error(ErrorType errorNum) {
  397.     switch (errorNum) {
  398.         case MISPAREN:
  399.             fprintf(stderr, "Mismatched parenthesis\n");
  400.             break;
  401.         case NOTNUMID:
  402.             fprintf(stderr, "Number or identifier expected\n");
  403.             break;
  404.         case NOTFOUND:
  405.             fprintf(stderr, "%s not defined\n", getLexeme());
  406.             break;
  407.         case RUNOUT:
  408.             fprintf(stderr, "Out of memory\n");
  409.     }
  410.     exit(0);
  411. }
  412.  
Success #stdin #stdout 0s 26072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
>>
https://ideone.com/xmFj1D
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!