Vincent Chu Tinkerer | Leader | Innovator

Senior full stack software developer.
Passionate with technology. Worked at Electronic Arts and Apple before venturing into the startup world.

Programming Language Translation

This is a program proudly done for my symbolic computing class' assignment. One of the applications of symbolic computing is translating programs from one language to another. What this program does is it takes input that satisfies the input grammar, and output it back using the output grammar. In our case, the input grammar is the "Small Lisp" grammar, and the output grammar is a subset of the Haskell grammar. So in effect, this is a program that translate Small Lisp program into a Haskell program.

The input grammar is defined as follow, using EBNF notation:

<expression> ::= <constant> | <id> | <function Call> | <conditional Expression>
<constant> ::= <number> | "<symbol>" | [ {<constant>} ]
<id> ::= <smallLetter>{<letter> | <digit>}
<function Call> ::= <id> [ <expression> {;<expression>} ]
<conditional Expression> ::= [ <clause> {; <clause>} ]
<clause> ::= <expr> --> <expr>
<number> ::= <digit> {<digit>}
<symbol> ::= <Char>
<digit> ::= 0 | 1 | ... | 9
<smallLetter> ::= a | b | ... | z
<letter> ::= <smallLetter> | A | B | ... | Z


How it works?

The program does its job not by token-by-token translation. This is because ";" is translated to "," inside a function call, but it is translated to "else if" in a conditional expression. Hence, a standard method called "recursive descent" is used.

To try it, enter the following expression:

[equal[x;2]-->show["Equal"];otherwise-->show[minus[x;2]]]


Sample Input / Output

In the translated Haskell program, we used uncurry form for function calls. Because the elements of a list in the input grammar(Small Lisp) can be of both String and Int, we introduce custom-defined data type CONSTANT and has constructors "LST", "NUM", and "SYM" , so that all lists are list of CONSTANTs.

*Bolded ones are users input (in input grammar notation) and the ones with regular font are program output (in Haskell notation)

cons[abc;()]

cons (abc ,(LST []))

cons["abc";()]

cons ((SYM "abc"),(LST []))

[cons[32;(2)]-->"Vincent"]

if cons ((NUM "32"),(LST [(NUM "2")])) then (SYM "Vincent")

[eqp[2;3]-->foo[1;2];endp[list]-->"Vincent";otherwise-->3]

if eqp ((NUM "2"),(NUM "3")) then foo ((NUM "1"),(NUM "2"))
else if endp (list ) then (SYM "Vincent")
else if otherwise then (NUM "3")

[cons[1;cons[2;list]]-->"vincent";foo-->[a-->b; c-->d]]

if cons ((NUM "1"),cons ((NUM "2"),list )) then (SYM "vincent")
else if foo then if a then b
else if c then d


Compiling Program

This translation program is written in Haskell. I used Glasgow Haskell Compiler to turn it into an executable (in Windows).

Download File Download S-Lisp/Haskell Translation Program