Precedence Climbing in JavaCC

Precedence Climbing is described in Parsing Expressions by Recursive Descent.  Here we look at how to implement the highlighted part in JavaCC, namely, how to exit the loop.

Exp( p ) is
    var t : Tree
    t := P
    while next is a binary operator and prec(binary(next)) >= p
       const op := binary(next)
       consume
       const q := case associativity(op)
                  of Right: prec( op )
                     Left:  1+prec( op )
       const t1 := Exp( q )
       t := mkNode( op, t, t1)
    return t

Semantic lookahead looks like a nice solution.  Below is a sample implementation:

public ExprNode Expr(int p) :
{
    ExprNode expr, expr1;
    OpBinary op;
}
{
    (
        expr = ExprPrefix()
        (
            LOOKAHEAD({ nextBinaryOp() != null && 
                nextBinaryOp().getPrecedence() >= p })
            op = BinOp()
            expr1 = Expr(op.getAssoc() == OpBinary.Assoc.RIGHT ?
                op.getPrecedence() : op.getPrecedence() + 1)
            { expr = new ASTExprBinary(op, expr,  expr1); }
        )*
    )
    { return expr; }

} 

()* construct corresponds to the while loop.  Since this construct is a choice point, the false expression value in the LOOKAHEAD simply exits the loop.

We define nextBinaryOp() in the parser class as follows:

private OpBinary nextBinaryOp()
{
    return OpBinary.fromCode(getToken(1).kind);
}

getToken(1) does not modify the input stream and is equivalent to next in the original algorithm.

Definitions of ExprNode, OpBinary, ExprPrefix, BinOp and ASTExprBinary are omitted for brevity.

Formatter/encoder widgets from Bing

These are quite useful when you need to quickly format/encode some strings.

A novice's guide to installing CM 13 on HTC One A9 - Fail!

In the previous post I described how after following these steps to install CM 13 I ended up in a boot loop.  I also described the recovery process that allowed me to install the official system image provided by HTC.

Then I tried to repeat the same CM 13 installation steps expecting different results (is this what is called insanity?) but ended up in the same boot loop.  I recovered again back to the official HTC system image (now I know how to do it), but then made the same mistake one more time and ended up in a third boot loop.

After that I decided to test the effect of every step.  First, I rebooted the phone to download mode and installed custom recovery image:

fastboot flash recovery twrp-3.0.2-0-hiae.img

I rebooted to system and verified that the official HTC system still worked.  Then I rebooted the phone to recovery mode.  The first thing TWRP asked be was to enter password to decrypt the storage.  Since I haven't setup any password yet and I didn't know the default password, after reading this thread I setup my password and told the system to ask for the password at boot time.  While I was able to boot the phone with the new password successfully, TWRP did not recognize it. From the thread above it seems to be a known issue: TWRP only recognizes the password on certain device/OS version combinations.

I booted to recovery mode again and pressed Cancel when TWRP asked for the password.  Then I Swiped to Allow for Modifications, pressed Wipe and Swiped to Factory Reset.  Then rebooted to System.  At this point the official HTC system was still there, only all the settings were lost, so the phone asked me to set it up again.  I didn't, powered it down and booted to recovery mode again.

While in recovery mode, I pushed CM 13 and Google apps to sdcard:

adb push cm-13.0-20160710-NIGHTLY-hiaeul.zip /sdcard/

adb push open_gapps-arm64-6.0-nano-20160704.zip /sdcard/

Then I tried to back up the System, Data, and Boot (together and each separately) without any luck.  TWRP would give me Unable to mount storage error message.  This is probably due to the same not recognizing password issue mentioned earlier.

Not being able to back up the system, I simply clicked on Install, added cm-13.0-20160710-NIGHTLY-hiaeul.zip. Then I clicked on Add more Zips, added open_gapps-arm64-6.0-nano-20160704.zip and Swiped to confirm Flash. Fingers crossed...

TWRP installed both ZIP files but at the end displayed an error saying Unable to mount storage - the same error when I tried to back up the system.  I went on and clicked on Reboot System and ended up in the same boot loop: a white screen, a green HTC logo, and a message in red: 

This  build is for development purposes only.  Do not distribute outside of HTC without HTC's permission, Failure to comply may lead to legal action. 

Then reboot.  Then the same message. Then reboot again...

