I want to create a programming language that has multiple functions and a single main function. For the interpreter of the language I am using a hash map, but I do not know how to store intermediate values in the hash map. An example of a valid program includes:
DEF MAIN { ADDITION(4) } ;
DEF ADDITION x { x+3 } ;
This is what I have so far:
HashMap<String, Function> Program() : {
HashMap<String, Function> symbolTable = new HashTable<>();
}
{
(FunctionDefinition(symbolTable))*
<EOF>
{return symbolTable;}
}
void FunctionDefinition(SymbolTable table)
{
Function f;
String name;
}
{
<DEF> <SPACE>
(
(name = <MAIN>)
| (name = <FUNC> (<SPACE> <PARAM> ))
<SPACE>
f = FunctionBody()
";"
{
if (table.hashKey(name)) { System.out.println("do something");}
else { table.add(name, f); }
})
}
void FunctionBody() : {}
{
<LEFT> <SPACE>
Expression()
<SPACE> <RIGHT>
}
void Expression() : {}
{
AdditiveExpression()
}
void AdditiveExpression() : {
}
{
MultiplicativeExpression() (<PLUS> MultiplicativeExpression()
{
try {
int a = s.pop();
int b = s.pop();
stack.push(a+b);
}
catch (ClassCastException ex) {
System.out.println("Only numbers can be used for arithmetic operations.");
throw new ParseException();
}
})*
}
void MultiplicativeExpression() : {
}
{
UnaryExpression() (<MUL> UnaryExpression()
{
try {
int a = s.pop();
int b = s.pop();
stack.push(a*b);
}
catch (ClassCastException ex) {
System.out.println("Only numbers can be used for arithmetic operations");
throw new ParseException();
}
})*
}
void UnaryExpression() : {
Token x;
}
{
(x = <NUMBER> | x = <PARAM>)
{s.push(x.image);}
}
Any help will be greatly appreciated.
As @Theodore has said, you can't execute the program while you're parsing it. I thought I'd add my two cents here.
The result of the parsing could be the table of functions though, and you would have a main method that would do something like this:
Parser parser = new Parser(System.in, "UTF-8");
Map<String, Function> table = parser.program();
Function main = table.get("MAIN");
if (main == null) {
System.out.println("Function MAIN doesn't exist");
} else {
int r = main.invoke(table);
System.out.println("Result: " + r);
}
I see a few weird things in your code:
Instead of using a token <SPACE> between each token, you'd be better off using the SKIP instruction:
SKIP : { " " | "\r" | "\n" | "\t" }
You're using three different tokens for the same thing: <MAIN>, <FUNC>, <PARAM>. They're all names, and you could define a token <NAME> as follows:
TOKEN: {
< NAME: <LETTER>(<LETTER>|<DIGIT>)* >
| < #LETTER: ["a"-"z", "A"-"Z", "_"] >
| < #DIGIT: ["0"-"9"] >
}
The rule for a function definition would then become:
<DEF> <NAME> ( <NAME> )* functionBody() ";"
note that a function can have zero or more parameters; function MAIN would have zero.
In your example, function MAIN contains a forward reference to the function ADDITION, meaning that while parsing the body of function MAIN you will find a call to a function ADDITION that is not yet in the symbol table. The ability to use forward reference is a nice feature for a programming language, but it complicates the implementation slightly.
If you're doing an interpreter, you have basically two options to deal with forward references: 1) do a second pass after the parsing to "fix" the forward references, 2) do the name resolution during run time. The second option is simpler but slower.
Note that the parameters of a function are always defined before they are used. They are only accessible within the body of a function. You can build a table for the parameter while parsing the head of the definition, and then pass that table to the method that parses the body of the function.
Example:
void functionDefinition(Map<String, Function> table): {
Expression body;
Function f;
String name;
String param;
int paramCount = 0;
Map<String,Parameter> params = new HashMap<String,Parameter>();
}
{
<DEF> name=<NAME>.image (
param=<NAME>.image {params.put(param, new Parameter(paramCount++));}
)*
body=functionBody(params)
{ f = new Function(paramCount, body); }
";"
{
if (table.containsKey(name)) {
System.out.println("Function " + name + "already exists");
} else {
table.put(name, f);
}
}
}
To evaluate the expression in a function body, you can use the interpreter pattern, where the elements of an expression are all an implementation of an Expression interface:
public interface Expression {
public int evaluate(Map<String,Function> table, int... parms);
}
Here parms are the actual parameters passed to the function being executed.
The following files are the sources of a very simple, functioning implementation of a very simple language based on your question. It can execute your example:
DEF MAIN { ADDITION(4) } ;
DEF ADDITION x { x+3 } ;
and it can also execute something like this:
DEF MAIN { ADDITION3(4) } ;
DEF ADDITION3 x { ADDITION(x,3) } ;
DEF ADDITION x y { x+y } ;
I hope it will help.
JavaCC file, parser.jj:
options {
STATIC = false;
IGNORE_CASE = false;
}
PARSER_BEGIN(Parser)
package org.tastefuljava.minilang;
import java.io.InputStream;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
public class Parser {
public static void main(String[] args) {
try {
Parser parser = new Parser(System.in, "UTF-8");
Map<String, Function> table = parser.program();
int r = Expression.call("MAIN").evaluate(table);
System.out.println("Result: " + r);
} catch (ParseException e) {
e.printStackTrace();
}
}
}
PARSER_END(Parser)
SKIP : { " " | "\r" | "\n" | "\t" }
TOKEN: {
< DEF: "DEF" >
| < NAME: <LETTER>(<LETTER>|<DIGIT>)* >
| < #LETTER: ["a"-"z", "A"-"Z", "_"] >
| < #DIGIT: ["0"-"9"] >
| < PLUS: "+" >
| < MUL: "*" >
| < LEFT: "{" >
| < RIGHT: "}" >
| < NUMBER: (<DIGIT>)+ >
}
Map<String, Function> program(): {
Map<String, Function> symbolTable = new HashMap<>();
}
{
(functionDefinition(symbolTable))*
{return symbolTable;}
}
void functionDefinition(Map<String, Function> table): {
Expression body;
Function f;
String name;
String param;
int paramCount = 0;
Map<String,Parameter> params = new HashMap<String,Parameter>();
}
{
<DEF> name=<NAME>.image (
param=<NAME>.image {params.put(param, new Parameter(paramCount++));}
)*
body=functionBody(params)
{ f = new Function(paramCount, body); }
";"
{
if (table.containsKey(name)) {
System.out.println("Function " + name + "already exists");
} else {
table.put(name, f);
}
}
}
Expression functionBody(Map<String,Parameter> params): {
Expression e;
}
{
<LEFT>
e=expression(params)
<RIGHT>
{
return e;
}
}
Expression expression(Map<String,Parameter> params): {
Expression e;
}
{
e=additiveExpression(params)
{
return e;
}
}
Expression additiveExpression(Map<String,Parameter> params): {
Expression e, f;
}
{
e=multiplicativeExpression(params)
(<PLUS> f=multiplicativeExpression(params) {
e = Expression.add(e,f);
})*
{
return e;
}
}
Expression multiplicativeExpression(Map<String,Parameter> params): {
Expression e, f;
}
{
e=unaryExpression(params) (<MUL> f=unaryExpression(params) {
e = Expression.mul(e,f);
})*
{
return e;
}
}
Expression unaryExpression(Map<String,Parameter> params): {
Expression e;
String s;
int n;
Expression[] parms;
}
{
(
n=number() {
e = Expression.number(n);
}
| s=<NAME>.image ( parms=parameterList(params) {
e = Expression.call(s, parms);
} | {
Parameter p = params.get(s);
if (p != null) {
e = Expression.param(p.index);
} else {
// no parameter found: assume it's a parameterless function
e = Expression.call(s);
}
})
)
{
return e;
}
}
int number(): {
String s;
}
{
s=<NUMBER>.image
{
return Integer.parseInt(s);
}
}
Expression[] parameterList(Map<String,Parameter> params): {
List<Expression> parms = new ArrayList<Expression>();
Expression p;
}
{
"("
(
p=expression(params) { parms.add(p); }
( "," p=expression(params){ parms.add(p); } )*
)?
")"
{
return parms.toArray(new Expression[parms.size()]);
}
}
Function class, Function.java:
package org.tastefuljava.minilang;
public class Function {
public final int paramCount;
public final Expression body;
public Function(int paramCount, Expression body) {
this.paramCount = paramCount;
this.body = body;
}
}
Parameter class, Parameter.java:
package org.tastefuljava.minilang;
public class Parameter {
public final int index;
public Parameter(int index) {
this.index = index;
}
}
Expression interface, Expression.java:
package org.tastefuljava.minilang;
import java.util.Map;
public interface Expression {
public int evaluate(Map<String,Function> table, int... parms);
public static Expression number(int x) {
return (table, parms) -> x;
}
public static Expression add(Expression a, Expression b) {
return (table, parms) ->
a.evaluate(table, parms) + b.evaluate(table, parms);
}
public static Expression mul(Expression a, Expression b) {
return (table, parms) ->
a.evaluate(table, parms) * b.evaluate(table, parms);
}
public static Expression call(String name, Expression... parms) {
return (table, oldParms) -> {
Function f = table.get(name);
if (f == null) {
System.out.println("Unknown function " + name);
return 0;
} else if (f.paramCount != parms.length) {
System.out.println("Wrong number of parameters for function "
+ name + ": expected " + f.paramCount
+ ", actual " + parms.length);
return 0;
}
int[] newParms = new int[parms.length];
for (int i = 0; i < parms.length; ++i) {
newParms[i] = parms[i].evaluate(table, oldParms);
}
return f.body.evaluate(table, newParms);
};
}
public static Expression param(int index) {
return (table, parms) -> parms[index];
}
}