Tuesday, 20 March 2018

Building a COOL lexical analyzer generator using JLex

The reason for making this post, is to give an overview of the procedure I followed while making a lexical analyzer generator for the COOL programming language, under this Stanford course. 

CHEATING:

Not exactly, but that's how I made the lexical analyzer generator (LAG). Why you ask? Yeah, coming on that topic. What would you call copying someone else's code your starting point of work? PLAGIARISM! 

Yes, I definitely did it. 

I copied whole of the code from here. "Boy you're a bad one!" might be your line of choice, but I'd rather ask you to wait and listen, that when I tried to submit this code (not to skip the work, just curious about the accuracy of the solution), and got a score of 11 out of 63. 

"What's a score?" you ask? Well, it tells us about the successful recognition of tokens in cool program files. So, a score of 11 out of 63 would tell that there are a lot of cool files whose tokens, weren't recognized properly.

This, was good. The effort put to make this score better made me understand a plethora of stuff, that I didn't know about earlier.

So, here I'll discuss the modifications I made to the code, and the reasons for doing so. Some are general explanations on the things that I think I should've known before.

STRINGS:

Oh dear. I love strings. They are so, curiously built, have so much inside them, still remain under a single name. Ohh the unity.

 1. How to recognize Strings?
Well, we all know that a string starts with a quote, that is the '\"' character. So, you'll be needed to   recognize that when in the initial (YYINITIAL) state, and then change the state to a state that represents a string only. We can call it the STRING state.
The initialization state and it's code looks like this :

<YYINITIAL> \"  { 
  string_buf.delete(0, string_buf.length());
  yybegin(STRING); 
  stringTooLong=false;
  nullInString=false;
  stringError=false;
  skip = false ;
 }


2. What to do when a string has just started?
You'll definitely want to save the string and return it when you recognize one. So, in order to do that, you have two options:
  1. Use a String object, or
  2. Use the String buffer.
We're more used to using the String class, but it has a problem, that it is immutable.  We can't change the stuff that has gone inside the string. But wouldn't we have to just add characters as we see and then return the string when the ending quote is seen? No. I wish it was that easy.

We would have to use the String buffer, as we need to make changes to characters already added to the buffer (will explain later you hungry beast).

So, when  the string recognition phase has just started, we'll initialize a string buffer.
string_buf.delete(0, string_buf.length());

Here, this initialization is to delete the previous string saved (if any) inside the buffer.

The next step is to change the state from the YYINITIAL  to STRING. This can be done by :
yybegin(STRING) ; 
Next is to check for a "null" in a string, or if the string is too long. If the previous string had a "null" in it then the boolean variable nullInString would be true. So when we see a new string, we'll change it back to false. Same for the variable stringTooLong. 

There is one more variable skip inside the initialization, but we'll discuss it later.
3. What to do when inside the string?This one is pretty complex. We'll reach this stage after the current state (which is given by yy_lexical_state ), has changed from YYINITIAL to STRING state. This can be divided into three major parts:
  1. The ending quote.
  2. All the stuff inside the string, except the newline, or a quote
  3. The newline
The newline is considered separately because in COOL, we need to escape the newline. So, extra measures have to be taken when we see a newline inside a string.

A. The ending quote has been recognized while traversing the string

<STRING> \" {
 // If an escape character appears before a quote, we must put a quote into the string
  if(stringTooLong) {
        yybegin(YYINITIAL) ;
 
    return new Symbol(TokenConstants.ERROR, "String constant too long");

  } else if(nullInString) {
        yybegin(YYINITIAL) ;
       return new Symbol(TokenConstants.ERROR, "Null character appeared in string");
  } else if(stringError) {
        yybegin(YYINITIAL) ;
    return new Symbol(TokenConstants.ERROR, "Error occurred while parsing string");
  } 
  

  if(!skip && string_buf.length()>0 && string_buf.charAt(string_buf.length()-1)=='\\') {
    string_buf.setCharAt(string_buf.length()-1, '\"');
  } else {
    yybegin(YYINITIAL); 
    return new Symbol(TokenConstants.STR_CONST, AbstractTable.stringtable.addString(string_buf.toString())); 
  }
 }

When the ending quote has been recognized, then we are sure that the current string has ended. So, if some error ocurred while the recognition of the string, then we can reject the string after raising an error.