I thought that installation of CM 13 failed again, but after the third reboot the phone showed CyanogenMod logo.  Finally!  But then the system asked me to enter password to decrypt the storage.  Since I didn't have any password after the system was wiped earlier, I typed my previous password that I used before wiping the system.  It did not work of course.  The system said that I needed to reset to factory defaults in order to continue using it.  I clicked the presented button and the phone rebooted to recovery mode.

In recovery mode TWRP asked me to Enter Password.  I clicked on Cancel since I did not have any password.  Swiped to Allow Modifications. Wipe. Swipe to Factory Reset. Reboot System. The same boot loop again, this time around without any luck.  CyanogenMod did not boot on the third time, on the fourth time, and so on.  I decided to let the phone sit in the boot loop for a while and watch what happens.

I went to a supermarket (about 20 minutes trip) - the phone was still sitting in the boot loop.  It's time to do something else.  Waited until the phone starts rebooting, pushed Volume Down and Power keys, booted into download mode, rebooted to bootloader mode and then to recovery mode.  In TWRP, Swiped to Allow Modifications,  Wipe, Swipe to Factory Reset.   Pushed cm-13.0-20160710-NIGHTLY-hiaeul.zip and open_gapps-arm64-6.0-nano-20160704.zip as earlier,  Install, chosen both ZIP files as before, Swiped to confirm Flash, then clicked on Reboot System. 

Boot loop again...  After about 15-20 reboots CyanogenMod logo appeared.  Wow!  Let's wait.  Android is starting... Optimizing app 78 of 106.  I haven't seen this before!  Looks like we're finally getting there!  Oops... Reboot, boot loop again... 

Washed dishes, came back - the phone was still rebooting.  Volume Down + Power when the phone rebooted.  Entered download mode.  Unzipped cm-13.0-20160710-NIGHTLY-hiaeul.zip, found boot.img.   Ran

fastboot flash boot boot.img

Rebooted and entered the same boot loop.  Somebody does not want me to install CyanogenMod.  Either CyanogenMod developers, TWRP developers or HTC developers.  Or they simply joined forces against me...

Back to recovery mode through download and bootloader modes.  Wipe, Advanced Wipe, then wiped Dalvic/ART Cache, System, Cache and Data.  Then installed cm-13.0-20160710-NIGHTLY-hiaeul.zip and open_gapps-arm64-6.0-nano-20160704.zip.  Reboot System.  Boot loop...

I've already seen CyanogenMod logo twice, that's enough for today.  At least I know how to recover to the official HTC system.  Not sure if I continue exploring CyanogenMod any longer.  Why does it have to be so hard?

Recovering HTC One A9 from boot loop.

I followed these steps to install CM 13 on an HTC One A9 phone, but the phone ended up in a boot loop. Asking for help in G+ CyanogenMod community and CyanogenMod forum didn't produce any response, and I decided to try re-installing an official system image from HTC.

I downloaded HTC RUU utility (Unlocked/Developer HTC One A9).  Unfortunately, the utility would not detect my phone because it thought there was no USB connection with it.   The phone was unlocked at this point.  I re-locked the phone back and re-run RUU utility, but result was the same - no USB connection.  This was strange because when I booted the phone to recovery mode (TWRP), I could connect to the phone using adb utility without problems.  As it turned out later, there was no need to re-lock the phone, the process would also work for an unlocked phone.

The problem was that Android boot loader interface was not installed on my PC.  When I rebooted the phone to boot loader mode, fastboot utility could not recognize it and would display a message "waiting for any device".  To fix this error, I followed these steps to install boot loader interface on the PC.

After installing boot loader interface and rebooting the phone to boot loader mode, HTC RUU utility was able to recognize the phone.  But it started to complain that the phone's battery was charged below 30%, even though the battery was fully charged.  The key here is instead of staying in boot loader mode, the phone needs to be rebooted to download mode.  Make sure that after rebooting the boot loader interface is still available.  If not, repeat these steps again to bring boot loader interface back.

Finally, having the phone in download mode, I started the recovery process.  Everything was going fine until the utility rebooted the phone from download mode to boot loader mode at the beginning of the process.  At this point HTC RUU failed.  I tried to go through the recovery steps offered by the utility with no luck.

