プログラム minicomp.rr

前の節で定義した文法を満たす式を後置記法に直すプログラムは次のようになる.

#define 文で定義している, CodeOf で始まるシンボルは, アスキーコードをプログラム中に直接書くと読みにくいので 使用している. たとえば CodeOfA は A のアスキーコード 0x41 に対応している.

大域変数の解説をしよう.

Ch	最後に読み込んだ文字.
Sy	シンボルのタイプ. VARIABLE が変数, NUMBER が数字, その他が特殊記号.
Val	シンボルに対する値. NUMBER の時は実際の数値.
Ptr	入力文字列 Str の何文字目を読むか?
Result	後置記法に変換した結果の文字列.

関数名と非終端記号はつぎのように対応している.

expr()	最上位レベルの式 (expression)
exprterm()	項 (term)
exprfactor()	因子 (factor)

#define SPACE 0x20
#define CodeOfA 0x41
#define CodeOfZ 0x5a
#define CodeOfa 0x61
#define CodeOfz 0x7a
#define CodeOf0 0x30
#define CodeOf9 0x39
#define CodeOfPlus  0x2b
#define CodeOfMinus 0x2d
#define CodeOfMult  0x2a 
#define CodeOfDiv   0x2f
#define CodeOfLeftBracket  0x28
#define CodeOfRightBracket 0x29

#define VARIABLE 1
#define NUMBER   2

Ch = 0x20$ Sy = 0$ 
Value =0$ Ptr = -1$
Result=""$

次の関数 parse() に変換したい文字列 を引数として与えると, 後置記法に直す. たとえば

parse("2+3*(45+2);");

と入力すればよい. ; を忘れると parse() が修了しないので注意.

def parse(S) {
  extern Ch,Sy,Value,Ptr,Str, Result;
  Str = strtoascii(S);
  Ch = 0x20; Sy = 0; Value = 0; Ptr = -1;
  Result = "";
  in_symbol();
  expression();
  Result += " = ";
  return Result;
}

次は補助関数群である.

def is_space(C) {
  if (C <= SPACE) return 1;
  else return 0;
}

def is_alpha(C) {
  if ((C >= CodeOfA) && (C <= CodeOfZ)) return 1;
  if ((C >= CodeOfa) && (C <= CodeOfz)) return 1;
  return 0;
}

def is_digit(C) {
  if ((C >= CodeOf0) && (C <= CodeOf9)) return 1;
  return 0;
}

def getch() {
  extern Ptr, Str;
  if (Ptr >= length(Str)-1) return -1;
  else {
    Ptr++;
    return Str[Ptr];
  }
}

構文解析と変換は Str より文字を順番に読むことにより, おこなわれる. このとき文字列のなかの不必要な空白を読み飛ばしたり, 数字文字列を数字に変換したり, 数字と演算子を切り分けたりする必要がある. このような作業をトークンへの分解 とよぶ. この作業を担当しているのが, in_symbol() である.

def in_symbol() {
  extern Ch;
  while (is_space(Ch)) {
    Ch = getch();
  }
  if (is_alpha(Ch)) {
    Sy = VARIABLE;
    Value = Ch;
    Ch = getch();
  } else if (is_digit(Ch)) {
    Sy = NUMBER;
    Value = 0;
    do {
      Value = Value*10+(Ch-CodeOf0);
      Ch = getch();
    }while (is_digit(Ch));
  } else {
    Sy = Ch;
    Ch = getch();
  }
}

構文図に対応する関数達. 再帰的に呼ばれている.

def expression() {
  expr(); 
}

def expr() {
  extern Result;
  exprterm();
  while ((Sy == CodeOfPlus) ||
         (Sy == CodeOfMinus)) {
    Ope = (Sy == CodeOfPlus? CodeOfPlus :
                             CodeOfMinus);
    in_symbol();
    exprterm();
    Result += asciitostr([Ope])+" ";
  }
}

def exprterm() {
  extern Result;
  exprfactor();
  while ((Sy == CodeOfMult) ||
         (Sy == CodeOfDiv)) {
    Ope = (Sy == CodeOfMult? CodeOfMult :
                             CodeOfDiv);
    in_symbol();
    exprfactor();
    Result += asciitostr([Ope])+" ";
  }
}

def exprfactor() {
  extern Result;
  if (Sy == NUMBER) {
    Result += rtostr(Value)+" ";
    in_symbol();
  }else if (Sy == CodeOfLeftBracket) {
    in_symbol();
    expr();
    if (Sy != CodeOfRightBracket) {
       error("Mismatched parenthesis");
    }
    in_symbol();
  }else{
    error("Invalid factor");
  }
}

これらの関数をまとめて, minicomp.rr なる名前にまとめて 入力, ロード, 実行すると関数 parse() で 中置記法の後置記法への変換を実現できる. これと 12 章の関数 casio() を組み合わせれば, 簡単な数式の処理システムが書ける.