F14 doesn't install Perl by default?!

WTF!? Just installed Fedora14 32-bit It doesn't have Perl installed by default? Lame!

Antlr 3.3 Sanity Setup

These are the steps to follow to setup Antlr v3.3 on Ubuntu 10.04

1. Download the antlrworks-1.4.2.jar


2. Add antlrworks-1.4.2.jar to the CLASSPATH variable. For example: export CLASSPATH=.:/path/to/jar/antlrworks-1.4.2.jar


3. Create a simple grammar called Expr.g. It's contents are:

grammar Expr;

prog: stat+ ;

stat: expr NEWLINE
| ID '=' expr NEWLINE { System.out.println("you entered a statement!"); }
| NEWLINE
;


expr: multExpr (('+'|'-') multExpr)*
;

multExpr
: atom ('*' atom)*
;


atom: INT
| ID
| '(' expr ')'
;


ID : ('a'..'z'|'A'..'Z')+ ;
INT : '0'..'9' ;
NEWLINE : '\r'? '\n' ;
WS : (' '|'\t'|'\n'|'\r')+ { skip(); } ;

4. Create a java file called Test.java that will call the objects created by Antlr3. Test.java's contents are:

import java.io.*;
import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;

public class Test {
public static void main(String args[]) throws Exception {
ExprLexer lex = new ExprLexer(new ANTLRInputStream(System.in));
CommonTokenStream tokens = new CommonTokenStream(lex);

ExprParser parser = new ExprParser(tokens);
parser.prog();
}
}

5. Compile the antlr grammar and Test.java file as follows:

java org.antlr.Tool Expr.g
javac *.java

6. Test your grammer by then typing:

java Test

and entering this expression:

a=1+2

followed by ctrl-d. This should result in the this statement appearing:

you entered a statement!

haskell.org still down!

In case you were wondering, haskell.org has been down all weekend. I hopw it is back up soon. The 2010 ICFP Programming Contest is only 2 weeks away.

Correcting Towers of Hanoi Haskell Solution

I've been really having fun playing with Haskell. I found a solution via Wikipedia for the Towers of Hanoi. The solution is here http://www.kernelthread.com/projects/hanoi//html/hs.html.



This solution will not compile with ghci v6.12.1. This is the corrected solution I tested and confirmed works with ghci v6.12.1:



dohanoi :: (Num a) => a -> a -> a -> a -> [(a,a)]

dohanoi 0 _ _ _ = []

dohanoi n from to using = let m=n-1

in dohanoi m from using to ++ [(from,to)] ++ dohanoi m using to from



hanoi :: (Num a) => a -> [(a,a)]

hanoi n = dohanoi n 1 3 2

Parsing notes

Top-down vs. bottom-up

Top-down(e.g. ANTLR) is a left most derivation(LL)
Implemented as a recursive-descent algorithm
Finds next node in left sentential form where a non-terminal is replaced with its equivalent RHS.

Bottom-up(such as yacc or parsec) is a right most derivation(LR)
Find a non-terminal in right sentential form such that non-terminal can be replaced with its equivalent LHS.

Complexity of parsing algorithms ususally O(n^3)

LL parsers cannot handle left-recursion. e.g. A->A+B will never stop
left-recursion is a rule where the LHS rule name is also on the RHS.

Pairwsie disjoint test used to evaluate a grammar if it can be LL parsed.
If a rule passes the pairwise disjoint test, then this means no RHS of a rule has a common terminal token.

left factoring(grouping common terminal/non-terminals together toward the left side) can help wiht LL parsers but not in all cases.

LR usually implemented as shift reduce algorithms.
LR advantages:

1. Works for almost all grammars
2. Works on more grammars than most other bottom-up algorithms
3. Syntax errors detected early
4. LR grammars are a superset of the grammars parsable by LL grammars

Setup of Wiktionary (Simplified) Android project

Looks like my previous instrutions for Api Demos don't apply for the new Simplewiktionary project for Android.

Even File->Import and other variations are failing. I discovered that something new and more specific was required. You might be wondering why I'm even bothering to blog this. Well, it seems that there are many wrong ways to get these sample projects into Eclipse. It seems that the 'art' is find the few right ways to do this.

1. Start Eclipse

2. File->New->Project->Android->Android Project

3. Click on the 'next' button

4. Choose your build target

5. Uncheck the 'Create Activity' checkbox

6. Specify the Project Name as 'WiktionarySimple'

7. Uncheck the 'Use default location' checkbox

8. Click on the 'Browse' of the Location textbox and go to the WiktionarySimple directory created by unzipping latest_samples.zip in the directory of your choice.

9. In the contents area, select the radio button 'Create project from existing source'

10. In the properties area, set the application name to 'WiktionarySimple'

11. Click the 'Finish' button

12. If these steps were followed, when Eclipse is done updating the workspace, the WiktionarySimple project will be compiled and the R.java file will be generated in the project.

Creating Android Sample Application

Recently, Android 2.0 had some new sample projects added. They are available as a .zip file from the Android developers site. However, if you unzip and import a project, something wrong happens. The R.java is not generated. The instructions for importing these sample project are as follows from the Android developer site:

You can easily create new Android projects with these samples, modify them if you'd like, then run them on an emulator or device. For example, to create a project for the API Demos app from Eclipse, start a new Android Project, select "Create project from existing source", then select ApiDemos in the samples/ directory. To create the API Demos project using the android tool, execute:

android update project -s -n API Demos -t -p /samples/ApiDemos/

The given instructions give 2 possible actions. The first, as indicated previously, does not work. The second action uses the 'android' executable which is part of the SDK. The options given do the following:


update project : updates an existing android project
-s : only errors produce output (silent mode)
-n : name of new android device (in this case it is 'API Demos'
-t : target id of new android device
-p : Location path of the directory where the new AVD will be created

If you run the above 'android' command-line, you will get the following result:

Updated default.properties
Updated local.properties
File build.xml is too old and needs to be updated.
Added file /home/me/Projects/A20/samples/ApiDemos/build.xml
Updated default.properties
Updated local.properties
File build.xml is too old and needs to be updated.
Added file /home/me/Projects/A20/samples/ApiDemos/tests/build.xml

So, neither of the above procedures really lets you create one of the sample projects for use. The entry will show you the right way to do this for the new ApiDemos sample.

1. The ApiDemos project is an Android 1.6 project. So, in general, make sure before using any of the sample projects that you have the right SDK version installed.

2. Start Eclipse.

3. File->New->Project...->Android->Android Project

4. click on the 'next' button

5. In the next window that appears, select the radio button 'Create Project from existing source'

6. Click on the 'Browse...' button next to the 'Location' text box.

7. Browse to the directory that contains the ApiDemos directory from the latest_samples.zip file.
The 'Location' text box should have a path like /path/to/latest/ApiDemos

8. Select OK

9. In the 'Build Target' area, select the 'Android 1.6' build target.

10. Select the radio button 'Create Project from Existing Sample'

11. In the 'Samples' drop-down, select 'ApiDemos'

12. Click on the 'Finsh' button

13. If this is succesful, the ApiDemos project will build with no errors and the R.java files will be generated automagically.

The above method should be used for the other samples, too. If you do not, the R.java file will not be generated.