(a|b)*abbという正規表現を認識する DFAの状態遷移表は次のようになる。
| AC | B | D | E | |
| a | B | B | B | B |
| b | AC | D | E | AC |
この状態遷移表を用いて、引数として渡された文字列が、正規表現 (a|b)*abbにマッチするならば 1をそうでなければ 0を返す関数 int ababb(char*)を定義せよ。
プログラムはこんな感じ
#include <stdio.h>
int table[?][?] = {?}; /* 遷移表を配列として表現 */
int ababb(char* str) {
?
}
int main(int argc, char** argv) {
int i;
for (i=1; i<argc; i++) {
char* str = argv[i];
if (ababb(str)) {
printf("%sは正規表現 (a|b)*abbにマッチします。\n", str);
} else {
printf("%sは正規表現 (a|b)*abbにマッチしません。\n", str);
}
}
return 0;
}
E -> id
| E "[" E "]"
| E "." id
| E "(" X ")"
X -> E X'
X' -> "," E X'
| ε
に対して、
次の文法（開始記号は Expr）:
Expr → CON
| FunCall
FunCall → FID '(' Expr ',' Expr ')'
-- 以下は終端記号: 字句解析部で処理
EOL → '\n' -- End Of Line
CON → '0' | '1' | ... | '9' -- 一桁の数のみ
FID → '+' | '-' | '*'
に対する再帰下降構文解析プログラムの例
を参考にして、問の文法に対する再帰下降構文解析プログラムを作成せよ。
入力が E であれば、"Correct!"（または「正しい!」）と表示し、 間違っていれば、適当なエラーメッセージを出力するようにせよ。
ただし、「終端記号に対応するマクロの定義」の部分は代わりに
#define ID 256 #define EOL 257「簡易字句解析ルーチン」は代わりに
/* 簡易字句解析ルーチン */
int yylex(void) {
int c;
do {
c = getchar ();
} while (c == ' ' || c == '\t'); /* 空白は読みとばす */
if (isalpha(c)) { /* IDは一文字のアルファベット */
yylval = c;
return ID;
}
if (c == '\n') { /* 行末が $（入力の終わり）に対応する */
return EOL;
}
if (c == EOF) { /* ファイルの終 */
exit(0);
}
/* 上のどの条件にも合わなければ、文字をそのまま返す。*/
return c; /* '(', ')', '*', '[', ']'など */
}
を用いよ。（プログラムのテンプレート）
少なくとも以下のような例については、テストして下さい。
| 入力 | 結果 |
|---|---|
| a[x] | Correct! |
| a[(x)] | エラー |
| a.t | Correct! |
| f() | エラー |
| f(x) | Correct! |
| f(x, y) | Correct! |
| f(x, y,) | エラー |
| f(x.t.x, a[x][y], z) | Correct! |
上の問題を解いて、プログラムを作成し、 またそれに対するレポートを作成して下さい。 （締切 2月 14日 火曜日 18時）
レポートは, OpenOffice Writer（もしくは同等のワープロソフト）で作成します。 作成したソースファイルとレポートのファイルをオンラインで提出してください。 （OpenOffice Writer以外のワープロの場合は、RTF, PDF, PostScriptなど、そのソフトを持っていなくても読める形式に変換して下さい。） また同時に、レポートをA4用紙に印刷し、 ホッチキスで左上を綴じたものを学務係前のレポートボックスに提出してください。
オンラインの提出場所は
レポート作成上の注意
問題を数人で相談しながら解くのはもちろん構いませんが、 実行例とレポートは各自で作成してください。 実行例まで同一のレポートは不正レポートと見なします。