/********************************************************
* 再帰的下降型構文解析の例
* E: expressionを加減算の結果とする
* T: term を乗除算の結果
* F: factor 項(被演算子)とする
* n: numeric 値（簡単のため１文字）
*
* 構文規則（BNF）
* <L>::= <E> '\n'
* <E>::= <T> { {+|-} T}
* <T>::= <F> { {*|/} <F> }
* <F>::= n | ( <E> )
*
応用練習問題
1)Pーマシン言語に翻訳する
2)一桁の数字からなる式の計算する電卓プログラムに改造する。
(2+8)/(7-4) * 5
15
********************************************************/
#include <stdio.h>
void scan();
void error();
typedef int val_type; /* 浮動小数点演算なら double へ */
void print_val(val_type val)
{
printf("-> %d\n", val); /* 浮動小数点演算なら %lf に */
}
val_type E(); /* 非終端記号Eを解析する関数 戻りは計算値 */
val_type T(); /* 非終端記号Fを解析する関数 戻りは計算値 */
val_type F(); /* 非終端記号Tを解析する関数 戻りは計算値 */
char next; /*次のトークン*/
/*******************************************
* <L>::= <E> 改行文字
* lineは開始記号なので
* プログラムを短くするためmainにしてしまう
******************************************/
int main (int argc, char* argv[])
{
val_type v;
scan();
printf("L--->E\n");
v = E();
if (next != '\n') error();
print_val(v);
exit(0);
}
/*****************************************************
* トークン(非終端記号)を読みこむ関数
* 空白（タブはないものとして）を読み飛ばす
* 字句解析はしばしばスキャナーと呼ばれるので、ここではscan()とする。
****************************************************/
void scan()
{
while ( (next = getchar()) == ' ');
}
/******************************************************
* 簡単のためエラー回復なし、で構文解析終了とする
*****************************************************/
void error()
{
printf("*********error**********\n");
exit(1);
}
/*****************************************
* <E>::= <T> { {+|-} T }
*
* 解析プログラム E( ):
* 最初のトークンは既に読まれている
* T();
* while(トークン == 加算演算子) {
* 次のトークンを読む();
* T();
* }
* 戻るときは次のトークンまで読んでいる
*****************************************/
val_type E() {
val_type v1, v2;
printf("E--->T <E-rest> \n");
v1 = T();
if (next !='+' && next !='-')
printf("<E-rest>--->empty\n");
while (next == '+' || next == '-') {
int c = next; /* 後ろの処理で next が変わるので保持 */
printf("<E-rest> ---> %c T\n", next);
scan();
v2 = T();
/* ADDまたはSUBの演算 */
if (c == '+') {
v1 += v2;
}
else if (c == '-') {
v1 -= v2;
}
}
return v1;
}
/***************************
* <T>::=<F> { {*|/} <F> }
*
*解析プログラムT()：
* 最初のトークンは既に読まれている
* F();
* while(トークン == 乗除演算子) {
* 次のトークンを読む();
* F();
* }
* 戻るときは次のトークンまで読んでいる
****************************/
val_type T() {
val_type v1, v2;
printf("T--->F <F-rest>\n");
v1 = F();
if (next !='*' && next !='/')
printf("<F-rest>--->empty\n");
while (next=='*' || next=='/') {
int c = next; /* 後ろの処理で next が変わるので保持 */
printf("<F-rest>---> %c F\n", next);
scan();
v2 = F();
/* MULまたはDIVの演算 */
if (c=='*') {
v1 *= v2;
}
else if (c=='/') {
v1 /= v2;
}
}
return v1;
}
/********************************************
* <F>::= <0-9の1文字>
* | ( <E> )
*
*解析プログラムF()
* if (トークン == 値) {
* 次のトークンを読む();
* }
* else if (トークン == 括弧開き) {
* 次のトークンを読む();
* T();
* 括弧閉じを確定
* 次のトークンを読む();
* }
* 戻るときは次のトークンまで読んでいる
********************************************/
val_type F() {
val_type v;
if (next >='0' && next <= '9') {
printf("F--->id(%c)\n", next);
/* LOAD */
v = (val_type)(next - '0');
scan();
}
else if (next == '('){
printf("F --->( E )\n");
scan();
v = E();
if (next == ')') {
scan();
}
else
error();
}
return v;
}