Note that I will not discuss Symbol, TokenConstants, and AbstractTable here, (because I just don't understand them properly yet). They will be added as a footnote later or as another blog post, as soon as I understand them.

We'll have to change the current state to YYINITIAL in order to signify that what comes next is code not string.

This is done for all the errors that could be raised.

Now did you realize, that a quote can also come inside a string, when escaped. Boom. That was an increase in complexity. So, how will you know that the current quote is THE end quote, or just some normal escaped quote inside the string?

This can be done by checking the last entry of the string buffer. That is, checking the

string_buf.charAt(string_buf.length()-1)
for '\\'. If it is '\\' then we know that the quote is escaped, and thus it simply should be added to the string buffer, as '\"'. Note that we replaced '\\' by '\"' inside the String buffer. The input doesn't take "\n" as '\n' but as '\\' and 'n'. 

But when we know that the current quote is not escaped and is not to be skipped, then we can safely conclude that the current quote is THE ENDING QUOTE. And we can safely go back to the YYINITIAL state and add the string to the AbstractTable.

What about "skip"?
Wait, until normal character recognition comes in. Just wait. Please.

B. All the stuff inside the string, except the newline, or a quote

<STRING> [^\n\"] { // Code for handling other characters encountered in strings
  // including special cases for escaped characters
  if(string_buf.length()==0) 
  {
    string_buf.append(yytext());
  } else 
  {
    
    // Check if null character appears in input stream
    if(yytext().charAt(0)=='\0' || nullInString) 
 {
      nullInString=true;
    } else
    {
      int length=string_buf.length();
      if(string_buf.charAt(string_buf.length()-1)=='\\') 
   {
  if(skip)
        {
   string_buf.append(yytext()) ;
   skip = false ;
        }
  else
       {
        switch(yytext().charAt(0))
  {
  case 'b':
    string_buf.setCharAt(length-1, '\b');
    break;
  case 't':
    string_buf.setCharAt(length-1, '\t');
    break;
  case 'n':
    string_buf.setCharAt(length-1, '\n');
    break;
  case 'f':
    string_buf.setCharAt(length-1, '\f');
    break;
  case '\\':
    string_buf.setCharAt(length-1, '\\');
    skip = true ;
    break;
  default:
    string_buf.setCharAt(length-1,yytext().charAt(0)) ;
  }
       }
 
      }
     else
  {
  string_buf.append(yytext());
     }
    }

  }
    if(string_buf.length()>=MAX_STR_CONST)
  {
    stringTooLong=true;
  }
 }  


This looks scary. It isn't. Simply, check if the buffer is empty, if yes then add whatever is coming in. Then some error checking. Bleh. Boring.

Remember when I said that "\n" is seen as '\\' and 'n'? Yeah, now we'll have to do that for all escaped characters. The special ones like a backspace and tabs are like "\b" and "\t", so they're actually '\\' with 'b' and '\\' with 't'. So, if the last character seen is a '\\' then we'll have to handle this escaping procedure.

Note that we can't have a newline here, so we don't have to worry about it much.

By "handling this escaping procedure" I mean that we'll replace the seen '\\' with the correct characters, like '\t' and '\r' et cetera.

What's a 'n' doing in there? Aren't newlines not allowed?

Yeah but that isn't a newline! That is just  "\n"  in a string. A newline is \n or "
"

Pressing "Enter"  creates a newline. Simply writing "\n" won't simulate it$^1$. Though we can explicitly tell the receiver that my "\n" means a newline, then only it can simulate a newline. Even though without the said agreement, \n has no real meaning of it's own.

So, we'll do the same for a "\n" as we did for "\t" or "\b".

Also note the '\c' has no special significance, and is equivalent to 'c'.

What if the last '\\' seen, itself is an escaped '\\'? 

Boom. Boom. Boom. High complexity levels. Existential crisis in here.

Yeah, what will you do now? If we didn't do anything, then strings like "Hello \\\kitty", which actually is "Hello \kitty" is converted to "Hello kitty", removing the '\\' altogether. This happens in this sequence:
  1.  "\\" is converted to "\"
  2. "\k" is converted to "k"
This is problematic. The solution that seemed apt to me was to skip the next character from this "if the previous character was '\\' check" altogether, signifying that the '\\' is not to escape anything at all.
So, skip is initialized to false. It is made true when a '\\' is seen after a '\\' and is made false again, when a character is skipped.
We must skip the conversion of a escaped newline into a newline, if the last '\\' doesn't signify the newline's escape. Same for a quote.
We also must re-initialize skip to false when we see a new string.
Everything else in the code is self explanatory and I will not bother to explain them.
C. A newline is seen

<STRING> \n { // Code for newline characters
  // If a newline appears in a string, it must be escaped, else error
  if(string_buf.length()==0 || skip || string_buf.charAt(string_buf.length()-1)!='\\') {
    curr_lineno++;
    yybegin(YYINITIAL) ;
    return new Symbol(TokenConstants.ERROR, "Unterminated string constant");
  } else {
    curr_lineno++ ;
    // Replace '\' character in string buffer with newline
    string_buf.setCharAt(string_buf.length()-1, '\n');
  }
 }

A newline is seen in the string. This is a rare and auspicious occasion. No. Not really.

We just need to check if the current newline is legit or not. If it isn't then we need to return an error, otherwise we add it to the buffer after making some modifications.

 COMMENTS:

Comments in cool are of the form (*...*). They can be nested as well. Again when a '(' is seen before a '*'  while in the initial YYINITIAL state, then we can say that a comment has begun and thus go to the BLOCK-COMMENT state.

When in the BLOCK-COMMENT state if a '*' or a ')' or a '(' is seen then, it's okay! They shouldn't be together though. if we see a "(*" then we increase the nestedCommentCount and when a "*) " is seen then we decrease it. When it reaches zero, then we can simply change our current state back to YYINITIAL. Here is the code telling you the same thing, you dumbo:

<YYINITIAL> "(*" { yybegin(BLOCK_COMMENT); }
<BLOCK_COMMENT> \(\*  { nestedCommentCount++; }
<BLOCK_COMMENT> \n  { curr_lineno++; }
<BLOCK_COMMENT> [^\n\)\*] { /* Do Nothing */ }
<BLOCK_COMMENT> \*  { /* Do nothing */ }
<BLOCK_COMMENT> \)  { /* Do Nothing */ }
<BLOCK_COMMENT> \*\) {
  if(nestedCommentCount!=0) {
    nestedCommentCount--;
  } else {
    yybegin(YYINITIAL);
  }
 
}

