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).