記号処理・第 5 回

記号処理・第 5 回
2015 年 5 月 19 日
今回の内容
5.1
プログラミング言語 Minimum C . . . . . . . . . . . . . . . . . . . . . . . . .
5–1
5.2
演習問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5–3
5.1
プログラミング言語 Minimum C
今回以降、例題として Minimum C という C に似たプログラミング言語を考え、これをソース言
語と想定して具体的なコンパイラを構築していくことにします。次の 2 つは Minimum C プログ
ラムの例です1 。
pow3.mc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
gcd.mc
int x, y, z;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
pow ()
{
z = 1;
while (y > 0) {
z = z * x;
y = y - 1;
}
}
main ()
{
input x;
input y;
pow();
print z;
}
gcd (x, y)
{
int z;
if (x
z
x
y
}
<
=
=
=
y) {
x;
y;
z;
while
z
y
x
}
(y != 0) {
= y;
= x % y;
= z;
return x;
}
main ()
{
int a, b;
input a;
input b;
print gcd(a, b);
}
C と比較すると、Minimum C には以下のような制限があります。
1. データ型は int 型のみで、演算子の種類が非常に限られている。
2. 入出力のための特別な構文 (input 文と print 文) が用意されている。
3. for 文や switch 文、do 文、break 文、continue 文、goto 文はない。
4. #define や #include などの前処理指令 (プリプロセッサ制御文) は使用できない。
1
ただし行頭の数は行番号で、プログラムの一部ではありません
5–1
Minimum C の文法
Minimum C は C のサブセットであり、その文法を BNF 記法で記述すると以下のようになりま
す。hP rogi が Minimum C で書かれたプログラム全体を表す非終端記号です。
hP rogi ::= { hVarDef i | hF unDef i } .
hVarDef i ::= “int”hIdenti { “,”hIdenti } “;” .
hF unDef i ::= hIdenti“(” [ hIdenti { “,”hIdenti } ] “)”hBlock i.
hBlock i ::= “{” [ hVarDef i ] { hStatementi } “}”.
hStatementi ::= hIdenti“=”hExpi“;” | hIdentihF unArgsi“;”
| “return”hExpi“;” | “print”hExpi“;” | “input”hIdenti“;”
| “if”“(”hCondi“)”hStatementi [ “else”hStatementi ]
| “while”“(”hCondi“)”hStatementi
| hBlock i .
hF unArgsi ::= “(” [ hExpi { “,”hExpi } ] “)” .
hF actori ::= hIdenti [ hF unArgsi ] | hN umberi | “(”hExpi“)”.
hM ultDivi ::= “*” | “/” | “%”.
hT ermi ::= hF actori { hM ultDivihF actori } .
hP lusM inusi ::= “+” | “-”.
hExpi ::= [ hP lusM inusi ] hT ermi { hP lusM inusi hT ermi } .
hReli ::= “==” | “!=” | “<” | “>” | “<=” | “>=” .
hCondi ::= hExpihRelihExpi.
空文は許されないこと、変数への代入は文であり、式ではないこと、if 文の構文には曖昧性がある
こと、if 文や while 文の条件部には 2 つの式の比較しか書くことができないことに注意してくだ
さい。また、BNF 記法では表現されていない文法上の制限として以下のようなものあります。
1. hN umberi は 10 進数表記の非負整数を表す。
2. hIdenti は変数名や関数名などの識別子であり、“int”、“return”、“while” などの予約語と
は重ならないものとする。
3. hN umberi や hIdenti は字句解析部がトークンとして切り出す。この際、トークン間の空白
類は無視される。
4. C と同様に、hV arDef i によってあらかじめ宣言されていない変数を使うことはできない。
ただし、関数は後から定義してもよい。
5. C と同様に、main という名前の関数が定義されていなければならない。プログラム全体の
実行は、この main から開始される。
5–2
5.2
演習問題
1. x と f が hIdenti で、123 が hN umberi であるとして、x = f(-123); の hStatementi に対
する構文木を書きなさい。
2. Minimum C の if 文に関する曖昧性を示しなさい。
3. BNF 記法で書かれた Minimum C の文法に従って各非終端記号の構文図を書きなさい。ま
た、できあがった構文図が決定的でないことを示しなさい。
記号処理・第 5 回・終り
付録 : 第 3 回演習問題の解答例
1.
1
0
2
整数
非ゼロ数字
3
–
数字
4
5
非ゼロ数字
.
小数部
6
非ゼロ数字
数字
7
8
9
実数
整数
小数部
0
数字
–
非ゼロ数字
0
小数部
2.
小数部
.
非ゼロ数字
0
非ゼロ数字
0
h小数部i ::= “.” { “0” } h非ゼロ数字i { { “0” } h非ゼロ数字i } .
(構文図の別解)
小数部
.
非ゼロ数字
0
5–3
3.
1 以上
非ゼロ数字
数字
小数部
0
小数部
1 以上
実数
–
1 以上
0
小数部
h1以上i ::= h非ゼロ数字i { h数字i } [ h小数部i ] .
h実数i ::= “0” [ h小数部i ] | h1以上i | “-” ( h1以上i | “0”h小数部i ) .
(別解)
0
小数部
実数
非ゼロ数字
–
数字
小数部
数字
小数部
非ゼロ数字
0
小数部
h実数i ::= “0” [ h小数部i ] | h非ゼロ数字i { h数字i } [ h小数部i ]
| “-” ( h非ゼロ数字i { h数字i } [ h小数部i ] | “0”h小数部i ) .
(構文図の別解)
0
実数
非ゼロ数字
数字
–
0
5–4
小数部

Download Report