Minor Points:

  1.  Pressing "Enter" in windows means "\r\n" not "\n" only. '\r' is carriage return, that brings back the cursor back to the initial point, and '\n' is simply the newline or the linefeed.
  2. Know that [==] isn't the same as "==" or ==. It simply means a =.
These are the main points of the things I learned while building the LAG for COOL. I consciously excluded discussion over JLex' functioning, and the minor errors that I got. They aren't that important as they are either easy to learn or debug.
Here is my code for the LAG:

Wednesday, 7 February 2018

Pima Indians Dataset: Logistic Regression, KNN, PCA, Random Forests

newNotebook
In [1]:
import pandas as pd
from sklearn.model_selection import cross_val_score
Importing the dataset, locally.
In [2]:
df = pd.read_csv('c:\\Python\\PIMAINDIAN.csv',sep=',',names=['Pregnant','Plasma','bp','tricep','insulin','bmi','dpf','age','class'])
In [3]:
df.head()
Out[3]:
Pregnant Plasma bp tricep insulin bmi dpf age class
0 6 148 72 35 0 33.6 0.627 50 1
1 1 85 66 29 0 26.6 0.351 31 0
2 8 183 64 0 0 23.3 0.672 32 1
3 1 89 66 23 94 28.1 0.167 21 0
4 0 137 40 35 168 43.1 2.288 33 1

KMeans

Now we'll apply the KMeans clustering algorithm to the dataset.
In [4]:
from sklearn.cluster import KMeans
In [5]:
kmeans = KMeans(n_clusters = 2)
In [6]:
kmeans.fit(df)
Out[6]:
KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
    n_clusters=2, n_init=10, n_jobs=1, precompute_distances='auto',
    random_state=None, tol=0.0001, verbose=0)
Now, we have made two clusters, by using the KMeans algorithm. Our point now, is to find out the distribution of diabetic people in both the clusters, and deciding whether it makes any sense.
In [7]:
labels = kmeans.labels_ #this gives us the cluster number of the entries
In [8]:
count1 = 0
count2 = 0
for i in range(len(labels)):
    if(labels[i] == 0):
        if(df.iloc[i]['class']==1):
            count1+=1
    else:
        if(df.iloc[i]['class']==1):
            count2+=1
            
