Syntax analysis from the Dragoon Book

by Forrest Sheng Bao http://fsbao.net

I got quite confused about my compiler class this semester. The textbook we used is the famous "Dragoon Book" - Compilers, Principles, Techniques and Tools, by Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman. Now I have figured everything out regarding syntax analysis. So I decide to write the algorithms in my way.

How to eliminate left recursion

Replace the rule $$B\to B{P}_1|\cdots |B{P}_m|P_{m+1}|\cdots |P_n$$

by $$B\to P_{m+1}{B}^{\prime }|\cdots |P_n{B}^{\prime }$$ and$$B^{\prime }\to P_1{B}^{\prime }|\cdots |P_m{B}^{\prime }|ϵ$$

How to eliminate common prefixes

Replace the rule $$A\to \alpha {\beta }_1|\alpha {\beta }_2|\cdots |\alpha {\beta }_n|{\mathrm{\Sigma }}_1|\cdots |{\mathrm{\Sigma }}_{n+m}$$

by $$A\to \alpha A^{\prime }|{\mathrm{\Sigma }}_1|\cdots |{\mathrm{\Sigma }}_{n+m}$$

and $$A^{\prime }\to {\beta }_1|\cdots |{\beta }_n$$

Top-down parsing

To rule $$X\to Y_1{Y}_2\cdots Y_n$$

First(X):

1. $$\text{First}(Y_1)\subseteq \text{First(X)}$$
2. If $$Y_1\cdots Y_k\Rightarrow *ϵ$$ , then $$\text{First}(Y_{k+1})\subseteq \text{First(X)}$$
3. If $$Y_i\to ϵ,\forall i$$ , then $$ϵ\in \text{First}(X)$$

Follow(X):

1. $ is contained in Follow(X)
2. If $\forall A\to \alpha S\beta$, then $\text{First}(\beta )/ϵ\subseteq \text{Follow}(S)$
3. If $A\to \alpha B$ or $A\to \alpha B\beta$ and $\beta \Rightarrow *ϵ$ , then Follow(A) $\subseteq$ Follow(B)

Happy Free Software day!

by Forrest Sheng Bao http://fsbao.net

Today, yes, Sept. 20, is the Free Software Day!

So, I wanna give you a joke as the gift.

What is the No. 1 bug of Ubuntu, the most popular Linux distribution?

You may say, my wireless card doesn't have open source driver, or my multimedia key can't work out-of-the-box.

But, you are wrong. The No. 1 bug of Ubuntu Linux is: Microsoft has a majority market share.

I am kidding? No, I am serious. If you don't believe me, then go to launchpad.net and see what's the top 1 bug of Ubuntu.

https://bugs.launchpad.net/ubuntu/+bug/1

See? This is a bug, and it's in progress, and it's critical, and it's assigned to Mark Shuttworth, the founder of Ubuntu Foundation.

Here is the description:

Microsoft has a majority market share in the new desktop PC marketplace.
This is a bug, which Ubuntu is designed to fix.

Non-free software is holding back innovation in the IT industry, restricting access to IT to a small part of the world's population and limiting the ability of software developers to reach their full potential, globally. This bug is widely evident in the PC industry.

Steps to repeat:

1. Visit a local PC store.

What happens:
2. Observe that a majority of PCs for sale have non-free software pre-installed.
3. Observe very few PCs with Ubuntu and free software pre-installed.

What should happen:
1. A majority of the PCs for sale should include only free software like Ubuntu.
2. Ubuntu should be marketed in a way such that its amazing features and benefits would be apparent and known by all.
3. The system shall become more and more user friendly as time passes.

Control your home appliance thru Internet via freetalk, Jabber/Google talk and X10

by Forrest Sheng Bao http://fsbao.net

Few months ago, I made a video.

Many friends asked me how I made it. Now here it is. This is a very brief one and I will enrich it later.

Hardware requirements:

1. You will need a computer interface to X10. It is an adapter between your computer and the X10 network. And since your computer can connect to the Internet, you can control all home appliances connected to X10 network thru your computer, and thus, over the Internet.
2. You will also need a lamp or appliance module to receive the X10 signal and to switch on/off your home appliance.

You can get above two stuffs from many companies. But I recommend X10.com 's stuffs. My computer interface model is HC60CRX. A popular model number is CM15/CM11.
This article is based on an X10 communication software called Heyu. It could work well with X10.com 's stuff.

Jabber account requirements:

You will need two Jabber IM accounts, like Google talk. Freetalk is an Jabber protocol client software. We can hook up some extra functions to Freetalk so that it will do something when you send special texts to it.

