javacc 中的哈希图

Question

我想创建一种具有多种功能和单一主要功能的编程语言。对于我正在使用哈希映射的语言的解释器，但我不知道如何在哈希映射中存储中间值。有效程序的示例包括：

DEF MAIN { ADDITION(4) } ;
DEF ADDITION x { x+3 } ;

这是我目前拥有的：

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);}
}

任何帮助将不胜感激。

Answer 1

您需要 FunctionBody 非终结符到 return 函数的中间表示。

问题是您没有中间表示。您正在尝试进行直接解释，即您在解析程序的同时执行程序。这对于像 this ancient tutorial. However, once you start dealing with loops and functions you really need to generate (and later execute) intermediate code. See this FAQ 中的简单交互式计算器来说很好。

如果您正在参加课程，请询问您的讲师他或她会推荐什么中级代码。

如果您没有指导员，我的建议是为堆栈机器生成机器代码，因为您已经在使用堆栈执行。例如，参见 my notes on generating machine code for a stack machine in a recursive descent parser，尤其是第 14 至 20 页；我没有为此使用解析器生成器，但这无关紧要。（我使用 ^ 进行序列连接，因此，例如，m := m^div 只是意味着在中间表示的末尾添加一条 div 指令。）

任何关于编译器的书也会涵盖这类内容。

Tom Copeland's book 可能有更多信息并且是特定于 JavaCC 的。

Answer 2

正如@Theodore 所说，您无法在解析程序时执行程序。我想我应该在这里加上我的两分钱。

虽然解析的结果可能是 table 函数，但您将有一个 main 方法可以执行如下操作：

        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);
        }

我在你的代码中看到了一些奇怪的东西：

与其在每个标记之间使用标记 <SPACE>，不如使用 SKIP 指令更好：

SKIP : { " " | "\r" | "\n" | "\t" }

您为同一件事使用了三种不同的标记：<MAIN>、<FUNC>、<PARAM>。它们都是名字，你可以定义一个标记 <NAME> 如下：

TOKEN: {
    < NAME: <LETTER>(<LETTER>|<DIGIT>)* >
    | < #LETTER: ["a"-"z", "A"-"Z", "_"] >
    | < #DIGIT: ["0"-"9"] >
}

函数定义的规则将变为：

<DEF> <NAME> ( <NAME> )* functionBody() ";"

请注意，一个函数可以有零个或多个参数；函数 MAIN 将有零。

在您的示例中，函数 MAIN 包含对函数 ADDITION 的前向引用，这意味着在解析函数 MAIN 的主体时，您会发现对函数 MAIN 的调用=29=] 还没有出现在符号 table 中。使用前向引用的能力是编程语言的一个很好的特性，但它使实现稍微复杂化。

如果你正在做一个解释器，你基本上有两种选择来处理前向引用：1）在解析后进行第二次传递以“修复”前向引用，2）在[=期间进行名称解析85=] 时间。第二个选项更简单但更慢。

请注意，函数的参数总是在使用前定义。它们只能在函数体内访问。您可以在解析定义的头部时为参数构建一个 table，然后将那个 table 传递给解析函数体的方法。

示例：

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);
        }
    }
}

要计算函数体中的表达式，可以使用 interpreter pattern，其中表达式的元素都是 Expression 接口的实现：

public interface Expression {
    public int evaluate(Map<String,Function> table, int... parms);
}

这里parms是传递给正在执行的函数的实际参数。

以下文件是基于您的问题的一种非常简单的语言的非常简单、有效的实现的源代码。它可以执行你的例子：

DEF MAIN { ADDITION(4) } ;
DEF ADDITION x { x+3 } ;

它也可以执行这样的操作：

DEF MAIN { ADDITION3(4) } ;
DEF ADDITION3 x { ADDITION(x,3) } ;
DEF ADDITION x y { x+y } ;

希望对你有所帮助。

JavaCC 文件，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()]);
    }
}

函数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;
    }
}

参数class、Parameter.java:

package org.tastefuljava.minilang;

public class Parameter {
    public final int index;

    public Parameter(int index) {
        this.index = index;
    }
}

表情界面，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];
    }
}

javacc 中的哈希图

Hashmaps in javacc

hashmap

javacc