Finally I figured out what was going on.  After HTC RUU rebooted the phone, boot loader interface disappeared from my PC.  I had to open the Windows device manager and carefully watch the state of the boot loader interface driver.  When HTC RUU utility rebooted the phone, I could see that the boot loader interface was gone.  At this point, while HTC RUU was trying to re-connect to the phone, I quickly repeated these steps again. Right in the middle of the recovery process.  As soon as the driver was re-installed, HTC RUU recognized my phone and continued the installation process.  After several trial and error attempts and going through recovery process offered by HTC RUU, the utility correctly installed the official system image from HTC.

A few words about recovery process: the instructions displayed by HTC RUU did not work for HTC One A9.  There is no way to take out the battery, and pressing power button for 10 seconds or more did not power the phone down.  To power the phone down, I had to reconnect it to the PC and run fastboot reboot bootloader command.  After getting to the boot loader menu there was an option to power the phone down.

Now I have the phone back.   I'm going to give CM 13 another try.  Hopefully this time the installation will be successful.  If not, at least I know how to recover the phone to its original state.

I hope this information will be helpful to someone who runs into similar issues.

GQL Parser 1.1.0

Version 1.1.0 is now available on github and bintray.  It is a breaking change were Series interface was renamed to Sequence because the new name better reflects the purpose of the interface.

Including in Gradle build file

buildscript {
    repositories {
        jcenter()
    }
}

dependencies {
    compile 'mobi.tjorn.parsers:gql:1.1.0'
}

GQL Parser 1.0.1

The first release of GQL Parser was compiled with Java 8 which made it impossible to include in Android projects unless the project was using buildToolsVersion 24.

A version 1.0.1 is now available on github and bintray.  It is compiled with Java 7 and does not require buildToolsVersion 24 when included in Android projects.

Including in Gradle build file

buildscript {
    repositories {
        jcenter()
    }
}

dependencies {
    compile 'mobi.tjorn.parsers:gql:1.0.1'
}

GQL Parser is available

First release of GQL Parser library is available on github and bintray.

Including in Gradle build file

buildscript {
    repositories {
        jcenter()
    }
}

dependencies {
    compile 'mobi.tjorn.parsers:gql:1.0.0'
}

The above will include classes, sources and API docs.  For more details visit the project's github page.

Right recursion in JavaCC

Being LL(k) parser generator, JavaCC does not support left recursion and productions like

A ->  a | Ax

need to be converted to 

A -> a (x)*

Apparently, right recursion also requires some care.  Suppose we need to implement a right-associative operator = to parse strings like a=b=c=d:

right -> letter = right | letter
letter -> ["a"-"z"]

Simple JavaCC grammar, like below, would not work.

SKIP :
{
  " "
| "\t"
| "\n"
| "\r"
| "\f"
}

TOKEN [IGNORE_CASE] :
{
    <EQ: "=">
  | <LETTER: ["a"-"z"]>
}

public void Right() :
{}
{
    <LETTER> <EQ> Right() | <LETTER>
}

Compiling generated Java code would produce an error:

Error:(29, 12) error: unreachable statement

try {
  switch ((jj_ntk==-1)?jj_ntk_f():jj_ntk) {
  case LETTER:{
    jj_consume_token(LETTER);
    jj_consume_token(EQ);
    Right();
    break;
    }{
    jj_consume_token(LETTER);
    break;
    }
  default:
    jj_la1[0] = jj_gen;
    jj_consume_token(-1);
    throw new ParseException();

}

Adding a LOOKAHEAD at the first choice point fixes the problem:

public void Right() :
{}
{
    LOOKAHEAD(2) <LETTER> <EQ> Right() | <LETTER>

}

Usually JavaCC issues a warning about choice conflict involving two expansions, but not in this case.

Loaders 1.0.0

First release of Loaders library is now available on github and bintray.

Including in Android Studio/Gradle

buildscript {
    repositories {
        jcenter()
    }
}

dependencies {
    compile 'mobi.tjorn.content:loaders:1.0.0'
}

The above will include classes, sources and API docs.  For more details visit the project's github page.

Creating a bootable USB stick on OSX

Good instructions on how to create a bootable USB stick on OSX.  Just pay attention to how a raw disk /dev/rdiskN is used in step 8 instead of a regular disk /dev/diskN that is used in all other steps.  After following these instructions I was able to install Ubuntu 15.10 on an old Dell Latitude E6410 without any problem.