whileプログラム

ざっくりいうと、if文とwhile文からなるプログラム

任意の基本プログラムはwhileプログラムに変換できる

それもwhileをたかだか1回しか使わないものに変換できる

つまり、高級言語で扱っているようなfor文などを使ったプログラムも全てwhileプログラムに変換可能

定義

code:bnf

Program = input(..); Stmt; output(.)

Stmt = <代入命令>

| Stmt_1; Stmt_2; Stmt_3; ... ; Stmt_n

| if <判定命令> then Stmt_1 else Stmt_2

| while Q do Stmt

補足

input: 入力命令

output: 出力命令

[]はブロックを表す

while Q do [P1; P2]とwhile Q do [P1]; P2を見ると違いがわかりやすい

後者はP1のみをループしている

基本プログラムはwhileプログラムに変換する

雑な手順

if文をラベルとgoto文に変換する

goto文をswtich文に変換する

swtich文をif文で書き直す

『計算可能性・計算の複雑さ入門』.icon p.28がわかりやすい

参考