インタプリタのしくみ(その1)

インタプリタやコンパイラは、基本的に、
  字句解析 → 構文解析 → 意味解析 → 意味出力
の順に処理を行います。

〈字句解析〉

文字列を意味のある最小単位の部分文字列(トークン)に分割することです。
生成規則の終端記号がトークンに相当します。
例えば、文字列 “11*(x+27)” は、“11”, “*”, “(”, “x”, “+”, “27”, “)” に分割されます。
生成規則にないトークンが使用された場合は、この段階でチェックされます。
注)後述のプログラムでは、構文解析の段階で生成規則にないトークンのチェックをしています。

〈構文解析〉

構文が生成規則に違反していないかどうかをチェックすることです。
例えば、
  1 +- 2;
のようなエラーは構文解析の段階でチェックされます。
注)次回お話する算術演算インタプリタでは、字句解析の段階でも構文チェックをしています。

〈意味解析〉

構文以外の意味的なエラーをチェックすることです。
意味とは、インタプリタでは式の値、コンパイラでは式を評価するためのアセンブリコードのことです。
例えば、
  x = 1;
  x + y;
は構文的には間違っていませんが、y の値が未入力なので、x + y は意味を持ちません。
このようなエラーや型の不整合(xの値が数値でyの値が文字列のような場合)は意味解析の段階でチェックされます。

〈意味出力〉

インタプリタでは式の値を出力し、コンパイラではアセンブリコードを出力します。
プログラムが、
  x = 1;
  y = 2;
  x + y;
となっていれば、インタプリタでは 3 を出力し、コンパイラではアセンブリコード
  mov AX, 1
  mov BX, 2
  add AX, BX
を出力します。コンパイラでは意味出力をコード生成と呼びます。
尚、アセンブリコードは、アセンブラでマシンコードに変換されます。

〈生成規則〉

今、 例として以下のような生成規則を考えます。


-- Production Rules --
<expression> ::= <number> | <operator> '(' <expression> ',' <expression> ')'
<operator> ::= '+' | '*'
<number> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

< >で囲まれた記号が非終端記号(構文変数)、‘ ‘で囲まれた記号が終端記号(構文定数)を表します。

上記の生成規則に従って、一桁の自然数の加算、乗算を行うインタプリタを作成すると、interpreter.c のようになります。
構文解析にはいくつかの種類がありますが、このプログラムでは再帰下降構文解析器(recursive descent parser)を用いています。

interpreter.c


#include <stdio.h>
#include <stdlib.h>

char token;
void gettoken(void);
int expression(void);
void match(char);
void error(const char[]);

int main(void) {
  int i;
  for (;;) {
    gettoken();
    i = expression();
    if (token == '\n') printf("-> %d\n", i);
  }
  return 0;
}

void gettoken(void) {
  char c;
  do {
    c = getchar();
  } while (c == ' ' || c == '\t');
  token = c;
}

int expression(void) {
  int i, i1, i2;
  if ('0' <= token && token <= '9') {
    i = token - '0';
    gettoken();
  }
  else if (token == '+') {
    match('+'); match('('); i1 = expression(); match(','); i2 = expression(); match(')');
    i = i1 + i2;
  }
  else if (token == '*') {
    match('*'); match('('); i1 = expression(); match(','); i2 = expression(); match(')');
    i = i1 * i2;
  }
  else error("Syntax Error!");
  return i;
}

void match(char c) {
  if (token == c) gettoken();
  else error("Syntax Error!");
}

void error(const char message[]) {
  fprintf(stderr, "%s\n", message);
  exit(1);
}

使用例


+(1,*(+(1,2),2))
-> 7

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中