MiniBasicの文法と解析

■MiniBasicの文法と解析

1. MiniBasicの概要

2. 文法の記述

3. 導出木の例

2005年10月5日 6:47 更新

1. MiniBasicの概要

簡単なBASICインタプリター（逐次翻訳・実行プログラム）をSableCCを用いて作成する。

【使用上の注意】
対象としているBASICのサブセット（MiniBasic）は、SableCCプロジェクトが評価用サンプルプロジェクトとして配布している minibasic-1.0.grammar を利用・改変したものである。ライセンス／配布条件等についてはこのLGPL文書(MiniBasic-LICENSE)を参照のこと。

1.1 MiniBasic言語の仕様
 1.2 MiniBasic言語のプログラム例

1.1 MiniBasic言語の仕様

ここで対象としているBASICのサブセット（以下、MiniBasicと呼ぶ）は、以下のようなデータ型と演算子、変数と代入、予約語、プログラム制御、ならびに組み込み関数（built-in function）を有するものである。

A. データ型と演算子

・定数は０を含む正整数とする
・数値演算可能なデータ型は、整数型とする
・数値演算子は、加減乗除（'+','-','*','/'）ならびに剰余('%')の５種類とする
・数値演算子の優先順位は考慮しない
・数値演算式は、括弧（'(',')'）を用いることができる
・数値演算子より、括弧の評価を優先する
・数値演算の結果は、整数値を返す。
・論理演算子は、等号（'='）と不等号（'>','<'）の３種類とする
・論理演算の結果は、論理値（真／偽）を返す。
・文字列は、文字の列を引用符 "" で囲んだものとする

B. 変数と代入

・変数の型宣言は不要とする
・代入前の変数の値はゼロをとるものとする
・変数への式評価値の代入は、代入記号 ':=' を用いて行う

C. 予約語

・演算子と括弧 '+','-','*','/','%','=','>','<','(',')'
・代入記号 ':='
・条件実行文 'IF','THEN','ELSE','ENDIF'
・繰り返し実行文 'FOR','TO','NEXT'
・組み込み関数名 'READ','PRINT','PRINTLN'

D. プログラム制御

・命令は、１行に１命令とする。
・各命令の終わりは改行コードであるとする。
・１行目から順番に実行する。
・プログラム終端（EOF）に達したら、プログラムは終了する

・条件実行文（IF）の書式は以下の通り

IF 条件 THEN [改行]
　　条件が真の場合に実行する命令列 [改行]
ELSE [改行]
　　条件が偽の場合に実行する命令列 [改行]
ENDIF [改行]

ただし、"ELSE [改行] 条件が偽の場合に実行する命令列 [改行]"　の部分は空でもよい。

・繰り返し実行文（FOR）の書式は以下の通り（インクリメントのみ）

FOR 変数 := 開始値 TO 終了値 [改行]
　　命令列 [改行]
NEXT [改行]

E. 組み込み関数

・関数名 READ　引数変数
　標準入力から整数値の読み込みを行う

・関数名 PRINT　引数数値演算式
　式の値を、標準出力へ表示する

・関数名 PRINT　引数文字列
　文字列の内容を、標準出力へ表示する

・関数名 PRINTLN　引数なし
　標準出力へ [改行] を表示する

1.2 MiniBasic言語のプログラム例

例１：代入と表示（乗算結果の表示）

I := 3
PRINT I * 5

例２：条件判断（絶対値の表示）

READ I
IF I < 0 THEN
  PRINT ( 0 - I )
ELSE
  PRINT I
ENDIF

例３：繰り返し（九九の表）

FOR X := 1 TO 9
  FOR Y := 1 TO 9
    PRINT X * Y
    PRINT " "
  NEXT
  PRINTLN
NEXT

2. 文法の記述

MiniBasic言語の文法について、以下に示す。

＜MiniBasic言語の文法＞

記号の定義

        letter = 英文字 ('A'..'Z')
        digit  = 数字 ('0'..'9')
        cr = CR改行コード (13);
        lf = LF改行コード (10);
        not_cr_lf = 改行コード以外の有効文字の集合
 
 
終端記号

　・変数名、リテラル、文字列
        identifier = 英文字で開始し２文字目以降が英文字あるいは数字の列
        number     = 数字が１文字以上の列
        string     = 引用符で囲まれた ０個以上の有効文字の列
        empty      = 空列

