6802用アセンブラを作る(2) JFlexとCUPの導入

プログラミング
2017.03.05

6802用アセンブラの構文解析部分を、将来の拡張性を見据えて、自前で作成するのではなく字句解析にJFlex、構文解析にCUPを使って作成することにしました。この記事ではそれぞれの導入と、それらを使った構文解析部分のプロトタイプを紹介します。

インストール

以下の環境にインストールするためのメモを記します。

  • Windows 10
  • Eclipse Version Mars.2 Release 4.5.2

JFlex

ダウンロードページからtar.gzまたはzipファイルをダウンロードし、適当な場所に保存します。2017年2月26日現在、最新版は1.6.1。tar.gzもzipも内容は同じです。
以下ではc:\tools\jflexに展開したものとします。

C:\tools\jflex\ 
    +--bin\                        (start scripts) 
    +--doc\                        (FAQ and manual) 
    +--examples\ 
        +--byaccj\                 (calculator example for BYacc/J) 
        +--cup\                    (calculator example for cup) 
        +--interpreter\            (interpreter example for cup) 
        +--java\                   (Java lexer specification) 
        +--simple-maven\           (example scanner built with maven) 
        +--standalone-maven\       (a simple standalone scanner, 
                                    built with maven) 
        +--zero-reader\            (Readers that return 0 characters) 
    +--lib\                        (precompiled classes, skeleton files) 
    +--src\ 
        +--main\ 
            +--cup\                (JFlex parser spec) 
            +--java\ 
                +--java_cup\ 
                    +--runtime\    (source code of cup runtime classes) 
                +--jflex\          (source code of JFlex) 
                    +--gui\        (source code of JFlex UI classes) 
            +--jflex\              (JFlex scanner spec) 
            +--resources\          (messages and default skeleton file) 
        +--test\                   (unit tests)

Eclipseだけで開発する場合は不要ですが、DOSプロンプトから実行する場合も想定して、展開してできたフォルダ内のbin/flex.bat (今回の例ではc:\tools\jflex\bin\flex.bat)を自分の環境に合うように修正します。修正箇所は環境変数の設定部分です。

@echo off
REM Please adjust JFLEX_HOME to suit your needs
REM (please do not add a trailing backslash)

set JAVA_HOME=C:\Program Files\Java\jdk1.8.0_51
set JFLEX_HOME=c:\tools\jflex

java -Xmx128m -jar %JFLEX_HOME%\lib\jflex-1.6.1.jar %1 %2 %3 %4 %5 %6 %7 %8 %9

JAVA_HOMEの行はJDKのあるディレクトリ、JFLEX_HOMEはJFlexを展開したディレクトリに合わせて変更します。
必要に応じて上記のbatファイルの場所を環境変数PATHに追加してください。

CUP

ダウンロードページからtar.gzファイルをダウンロードし、適当な場所に保存します。2017年2月26日現在、最新版はjava-cup-bin-11b-20160615。
以下ではc:\tools\cupに展開したものとします。

C:\tools\cup\
    java-cup-11b.jar
    java-cup-11b-runtime.jar

CUPをインストールして試そうとするとUnsupported major.minor version 52.0が発生することがありました。CUPはJava 1.8が前提なのかもしれません。ここの原因究明は深入りせず、今回の開発環境はJava 1.8に統一しました。

Eclipseの設定

JFlexとCUPのソースコードとJavaコードの生成先をどこにするか悩み、次のようにしてみました。

src/
    AsmScanner.flex    # 字句解析のソース
    AsmParser.cup      # 構文解析のソース
    +--- jp
        +-- asamomiji
            +-- assembler
                AsmScanner.java    # AsmScanner.flexから生成されたもの
                AsmParser.java     # AsmParser.cupから生成されたもの
                AsmParserSym.java  # AsmParser.cupから生成されたもの
                自作ソース

Eclipseのワークスペースのソースフォルダ直下に.flexと.cupを配置し、これらを処理して生成される.javaファイルを自作ソースコードのあるパッケージフォルダ(パッケージ名がjp.asamomiji.assemblerなのでjp/asamomiji/assembler)を指定しています。自作ソースと自動生成ソースが同じ場所に混在するのがちょっと汚いのですが…。

次にAnt用のbuild.xmlを作成します。