In [9]:
accuracy1 = 1.0*count1/(len(df)-sum(labels))
In [10]:
accuracy2 = 1.0*count2/sum(labels)
In [11]:
print ('KMeans :Cluster 1 with ',accuracy1*100,'% diabetic people and cluster 2 with',accuracy2*100,'%')			
KMeans :Cluster 1 with  30.18242122719735 % diabetic people and cluster 2 with 52.121212121212125 %

Result


Here, there are two clusters, one of which has 30.18 % diabetic people and the other one has 52.12% diabetic people. This shows us that if a person is in the first cluster then he is more likely to be non-diabetic. We can't say much about the second cluster.

Logistic Regression

We'll try the logistic regression over the dataset now.
In [12]:
from sklearn.linear_model import LogisticRegression
In [14]:
y = df['class']
df.drop(['class'],1,inplace=True)
In [16]:
lr = LogisticRegression()
An Logistic Regression object has been made, which we'll use for the cross_val_score() function, which performs cross validation over the dataset, using the predictors and the outputs.
In [17]:
score = cross_val_score(lr,df,y,cv=10)
In [18]:
print('LogisticRegression :',(score.mean()*100),'%')
LogisticRegression : 76.566985645933 %

Result


So, as we can see, logistic regression gave 76.566% accuracy over the dataset.

PCA + Logistic Regression

Here, we'll use PCA(principle components analysis) to reduce the dimensions of the problem to the bare important ones. (Quite a brief explanation). Then we'll use Logistic Regression over this dimensionally varied dataset.

This can be done via pipelining. The point being that, just like a pipeline (for what?) we put in our resulting PCA model, and an object of the logistic regression, into the pipeline. After which we'll again use the cross_val_score() to find the cross-validated accuracy of the model.
In [19]:
from sklearn.decomposition import PCA
In [21]:
from sklearn.pipeline import Pipeline
In [22]:
pca = PCA()
In [24]:
pipeline = Pipeline(steps=[('pca',pca),('logistic',lr)])
score = cross_val_score(pipeline,df,y)
print('PCA+logisticRegression :',(score.mean()*100),'%') 
PCA+logisticRegression : 76.69706152564787 %

Result


Well, as we can see, this procedure results in an accuracy of 76.69%, which will make us say Cooooooool, but not cool enough. as the accuracy didn't rise a lot. Shit happens.

Random Forests:

Where are my random forests?


Ohh. Not again! You're growing over the fan now? Why are you so random?

Okay they're back.

So random forests are a very cool method for supervised learning, which use bagging (bootstrap aggregation). A good source to learn about them would be this video by Trevor Hastie and Robert Tibshirani. (I would strongly recommend their book Introduction to statistical learning, which is free, and has a parallel Stanford Course too.
In [25]:
from sklearn.ensemble import RandomForestClassifier
In [26]:
rf = RandomForestClassifier()
score = cross_val_score(rf,df,y,cv=10)
In [27]:
print('RandomForests :',(score.mean()*100),'%')
RandomForests : 73.96103896103897 %

Result:


Random forests give an accuracy of 73.96%. Not quite good. No.

K Nearest Neighbors

Well back to basics. If you're new, see what the majority of nearby poeple are doing, and then imitate.But how many of those nearby people should you see?

For this case, we'll do KNN for $k=\{5,10,15,20\}$
In [28]:
from sklearn.neighbors import KNeighborsClassifier
In [29]:
for i in {5,10,15,20}:
    neigh = KNeighborsClassifier(n_neighbors=i)
    score = cross_val_score(neigh,df,y,cv=10)
    print('RandomForests :',(score.mean()*100),'%')
RandomForests : 74.34723171565277 %
RandomForests : 74.61893369788108 %
RandomForests : 72.13773069036226 %
RandomForests : 74.48051948051948 %
Can we get an $k$ versus accuracy graph please?
In [30]:
import matplotlib.pyplot as plt
accuracies = []
for i in range(20):
    neigh = KNeighborsClassifier(n_neighbors=i+1)
    score = cross_val_score(neigh,df,y,cv=10)
    accuracies.append(score.mean())
k = [i+1 for i in range(20)]    

    
In [31]:
plt.plot(k,accuracies)
Out[31]:
[<matplotlib.lines.Line2D at 0x446f5c0dd8>]

Result

We get maximum accuracy for $k=18$. Acceptable accuracy can be obtained at $k = 13$ too.

Some thoughts around fenwick trees

Some thoughts around fenwick trees References Questions https://codeforces.com/contest/863/problem/E https://www.hackerearth.com/practice/da...