　・演算子と括弧
        plus  = '+'
        minus = '-'
        mult  = '*'
        div   = '/'
        mod   = '%'
        less_than    = '<'
        greater_than = '>'
        equal        = '='
        l_par = '('
        r_par = ')'

　・代入記号
        assign = ':='

　・条件実行文
        if    = 'IF'
        then  = 'THEN'
        else  = 'ELSE'
        endif = 'ENDIF;

　・繰り返し実行文
        for  = 'FOR'
        to   = 'TO'
        next = 'NEXT'

　・組み込み関数名
        read    = 'READ'
        print   = 'PRINT'
        println = 'PRINTLN'

　・改行
        new_line = CR, LF または CR LF の列


非終端記号

　・プログラム命令（列）
        Statement, Statements

　・条件実行文（IF）のELSE
        Optional_else

　・条件実行文（IF）の論理演算式
        Condition
        
　・数値演算式
        Expression

　・リテラル、変数名、括弧付き式の評価値
        Value

　・代入文
        Assignment
	

開始記号
        Statements


生成規則：
    (1)  Statements → Statement Statements
    (2)  Statements → empty

    (3)  Statement  → 'IF' Condition 'THEN' new_line
                            Starements
                            Optional_else
                       'ENDIF' new_line
    (4)  Statement  → 'FOR' identifier assign Expression 
	                                   TO Expression new_line
                            Starements
                       'NEXT' new_line
    (5)  Statement  → 'READ' identifier new_line
    (6)  Statement  → 'PRINT' Expression new_line
    (7)  Statement  → 'PRINT' string new_line
    (8)  Statement  → 'PRINTLN' new_line
    (9)  Statement  → identifier assign Expression new_line

   (10)  Optional_else → 'ELSE' new_line
                                 Starements
   (11)  Optional_else → empty

   (12)  Condition  → Expression '<' Expression 
   (13)  Condition  → Expression '>' Expression 
   (14)  Condition  → Expression '=' Expression 

   (15)  Expression → Value
   (16)  Expression → Value '+' Value
   (17)  Expression → Value '-' Value
   (18)  Expression → Value '*' Value
   (19)  Expression → Value '/' Value
   (20)  Expression → Value '%' Value

   (21)  Value      → number
   (22)  Value      → identifier
   (23)  Value      → '('  Expression  ')'

3. 導出木の例

上記 2.の文法に基づいて生成された、導出木の例（プログラムの表現）を、図5.1に示す。

プログラム例１：代入と表示（乗算結果の表示）

I := 3
PRINT I * 5

プログラム例1に対する導出木

図5.1: プログラム例１の導出木

4. SableCCによる解析器の生成

4.1 文法ファイル
 4.2 minibasic.grammarの説明
 4.3 SableCCによる構文解析器の生成とテスト

4.1 文法ファイル

2.文法の定義に基づいて、SableCC用 minibasic.grammar 文法ファイルを作成する。
（説明上、左端に行番号を付した。実際の文法ファイル中に行番号は付されていない）