<?xml version="1.0" encoding="utf-8" ?>
<project    name="Compiler" default ="compile" basedir=".">
  <property name="src"              location="src" />
  <property name="classes"          location="bin" />
  <property name="jflexlib"         location="c:/tools/jflex/lib" />
  <property name="cuplib"           location="c:/tools/cup" />
  <property name="cupruntimelib"    location="${cuplib}/java-cup-11b-runtime.jar" />

  <taskdef  name="jflex" classname="jflex.anttask.JFlexTask"   classpath="${jflexlib}/jflex-1.6.1.jar" />
  <taskdef  name="cup"   classname="java_cup.anttask.CUPTask"  classpath="${cuplib}/java-cup-11b.jar"   />

  <target name="generate">
    <jflex  file="${src}/AsmScanner.flex" destdir="${src}" />
    <cup srcfile="${src}/AsmParser.cup" destdir="${src}" parser="AsmParser"
      interface="true" locations="false" />
  </target>

  <target name="compile" depends="generate">
    <javac srcdir="${src}" destdir="${classes}" classpath="${cupruntimelib}" includeantruntime="false" encoding="utf-8" />
  </target>

  <target name="clean">
    <delete file="${src}/jp/asamomiji/assembler/AsmParser.java" />
    <delete file="${src}/jp/asamomiji/assembler/AsmParserSym.java" />
    <delete file="${src}/jp/asamomiji/assembler/AsmScanner.java" />
  </target>
</project>

ポイントは、JFlexとCUPから生成されたJavaコードをもとに全体をビルドする必要があるため、compileタスクで明示的にJavaソースコードのコンパイルを実行しているところです。その他、パス名は自分の環境に合わせて修正してください。

さらにJavaのビルドパスに、外部JARとしてCUPのランタイムライブラリ(java-cup-11b-runtime.jar)を追加します。

最後にEclipseにCUP用プラグインを追加します。ダウンロードページの指示にしたがって、Eclipseの「ヘルプ→更新ソフトウエアのインストール」からインストールしてください。

JFlex用のプラグインは無いみたいです。。。一応cup-lex-eclipseというのが見つかってはいるのですが、うまくインストールできませんでした。

サンプル構文解析コード

字句解析 (AsmScanner.flex)

昔ながらのlexやGNUのflexを触ったことのある人なら、書式はそれほど難しくないと思います。JFlexはCUPとの連携をするための構文が用意されているので、CUPを使っておけば楽できそうです。

で、昔ながらのアセンブラの書式だと、数値の表現方法が今どきから見るとちょっと特殊です。

  • $1000    ('$'を前置すると16進数)
  • 1000H   ('H'を後置すると16進数)
  • %00101111 ('%'を前置すると2進数)
  • @0777 ('@'を前置すると8進数)

これに、"0x"を前置したら16進数、みたいな規則もやはり欲しいので、この辺りの処理に手間取りそうです。

/*
 * Scanner for 6802 assembler
 */
package jp.asamomiji.assembler;

import java_cup.runtime.*;

%%

%class AsmScanner
%unicode
%cup
%line
%column

%state HEXNUMBER

%{
    private SymbolFactory sf;
    public AsmScanner(java.io.Reader in, SymbolFactory sf) {
        this(in);
        this.sf = sf;
    }

    private int intValue(String s, int radix) {
        try {
            return Integer.parseInt(s, radix);
        }
        catch (NumberFormatException e) {
            throw new RuntimeException("exception occured in intValue(): " + s);
        }
    }

    private boolean isByteRange(int value) {
        return value <= 255 ? true : false;
    }
%}

Identifier          = [:jletter:] [:jletterdigit:]*
LineTerminator      = \r|\n|\r\n
InputCharacter      = [^\r\n]
WhiteSpace          = [ \t\f]
Comment             = ; {InputCharacter}* {LineTerminator}
HexadecimalPrefix   = "0x"
HexadecimalNumber   = [0-9a-fA-F]+

%%

<YYINITIAL> {
    /* 予約語 */
    "ADDA"              { return sf.newSymbol("ADDA", AsmParserSym.ADDA); }
    "ADDB"              { return sf.newSymbol("ADDB", AsmParserSym.ADDB); }
    "ABA"               { return sf.newSymbol("ABA", AsmParserSym.ABA); }

    "X"                 { return sf.newSymbol("X", AsmParserSym.REG_X); }

    /* 記号 */
    ":"                 { return sf.newSymbol("COLON", AsmParserSym.COLON); }
    ","                 { return sf.newSymbol("COMMA", AsmParserSym.COMMA); }
    "#"                 { return sf.newSymbol("HASH", AsmParserSym.HASH); }
    {LineTerminator}    { return sf.newSymbol("NEWLINE", AsmParserSym.NEWLINE); }

    {Identifier}        { return sf.newSymbol("IDENTIFIER", AsmParserSym.IDENTIFIER, yytext()); }

    {HexadecimalPrefix} { yybegin(HEXNUMBER); }

    {Comment}           { /* ignore */ }
    {WhiteSpace}        { /* ignore */ }
}

