今回は、インタプリンター／コンパイラ作成に向けて、数値や関数の検査と評価を試してみます。これは、文字列を読み込んでその「構文」を検査し、その文字列が一定の構文規則を満たして評価可能なものであれば評価する、という処理（字句解析）です。処理としてはあらかじめ定めた構文規則（文法）に基づく単純な文字列検査や切り分けが中心ですが、こういった処理を一定の「形式」にそって行うことで文字列から構文の「要素」を切り分けてそれぞれ評価していくことが可能になります。
今回は、この構文の検査や評価の最も簡単な例として「数値」と「数値を一つ引数に持つ関数」を扱ってみることにしました。
数値と引数の検査
最初に、今回扱う数値と関数の構文を定義しておきましょう。まず、数値は「0-9の数字のみからなる文字列」である、と定義します。つまり、0-9の数字以外の文字が一つでもあればそれは数値ではありません。具体的にとり得る値としては、０以上の整数ということになります。次に関数は、関数名とそれに続く()、そして()内の引数から構成される文字列である、と定義します。関数名をfuncとするのなら、func(数値)という形式の文字列ですね。この場合、引数に数値がなければエラーです。
今回は、関数としてinc（引数に１加算した値を返す）とsqr（引数を２乗した値を返す）の２つを用意しました。つまり、以下のような文字列を評価し、その値を得るような処理を考えてみるわけです。
| 文字列 | 検査 | 関数 | 引数 | 値 |
|---|---|---|---|---|
| inc(0) | 受理 | inc | 0 | 1 |
| sqr(16) | 受理 | inc | 16 | 256 |
| inc(0)w | エラー | - | - | - |
| (0) | エラー | - | - | - |
| inc() | エラー | - | - | - |
では、実際にこの文法に沿って文字列を検査する処理を考えていきます。数値に関しては、単純に文字列を走査し文字列を構成する文字がすべて0-9の数値がどうか調べれば良いでしょう。たとえば、以下のような処理です。
private boolean isNum(String stArg) { // 文字列が数値か検査
if (stArg.length()==0)
return false;
for (int i=0;i<stArg.length();i++)
switch (stArg.charAt(i)) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
break;
default: // 数字以外の文字があれば偽
return false;
}
return true;
}
また、文字列を数値であるものとして評価し、値を得る関数は以下のようになります。
private int parseNum(String stArg) { // 数値を評価し値を返す
int num=0,position=1,len=stArg.length();
if (stArg.length()==0)
return 0;
for (int i=1;i<=len;i++)
switch (stArg.charAt(len-i)) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
num+=(stArg.charAt(len-i)-'0')*position;
position*=10; // 位取り
break;
default:
return 0; // 数値以外の文字があれば0
}
return num;
}
関数の検査は、少し複雑です。まず、関数であるためには内部に数値を含む()が一組必要ですね。また、その()の前には関数名として評価しうる文字列があることも条件になります。今回は、文字列が関数であるか調べるため、まず関数の構文を調べることにしました。その判定条件は
- 正しく対応している()が一組のみある
- ()内に数値として評価しうる文字列がある
- ()の前に文字列がある（(が文字列の最初にない）
- ()の後に文字列がない（)が文字列の最後にある）
というものです。この条件で、文字列が「文字列(文字列)」という「評価可能な関数になる可能性がある構文規則」を満たしているか調べます。
では、この条件を具体的な処理として考えてみましょう。まず、「()が一組」あって「(の後少なくとも１文字以上の文字列が存在してから)が出現」していれば、１と２を満たすことになります。さらに「(の位置が２文字目以降」で「)の位置が文字列の最後」であれば、すべての条件を満たすわけですね。この検査は、検査対象の文字列をstArgとすれば以下のように書けます。この処理を終えた段階でfErrがtrueなら、()の形式に問題があることになります。
int len=stArg.length(),n=0,index=0,num;
boolean bErr=false;
// ()を検査
for (int i=0;i<len;i++) {
if (stArg.charAt(i)=='(') {
// (が最初に、または複数あればエラー
if (i==0 || n!=0)
bErr=true;
else
n=1;
// (の出現位置を保存
index=i;
}
if (stArg.charAt(i)==')') {
// )が(の直後にある、または最後になければエラー
if (n>2 && i==len-1)
n=-1;
else
bErr=true;
}
if (n>0) // 既に(が出てきていたらn++
n++;
}
// ()の検査結果が異常ならエラー
if (n!=-1)
bErr=true;
上の処理では、(の出現フラグnに注目してください。nは(が出現した時点で１になり、その後ループ最後で毎回１加算されていきます。つまり、)が出現した時点でnが２なら、それは(のすぐ後（次のループ実行時）に)が来ている（エラー）であることを意味するわけです。また、それまでに(がなければnは初期値０のままなので、)を見つけた時点でnは２より大きい必要があることになります。
関数になりうる文字列であることが確認できたら、()の前の文字列（関数名候補）と()内の文字列（引数候補）を取得して、それぞれ検査・評価しましょう。まず、文字列の取得に関しては(の出現位置をindexに保存してあるので、以下のようにして「最初から(の前まで」の文字列と「(の次から最後から２番目まで」の文字列を取得すれば良いでしょう。
// (の前の関数名候補と()内の引数候補の文字列を取得 stFunc=stArg.substring(0,index); stNum=stArg.substring(index+1,len-1);
引数が数値であるかの検査は
if (!isNum(stNum))
とするだけですね。関数名の方は、関数名のリストと一つずつ照合していけば良いでしょう。関数名と一致したら、引数numで関数を評価しその値を返します。
num=parseNum(stNum);
if (stFunc.equals("inc"))
return ++num;
if (stFunc.equals("sqr"))
return num*num;
これで「渡された文字列が関数であればその値を評価して返す」処理ができました。もし、文字列が数値であればその値を返すようにすると、「渡された文字列の値を評価して返す（文字列が異常なら−１を返す）」関数parse()は以下のようになります。
private int parse(String stArg) { // 渡された文字列を数値・関数として評価
String stFunc,stNum;
int len=stArg.length(),n=0,index=0,num;
boolean bErr=false;
if (len==0)
return -1;
if (isNum(stArg)) // 数値なら、その値を返す
return parseNum(stArg);
// ()を検査
for (int i=0;i<len;i++) {
if (stArg.charAt(i)=='(') {
// (が最初に、または複数あればエラー
if (i==0 || n!=0)
bErr=true;
else
n=1;
// (の出現位置を保存
index=i;
}
if (stArg.charAt(i)==')') {
// )が(の直後にある、または最後になければエラー
if (n>2 && i==len-1)
n=-1;
else
bErr=true;
}
if (n>0) // 既に(が出てきていたらn++
n++;
}
// ()の検査結果が異常ならエラー
if (n!=-1)
bErr=true;
if (bErr)
return -1;
// (の前の関数名候補と()内の引数候補の文字列を取得
stFunc=stArg.substring(0,index);
stNum=stArg.substring(index+1,len-1);
// 引数が数値でなければエラー
if (!isNum(stNum))
return -1;
num=parseNum(stNum);
if (stFunc.equals("inc"))
return ++num;
if (stFunc.equals("sqr"))
return num*num;
// 関数名が異常ならエラー
return -1;
}
プログラム
実行したら左側のString入力欄に文字列を入力し、=ボタンをクリックしてその文字列を評価してみてください。結果が右側に表示されます。