Apribase

BNF をパースできるパーサを作成しました。
JavaCC を利用して実装しています。
EBNF にはまだ対応していません。

使用用途として、BNF に従って何かしたい、何かを生成したいときに利用します。
例えば、インタプリタやコンパイラ、オブジェクトの生成、アクションの追加等。
図は BNF ファイルを構文木で表し XML へ変換するコンパイラを作成する際に利用した例。

BNF (exp.bnf)

$start input
input ::= line
    ;
line ::= exp
    ;
exp ::= NUM
    | ADD exp exp
    | SUB exp exp
    | MULTI exp exp
    | DIV exp exp
    ;

Grammar.java

/*****************************************************************
 * Grammar.java
 * Created on 2008/02/16
 *
 * 文法を表すクラスです。
 * 文法は、初期シンボルと生成規則の2つから成ります。
 * 生成規則は複数存在するため、リスト形式で管理されます。
 ****************************************************************/
package net.apribase.bnfparser;

import java.util.ArrayList;
import java.util.List;

public class Grammar {

    /* 初期シンボルを表します。 */
    private final String startSymbol;
    /* 生成規則のリストを表します。 */
    private final List<ProductionRule> productionRules;

    /**
     * Grammar インスタンスを生成します。
     * インスタンス生成時に初期シンボルを決めます。
     * 生成規則は文法ファイルを読みながら追加していきます。
     * @param startSymbol
     */
    public Grammar(String startSymbol) {
        super();
        this.startSymbol = startSymbol;
        this.productionRules = new ArrayList<ProductionRule>();
    }

    /**
     * 生成規則を追加します。
     * @param productionRule
     */
    public void addProduction(ProductionRule productionRule) {
        productionRules.add(productionRule);
    }

    /**
     * 初期シンボルを取得します。
     */
    public String getStartSymbol() {
        return this.startSymbol;
    }

    /**
     * 生成規則を取得します。
     */
    public List<ProductionRule> getProductionRules() {
        return this.productionRules;
    }

}

ProductionRules.java

/*****************************************************************
 * ProductionRule.java
 * Created on 2008/02/16
 *
 * 生成規則を表すクラスです。
 * lhs ::= rhs のように表されます。
 * rhs は複数の文字列から成るためリスト形式で管理されます。
 ****************************************************************/
package net.apribase.bnfparser;

import java.util.List;

public class ProductionRule {

    private String lhs; // leftHandSide
    private List<String> rhs; // rightHandSideList

    /**
     * Creates a new instance of ProductionRule.
     * @param lhs Left-Hand Side
     * @param rhs Right-Hand Side
     */
    public ProductionRule(String lhs, List<String> rhs) {
        super();
        this.lhs = lhs;
        this.rhs = rhs;
    }

    /**
     * Get Left-Hand Side.
     */
    public String getLhs() {
        return this.lhs;
    }

    /**
     * Get Right-Hand Side.
     */
    public List<String> getRhs() {
        return this.rhs;
    }
}

BnfParser.jj

/*****************************************************************
 * BnfParser.jj
 * Created on 2008/02/16
 *
 * BNF で記述された文法をパースできる JavaCC 用のプログラムです。
 * 文法と生成規則を知ることができます。
 ****************************************************************/

PARSER_BEGIN(BnfParser)

package net.apribase.bnfparser;

import java.util.ArrayList;
import java.util.List;

public class BnfParser {
}

PARSER_END(BnfParser)

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

TOKEN : {
    <START: "$start">
    | <VOCABULARY: (["A"-"Z","a"-"z","0"-"9","'", "+", "-", "*", "/", "^"])+>
}

Grammar grammar() :
{
    Grammar grammar;
    List<ProductionRule> productionRules;
}
{
    <START> <VOCABULARY>
    {
        grammar = new Grammar(token.image);
    }
    (
        productionRules = productionRule()
        {
            for(ProductionRule productionRule : productionRules) {
                grammar.addProduction(productionRule);
            }
        }
    )*
    <EOF>
    {
        return grammar;
    }
}

List<ProductionRule> productionRule() :
{
    String nonTerminal;
    List<ProductionRule> productionRules = new ArrayList<ProductionRule>();
    List<String> rhs;
}
{
    <VOCABULARY>
    {
        nonTerminal = token.image;
    }
    "::="
    rhs = rhs()
    {
        productionRules.add(new ProductionRule(nonTerminal, rhs)); // nonTerminal ::= rhs
    }
    (
    "|"
        rhs = rhs()
        {
            productionRules.add(new ProductionRule(nonTerminal, rhs));
        }
    )*
    ";"
    {
        return productionRules;
    }
}

List<String> rhs() :
{
    List<String> vocabularys = new ArrayList<String>();
}
{
    (
        <VOCABULARY>
        {
            vocabularys.add(token.image);
        }
    )*
    {
        return vocabularys;
    }
}