My M:tg decks
Povray Files
OTF Roleplaying
2A4X2\2A5X3A
3C0X1\2E2X1
Alpha NAQ
The Crew
E-mail
Reading List
Blog 2016
Blog 2015
Blog 2014
Blog 2013
Blog 2012
Blog 2011
Blog 2010
Blog 2009
Blog 2008
Blog 2007
Blog 2006
Blog 2005
Blog 2004
Blog 2003
Blog 2002
Blog 2001

2013

C urrently taking UMUC's CMSC 330 (Advanced programming languages). I'm only in week 2, but had something to share.   SLC, UT - June 15, 2013
front.c
Chapter 4 of Sebesta's Concepts of Programming Languages (10th ed) has some code for a lexical and syntax analyzer. Since typing all that out isn't too fun, I thought I'd post the code. Also, I spent hours trying to find a nice C compiler and finally settled on Pelles C compiler. Had to make a few tweaks to front.c, since the book's code tries to pass getc into a char (which doesn't work). Also, this uses front.txt instead of front.in. To get rid of the syntax analyzer, just comment out the call to expr();
/* front.c - a lexical analyzer system for simple
             arithmetic expressions */

   #include <stdio.h>
   #include <ctype.h>

   //Global variables   
   int charClass;
   char lexeme [100];
   int nextCharInt;
   char nextChar;
   int lexLen;
   int token;
   int nextToken;
   FILE *in_fp, *fopen();

   // Function Declarations
   void expr();
   void term();
   void factor();
   void addChar();
   void getChar();
   void getNonBlank();
   int lex();

   //Character classes
   #define LETTER 0
   #define DIGIT 1
   #define UNKNOWN 99

   //Token codes
   #define INT_LIT 10
   #define IDENT 11
   #define ASSIGN_OP 20
   #define ADD_OP 21
   #define SUB_OP 22
   #define MULT_OP 23
   #define DIV_OP 24
   #define LEFT_PAREN 25
   #define RIGHT_PAREN 26

   //Main
       int main(){
        if ((in_fp = fopen("front.txt", "r")) == NULL)
            printf("ERROR - cannot open front.txt \n");
        else{
            getChar();
            do {
                lex();
                expr();
            } while (nextToken != EOF);
          }
       }


       void expr() {
	     printf("Enter <expr>\n");
         term();

         while (nextToken == ADD_OP || nextToken == SUB_OP) {
           lex();
           term();
         }
	     printf("Exit <expr>\n");
       }  /* End expr() */

       void term() {
         printf("Enter <term>\n");
         factor();

	     while (nextToken == MULT_OP || nextToken == DIV_OP) {
           lex();
           factor();
         }
	     printf("Exit <term>\n");
       } /* End term() */

       void factor() {
         printf("Enter <factor>\n");

	     if (nextToken == IDENT || nextToken == INT_LIT)
		   lex();

         else {
		   if (nextToken == LEFT_PAREN) {
			lex();
			expr();
			if (nextToken == RIGHT_PAREN)
				lex();
			else
				 printf("Error");
		}

		else
		  printf("Error");
	  }

	     printf("Exit <factor>\n");
       } /* End factor() */


       // lookUp
       int lookup(char ch){
       switch(ch){
       case '(':
           addChar();
           nextToken = LEFT_PAREN;
           break;

       case ')':
           addChar();
           nextToken = RIGHT_PAREN;
           break;

       case '+':
           addChar();
           nextToken = ADD_OP;
           break;

       case'-':
           addChar();
           nextToken = SUB_OP;
           break;

       case'*':
           addChar();
           nextToken = MULT_OP;
           break;

       case'/':
           addChar();
           nextToken = DIV_OP;
               break;

       default:
           addChar();
           nextToken = EOF;
           break;
       }
       return nextToken;
       }

       //AddChar
       void addChar(){
           if (lexLen <= 98) {
               lexeme[lexLen++] = nextChar;
               lexeme[lexLen] = 0;
           }
           else
               printf("Error - lexeme is too long \n");
       }

       //getChar
       void getChar(){
           if ((nextCharInt = getc(in_fp)) != -1) {
		       nextChar=(char)nextCharInt;
               if (isalpha(nextChar))
                   charClass = LETTER;
               else if (isdigit(nextChar))
                   charClass = DIGIT;
               else charClass = UNKNOWN;
           }
           else
               charClass = EOF;
       }

       // getNonBlank
       void getNonBlank(){
           while (isspace(nextChar))
               getChar();
       }

       //lex
       int lex(){
           lexLen = 0;
           getNonBlank();
           switch (charClass){
           case LETTER:
                   addChar();
                   getChar();
                   while (charClass == LETTER || charClass == DIGIT){
                       addChar();
                       getChar();
                   }
                   nextToken = IDENT;
                   break;
                   // parse int lits
               case DIGIT:
                   addChar();
                   getChar();
                   while (charClass == DIGIT){
                       addChar();
                       getChar();
                   }
                   nextToken = INT_LIT;
                   break;

                //pares and ops
               case UNKNOWN:
                   lookup(nextChar);
                   getChar();
                   break;

                   //EOF
               case EOF:
                   nextToken = EOF;
                   lexeme[0] = 'E';
                   lexeme[1] = 'O';
                   lexeme[2] = 'F';
                   lexeme[3] = 0;
                   break;
           }
        // end of switch
           printf("Next token is: %d, next lexeme is %s\n",nextToken, lexeme);
           return nextToken;
       }

PS - I later stumbled onto compileonline.com, which is a really handy way to test programs in any GCC language.

SLC - 14 Apr 2013
Crete
I 'm taking another Java class and in looking to do a speedy sort, found this great blog post: http://stas-blogspot.blogspot.com/2010/10/all-you-need-to-know-about-quicksort.html
Only problem was the code is not copy-paste ready. So I thought I'd post a ready-to-go version. This is lacking the additional insertion sort and I didn't bother with dual-pivoting, but as is, this median-selected pivot, three way partition quicksort was much faster (about 20x for n=1000000) than the quicksort used for primitives in SE7 (arrays.sort). All you do is pass an integer array using "quickSort(arrayName);".
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
} // end swap