＜文法ファイル：minibasic.grammar＞

     1  /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
     2   * This file is part of MiniBasic.                                 *
     3   * See the file "MiniBasic-LICENSE" for Copyright information and  *
     4   * the terms and conditions for copying, distribution and          *
     5   * modification of MiniBasic.                                      *
     6   * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
     7
     8  Package minibasic;
     9
    10  Helpers
    11    letter = ['A'..'Z'];
    12    digit  = ['0'..'9'];
    13    cr = 13;
    14    lf = 10;
    15    not_cr_lf = [[32..127] - [cr + lf]];
    16
    17  Tokens
    18    if    = 'IF';
    19    then  = 'THEN';
    20    else  = 'ELSE';
    21    endif = 'ENDIF';
    22
    23    for  = 'FOR';
    24    to   = 'TO';
    25    next = 'NEXT';
    26
    27    read    = 'READ';
    28    print   = 'PRINT';
    29    println = 'PRINTLN';
    30
    31    assign = ':=';
    32
    33    less_than    = '<';
    34    greater_than = '>';
    35    equal        = '=';
    36
    37    plus  = '+';
    38    minus = '-';
    39    mult  = '*';
    40    div   = '/';
    41    mod   = '%';
    42
    43    l_par = '(';
    44    r_par = ')';
    45
    46    identifier = letter (letter | digit)*;
    47    number     = digit+;
    48    string     = '"' [not_cr_lf - '"']* '"';
    49
    50    new_line = cr | lf | cr lf;
    51
    52    blank = ' '*;
    53
    54  Ignored Tokens
    55    blank;
    56
    57  Productions
    58    statements = 
    59      {list}  statement statements | 
    60      {empty} ;
    61
    62    statement = 
    63      {if}         if condition then [nl1]:new_line
    64                     statements
    65                     optional_else
    66                   endif [nl2]:new_line |
    67
    68      {for}        for identifier assign [from_exp]:expression 
	                                    to [to_exp]:expression [nl1]:new_line
    69                     statements
    70                   next [nl2]:new_line |
    71
    72      {read}       read identifier new_line |
    73
    74      {print_exp}  print expression new_line |
    75      {print_str}  print string new_line |
    76      {println}    println new_line |
    77
    78      {assignment} identifier assign expression new_line;
    79
    80    optional_else = 
    81      {else}  else new_line
    82                statements |
    83      {empty} ;
    84    
    85    condition =
    86      {less_than}    [left]:expression less_than    [right]:expression |
    87      {greater_than} [left]:expression greater_than [right]:expression |
    88      {equal}        [left]:expression equal        [right]:expression;
    89
    90    expression =
    91      {value} value |
    92      {plus}  [left]:value plus  [right]:value |
    93      {minus} [left]:value minus [right]:value |
    94      {mult}  [left]:value mult  [right]:value |
    95      {div}   [left]:value div   [right]:value |
    96      {mod}   [left]:value mod   [right]:value;
    97
    98    value =
    99      {constant}   number |
   100      {identifier} identifier |
   101      {expression} l_par expression r_par;

4.2 minibasic.grammarの説明

※SableCCの文法ファイル形式はここから参照されたい。
http://sablecc.org/grammars/sablecc-2x.sablecc.web.html

文法ファイル（minibasic.grammar）について、各ディレクティブについて説明する。

8行目（Packageディレクティブ）

パッケージ名を指示している。これは minibasic パッケージである。

10--15行目（Helpersディレクティブ）

字句規則ならびに構文規則中で使用する記号の定義（マクロ）を行っている。
各記号の意味は、2.文法を参照のこと。

17--52行目（Tokensディレクティブ）

字句規則を指定している。
各記号の意味は、2.文法を参照のこと。

54--55行目（Ignored Tokensディレクティブ）

字句解析時に無視するトークンを指定している。ここでは　blank（１個以上続く空白文字列）を指定している。

57-101行目（Productionsディレクティブ）：

構文規則を指定している。
各生成規則の意味は、2.文法を参照のこと。

4.3 SableCCによる構文解析器の生成とテスト

minibasic.grammar試験用プロジェクトファイルをビルドして、SableCCによる構文解析器を生成してみよう。

minibasicプロジェクトファイルはここからダウンロード（minibasic-src.tar.gz）
ビルド済みのプロジェクトファイルはここからダウンロード（minibasic-build.tar.gz）

minibasicパッケージ全体のjavadocドキュメントセット

実際に、プログラム例を解析器（minibasic.jar）に入力した場合の実行結果を以下に示す。プログラム例は、上記プロジェクトファイルに含まれている。
実行結果は、minibasic.tool.PrintTreeクラスによって、導出木全体を深さ優先探索した結果で表示されている。

実行時には、classpath（-cp）として生成した minibasic.jar を指定し、更に、開始時mainメソッドが含まれているクラスとして minibasic.tool.PrintTreeクラスを指定することに注意する。このmainメソッドは、コマンドライン引数の最後として、入力プログラムが格納されたテキストファイルを指定されることを仮定している。詳しくは、PrintTreeクラスのソースファイルを参照のこと。

＜実行結果１：プログラム test0.basic＞

I := 3
PRINT I * 5
PRINTLN

$ java -cp minibasic.jar minibasic.tool.PrintTree test0.basic