<HEXNUMBER>
    {HexadecimalNumber} { yybegin(YYINITIAL);
                          int value = intValue(yytext(), 16);
                          return isByteRange(value)
                              ? sf.newSymbol("BYTE_VALUE", AsmParserSym.BYTE_VALUE, value)
                              : sf.newSymbol("SHORT_VALUE", AsmParserSym.SHORT_VALUE, value); }

<<EOF>>             { return sf.newSymbol("<<EOF>>", AsmParserSym.EOF); }

 

構文解析 (AsmParser.cup)

こちらの方はyaccやbisonとは若干書式が異なりますが、それらを使ったことのある人には特に難しくはないと思います。書式で苦労するよりも、むしろ構文のデバッグの方がはまるでしょう。こんな短い構文でも、シフト・還元衝突の解決に時間を費やしています……。

/*
 * Parser for 6802 assembler
 */
package jp.asamomiji.assembler;

import java_cup.runtime.*;
import java.util.Vector;

class AsmParser;

parser code {:
    private Vector<Instruction> instructions = new Vector<Instruction>();
:};

/* 終端記号 */
terminal            COLON, COMMA, HASH, NEWLINE;
terminal            ADDA, ADDB, ABA;
terminal Integer    BYTE_VALUE;
terminal Integer    SHORT_VALUE;
terminal String     IDENTIFIER;
terminal            REG_X;

/* 非終端記号 */
nonterminal Vector<Instruction> program;
nonterminal                     line_list;
nonterminal String              label;
nonterminal Instruction         line, operation;

/* 文法 */
start with program;

program   ::= line_list
              {: RESULT = instructions; :}
              ;

line_list ::= line_list line:inst
              {: if (inst != null) {instructions.add(inst);} :}
              |
              line:inst
              {: if (inst != null) {instructions.add(inst);} :}
              ;

line      ::= label:name operation:inst NEWLINE
              {: inst.setLabel(new Label(name)); RESULT = inst; :}
              |
              label:name NEWLINE
              {: RESULT =new DummyInstruction(); RESULT.setLabel(new Label(name)); :}
              |
              operation:inst NEWLINE
              {: RESULT = inst; :}
              |
              NEWLINE
              {: /* ignore */ :}
              ;

label     ::= IDENTIFIER:str COLON
              {: RESULT = str; :}
              ;

operation ::= ADDA HASH BYTE_VALUE:value
              {: RESULT = new ADDA(Instruction.MODE_IMMEDIATE, value.intValue()); :}
              |
              ADDA BYTE_VALUE:value
              {: RESULT = new ADDA(Instruction.MODE_DIRECT, value.intValue()); :}
              |
              ADDA BYTE_VALUE:value COMMA REG_X
              {: RESULT = new ADDA(Instruction.MODE_INDEXED, value.intValue()); :}
              |
              ADDA SHORT_VALUE:value
              {: RESULT = new ADDA(Instruction.MODE_EXTENDED, value.intValue()); :}
              |
              ADDB HASH BYTE_VALUE:value
              {: RESULT = new ADDB(Instruction.MODE_IMMEDIATE, value.intValue()); :}
              |
              ADDB BYTE_VALUE:value
              {: RESULT = new ADDB(Instruction.MODE_DIRECT, value.intValue()); :}
              |
              ADDB BYTE_VALUE:value COMMA REG_X
              {: RESULT = new ADDB(Instruction.MODE_INDEXED, value.intValue()); :}
              |
              ADDB SHORT_VALUE:value
              {: RESULT = new ADDB(Instruction.MODE_EXTENDED, value.intValue()); :}
              |
              ABA
              {: RESULT = new ABA(); :}
              ;

次に向けて

次は字句解析・構文解析系を完成させようと思います。もう少し詳細なコードの説明は次回に。

これまでの記録

 

コメント

タイトルとURLをコピーしました