TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
6
TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
M. Hielsche , Ch . Wagenknech
PHBe n – Uni e si y o Teache Educa ion
Cen um o Compu e Educa ion
Muesma s asse 29, 3012 Be n, Swi ze land
mail@michael-hielsche .de
Hochschule Zi au/Gö li z
Fachbe eich In o ma ik
B ückens aße 1, 02826 Gö li z, Deu schland
[email p o ec ed]
Abs ac
Teaching Language Theo y and Au oma a (LTaA) in such a way ha s uden s a e highly mo i a ed
o ac i ely lea n is qui e a challenging ask. This pape p esen s a pedagogical app oach ha
connec s sui able pa s o hese a he abs ac opics wi h some applica ions in au oma ed compile
cons uc ion, i.e. compile gene a ion. To ge his app oach implemen ed in a eal class si ua ion we
ha e de eloped an app op ia e lea ning en i onmen , called A oCC. To illus a e how A oCC can
be used o suppo eaching as well as lea ning, an ex ensi e exe cise on compile gene a ion, which
he au ho s lec u e on, is p esen ed.
1. In oduc ion
Language Theo y and Au oma a (LTaA) is an in eg al pa o compu e science s udies a uni e si y
le el ([4]). "P ac ice makes pe ec " exp esses he ac ha knowledge and me hods mus be ained
in o de o in e nalize. Howe e , p ac icing he abs ac con en s o LTaA appea s o be impossible
o a he una ac i e. Mos cou ses a uni e si ies a e based on se ies o heo em-p oo -example-
blocks wi h a e y limi ed e e ence o p ac ical impo ance. LTaA is he e o e o en el o be
bo ing and oo heo e ical . Thus s uden s adop a nega i e a i ude o he subjec e en be o e hy
ake an LTaA cou se.
In o de o o e come di icul ies like ha we we e looking o mo i a ing p ac ical applica ions o
he heo e ical con en s ha ha e o be augh . Compile cons uc ion (CC) as a pa o he p ac ical
compu e science componen mee s ou needs. I applies bo h, knowledge abou o mal languages
and abs ac au oma a, which is well p o ed by CC cou ses o e ed by many uni e si ies. In mos o
he cases such cou ses a e buil on he op o a long heo y o ien ed sec ion, which de ini ely does
no imp o e he indi idual mo i a ion o he s uden s si ing in a heo y class.
TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
7
A good mix o heo y and p ac ice is o en e e ed o as he sec e o success. Wi h ega d o LTaA,
CC can se e as a sou ce o mo i a ion. P ac ical needs and necessa y heo e ical knowledge should
mu ually acili a e and equi e each o he .
Fo mo i a ing s uden s o he LTaA lec u e, we de ine he goal o de eloping ou own compile
ill he end o he cou se. To sol e his ex ensi e ask we spli i in o smalle pa s like: wha is a
language and syn ax, how we can check i a wo d belongs o a gi en language, how a compile
wo ks (in gene al) and how indi idual pa s like scanne and pa se wo k. In each lec u e he
s uden s p ac ically de elop necessa y pa s o he inal compile p ojec in a heo y-apply-cycle.
This can be e e ed o as a heo y on demand p ocess.
Acco ding o he pedagogical concep b ie ly desc ibed abo e we could o ce he s uden s o c ea e
hei own compile by p og amming a scanne and pa se by hand u ilizing hei a o i e
p og amming language. In ac , his is a challenging p og amming ask; howe e , s uden s will no
lea n eally much abou he concep s o LTaA and how o apply hem on a ious p oblems aside
om he conc e e example we ha e chosen o he lec u es. I seems mo e p omising o each he
concep s o LTaA and apply hem o au oma ed compile gene a ion. CC in e ms o compile
gene a ion means o apply a gene a o o app op ia e desc ip ions o bo h, he sou ce language and
he a ge one. I is undamen ally di e en om pe cei ing compile cons uc ion as a
c a smanship.
The well known CC ools like LEX and YACC (FLEX and BISON) a e made o expe enginee s
and no o educa ional pu poses. The e a e a lo o echnical pi alls ha can be ime consuming o
deal wi h. Tools like ha a e no designed o he hands o s uden s.
We use he compu e -based lea ning en i onmen A oCC ([1]) which was especially buil o
suppo LTaA lec u es based on he concep in oduced he e. The ou lined pedagogical app oach is
illus a ed in mo e de ail in sec ion 2 along wi h an example used in a eal class si ua ion. The
esul s and hei e alua ion a e summa ized in sec ion 3. The ea ly obse a ions a e p omising,bu
s ill no su icien o make a quan i a i e analysis ye .
2. Ou cou se
I is signi ican o choose mo i a ing examples. The e o e i is highly ecommended o a oid
choosing e y simpli ied languages like anbn. To selec assemble and machine code o be he a ge
language o a compile p ojec is also no a good choice. F om a s uden ’s pe spec i e i is mo e
in e es ing o ansla e hei own language in o a isual (e.g.: SVG) o acous ic (e.g.: MIDI) one.
The sou ce language should be complex enough o show a p ac ical ele ance as well as scalable
enough o p o ide limi a ions on some ep esen a i e language elemen s.
In his sec ion he sol ing p ocess o an ex ensi e exe cise is desc ibed. A his poin he s uden s
ha e al eady wo ked wi h ini e and push-down au oma a, egula exp essions and o mal g amma s
in p e ious exe cises. Howe e , we can use all componen s o A oCC o e lec back on heo y o
be applied in his exe cise.
The sou ce language o his example is a obo language called D awing Robo (DR). One can
hink o a d awing obo as a u le well-known om he u le geome y, being pa o he logo
TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
8
p og amming language. I is a mo eable sc een icon equipped wi h a pencil on he wais . While
pu ing he pencil on he isual playg ound, a ace is d awn along wi h he obo ’s mo emen . The
language is no oo i ial because b acke s a e used o loops, so a leas a push-down au oma on is
equi ed o desc ibe i .
2.1. The ask as gi en o he s uden s
De elop a compile ha ansla es he language DR in o PDF. The ollowing sample p og am in DR
p oduces he iny ose e in ig. 1:
L 36 [L 4 [F 100 R 90] R 10]
Figu e 1: Sample ou pu o a DR p og am
To w i e DR p og ams he ollowing commands can be used:
F n o wa d n s eps
R n u n igh o n deg ees
L n [ ... ] loop n- imes he con en o he b acke s
COLOR pen colo mus be ed, g een, blue o black
PEN n changes he s oke size o he pen
Hin : PDF i sel is a bina y o ma and canno be easily desc ibed by human beings as he a ge
language gene a ed. Tha is why you should aim o some hing like a mul i s ep s a egy o he
ans o ma ion p ocess om DR o PDF. Look o sui able ools o simpli y his compila ion
p ocess.
2.2. Model he compila ion p ocess
The s uden s ha e o model he p ocess ha akes a DR p og am and compiles i o a inal PDF
documen which is conside ed as a p og am w i en in PDF language. Acco ding o he hin
p o ided o he ask desc ibed in he p e ious sec ion, he s uden s a e no able o ollow he idea
o a di ec ansla ion om DR o PDF. In p e ious exe cises he command line ool PS2PDF ( om
Ghos Sc ip ) was used o p oduce PDF om Pos Sc ip (PS) iles. PS is a language eadable o
human beings and he e o e i can be used as he a ge language o a DR o PS compile . We ha e
a wo-s ep compila ion p ocess om DR o PS and hen om PS o PDF. We can isualize and
model his p ocess wi h he help o T-diag ams ( i s in oduced in [3]).
TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
9
T-diag ams can be de eloped easily wi h pen and pape . In ac , his me hod makes i di icul o
s uden s o accomplish he connec ion ules de ined o he shapes o p oduce a alid diag am.
Ins ead o pape he s uden s use TDiag p o iding highligh ing and alida ion suppo . Fu he mo e,
TDiag allows us o au oma ically execu e a diag am bonded o eal iles on he local sys em.
In oking a diag am pe o ms he execu ion o compile s and p og ams in he sequence de ined
ough he diag am. In ig. 2 a s uden ’s solu ion o he DR example is shown (conc e e ilenames
a e no included). The T-diag am ob iously lacks he DR2PS compile . This is exac ly he piece o
so wa e ha has o be de eloped by he s uden s. Execu ing his diag am will la e on esul in o:
ja a DR2PS inpu .d ou pu .ps
ps2pd ou pu .ps
oxi eade ou pu .pd
Beside o he DR o PS compile all he o he so wa e componen s a e al eady ins alled on he
sys em he s uden s a e wo king on.
Figu e 2: T- diag am o he DR o PDF ansla ion
2.3. De ining DR
The DR o PS compile in ol es wo languages ha need o be decla ed and discussed be o e
c ea ing he missing compile . The s uden s ha e o de ine a con ex ee g amma o DR based on
he ask desc ip ion and sample DR p og ams. The s uden s can use k G-Edi om A oCC o c ea e
a alid g amma and de i e he examples gi en in he ask desc ip ion. The s uden may use he
manual de i e op ion wi hin k G-Edi o iden i y mis akes. As a esul he s uden s de ine a con ex
ee g amma o DR like his ( ep esen ed in BNF):
TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
10
2.4. A scanne and pa se o DR
As one pa o he inal DR o PS compile he s uden s ha e o c ea e a scanne which okenizes
DR p og ams. Fo his pu pose hey use VCC om A oCC o de ine a scanne desc ip ion wi h
oken classes and associa ed pa e ns ( egula exp essions). Fo he sublanguage o Numbe one
may de ine a egula exp ession pa e n like [1-9][0-9]*. This pa e n can be e alua ed and
simula ed on a andom ex in RegExpEdi . When using egula exp essions (RegExp) i is always a
good idea o gene a e a egula g amma and a ini e au oma on o he associa ed egula language.
The s uden s can compa e he expec ed beha io wi h he one o he au oma on in Au oEdi (see ig.
3).
The second pa needed o he DR o PS compile is de ining a pa se wi h ansla ion ules. Once
again we use VCC which o e s de eloping a scanne and a pa se in a single p ojec ile and
seamlessly connec bo h pa s oge he . The pa se can be easily de i ed om he g amma G
p e iously de ined by he s uden s. Some o he p oduc ion ules o G can be educed because we
al eady accommoda ed hem wi hin he egula exp essions o he scanne desc ip ion (like
Numbe ). The emaining p oduc ions can be di ec ly ans e ed o he pa se de ini ion in VCC (see
ig. 4).
VCC cu en ly suppo s Ja a, C#, Delphi and Scheme as p og amming languages he gene a ed
compile p og am is implemen ed in. A e ha ing chosen one o hem, he s uden can p oduce a
DR o DR compile w i en in he selec ed language wi hou making any adjus men s. Such a
compile will ou pu an inpu DR p og am wi hou any changes. Howe e , he compile al eady
pe o ms a comple e syn ax check and will only ou pu alid DR p og ams. The s uden s can now
pe o m li le adjus men s o change his p ede ined ou pu beha io .

TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
11
Figu e 3: A ini e au oma on ep esen ed wi h Au oEdi
2.5. Adding he a ge language PS
In o de o gene a e Pos Sc ip he s uden s ha e o lea n some basics o PS i s . Fo he e y
limi ed ope a ions o DR, only a ew commands o PS a e equi ed. An app op ia e wo kshee is
gi en o he s uden s o help hem.
The pa se gene a ed by VCC execu es a small code agmen (a so called S-a ibu e) o p oduce i s
ou pu whene e a pa se ule is success ully applied. A ja a exp ession desc ibing he alue o an
S-a ibu e o he p oduc ion ule S a emen  COLOR Colo alue may look like his:
i ($2.equals("blue")) $$ = "0 0 255 se gbcolo ";
i ($2.equals(" ed")) $$ = "255 0 0 se gbcolo ";
i ($2.equals("g een")) $$ = "0 255 0 se gbcolo ";
i ($2.equals("black")) $$ = "0 0 0 se gbcolo ";
The a iable $2 con ains he li e al alue om he DR sou ce p og am o Colo alue. All elemen s
on he igh hand side o he p oduc ion ule a e numbe ed consecu i ely om $1 o $n. The esul
o he ule S a emen is s o ed in $$. A s a emen like COLOR ed will he e o e be ansla ed in o
255 0 0 se gbcolo ( he command se gbcolo is a Pos Sc ip me hod o se ing he
cu en pen colo ).
I is ypical o add S-a ibu e exp essions s epwise. A e implemen ing a ans o ma ion ule, he
s uden s can p e iew hei wo k by gene a ing an execu able compile . Each ule which is no
ansla ed ye will jus pe o m a pass- h ough based on he DR o DR compile we s a ed om.
TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
12
Figu e 4: Pa se de ini ion ep esen ed in VCC
A e ha ing de ined all ansla ion ules he s uden s le VCC gene a e he inal DR o PS compile .
This compile can be a ached o he p e ious de ined T-diag am wi hin TDiag. F om a pedagogical
pe spec i e i is e y impo an o e u n o he le el o modeling and alida e his model by
execu ing he diag am wi h eal DR p og ams as inpu .
3. Resul s and e alua ion
Compu e science s uden s om he Uni e si y o Applied Sciences in Zi au/Goe li z o he second
and hi d semes e a ended LTaA classes we e A oCC was he only so wa e used. In hese classes
he s uden s success ully de eloped eal compile s in iny g oups as a necessa y equi emen o
hei examina ion. The mo i a ing opic was o de elop a VCARD o SVG compile (VCARD is a
language o business ca ds). These languages a e well desc ibed, bu only minimal subse s o bo h
we e used. En husias ic s uden s had a lo o possibili ies o exceed he minimum equi emen s we
had de ined o his p ojec . Some g oups gene a ed nicely colo ed business ca ds wi h backg ound
images and so on.
4. Conclusions
A oCC suppo ed ou s uden s o in e nalize and apply con en s o LTaA. Especially con ex ee
g amma s and hei applica ions in au oma ed compile gene a ion we e highly mo i a ing o he
s uden s. Some s uden s e en used A oCC o hei Bachelo /Mas e hesis p ojec s wi h no o
limi ed ela ions o LTaA opics, bu whe e ansla ion p ocesses we e in ol ed. This le s us assume
TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
13
ha ou pedagogical concep imp o es he s uden s’ abili y o hink in an abs ac way by applying
hei knowledge o LTaA.
In nume ous wo kshops acili a ed by he au ho s, A oCC was conside ed o be e y use ul o
eache educa ion and e en o use in seconda y schools. The high quali y expo op ions in a ious
da a o ma s in almos all componen s o A oCC, e.g. di ec LaTeX ou pu o au oma a ables,
de ini ions and g aphs, suppo eache s and s uden s while p oducing lea ning ma e ial and p ojec
documen a ions.
Li e a u e
[1] Hielsche M.: A oCC Websi e, Ma ch 2009. h p://www.a occ.de.
[2] Hielsche M., Wagenknech C.: A oCC: lea ning en i onmen o eaching heo y o
au oma a and o mal languages. In ITICSE '06: P oceedings o he 11 h annual SIGCSE
con e ence on Inno a ion and echnology in compu e science educa ion, page 306, New
Yo k, NY, USA, 2006. ACM.
[3] McKeeman W., Wo man D., Ho ning J.: Compile Gene a o (Au oma ic Compu a ion).
P en ice-Hall Englewood Cli s, N.J., USA, 1970.
[4] T. J. T. F. on Compu ing Cu icula: Compu ing Cu icula 2001 Compu e Science, Final
Repo . IEEE Compu e Socie y, Associa ion o Compu ing Machine y, 2001.
[5] Rodge S.: Lea ning au oma a and o mal languages in e ac i ely wi h j lap.
In ITICSE '06: P oceedings o he 11 h annual SIGCSE con e ence on Inno a ion and
echnology in compu e science educa ion, page 360, New Yo k, NY, USA, 2006. ACM.
Do učeno edakci: 6. 4. 2009
Recenzo áno: 15. 6. 2009
Sch áleno k publiko ání: 23. 6. 2009
TEACHING LANGUAGE THEORY AND AUTOMATA:
A COMPILER GENERATION ORIENTED APPROACH USING ATOCC
14
FORMALE SPRACHEN UND ABSTRAKTE AUTOMATEN LEHREN: EIN
ZUGANG VIA COMPILER-GENERIERUNG MIT ATOCC
Fo male Sp achen und abs ak e Au oma en (FSuA) so zu leh en, dass die S udie enden zu ak i em
Le nen mo i ie we den, is eine ech e He aus o de ung. Diese Au sa z s ell einen didak ischen
Weg o , de geeigne e Themen aus de heo e ischen In o ma ik sinn oll mi de en p ak ische
Anwendung im Compile bau e knüp . Um dieses Vo gehen umse zen zu können, haben wi eine
angepass e Le numgebung (A oCC) en wickel . An einem konk e en Un e ich sbeispiel wi d
o ges ell , wie A oCC sowohl den Leh enden als auch den Le nenden un e s ü z .
JĘZYKI FORMALNE A ABSTRAKCJA AUTOMATÓW NAUCZANIA:
UDOSTĘPNIENIE DROGI TWORZENIA KOMPILATORA –
GENEROWANIE Z ATOCC
Nauczanie języków o malnych i abs akcyjnych au oma ów (FSuA) w aki sposób, aby s anowiło
o dla s uden ów mo ywację do ak ywnej nauki, jes p awdziwym wyzwaniem. Niniejszy a ykuł
p zeds awia ukie unkowanie dydak yki, łączące w sensowny sposób odpowiednie zagadnienia eo ii
in o ma yki z jej p ak ycznym zas osowaniem. W celu ealizacji akiego podejścia op acowano
na zędzie do nauki (A oCC). Na konk e nym p zykładzie zajęć p zeds awiono, jak A oCC
wspomaga nauczycieli w nauczaniu i s uden ów w nauce.
FORMÁLNÍ JAZYKY A ABSTRAKTY AUTOMATICKÉ VÝUKY:
ZPŘÍSTUPNĚNÍ CESTY VYTVÁŘENÍ KOMPILÁTORU
– GENEROVÁNÍ S ATOCC
Vyučo ání o málním jazykům a abs ak ním au oma ům ak, aby o mo i o alo s uden y
k ak i nímu učení, je op a do ou ýz ou. Ten o příspě ek předs a uje didak ický smě , k e ý
smysluplně spojuje hodná éma a eo e ické in o ma iky s jejím p ak ickým yuži ím. K ealizaci
oho o pos upu bylo y ořeno hodné s udijní p os ředí (A oCC). Na konk é ním yučo acím
příkladu je znázo něno, jak je A oCC yučo ací opo ou p o uči ele i s udijní opo ou p o s uden y.