API tools faq
paste
razormc

FJAP zadanie 2

razormc
Dec 14th, 2011
367
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 17.33 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <ctype.h>
  3. #include <malloc.h>
  4. #include <string.h>
  5.  
  6. #define KeySet unsigned long int
  7.  
  8. #define SymType int
  9.  
  10. #define E 1 <<  // napr. E VALUE => 1 equiv {VALUE}, lebo VALUE = 0
  11. // Typy symbolov a mnozin symbolov
  12.  
  13. enum Symbols {
  14.     BOOLCONST, LPAR, RPAR, ANDD, ORR, SEOF, SERROR, INTCONST
  15. };
  16.  
  17. char* Keywords[2] = { "FALSE", "TRUE"};
  18.  
  19. KeySet SymbolSet = 0;
  20. // Nastavenie SymbolSet na prazdnu mnozinu
  21.  
  22. // Vstupne premenne
  23. char sourceString[100]; // - vstupny retazec
  24. char c;
  25. int ic; // vstupny znak a index do vstupneho retazca
  26.  
  27. // Vystupny symbol lexikalnej analyzy, jeho kod a atribut
  28. SymType symbol;
  29. int  attr;
  30.  
  31. void getsymbol();
  32.  
  33. char *errmsg[]={
  34.      /* 0 */ "Ocakava sa &&",
  35.      /* 1 */ "ocakava sa ||",
  36.      /* 2 */ "ocakava sa (",
  37.      /* 3 */ "ocakava sa ( alebo hodnota",
  38.      /* 4 */ "ocakava sa && alebo podvyraz",
  39.      /* 5 */ "ocakava sa || alebo podvyraz",
  40.      /* 6 */ "ocakava sa )",
  41.      };
  42.  
  43.  
  44. KeySet  HTerm       = (E BOOLCONST)|(E INTCONST)  | (E LPAR);
  45. KeySet  HSub        = HTerm;
  46. KeySet  HExpr       = HExpr;
  47.  
  48. int synerrs=0;
  49. void error(int n, KeySet keys) {
  50.     printf("SYN_CHYBA: %s\n",errmsg[n]);
  51.     synerrs++;
  52.     while (!((E symbol) & keys)) getsymbol();
  53. }
  54.  
  55. void check(int n, KeySet keys) {
  56.     if (!((E symbol) & keys)) error(n,keys);
  57. }
  58.  
  59. // Lexikalny analyzator
  60. void getsymbol() {
  61.         char instring[30];
  62.         int is; // pre retazec znakov a klúcové slovo
  63.         c = sourceString[ic];
  64.         ic = ic + 1;
  65.         while (c == ' ') {
  66.                 c = sourceString[ic];
  67.                 ic = ic + 1;
  68.         }
  69.         switch (c) {
  70.         case '&':
  71.                 c = sourceString[ic];
  72.                 ic = ic + 1;
  73.                 if (c == '&') {
  74.                     symbol = ANDD;
  75.                 }else {
  76.                     ic = ic-1;
  77.                     symbol = SERROR;
  78.                 }
  79.                 break;
  80.        case '|':
  81.                c = sourceString[ic];
  82.                ic = ic + 1;
  83.                 if (c == '|') {
  84.                     symbol = ORR;
  85.                 }else {
  86.                     ic = ic-1;
  87.                     symbol = SERROR;
  88.                 }
  89.                 break;
  90.         case '(':
  91.                 symbol = LPAR;
  92.                 break;
  93.         case ')':
  94.                 symbol = RPAR;
  95.                 break;
  96.         case '\0':
  97.                 symbol = SEOF;
  98.                 break;
  99.         default:
  100.             if (c >= '0' && c <= '9') { // celé císlo
  101.             symbol = INTCONST;
  102.             attr = 0;
  103.             while (c >= '0' && c <= '9') {
  104.                 attr = attr * 10 + (int) c - (int) '0';
  105.                 c = sourceString[ic++];
  106.             }
  107.             ic--;
  108.             } else if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) { // klúcové slovo
  109.             is = 0;
  110.             instring[is++] = toupper(c);
  111.             c = sourceString[ic++];
  112.             while ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
  113.                 instring[is++] = toupper(c);
  114.                 c = sourceString[ic++];
  115.             }
  116.             instring[is] = '\0';
  117.             ic--;
  118.             if (strcmp(instring, Keywords[0]) == 0) { // boolovská konštanta
  119.                 symbol = BOOLCONST;
  120.                 attr = 0;
  121.             } else if (strcmp(instring, Keywords[1]) == 0) { // boolovská konštanta
  122.                 symbol = BOOLCONST;
  123.                 attr = 1;
  124.             }else {
  125.                 symbol = SERROR;
  126.             }
  127.         } else {
  128.             symbol = SERROR;
  129.         }
  130.  
  131.         }
  132. }
  133. // Koniec lexikálnej analýzy ************************
  134.  
  135. // **************************************************
  136. // Preklad do syntaktického stromu riadený syntaxou
  137. // **************************************************
  138.  
  139. // Definícia syntaktického stromu výrazu
  140. // Znacky vrcholov stromu
  141. //Tu su zadefinovane vsetky typy  Kostantant -> Int a Boolean ktore sa pouzivaju v programe
  142. //Dalej Operatory  -> polymorfny  je OR lebo mozme bud porovnavat  int||int alebo vzhodnocovat logickz vyraz  BoolConst||BoolConst
  143. //      Operatory -> monomorfne te uz specifikuju  ake presne typy sa budu vzhodnocovat , ak napr. prava a lava strana bola Int tak sa nastavy operator na OR_INT_OP
  144.        
  145. enum NodeTags {
  146.     // druhy konštánt
  147.         BOOL_CONST,
  148.         INT_CONST,
  149.     // operátory polymorfných operácií
  150.         OR_OP,
  151.         AND_OP,
  152.     // operátory monomorfných operácií
  153.         OR_INT_OP,
  154.         OR_BOOLEAN_OP,
  155.         AND_BOOLEAN_OP,
  156.     UNDEFINED_OP
  157. };
  158.  
  159. // Typová definícia uzla stromu ExpTree
  160. typedef union ExpTreeNode {
  161.     struct {
  162.         int constTag; //znacka typu konstanty
  163.         int constVal; //hodnota konstanty
  164.     } operand; //operand resp. konstanta
  165.  
  166.     struct {
  167.         int binOp; //identifikator operatora
  168.         ExpTreeNode* leftTree; //lavy operand - podstrom
  169.         ExpTreeNode* rightTree; //pravy operand - podstrom
  170.     } binaryop; //binarna operacia
  171. } ExpTree;
  172.  
  173.  
  174.  
  175. // Konštruktory uzlov stromu výrazu
  176. // Konštruktor konštanty (listu stromu)
  177. ExpTree* mkValNode(NodeTags constTag, int constVal) {
  178.     //alokovanie pamate pre uzol stromu
  179.     ExpTreeNode* node = (ExpTreeNode*) malloc(sizeof(ExpTreeNode));
  180.     //priradenie hodnot konstantam uzla
  181.     node->operand.constTag = constTag;
  182.     node->operand.constVal = constVal;
  183.     //vrati vytvoreny uzol
  184.     return node;
  185. }
  186.  
  187. // Konštruktor binárneho operátora
  188. ExpTree* mkBinNode(NodeTags binOp, ExpTree* leftTree, ExpTree* rightTree) {
  189.     ExpTreeNode* node = (ExpTreeNode*) malloc(sizeof(ExpTreeNode));
  190.     node->binaryop.binOp = binOp;
  191.     node->binaryop.leftTree = leftTree;
  192.     node->binaryop.rightTree = rightTree;
  193.     return node;
  194. }
  195.  
  196. ExpTree* term(KeySet keys);
  197. ExpTree* expr(KeySet keys);
  198. ExpTree* sub(KeySet keys);
  199. // Funkcie pre preklad výrazu do syntakcického stromu
  200. // (podla pravidiel gramatiky)
  201. // Vstup: symboly podávané procedúrou getsymbol()
  202. // Výstup: výraz v tvare syntaktického stromu
  203. // (konštanty v listoch, operátory v ostatných uzloch
  204. // Operátory môžu by monomorfné aj polymorfné
  205. // Ak sú polymorfné, sú nevykonatelné!
  206.  
  207.  
  208.  
  209.  
  210. // Interpretator vyrazov s gramatikou
  211. // Expr -> Sub [ <||> Expr ]
  212. // Sub -> Term { <&&> Term }
  213. // Term ->  <BOOLVAL> | <INTVAL> | <(> Expr <)>
  214. // Pozn: Terminalne symboly su v zatvorkach < >
  215.  
  216. // Expr -> Sub [ <||> Expr ]
  217. ExpTree* expr(KeySet keys) {
  218.     SymType sy; // pre zapamätanie symbola na vstupe
  219.     ExpTree* rightTree;
  220.     ExpTree* leftTree; // konštruované (pod)stromy
  221.     KeySet loopkeys, allkeys;
  222.     loopkeys = (E ORR) | HExpr;
  223.     allkeys = loopkeys | keys;
  224.     leftTree = sub(allkeys);
  225.     check(5,allkeys);
  226.     if ((E symbol) & loopkeys)     {
  227.             if (symbol == ORR) {
  228.                 sy = symbol;
  229.                 getsymbol();
  230.             } else {
  231.         error(1, keys);
  232.             }
  233.             rightTree = expr(allkeys);
  234.             if (sy == ORR) {
  235.                  leftTree = mkBinNode(OR_OP, leftTree, rightTree);
  236.             }
  237.  
  238.              check(4,keys);
  239.         }
  240.     return leftTree;
  241. }
  242.  
  243. // Sub -> Term { <&&> Term }
  244. ExpTree* sub(KeySet keys){
  245.         SymType sy; // pre zapamätanie symbola na vstupe
  246.         ExpTree* rightTree;
  247.         ExpTree* leftTree; // konštruované (pod)stromy
  248.         KeySet loopkeys, allkeys;
  249.         loopkeys =  (E ANDD) | HSub;
  250.         allkeys = loopkeys | keys;
  251.         leftTree = term(allkeys);
  252.         check(4,allkeys);
  253.         while ((E symbol) & loopkeys)     {
  254.             if (symbol == ANDD) {
  255.                 sy = symbol;
  256.                 getsymbol();
  257.             } else {
  258.         error(0, keys);
  259.             }
  260.             rightTree = term(allkeys);
  261.             if (sy == ANDD) {
  262.                 leftTree = mkBinNode(AND_OP, leftTree, rightTree);
  263.             }
  264.  
  265.             check(4,allkeys);
  266.         }
  267.     return leftTree;
  268.  
  269. }
  270. // Term ->  <BOOLVAL> | <INTVAL> | <(> Expr <)>
  271. ExpTree* term(KeySet keys){
  272.     ExpTree* subtree; // konštruovaný (pod)strom
  273.     check(3,HTerm | keys);
  274.     switch (symbol) {
  275.         case LPAR :
  276.            if (symbol == LPAR) {
  277.                 getsymbol();
  278.            }else {
  279.                 error(2, keys);
  280.            }
  281.            subtree = expr((E RPAR) | keys);
  282.            if(symbol==RPAR) {
  283.                getsymbol();
  284.            }
  285.            else {
  286.                error(6,keys);
  287.            }
  288.             break;
  289.         case BOOLCONST:
  290.             subtree = mkValNode(BOOL_CONST, attr);
  291.             getsymbol();
  292.             break;
  293.         case INTCONST:
  294.             subtree = mkValNode(INT_CONST, attr);
  295.             getsymbol();
  296.         break;
  297.         default:
  298.             error(3,keys);
  299.             subtree = mkValNode(UNDEFINED_OP, 0);
  300.         }
  301.  
  302.     return subtree;
  303. }
  304.  
  305.  
  306. // **************************************************
  307. // TEST - Výpis syntaktického stromu
  308. // **************************************************
  309.  
  310.  
  311. // NETREBA VEDIET
  312. // Testovacia procedúra pre výpis syntaktického stromu v prefixnej forme
  313. // (navrhnutá všeobecne pre všetky operátory - monomorfné aj polymorfné)
  314. void ExpTreePrint(ExpTree* tree) {
  315.     switch (tree->operand.constTag) {
  316.     // Konštanty
  317.     case BOOL_CONST:
  318.         if (tree->operand.constVal == 0)
  319.             printf("False ");
  320.         else
  321.             printf("True ");
  322.         break;
  323.     case INT_CONST:
  324.         printf("%i ", tree->operand.constVal);
  325.         break;
  326.         // Polymorfné operácie
  327.     case AND_OP:
  328.         printf("&& ");
  329.         ExpTreePrint(tree->binaryop.leftTree);
  330.         ExpTreePrint(tree->binaryop.rightTree);
  331.         break;
  332.     case OR_OP:
  333.         printf("|| ");
  334.         ExpTreePrint(tree->binaryop.leftTree);
  335.         ExpTreePrint(tree->binaryop.rightTree);
  336.         break;
  337.     // Monomorfné operácie    
  338.     case OR_INT_OP:
  339.         printf("||_int ");
  340.         ExpTreePrint(tree->binaryop.leftTree);
  341.         ExpTreePrint(tree->binaryop.rightTree);
  342.         break;
  343.     case OR_BOOLEAN_OP:
  344.         printf("||_boolean ");
  345.         ExpTreePrint(tree->binaryop.leftTree);
  346.         ExpTreePrint(tree->binaryop.rightTree);
  347.         break;
  348.    case AND_BOOLEAN_OP:
  349.         printf("&&_boolean ");
  350.         ExpTreePrint(tree->binaryop.leftTree);
  351.         ExpTreePrint(tree->binaryop.rightTree);
  352.         break;
  353.     }
  354. }
  355.  
  356. // Koniec testu *************************************
  357.  
  358. // **************************************************
  359. // Sémantická analýza = kontrola typov [ + transformácia stromu]
  360. // **************************************************
  361.  
  362. // [Transformácia stromu vedie k stromu s monomorfnými operátormi]
  363.  
  364. // Množina typov
  365. enum Type {
  366.     BoolType, IntType, AnyType
  367. };
  368.  
  369. // Funkcia sémantického spracovania (typovej kontroly+transformácie)
  370. // Vstup: výraz (alebo podvýraz) (v našom prípade v tvare stromu)
  371. // Úcinok: zmena polymorfného operátora na monomorfný v závislosti
  372. // od typov argumentov operácie (reprezentovaných podstromami)
  373. // Výstup: monomorfný typ výrazu (podvýrazu)
  374.  
  375. // Pozn:
  376. // 1. Konštanty sú monomorfné (a sú v listoch stromu)
  377. // 2. Zlyhanie je indikované všeobecným typom AnyType
  378. // 3. Lepšie je najprv realizovat a otestovat interpretátor
  379.  
  380.  
  381.  //Tato funkcia meni polymorfného operátora na monomorfný v závislosti od toho vstupu
  382. //ak boli zadane spravne vstupy tak tak operacie nastavy na urcene monomorfne operatory inak
  383. //sa nastavy na neidentifikovatelny typ a tym padom typova kontrola pada a dalej uz sa nemoze vykonat ani vypocet
  384. Type TypeCheck(ExpTree* tree) {
  385.     Type tyvalLeft;
  386.     Type tyvalRight; // Typ laveho a praveho podvyrazu
  387.  
  388.     switch (tree->operand.constTag) {
  389.     case BOOL_CONST:
  390.         return BoolType;
  391.  
  392.     case INT_CONST:
  393.         return IntType;
  394.  
  395.         case OR_OP:// ak bol  nacitany operator OR tak
  396.             tyvalLeft = TypeCheck(tree->binaryop.leftTree);// si zisti typ  premmenej z laveho pod stromu
  397.             tyvalRight = TypeCheck(tree->binaryop.rightTree);// si zisti typ  premmenej s praveho pod stromu
  398.             if (tyvalLeft == IntType && tyvalRight == IntType) {//a ak  je lavy aj pravy Int tak
  399.                 tree->binaryop.binOp = OR_INT_OP; //nastavy operator na OR_INT_OP
  400.                 return BoolType;
  401.             }else if (tyvalLeft == BoolType && tyvalRight == BoolType) { // alebo ak je lavz aj pravy typu boolean tak
  402.                 tree->binaryop.binOp = OR_BOOLEAN_OP;//nastavy operator na OR_BOOLEAN_OP
  403.                 return BoolType;
  404.             }else
  405.                 return AnyType; // a ak ani jeden s tychto typov tak sa nastavy vysledok vyrazu na AnyType  a to znamena ze sa neda vykonat dana operacia a typova kontrola zlyha
  406.             break;
  407.  
  408.         case AND_OP: //Pri AND sa bud nastavy typ vysledku na boolean ak su obidva typy int inak sa nastavy na Anytype
  409.                 tyvalLeft = TypeCheck(tree->binaryop.leftTree);
  410.         tyvalRight = TypeCheck(tree->binaryop.rightTree);
  411.         if (tyvalLeft == BoolType && tyvalRight == BoolType) {
  412.                          tree->binaryop.binOp = AND_BOOLEAN_OP;
  413.                         return  BoolType;
  414.         }else
  415.                         return AnyType;
  416.                 break;
  417.         default:
  418.     return AnyType;
  419.     }
  420. }
  421.  
  422. // Koniec sémantickej analýzy ***********************
  423.  
  424.  
  425. // **************************************************
  426. // Interpretátor cielového výrazu v tvare stromu
  427. // s monomorfnými operáciami
  428. // **************************************************
  429.  
  430. // Typová definícia návratovej hodnoty všetkých monomorfných typov
  431. //
  432. typedef union {
  433.     int intval; //ciselna hodnota
  434. } MonoType;
  435.  
  436. // Funkcia výpoctu výrazu - interpretácia cielového stromu
  437. MonoType* Evaluate(ExpTree* tree) {
  438.     MonoType* cellLeft = (MonoType*) malloc(sizeof(MonoType));
  439.     MonoType* cellRight = (MonoType*) malloc(sizeof(MonoType));
  440.  
  441.     switch (tree->operand.constTag) {// podla operatora vyberie vyraz ktory bude pocitat
  442.     case BOOL_CONST:
  443.         cellLeft->intval = tree->operand.constVal;
  444.         return cellLeft;
  445.  
  446.     case INT_CONST:
  447.         cellLeft->intval = tree->operand.constVal;
  448.         return cellLeft;
  449.  
  450.  //podla typu operatora sa vykona dany case,  bud spravy OR s cislami alebo s true a false alebo AND s hodnotami true a false
  451.     case OR_INT_OP:
  452.         cellLeft = Evaluate(tree->binaryop.leftTree);   //nacita sa lava strana
  453.         cellRight = Evaluate(tree->binaryop.rightTree); //nacita sa pravastrana
  454.         if (cellLeft->intval == cellRight->intval) { // porovna sa a nastavy vysledok na 1 alebo 0
  455.             cellLeft->intval = 1;
  456.         } else {
  457.             cellLeft->intval = 0;
  458.         }
  459.         return cellLeft;
  460.         break;
  461.     case OR_BOOLEAN_OP:
  462.         cellLeft = Evaluate(tree->binaryop.leftTree);
  463.         cellRight = Evaluate(tree->binaryop.rightTree);
  464.         if (cellLeft->intval || cellRight->intval)
  465.                cellLeft->intval = 1;
  466.             else
  467.                cellLeft->intval = 0;
  468.         return cellLeft;
  469.         break;
  470.    case AND_BOOLEAN_OP:
  471.         cellLeft = Evaluate(tree->binaryop.leftTree);
  472.         cellRight = Evaluate(tree->binaryop.rightTree);
  473.         if (cellLeft->intval && cellRight->intval)
  474.                cellLeft->intval = 1;
  475.             else
  476.                cellLeft->intval = 0;
  477.         return cellLeft;
  478.         break;
  479.  
  480.     default:
  481.         return cellLeft;
  482.     }
  483. }
  484.  
  485.  
  486. int main() {
  487.         char tc;
  488.         int i;
  489.         Type ty; // typ hodnoty výrazu - pomocná premenná
  490.         printf("\nSeparatna lexikalna analyza a interpretator vyrazov\n");
  491.         printf("\nKody symbolov: BOOLCONST=0, LPAR=1, RPAR=2, AND=3, OR=4, SEOF=5, SERROR=6, INTCONST=7");
  492.         printf("\n-------------------------------------------------------------------------\n\n");
  493.  
  494.         printf("Vstupny vyraz (retazec znakov): ");
  495.         // Citanie vstupneho retazca
  496.         for (i = 0; (i < 100) &&
  497.         ((c = getchar()) != '\n'); i++) {
  498.                 sourceString[i] = c;
  499.         }
  500.         // Ukoncenie retazca znakom `\0`
  501.         sourceString[i] = '\0';
  502.         //
  503.         ic = 0; // nastavenie na 1. znak
  504.         printf("\nTest lexikalnej analyzy ------------> \n");
  505.         printf("\nVystup lexikalnej analyzy (retazec symbolov)\n\n");
  506.         do {
  507.                 getsymbol();
  508.                 printf("[%d] ", symbol);
  509.                 if (symbol == BOOLCONST)
  510.                         printf("<%d> ", attr);
  511.             //    tc = getchar();
  512.                 printf("\n");
  513.         } while (symbol != SEOF);
  514.  
  515.         printf("\n<------------Koniec testu lexikalnej analyzy a obnova vstupu\n"); tc=getchar();
  516.         printf("\nZaciatok syntaxou riadenej interpretacie\n\n");
  517.         ic=0; // opatovne nastavenie na 1. znak
  518.         getsymbol();
  519.  
  520.  
  521.         ExpTree* syntTree = expr(E SEOF);
  522.        // Kontrolny vypis vyrazu vo forme polymorfneho stromu
  523.        printf("\n----Vypis vo forme polymorfneho stromu: \n");
  524.        ExpTreePrint(syntTree);
  525.  
  526.            // Semanticka analyza
  527.         printf("\n----Typova kontrola: \n");
  528.         ty = TypeCheck(syntTree);
  529.         if (ty == AnyType) {
  530.             printf("ERROR: Zlyhala typova kontrola\n");
  531.         } else {
  532.             printf("Typova kontrola OK.\n");
  533.         }
  534.                
  535.                 if(ty == BoolType) {            
  536.                     if (Evaluate(syntTree)->intval == 0) {
  537.                                 printf("False ");
  538.                         } else {
  539.                                 printf("True ");
  540.                         }
  541.                 }else if (ty == IntType) {
  542.                     printf("%d", Evaluate(syntTree)->intval);
  543.                 }
  544.  
  545.     getchar();
  546.     return 0;
  547. }
  548.  
  549.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!