You can login your regular Jabber account from the machine you are using and login to your irregular Jabber account from the machine at your home place, where has the home appliance to be controlled.

Steps

1. Install freetalk and Heyu

sudo apt-get install freetalk

Go to http://heyu.org/download/ to download Heyu.

Open a terminal and unzip Heyu source code. Change to the directory containing Heyu source code and run

./Configure

And then follow the instruction.

You will be automatically prompted like this: I did not find a Heyu configuration file. Where would you like the sample Heyu configuration file installed? 1. In directory /home/forrest/.heyu/ 2. In subdirectory .heyu/ under a different user home directory 3. In directory /etc/heyu (for system-wide access) 4. No thanks, I'll take care of it myself Choice [1, 2, 3, or 4] ? 1 According to my experience, I prefer to put the configuration file under my home directory. So I input 1 and enter.

Then, your will be asked about the serial port address. By default, the port name is /dev/ttyS0 if you have a serial port on your computer. If you are using a USB-RS232 converter, then it should be /dev/ttyUSB0.

I will add the TTY port for your CM11 to the config file
Specify /dev/ttyS0, /dev/ttyS1, etc., or the word dummy
To which port is the CM11 attached?
/dev/ttyUSB0
Setting uid:gid = 1000:1000 for /home/forrest/.heyu/x10config

2. Configure you X10 adapter and lamp module

Now please set the home code (i.e., A) and device code (i.e., 2) of your lamp module, according to your device manual. For example, you can screw a knob to do that. The home code and device code are used in X10 protocol to address devices. I addressed my lamp module as A2.

Then, hook your X10 computer interface with your computer and plug it, as well as the lamp module, to the power outlets. Don't forget to connect your light with the lamp module.

3. Configure and test heyu

You can use heyu info command to see all devices under the same home code.

forrest@Xnote:~/.heyu$ heyu info
Heyu version 2.3.2
Configuration at /home/forrest/.heyu/x10config
Powerline interface on /dev/ttyUSB0
Firmware revision Level = 1
Interface battery usage = Unknown (0xFFFF)
Raw interface clock: Thu, 20:26:59, Day 254
(--> Civil Time: Thu  21:26:59  Sep 11 2008 CDT)
No schedule has been uploaded by Heyu.
Housecode = A
0 = off, 1 = on,               unit  16.......8...4..1
Last addressed device =       0x0000 (0000000000000000)
Status of monitored devices = 0x0000 (0000000000000000)
Status of dimmed devices =    0x0000 (0000000000000000)

If you got the error, like this:

tarting heyu_relay
Unable to send address bytes

maybe the X10 computer interface is not connected properly. If you are using USB-RS232 converter, try to plug-unplug the converter to solve this "freezing" problem.

To turn on a lamp module, run like this:

heyu on A2

. And to turn it off, run

heyu off A2

.

4. Hook freetalk with Heyu

Create a hidden directory under your home directory

mkdir ~/.freetalk

And create a file called freetalk.scm in that new hidden directory. If you already have one Jabber account, you need a new one. So they can "chat" each other. You will use one account to send messages to another one. After freetalk gets the message, it will do something you want.

You can set some login information, like this:

(ft-set-jid! "someone@gmail.com")
(ft-set-server! "talk.google.com")
(ft-set-password! "thepsswod")
(ft-set-prompt! "~\\/~ ")
(ft-set-sslconn! #t)
(ft-set-port! 5223)

Make sure it's the information of the account intent to receive your magic messages.

So you don't need to input all these information anymore. Just type freetalk at the shell terminal and they will be automatically used.

Now is the most exciting part. You can associate special behavior with the a sentence. Insert things like this into your freetalk.scm:

(define (issue timestamp from msg)
"Forward command"
(if (ignored-message? msg)
(ft-hook-return)
(cond ((equal? msg  "turn the slow cooker on")
(begin
(system "heyu on A2")
(system "echo Turn slow cooker on")
(ft-send-message "someone@gmail.com" "Sir, slow cooker is on now. Mission accomplished.")
(ft-hook-return)
))
((equal? msg "turn the slow cooker off")
(begin
(system "heyu off A2")
(system "echo  Turn slow cooker off")
(ft-send-message "someone@gmail.com" "Sir, slow cooker is off now. Mission accomplished.")
(ft-hook-return)
))
)
)
)

This configuration uses the grammar of the LISP programming language. In above example code, after you send "turn the slow cooker on", your A2 device will be on.

Ok, that's it. If you have anything not understood, please feel free to contact me.