text: /*
   * Projekt: IFJ05
   * Resitele: xbarin02, xdudka00, xfilak01, xhefka00, xhradi08
   *
   * Soubor: expr.c - Zpracovani vyrazu (volano z modulu "parser")
   * Autor: Kamil Dudka, xdudka00
   */
  
  #define STACK_INIT_SIZE		256	// Pocatecni velikost stacku (pocet polozek)
  
  #include "ifj05.h"
  #include "scanner.h"
  #include "parser.h"
  #include "expr.h"
  #include "runtime.h"
  
  #include <stdbool.h>
  #include <stdlib.h>
  
  static char szErrInternal[] =		"Internal error in module \"expr\"! Please, report bug to xdudka00@gmail.com";
  static char szErrInvalidExpr[] =	"Invalid expression";
  static char szErrHeapSort[] =		"Bad syntax of Heapsort call";
  static char szErrRPar[] =		"Unexpected ')'";
  static char szErrParenthesis[] =	"Expression error, check parenthesis!";
  static char szErrOperand[] =		"Operand expected";
  static char szErrOperator[] =		"Operator expected";
  
  #define READEXPR_ERR_NOERR		0
  #define READEXPR_ERR_HANDLED		1
  #define READEXPR_ERR_RPAR		2
  
  #ifdef NDEBUG
  #	define DStackPrint(pStack)
  #else
  #	define DStackPrint(pStack)	StackPrint (pStack)
  #endif
  
  /*
   * Vycet hodnot, ktere se daji ulozit na zasobnik (nektere se tam ale neukladaji)
   */
  typedef enum {
  	PTEqual,	// =
  	PTNotEqual,	// !=
  	PTLess,		// <
  	PTGreater,	// >
  	PTLessEqual,	// <=
  	PTGreaterEqual, // >=
  	PTPlus,		// +
  	PTMinus,	// -
  	PTMultiply,	// *
  	PTDivide,	// /
  	PTParLeft,	// (
  	PTParRight,	// )
  	
  	PTIdentifier,	// id
  	PTInt,		// int
  	PTFloat,	// float
  	PTString,	// string
  	
  	PTSemicolon,	// ;
  	PTGoTo,		// go_to
  	PTComma,	// ,
  	
  	PTEq,		// ridici = (aplikuji na pravidlo '(=)' )
  	PTLt,		// ridici <
  	PTGt,		// ridici >
  	PTExpr,		// Vyraz (rekurzivne)
  	
  	PTInv,		// Prazdna bunka - chyba
  	PTEFce,		// prava zavorka navic (konec voleni fce?)
  
  } EPTMember;
  
  /*
   *  Precedencni tabulka (14 radku, 14 sloupcu) - viz. dokumentace
   */
  static int pPTable [14][14] = {
  /*		0	1	2	3	4	5	6	7	8	9	10	11	12	13	*/
  /*		=	!=	<	>	<=	>=	+	-	*	/	(	)	i	$	*/
  /* =  */	{PTGt,	PTGt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* != */	{PTGt,	PTGt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* <  */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* >  */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* <= */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* >= */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* +  */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTLt,	PTLt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* -  */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTLt,	PTLt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* *  */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* /  */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTLt,	PTGt,	PTLt,	PTGt,	},
  /* (  */	{PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTEq,	PTLt,	PTInv,	},
  /* )  */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTInv,	PTGt,	PTInv,	PTGt,	},
  /* i  */	{PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTGt,	PTInv,	PTGt,	PTInv,	PTGt,	},
  /* $  */	{PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTLt,	PTEFce,	PTLt,	PTInv,	},
  };
  
  /*
   * Prevede zasobnikovy symbol na index do PA tabulky
   */
  static inline unsigned PTGetIndex (unsigned i) {
  	static const unsigned iPTI = 12;	// Identifikator ma v tabulce index 12
  	static const unsigned iPTDollar = 13;	// Dollar ma v tabulce index 13
  
  	if (i< PTInt)
  		// Binarni operator
  		return i;
  	
  	if (i< PTSemicolon)
  		// Identifikator
  		return iPTI;
  	else
  		// Dollar
  		return iPTDollar;
  }
  
  /*
   * Vrati prvek PA tabulky na souradnicich i,j
   */
  static inline EPTMember PTGetElement (unsigned i, unsigned j) {
  	if (i > PTComma || j > PTComma) {
  		//dprintf ("Table look-up: [%d,%d] - out of range!\n", i, j);
  		return PTInv;
  	}
  /*	dprintf ("Table look-up: [%d,%d] = %d\n",
  			PTGetIndex (i), PTGetIndex (j),
  			pPTable [PTGetIndex (i)][PTGetIndex (j)]);*/
  	return pPTable [PTGetIndex (i)] [PTGetIndex (j)];
  }
  
  /*
   * Prevede typ tokenu na zasobnikovy symbol
   */
  static inline EPTMember TokenToEnum (TToken iToken) {
  	switch (iToken) {
  		case tOpEqual:		return PTEqual;		// =
  		case tOpNotEqual:	return PTNotEqual;	// !=
  		case tOpLess:		return PTLess;		// <
  		case tOpGreater:	return PTGreater;	// >
  		case tOpLessEqual:	return PTLessEqual;	// <=
  		case tOpGreaterEqual:	return PTGreaterEqual;	// >=
  		case tOpPlus:		return PTPlus;		// +
  		case tOpMinus:		return PTMinus;		// -
  		case tOpMultiply:	return PTMultiply;	// *
  		case tOpDivide:		return PTDivide;	// /
  		case tParenthesisLeft:	return PTParLeft;	// (
  		case tParenthesisRight:	return PTParRight;	// )
  		case tIdentifier:	return PTIdentifier;	// id
  		case tLitInt:		return PTInt;		// int
  		case tLitFloat:		return PTFloat;		// float
  		case tLitString:	return PTString;	// string
  		case tSemicolon:	return PTSemicolon;	// ;
  		case tKeyGoTo:		return PTGoTo;		// go_to
  		case tComma:		return PTComma;		// ,
  		default:		return PTInv;		// chyba
  	}
  }
  
  /*
   * Vraci true, pokud zasobnikovy symbol odpovida dolaru
   */
  static inline bool IsTokenDollar (EPTMember e) {
  	switch (e) {
  		case PTSemicolon:
  		case PTGoTo:
  		case PTComma:
  			return true;
  		default:
  			return false;
  	}
  }
  
  /*
   * Vraci true, pokud je dany zasobnkovy symbol operand
   */
  static inline bool IsTokenOperand (EPTMember e) {
  	switch (e) {
  		case PTIdentifier:
  		case PTInt:
  		case PTFloat:
  		case PTString:
  			return true;
  		default:
  			return false;
  	}
  }
  
  /*
   * Vraci true, pokud je dany zasobnikovy symbol terminal
   */
  static inline bool IsTerminal (EPTMember e) {
  	return (e <= PTGoTo);
  }
  
  /*
   * Lokalni data zasobniku PA
   */
  typedef struct {
  	EPTMember *pStart;
  	size_t size;
  	size_t count;
  	unsigned iTerm;
  } TStack, *PStack;
  
  /*
   * Prototypy funkci pracujicich ze zasobnikem PA
   */
  static PStack StackInit (void);			// Inicializace stacku parseru
  static void StackDestroy (PStack);		// Destrukce stacku parseru
  static void StackPush (PStack, EPTMember);	// Vlozeni symbolu na zasobnik parseru
  static void StackInsertLt (PStack);		// Vlozeni '<' do zasobniku parseru
  static EPTMember StackPop (PStack);		// Vyjmuti symbolu na vrcholu zasobniku parseru
  static EPTMember StackTopTerm (PStack);		// Vraci nejvrchnijsi TERMINAL na zasobniku
  
  /*
   * Zpracuje vyraz v zdrojovem souboru
   * POZOR - Neprima rekurze pres funkci ReadSort()
   *
   * 1. parametr - ukazatel na lokalni data parseru
   * vraci: kod chyby
   *   EXPR_ERR_NOERR		ok
   *   EXPR_ERR_HANDLED		obslouzena chyba
   *   EXPR_ERR_RPAR		chybi prava zavorka
   */
  static int ReadExpr (PParserData);
  
  /*
   * Nacte volani funkce Heapsort()
   * POZOR - Neprima rekurze pres funkci ReadExpr()
   *
   * 1. parametr - ukazatel na lokalni data parseru
   * vraci: kod chyby (0 znamena vsechno OK)
   */
  static int ReadSort (PParserData pPData);	// Nacte volani funkce Heapsort()
  
  /*
   * VSTUPNI BOD MODULU EXPR
   * Zpracuje vyraz v zdrojovem souboru (volano z modulu "parser")
   * Pro obsluhu chyb pouziva funkci ParseError()
   *
   * 1. parametr - ukazatel na lokalni data parseru
   * vraci: kod chyby (0 znamena ok)
   */
  int ExprParse (PParserData pPData) {
  	switch (ReadExpr (pPData)) {
  		case READEXPR_ERR_NOERR:
  			return 0;
  			
  		case READEXPR_ERR_RPAR:
  			ParseError (pPData, szErrRPar);
  
  		case READEXPR_ERR_HANDLED:
  		default:
  			return 1;
  	}
  }
  
  /*
   * Zpracuje vyraz v zdrojovem souboru
   * Volano z modulu "parser", volano rekurzivne z funkce ReadSort() - jedna se neprimou rekurzi
   *
   * 1. parametr - ukazatel na lokalni data parseru
   * vraci: kod chyby (0 znamena vsechno OK)
   */
  static int ReadExpr (PParserData pPData) {
  	// Inicializaci stacku parseru
  	// Stack alokoji pro kazdou instanci funkce ReadExpr() zvnou..
  	PStack pStack = StackInit();
  
  	// Informace o poslednim operandu
  	TScannerToken tokenLastOp;
  	tokenLastOp.tType = tInvalidChar;
  	tokenLastOp.pData = NULL;
  	tokenLastOp.line = 0;
  	
  	// Prevedeni typu tokenu na enumericky typ
  	EPTMember eInput = TokenToEnum (pPData->token.tType);
  
  	if (IsTokenOperand (eInput))
  		// Ulozim si informace o poslednim operandu
  		tokenLastOp = pPData->token;
  
  	// Vlozim "$" na zasobnik - neco z mnoziny {';', 'go_to', ','} - takze treba ';'
  	StackPush (pStack, PTSemicolon);
  
  	// Hlavni cyklus precedencni analyzy
  	do {
  		if (tFuncSort== pPData->token.tType) {
  			// Nacitam Heapsort
  			if (0== ReadSort (pPData)) {
  				// Nacten Heapsort
  				eInput = TokenToEnum (pPData->token.tType);
  				StackPush (pStack, PTExpr);
  
  				if (IsTokenDollar (StackTopTerm (pStack)) && IsTokenDollar (eInput))
  					// Heapsort je jedinym prvkem vyrazu
  					break; // (do while)
  			} else {
  				// Chyba v syntaxi HeapSort
  				ParseError (pPData, szErrHeapSort);
  				StackDestroy (pStack);
  				return READEXPR_ERR_HANDLED;
  			}
  		}
  
  		// Klasicka PA
  		switch (PTGetElement (StackTopTerm (pStack), eInput)) {
  			case PTLt:
  				// Vlozim '<' za posledni terminal
  				StackInsertLt (pStack);
  				
  			case PTEq:
  				// Vlozim symbol na zasobnik a nactu dalsi
  				StackPush (pStack, eInput);
  				ParserGetNextToken (pPData);
  				eInput = TokenToEnum (pPData->token.tType);
  				
  				if (IsTokenOperand (eInput))
  					// Ulozim si informace o poslednim operandu
  					tokenLastOp = pPData->token;
  
  				break;	// (PTLt, PTEq)
  
  			case PTGt:
  				// Redukce (aplikuju gramaticke pravidlo)
  
  				if (IsTokenOperand (StackTopTerm (pStack)) ) {
  					// Token je operand - odeberu ze zasobniku
  					StackPop (pStack);
  
  					// Odeberu '<' pokud tam je (melo by tam byt)
  					if (PTLt!= StackPop (pStack)) {
  						ParseError (pPData, szErrInvalidExpr);
  						StackDestroy (pStack);
  						return READEXPR_ERR_HANDLED;
  					}
  
  					// Nahrazeni terminalu non-terminalem
  					StackPush (pStack, PTExpr);
  
  					// Generovani kodu podle typu operandu
  					switch (tokenLastOp.tType) {
  						case tIdentifier:
  							Generate (pPData, inPUSHV, tokenLastOp.pData);
  							break;
  						case tLitInt:
  						case tLitFloat:
  						case tLitString:
  							Generate (pPData, inPUSHC, tokenLastOp.pData);
  							break;
  						default:
  							// Jiny operand neni
  							ParseError (pPData, szErrInternal);
  							StackDestroy (pStack);
  							return READEXPR_ERR_HANDLED;
  					}
  					break; // (PTGt)
  				}
  
  				if (PTParRight == StackTopTerm (pStack)) {
  					// Redukuji zavorky
  					StackPop (pStack);
  
  					if (PTExpr!= StackPop (pStack) ||
  							PTParLeft!= StackPop (pStack) ||
  							PTLt!= StackPop (pStack)) {
  						
  						ParseError (pPData, szErrParenthesis);
  						StackDestroy (pStack);
  						return READEXPR_ERR_HANDLED;
  					}
  					dprintf ("  ; Drop brackets..\n");
  					StackPush (pStack, PTExpr);
  					break; // (PTGt)
  				}
  				
  				// Predpoklada se binarni operace
  
  				// Odeberu jeden perand
  				if (PTExpr!= StackPop (pStack)) {
  					ParseError (pPData, szErrOperand);
  					StackDestroy (pStack);
  					return READEXPR_ERR_HANDLED;
  				}
  				
  				// obsluha binarniho operatoru
  				switch (StackPop (pStack)) {
  					case PTEqual:
  						Generate (pPData, inCMPE, NULL);
  						break;
  					case PTNotEqual:
  						Generate (pPData, inCMPNE, NULL);
  						break;
  					case PTLess:
  						Generate (pPData, inCMPL, NULL);
  						break;
  					case PTGreater:
  						Generate (pPData, inCMPG, NULL);
  						break;
  					case PTLessEqual:
  						Generate (pPData, inCMPLE, NULL);
  						break;
  					case PTGreaterEqual:
  						Generate (pPData, inCMPGE, NULL);
  						break;
  					case PTPlus:
  						Generate (pPData, inADD, NULL);
  						break;
  					case PTMinus:
  						Generate (pPData, inSUB, NULL);
  						break;
  					case PTMultiply:
  						Generate (pPData, inMUL, NULL);
  						break;
  					case PTDivide:
  						Generate (pPData, inDIV, NULL);
  						break;
  					default:
  						ParseError (pPData, szErrOperator);
  						StackDestroy (pStack);
  						return READEXPR_ERR_HANDLED;
  				}
  				
  				// Odeberu operand
  				if (PTExpr!= StackPop (pStack)) {
  					ParseError (pPData, szErrOperand);
  					StackDestroy (pStack);
  					return READEXPR_ERR_HANDLED;
  				}
  
  				if (PTLt!= StackPop (pStack)) {
  					ParseError (pPData, szErrInvalidExpr);
  					StackDestroy (pStack);
  					return READEXPR_ERR_HANDLED;
  				}
  				
  				// Nahrazeni binarni operace vyrazem
  				StackPush (pStack, PTExpr);
  				break;
  
  			case PTEFce:
  				// Neparova ')' - posledni parametr Heapsortu?
  
  				if (IsTokenDollar (StackPop (pStack))) {
  					// Nebyl zadan vyraz
  					ParseError (pPData, szErrParenthesis);
  					StackDestroy (pStack);
  					return READEXPR_ERR_HANDLED;
  				} else {
  					StackDestroy (pStack);
  					return READEXPR_ERR_RPAR;
  				}
  
  			default:
  				ParseError(pPData, szErrInvalidExpr);
  				StackDestroy (pStack);
  				return READEXPR_ERR_HANDLED;
  		}
  	} while (!IsTokenDollar (StackTopTerm (pStack)) || !IsTokenDollar (eInput) );
  
  	// All ok
  	StackDestroy (pStack);
  	return READEXPR_ERR_NOERR;
  }
  
  static int ReadSort (PParserData pPData) {
  	int iParamsCnt = 0;
  
  	// Nacteni '('
  	ParserGetNextToken (pPData);
  	if (tParenthesisLeft!= pPData->token.tType)
  		return 1;
  
  	// Nactu prvni token nasledujici za '('
  	ParserGetNextToken (pPData);
  
  	// Cyklus
  	for (bool bReading = true; bReading; iParamsCnt++) {
  		switch ( ReadExpr (pPData) ) {
  			case READEXPR_ERR_RPAR:
  				// $ je ')'
  				bReading = false;
  				break;
  
  			case READEXPR_ERR_NOERR:
  				// $ je symbol z mnoziny { ';', 'go_to', ',' }
  				if (tComma== pPData->token.tType)
  					break;
  					
  			case READEXPR_ERR_HANDLED:
  			default:
  				//dprintf ("  ; Error in Heapsort (E, ...)\n");
  				return 1;
  		}
  
  		// Nactu dalsi token
  		ParserGetNextToken (pPData);
  	}
  
  	// Vlozeni instrukce sort na vystupni pasku
  	dprintf ("  sort          %d\n", iParamsCnt);
  	TInstBlock inst;
  	
  	inst.Inst = inSORT;
  	inst.Params.number = iParamsCnt;
  	inst.line_no = pPData->token.line;
  
  	TapeAddInst (pPData->pTape, &inst);
  
  	//dprintf ("  ; Heapsort (E, ...) readed successful\n");
  	return 0;
  }
  
  /*
   * Inicializace zasobniku parseru - (bude se volat pro kazdou instanci ReadExpr()
   */
  static PStack StackInit (void) {
  	// Alokuji prostor pro lokalni data zasobniku
  	PStack pStack = malloc (sizeof(TStack));
  	if (NULL== pStack)
  		GlobalErrAlloc ();
  
  	// Inicializace lokalnich dat
  	pStack->count = 0;
  	pStack->iTerm = 0;
  	pStack->size = STACK_INIT_SIZE;
  
  	// Alokace prostoru pro vlastni zasobnik
  	if (NULL==( pStack->pStart = malloc (STACK_INIT_SIZE * sizeof(EPTMember)) ))
  		GlobalErrAlloc ();
  
  	// Vraci ukazatel na lokalni data
  	return pStack;
  }
  
  /*
   * Destrukce zasobniku parseru - ke kazdemu StackInit() je potreba zavolat StackDestroy()
   */
  static void StackDestroy (PStack pStack) {
  	free (pStack-> pStart);
  	free (pStack);
  }
  
  // Funkce vypisujici obsah zasobniku (pouze pro ladici ucely)
  #ifndef NDEBUG
  static inline void StackPrint (PStack pStack) {
  	return;
  	dprintf ("Stack: ");
  	for (unsigned i=0; i< pStack->count; i++)
  		printf ("%d ", pStack->pStart [i]);
  	dprintf ("\n");
  }
  #endif
  
  /*
   * Vlozi symbol na vrchol zasobniku
   */
  static void StackPush (PStack pStack, EPTMember data) {
  	if ( pStack->count >= pStack->size) {
  		pStack->size <<= 1;
  		dprintf ("  ; Change parser stack size to %d\n", pStack->size);
  		if (NULL==( pStack->pStart = realloc (pStack->pStart, pStack->size * sizeof(EPTMember)) ))
  			GlobalErrAlloc ();
  	}
  	pStack->pStart [pStack->count ++] = data;
  	DStackPrint (pStack);
  }
  
  /*
   * Vyjme symbol z vrcholu zasobniku
   */
  static EPTMember StackPop (PStack pStack) {
  	pStack->count --;
  	DStackPrint (pStack);
  	return pStack->pStart [pStack->count];
  }
  
  /*
   * StackTopTerm() vraci nejvrchnejsi TERMINAL na zasobniku
   * Bude fungovat max. pro binarni operatory, coz nam bude stacit
   */
  static EPTMember StackTopTerm (PStack pStack) {
  	const EPTMember *stack = pStack->pStart;
  	const size_t top = pStack->count -1;
  
  	if (IsTerminal (stack [top]))
  		return stack [top];
  	else
  		return stack [top -1];
  }
  
  /*
   * Vlozi '<' za posledni terminal
   */
  static void StackInsertLt (PStack pStack) {
  	if (IsTerminal (pStack->pStart [pStack->count -1]))
  		StackPush (pStack, PTLt);
  	else {
  		EPTMember eTmp = StackPop (pStack);
  		StackPush (pStack, PTLt);
  		StackPush (pStack, eTmp);
  	}
  }
  
  