public static void swapPair(int i, int j) {
    int temp = i;
    i = j;
    j = temp;
} // end swapPair

public static void sortPair(int a, int b) {
    if(a > b) { swapPair(a, b); }
} // end sortPair

public static int median3(int a, int b, int c){
    return (a > b & a  < c) ? a : ( a >c &a <b ) ? a : ( c> a & c <b )? c :( c> b & c  < a  ) ?c:b; 
} // end median3

public static int median5(int a, int b, int c, int d, int e) {
    sortPair(a, b);
    sortPair(d, e);
    sortPair(a, d);
    sortPair(b, e);
    sortPair(c, d);
    sortPair(b, c);
    sortPair(c, d);
    
    return c;
} // end median5
    
public static void quickSort(int array[]) {
   quickSort(array,0,array.length-1);
}
   
public static void quickSort(int[] arr, int beginIdx, int len) {
    if ( len < 2 ) { return; }

    final int endIdx = beginIdx+len-1;
    final int pivot = getPivot(arr, beginIdx, len);
    final int lengths = threeWayPartitioning(arr, beginIdx, endIdx, pivot);

    final int lLen = (int)(lengths>>32);
    final int rLen = (int)lengths;

    quickSort(arr, beginIdx, lLen);
    quickSort(arr, endIdx-rLen+1, rLen);
}

public static int getPivot(int arr[], int beginIdx, int len) {
   if ( len <= 512 ) {
       int p1 = arr[beginIdx];
       int p2 = arr[beginIdx+(len>>1)];
       int p3 = arr[beginIdx+len-1];

       return median3(p1, p2, p3);
   } else {
       int p1 = arr[beginIdx+(len/4)];
       int p2 = arr[beginIdx+(len>>1)];
       int p3 = arr[beginIdx+(len-len/4)];
       int p4 = arr[beginIdx];
       int p5 = arr[beginIdx+len-1];

       return median5(p1, p2, p3, p4, p5);
   }
}

public static int threeWayPartitioning(int[] arr, int beginIdx, int endIdx, int pivot) {
   int i = beginIdx-1;
   int l = i;
   int j = endIdx+1;
   int r = j;
   
   while ( true ) {
       while (arr[++i] == pivot){}

       if ( i >= j ) { break; }

       swap(arr, i, j);
       if ( arr[i] == pivot ) {
           swap(arr, i, ++l);
       }
       if ( arr[j] == pivot ) {
           swap(arr, j, --r);
       }
   }
   // if i == j then arr[i] == arr[j] == pivot
   if ( i == j ) {
       ++i;
       --j;
   }

   final int lLen = j-l;
   final int rLen = r-i;

   final int pLen = l-beginIdx;
   final int exchp = pLen > lLen ? lLen: pLen;
   int pidx = beginIdx;
   for(int s = 0; s <= exchp; ++s) {
         swap(arr, pidx++, j--);
   }
   final int qLen = endIdx-r;
   final int exchq = rLen > qLen ? qLen : rLen;
   int qidx = endIdx;
   for(int s = 0; s <= exchq; ++s) {
         swap(arr, qidx--, i++);
   }
        long rlen = 0;

   return (int) ((((long)lLen)<<32)|rlen);
}
PS - Nevermind... doesn't work because Java is all 'pass by value'. That's retarded. Just another reason for me to hate Java over... just about every other language.

Copyright 2001-2013 Optic Fox. All rights reserved.
Some card names and all images of Magic: the Gathering including tap & mana symbols
and card artwork are copyrighted by Wizards of the Coast, Inc..