Start
 AListStatements
  AAssignmentStatement
   TIdentifier: I
   TAssign: :=
   AValueExpression
    AConstantValue
     TNumber: 3
   TNewLine: 

  AListStatements
   APrintExpStatement
    TPrint: PRINT
    AMultExpression
     AIdentifierValue
      TIdentifier: I
     TMult: *
     AConstantValue
      TNumber: 5
    TNewLine: 

   AListStatements
    APrintlnStatement
     TPrintln: PRINTLN
     TNewLine: 

    AEmptyStatements
 EOF:

＜実行結果２：プログラム test2.basic＞

PRINT "What is your number"
READ I
PRINT "ABS( "
PRINT I
PRINT " ) = "
IF I < 0 THEN
  PRINT ( 0 - I )
ELSE
  PRINT I
ENDIF
PRINTLN

$ java -cp minibasic.jar minibasic.tool.PrintTree test2.basic

Start
 AListStatements
  APrintStrStatement
   TPrint: PRINT
   TString: "What is your number"
   TNewLine: 

  AListStatements
   AReadStatement
    TRead: READ
    TIdentifier: I
    TNewLine: 

   AListStatements
    APrintStrStatement
     TPrint: PRINT
     TString: "ABS( "
     TNewLine: 

    AListStatements
     APrintExpStatement
      TPrint: PRINT
      AValueExpression
       AIdentifierValue
        TIdentifier: I
      TNewLine: 

     AListStatements
      APrintStrStatement
       TPrint: PRINT
       TString: " ) = "
       TNewLine: 

      AListStatements
       AIfStatement
        TIf: IF
        ALessThanCondition
         AValueExpression
          AIdentifierValue
           TIdentifier: I
         TLessThan: <
         AValueExpression
          AConstantValue
           TNumber: 0
        TThen: THEN
        TNewLine: 

        AListStatements
         APrintExpStatement
          TPrint: PRINT
          AValueExpression
           AExpressionValue
            TLPar: (
            AMinusExpression
             AConstantValue
              TNumber: 0
             TMinus: -
             AIdentifierValue
              TIdentifier: I
            TRPar: )
          TNewLine: 

         AEmptyStatements
        AElseOptionalElse
         TElse: ELSE
         TNewLine: 

         AListStatements
          APrintExpStatement
           TPrint: PRINT
           AValueExpression
            AIdentifierValue
             TIdentifier: I
           TNewLine: 

          AEmptyStatements
        TEndif: ENDIF
        TNewLine: 

       AListStatements
        APrintlnStatement
         TPrintln: PRINTLN
         TNewLine: 

        AEmptyStatements
 EOF:

＜実行結果３：プログラム test3.basic＞

PRINT "What is your number"
READ I
FOR X := 1 TO I
  FOR Y := 1 TO I
    PRINT X * Y
    PRINT " "
  NEXT
PRINTLN
NEXT
PRINTLN

$ java -cp minibasic.jar minibasic.tool.PrintTree test3.basic

Start
 AListStatements
  APrintStrStatement
   TPrint: PRINT
   TString: "What is your number"
   TNewLine: 

  AListStatements
   AReadStatement
    TRead: READ
    TIdentifier: I
    TNewLine: 

   AListStatements
    AForStatement
     TFor: FOR
     TIdentifier: X
     TAssign: :=
     AValueExpression
      AConstantValue
       TNumber: 1
     TTo: TO
     AValueExpression
      AIdentifierValue
       TIdentifier: I
     TNewLine: 

     AListStatements
      AForStatement
       TFor: FOR
       TIdentifier: Y
       TAssign: :=
       AValueExpression
        AConstantValue
         TNumber: 1
       TTo: TO
       AValueExpression
        AIdentifierValue
         TIdentifier: I
       TNewLine: 

       AListStatements
        APrintExpStatement
         TPrint: PRINT
         AMultExpression
          AIdentifierValue
           TIdentifier: X
          TMult: *
          AIdentifierValue
           TIdentifier: Y
         TNewLine: 

        AListStatements
         APrintStrStatement
          TPrint: PRINT
          TString: " "
          TNewLine: 

         AEmptyStatements
       TNext: NEXT
       TNewLine: 

      AListStatements
       APrintlnStatement
        TPrintln: PRINTLN
        TNewLine: 

       AEmptyStatements
     TNext: NEXT
     TNewLine: 

    AListStatements
     APrintlnStatement
      TPrintln: PRINTLN
      TNewLine: 

     AEmptyStatements
 EOF: