a21_txt01_7
の編集
https://essen.osask.jp/?a21_txt01_7
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
BracketName
EssenRev4
FormattingRules
FrontPage
Help
InterWiki
InterWikiName
InterWikiSandBox
K
MenuBar
PHP
PukiWiki
PukiWiki/1.4
PukiWiki/1.4/Manual
PukiWiki/1.4/Manual/Plugin
PukiWiki/1.4/Manual/Plugin/A-D
PukiWiki/1.4/Manual/Plugin/E-G
PukiWiki/1.4/Manual/Plugin/H-K
PukiWiki/1.4/Manual/Plugin/L-N
PukiWiki/1.4/Manual/Plugin/O-R
PukiWiki/1.4/Manual/Plugin/S-U
PukiWiki/1.4/Manual/Plugin/V-Z
RecentDeleted
SDL2_01
SandBox
WikiEngines
WikiName
WikiWikiWeb
YukiWiki
a21
a21_acl01
a21_bbs01
a21_challengers
a21_count
a21_edu01
a21_edu02
a21_edu03
a21_edu04
a21_edu05
a21_edu06
a21_edu07
a21_edu08
a21_edu09
a21_edu10
a21_edu11
a21_hlx000
a21_hlx001
a21_hlx001_1
a21_hlx001_2
a21_hlx001_3
a21_hlx002
a21_hlx002_1
a21_hlx003
a21_hlx003_1
a21_hlx004_1
a21_memo01
a21_opt
a21_opt02
a21_opt03
a21_p01
a21_special
a21_tl9a
a21_todo
a21_txt01
a21_txt01_10
a21_txt01_1a
a21_txt01_2
a21_txt01_2a
a21_txt01_2b
a21_txt01_3
a21_txt01_4
a21_txt01_5
a21_txt01_6
a21_txt01_6a
a21_txt01_7
a21_txt01_8
a21_txt01_8a
a21_txt01_9
a21_txt01_9a
a21_txt02
a21_txt02_10
a21_txt02_10a
a21_txt02_10b
a21_txt02_11
a21_txt02_11a
a21_txt02_12
a21_txt02_12a
a21_txt02_12b
a21_txt02_1a
a21_txt02_1b
a21_txt02_2
a21_txt02_2a
a21_txt02_3
a21_txt02_3a
a21_txt02_4
a21_txt02_4a
a21_txt02_5
a21_txt02_5a
a21_txt02_6
a21_txt02_6a
a21_txt02_6b
a21_txt02_6b_rev0
a21_txt02_6x
a21_txt02_7
a21_txt02_7a
a21_txt02_8
a21_txt02_8a
a21_txt02_9
a21_txt02_9a
a22_acl2_01
a22_acl2_02
a22_edu12
a22_intro01
a22_intro02
a22_intro03
a22_memman01
a22_memman02
a22_memman03
a22_memman04
a22_memman05
a22_memman06
a22_memman07
a22_memo01
a22_mingw_debug
a22_txt03
a22_txt03_1a
a22_txt03_1b
a22_txt03_2
a22_txt03_2a
a22_ufcs01
a23_bbs
a23_ec001
a23_ec002
a23_intro00
a23_intro000
a23_intro01
a23_intro02
a23_intro03
a23_intro04
a23_intro05
a23_intro06
a23_intro07
a23_intro08
a23_intro09
a23_intro10
a23_intro10wk1
a23_intro10wk2
a23_intro10wk3
a23_intro11
a23_intro12
a23_intro13
a23_intro13wk1
a23_intro14
a23_intro15
a23_intro16
a23_intro90
a23_intro91
a23_neopixel1
a23_os01
a23_useSelfMade
a23_usm001
a23_usm002
a23_usm003
a23_usm004
a23_usm005
a23_usm006
a23_usm007
a23_usm008
a23_usm009
a24_memo01
a24_osc20240310
a24_osc20241026
a24_raspberrypi01
a24_useSelfMade
aclib00
aclib01
aclib02
aclib03
aclib04
aclib05
aclib06
aclib07
aclib08
aclib09
aclib10
aclib11
aclib12
aclib13
aclib14
aclib15
aclib16
aclib17
aclib18
aclib19
aclib20
aclib21
aclib22
aclib23
aclib24
aclib25
aclib_bbs
arm64_01
avm0001
edu0001
edu0002
edu0003
esb02b_hrb
esb_dbg
esbasic0001
esbasic0002
esbasic0003
esbasic0004
esbasic0005
esbasic0006
esbasic0007
esbasic0008
esbasic0009
esbasic0010
esbasic0011
esbasic0012
esbasic0013
esbasic0014
esbasic0015
esbasic0016
esbasic0017
esbasic02a
esc0001
escm0001
essen_hist
esvm0001
esvm0002
esvm0003
esvm0004
esvm0005
esvm0006
esvm_i0
hh4a
idea0001
idea0002
idea0003
impressions
jck_0000
jck_0001
kawai
kbcl0_0000
kbcl0_0001
kbcl0_0002
kbcl0_0003
kbcl0_0004
kbcl0_0005
kbcl0_0006
kbcl0_0007
kclib1_0000
kclib1_0001
kclib1_0002
kclib1_0003
kclib1_0004
kclib1_0005
kclib1_0006
kclib1_0007
kclib1_0008
kclib1_0009
kclib1_0010
kpap0001
members
memo0001
osask4g
osask4g_r2
p20200311a
p20200610a
p20200610b
p20200624a
p20200711a
p20200716a
page0001
page0002
page0003
page0004
page0005
page0006
page0007
page0008
page0009
page0010
page0011
page0012
page0013
page0014
page0015
page0016
page0017
page0018
page0019
page0020
page0021
page0022
page0023
populars
seccamp
seccamp2019
sechack
sechack2019
seclang01
sh3_2020
sh3_2020_kw
sh3_2020_nk
sh3_2021_kw
sh3_2021_nk
sh3_2022_kw
sh3_2023_kw
sh3_2024_kw
sh3_kw_hist
termux001
termux002
text0001
text0001a
text0002
text0002a
text0003
text0004
text0005
text0006
text0006a
text0007
text0008
text0010
text0011
text0012
text0013
text0014
text0015
text0016
text0017
text0018
text0019
text0020
text0021
tl1c
tl2c
tl3c
tl3d
* 川合のプログラミング言語自作のためのテキスト第三版#7 -(by [[K]], 2021.03.09) ** (1) HL-7 -まずC言語の演算子一覧を書きます。 |優先順位|演算子|形式|名前|結合方向|HL-7| |1|( )|func(x,y,z)|関数呼び出し演算子|左|×| |1|[ ]|a[i]|添え字演算子|左|×| |1|.|abc.x|ドット演算子|左|×| |1|->|p->x|アロー演算子|左|×| |1|++|i++|後置インクリメント演算子|左|〇| |1|--|j--|後置デクリメント演算子|左|×| |2|++|++i|前置インクリメント演算子|右|〇| |2|--|--j|前置デクリメント演算子|右|×| |2|sizeof|sizeof a|sizeof演算子|右|×| |2|&|&x|単項&演算子|右|×| |2|*|*p|単項*演算子|右|×| |2|+|+a|単項+演算子|右|×| |2|-|-b|単項-演算子|右|〇| |2|~|~i|補数演算子|右|×| |2|!|!j|論理否定演算子|右|×| |3|( )|(typ)obj|型キャスト演算子|右|×| |4|*|x * y|二項*演算子|左|〇| |4|/|x / y|除算演算子|左|〇| |4|%|x % y|剰余演算子|左|〇| |5|+|x + y|二項+演算子|左|〇| |5|-|x - y|二項-演算子|左|〇| |6|<< >>|i << j など|シフト演算子|左|△| |7|< <= > >=|x < y など|比較演算子|左|〇| |8|== !=|x == y など|比較演算子|左|〇| |9|&|i & j|ビットAND演算子|左|〇| |10|^|i ^ j|ビットXOR演算子|左|×| |11|||i | j|ビットOR演算子|左|×| |12|&&|i && j|論理AND演算子|左|×| |13||||i || j|論理OR演算子|左|×| |14|? :|x ? y : z|条件演算子|右|×| |15|=|x = y|単純代入演算子|右|〇| |15|+= -= など|x += y など|複合代入演算子|右|×| |16|,|x, y|コンマ演算子|左|×| -全部の演算子をサポートするとHL-7のプログラムが長くなってしまうので、この中の一部だけを実装することにします、残りは拡張したい人が拡張するということにします。 -この取り合わせだと「この演算子があって、あの演算子がないのはなぜだ!」みたいに思うかもしれませんが、それはこの先のHL-9aのサンプルアプリで必要になる演算子を入れるようにしたためです。だから深い理由はありません。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> typedef unsigned char *String; // こう書くと String は unsigned char * の代用になる. int loadText(String path, String t, int siz) → HL-4と同じなので省略 /////////////////////////////////////////////////////////////////////////////// #define MAX_TC 1000 // トークンコードの最大値. String ts[MAX_TC + 1]; // トークンの内容(文字列)を記憶. int tl[MAX_TC + 1]; // トークンの長さ. unsigned char tcBuf[(MAX_TC + 1) * 10]; // トークン1つ当たり平均10バイトを想定. int tcs = 0, tcb = 0; int var[MAX_TC + 1]; // 変数. int getTc(String s, int len) → HL-4と同じなので省略 /////////////////////////////////////////////////////////////////////////////// int isAlphabetOrNumber(unsigned char c) → HL-2と同じなので省略 int lexer(String s, int tc[]) → HL-2と同じなので省略 int tc[10000]; // トークンコード. enum { TcSemi = 0, TcDot, TcWiCard, Tc0, Tc1, Tc2, Tc3, Tc4, Tc5, Tc6, Tc7, Tc8, TcBrOpn, TcBrCls, TcSqBrOpn, TcSqBrCls, TcCrBrOpn, TcCrBrCls, TcEEq, TcNEq, TcLt, TcGe, TcLe, TcGt, TcPlus, TcMinus, TcAster, TcSlash, TcPerce, TcAnd, TcShr, TcPlPlus, TcEqu, TcComma, TcExpr, TcExpr0, TcTmp0, TcTmp1, TcTmp2, TcTmp3, TcTmp4, TcTmp5, TcTmp6, TcTmp7, TcTmp8, TcTmp9 }; char tcInit[] = "; . !!* 0 1 2 3 4 5 6 7 8 ( ) [ ] { } == != < >= <= > + - * / % & >> ++ = , !!** !!*** _t0 _t1 _t2 _t3 _t4 _t5 _t6 _t7 _t8 _t9"; /////////////////////////////////////////////////////////////////////////////// int phrCmp_tc[32 * 100], ppc1, wpc[9], wpc1[9]; // ppc1:一致したフレーズの次のトークンをさす, wpc[]:ワイルドカードのトークンの場所をさす. int phrCmp(int pid, String phr, int pc) // HL-5のとは違う(改造). { int i0 = pid * 32, i, i1, j, k, t; if (phrCmp_tc[i0 + 31] == 0) { i1 = lexer(phr, &phrCmp_tc[i0]); phrCmp_tc[i0 + 31] = i1; } i1 = phrCmp_tc[i0 + 31]; for (i = 0; i < i1; i++) { t = phrCmp_tc[i0 + i]; if (t == TcWiCard || t == TcExpr || t == TcExpr0) { i++; j = phrCmp_tc[i0 + i] - Tc0; // 後続の番号を取得. wpc[j] = pc; if (t == TcWiCard) { pc++; continue; } k = 0; // カッコの深さ. for (;;) { if (tc[pc] == TcSemi) break; if (tc[pc] == TcComma && k == 0) break; if (tc[pc] == TcBrOpn || tc[pc] == TcSqBrOpn) k++; // 手抜きで ( と [ を区別せずに数えている. if (tc[pc] == TcBrCls || tc[pc] == TcSqBrCls) k--; if (k < 0) break; pc++; } wpc1[j] = pc; // 式の終了位置を記憶. if (t == TcExpr && wpc[j] == pc) return 0; // "!!**"では、長さ0は不一致とする. if (k > 0) return 0; // カッコの深さがおかしい時も不一致とする. continue; } if (t != tc[pc]) return 0; // マッチせず. pc++; } ppc1 = pc; return 1; // マッチした. } /////////////////////////////////////////////////////////////////////////////// typedef int *IntP; // こう書くと IntP は int * の代わりに使えるようになる. enum { OpCpy = 0, OpCeq, OpCne, OpClt, OpCge, OpCle, OpCgt, OpAdd, OpSub, OpMul, OpDiv, OpMod, OpAnd, OpShr, OpAdd1, OpNeg, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpLop, OpPrint, OpTime, OpEnd }; IntP ic[10000], *icq; // ic[]:内部コード、icq:ic[]への書き込み用ポインタ. void putIc(int op, IntP p0, IntP p1, IntP p2, IntP p3) → HL-6と同じなので省略 /////////////////////////////////////////////////////////////////////////////// char tmp_flag[10]; // 一時変数の利用状況を管理. int tmpAlloc() // 未使用の一時変数を確保. { int i; for (i = 0; i < 10; i++) { if (tmp_flag[i] == 0) break; } if (i >= 10) { printf("tmpAlloc: error\n"); return -1; } tmp_flag[i] = 1; return i + TcTmp0; } void tmpFree(int i) // 一時変数を未使用に戻す. ただし、指定されたトークンコードが一時変数でないときは何もしない. { if (TcTmp0 <= i && i <= TcTmp9) { tmp_flag[i - TcTmp0] = 0; } } /////////////////////////////////////////////////////////////////////////////// int epc, epc1; // exprのためのpcとpc1. int exprSub(int priority); // exprSub1()が参照するので、プロトタイプ宣言. int expr(int j); int exprSub1(int i, int priority, int op) // 二項演算子の処理の標準形. { int j, k; epc++; j = exprSub(priority); k = tmpAlloc(); putIc(op, &var[k], &var[i], &var[j], 0); tmpFree(i); tmpFree(j); if (i < 0 || j < 0) return -1; return k; } int exprSub(int priority) { int i = -1, e0 = 0; // iはここまでの計算結果が入っている変数のトークンコード番号. ppc1 = 0; if (phrCmp(99, "( !!**0 )", epc)) { // かっこ. i = expr(0); } else if (tc[epc] == TcPlPlus) { // 前置インクリメント. epc++; i = exprSub(2); putIc(OpAdd1, &var[i], 0, 0, 0); } else if (tc[epc] == TcMinus) { // 単項マイナス. epc++; e0 = exprSub(2); i = tmpAlloc(); putIc(OpNeg, &var[i], &var[e0], 0, 0); } else { // 変数もしくは定数. i = tc[epc]; epc++; } if (ppc1 > 0) epc = ppc1; for (;;) { tmpFree(e0); if (i < 0 || e0 < 0) return -1; // ここまででエラーがあれば、処理を打ち切り. if (epc >= epc1) break; e0 = 0; if (tc[epc] == TcPlPlus) { // 後置インクリメント. epc++; e0 = i; i = tmpAlloc(); putIc(OpCpy, &var[i], &var[e0], 0, 0); putIc(OpAdd1, &var[e0], 0, 0, 0); } else if (TcAster <= tc[epc] && tc[epc] <= TcPerce && priority >= 4) { // * / % i = exprSub1(i, 3, tc[epc] - TcAster + OpMul); // 左結合なので4より1小さくする. } else if (TcPlus <= tc[epc] && tc[epc] <= TcMinus && priority >= 5) { i = exprSub1(i, 4, tc[epc] - TcPlus + OpAdd); // 左結合なので5より1小さくする. } else if (tc[epc] == TcShr && priority >= 6) { i = exprSub1(i, 5, OpShr); // 左結合なので6より1小さくする. } else if (TcLt <= tc[epc] && tc[epc] <= TcGt && priority >= 7) { i = exprSub1(i, 6, tc[epc] - TcLt + OpClt); // 左結合なので7より1小さくする. } else if (TcEEq <= tc[epc] && tc[epc] <= TcNEq && priority >= 8) { i = exprSub1(i, 7, tc[epc] - TcEEq + OpCeq); // 左結合なので8より1小さくする. } else if (tc[epc] == TcAnd && priority >= 9) { i = exprSub1(i, 8, OpAnd); // 左結合なので9より1小さくする. } else if (tc[epc] == TcEqu && priority >= 15) { epc++; e0 = exprSub(15); // 右結合なので15のまま. putIc(OpCpy, &var[i], &var[e0], 0, 0); } else break; } return i; } int expr(int j) { int i, k, old_epc = epc, old_epc1 = epc1, s[19]; // epc, epc1を保存する. if (wpc[j] == wpc1[j]) return 0; for (k = 0; k < 9; k++) { // wpc[], wpc1[]を保存する. s[k] = wpc [k]; s[k + 9] = wpc1[k]; } s[18] = ppc1; // ppc1を保存する. epc = wpc [j]; // epc, epc1を準備してexprSub()を呼び出す. epc1 = wpc1[j]; i = exprSub(99); if (epc < epc1) return -1; // 式を最後まで解釈できなかったらエラー. epc = old_epc; // 保存しておいた変数をすべて復元する. epc1 = old_epc1; for (k = 0; k < 9; k++) { wpc [k] = s[k]; wpc1[k] = s[k + 9]; } ppc1 = s[18]; return i; } /////////////////////////////////////////////////////////////////////////////// int compile(String s) { int pc, pc1, i; IntP *icq1; pc1 = lexer(s, tc); tc[pc1++] = TcSemi; // 末尾に「;」を付け忘れることが多いので、付けてあげる. tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = TcDot; // エラー表示用のために末尾にピリオドを登録しておく. icq = ic; for (i = 0; i < 10; i++) { ・// 一時変数をすべて未使用にする. tmp_flag[i] = 0; } for (pc = 0; pc < pc1; ) { // コンパイル開始. int e0 = 0; if (phrCmp( 1, "!!*0 = !!*1;", pc)) { // 単純代入. putIc(OpCpy, &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0); } else if (phrCmp(10, "!!*0 = !!*1 + 1; if (!!*2 < !!*3) goto !!*4;", pc) && tc[wpc[0]] == tc[wpc[1]] && tc[wpc[0]] == tc[wpc[2]]) { putIc(OpLop, &var[tc[wpc[4]]], &var[tc[wpc[0]]], &var[tc[wpc[3]]], 0); } else if (phrCmp( 9, "!!*0 = !!*1 + 1;", pc) && tc[wpc[0]] == tc[wpc[1]]) { // 高速化のために+1専用の命令を用意(せこくてすみません). putIc(OpAdd1, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算. putIc(OpAdd, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 3, "!!*0 = !!*1 - !!*2;", pc)) { // 減算. putIc(OpSub, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); ! } else if (phrCmp( 4, "print !!**0;", pc)) { // print. + e0 = expr(0); ! putIc(OpPrint, &var[e0], 0, 0, 0); } else if (phrCmp( 0, "!!*0:", pc)) { // ラベル定義命令. var[tc[wpc[0]]] = icq - ic; // ラベルに対応するicqを記録しておく. } else if (phrCmp( 5, "goto !!*0;", pc)) { // goto. putIc(OpGoto, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 6, "if (!!*0 !!*1 !!*2) goto !!*3;", pc) && TcEEq <= tc[wpc[1]] && tc[wpc[1]] <= TcLt) { putIc(OpJeq + (tc[wpc[1]] - TcEEq), &var[tc[wpc[3]]], &var[tc[wpc[0]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 7, "time;", pc)) { putIc(OpTime, 0, 0, 0, 0); ! } else if (phrCmp( 8, "!!***0;", pc)) { // これはかなりマッチしやすいので最後にする. ! e0 = expr(0); } else goto err; tmpFree(e0); if (e0 < 0) goto err; pc = ppc1; } putIc(OpEnd, 0, 0, 0, 0); icq1 = icq; for (icq = ic; icq < icq1; icq += 5) { // goto先の設定. i = (int) icq[0]; if (OpGoto <= i && i <= OpLop) { icq[1] = (IntP) (*icq[1] + ic); } } return icq1 - ic; err: printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[pc + 3]]); return -1; } void exec() { clock_t t0 = clock(); IntP *icp = ic; int i; for (;;) { switch ((int) icp[0]) { case OpNeg: *icp[1] = - *icp[2]; icp += 5; continue; case OpAdd1: (*icp[1])++; icp += 5; continue; case OpMul: *icp[1] = *icp[2] * *icp[3]; icp += 5; continue; case OpDiv: *icp[1] = *icp[2] / *icp[3]; icp += 5; continue; case OpMod: *icp[1] = *icp[2] % *icp[3]; icp += 5; continue; case OpAdd: *icp[1] = *icp[2] + *icp[3]; icp += 5; continue; case OpSub: *icp[1] = *icp[2] - *icp[3]; icp += 5; continue; case OpShr: *icp[1] = *icp[2] >> *icp[3]; icp += 5; continue; case OpClt: *icp[1] = *icp[2] < *icp[3]; icp += 5; continue; case OpCge: *icp[1] = *icp[2] >= *icp[3]; icp += 5; continue; case OpCle: *icp[1] = *icp[2] <= *icp[3]; icp += 5; continue; case OpCgt: *icp[1] = *icp[2] > *icp[3]; icp += 5; continue; case OpCeq: *icp[1] = *icp[2] == *icp[3]; icp += 5; continue; case OpCne: *icp[1] = *icp[2] != *icp[3]; icp += 5; continue; case OpAnd: *icp[1] = *icp[2] & *icp[3]; icp += 5; continue; case OpCpy: *icp[1] = *icp[2]; icp += 5; continue; case OpPrint: printf("%d\n", *icp[1]); icp += 5; continue; case OpGoto: icp = (IntP *) icp[1]; continue; case OpJeq: if (*icp[2] == *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJne: if (*icp[2] != *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJlt: if (*icp[2] < *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpTime: printf("time: %.3f[sec]\n", (clock() - t0) / (double) CLOCKS_PER_SEC); icp += 5; continue; case OpEnd: return; case OpLop: i = *icp[2]; i++; *icp[2] = i; if (i < *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; } } } int run(String s) → HL-6と同じなので省略 /////////////////////////////////////////////////////////////////////////////// int main(int argc, const char **argv) → HL-5と同じなので省略 -トータルの行数は445行になっています。かなり増えました。しかしかっこよさもかなり増しています。 ---- -まず、print命令で、単に変数や定数を指定するだけではなく、式が書けるようになりました。 >print 1+2*3 7 >print (1+2)*3 9 -こんなふうに、ちゃんと演算子の優先順位も反映されます。 -次に、連続代入ができるようになりました。「x = y = z = 0;」とかそういうやつです。 -インクリメントもできます。 >a = 0; print ++a; print a 1 1 >a = 0; print a++; print a 0 1 -この違いがわかるでしょうか。C言語では、前置インクリメントと後置インクリメントは意味が違うのです。それもきちんと真似できています。 -HL-6aまでは、なんかこう「おもちゃ言語」の感じがしていた気がするのですが、一気にまともになった気がします! ** (2) HL-7の簡単な説明 -関数: --void loadText(String path, String t, int siz) ---ファイルパスpathで指定されたソースファイルをtに読み込む。sizはtの最大サイズを表す(これを超える長さのファイルは途中で打ち切られる)。 --int getTc(String s, int len) ---トークン(単語)をsに渡すと、それに対応するトークンコード(整数)を返す。 --int isAlphabetOrNumber(unsigned char c) ---引数で渡された文字コードが、英数字であれば1を返す。それ以外なら0を返す。 ---アンダースコアもHL-6の中ではアルファベットということにしておく。そうすることで、変数の一文字目に使えるようになる。 ---この関数は以下のlexer()の下請け。 --int lexer(String s, int tc[]) ---sにプログラムのソースコードを渡す。すると、tc[]にトークンコード(単語番号)に変換させられた数列が入って返される。 ---より詳しい動作は、[[a21_txt01_2a]]を参照のこと。 --int phrCmp(int pid, String phr, int pc) ---tc[pc]からのトークンコード列がphrで指定されたトークン列と一致するかどうか調べる。 ---pidはフレーズIDで、この番号を使ってphrCmp_tc[]のどこにphrのlexer結果をしまっておくかを決めている。 ---なお、処理できるフレーズの最大長はこのプログラムの場合は31トークンである。 ---HL-7以降のphrCmpでは、以下の3種類のワイルドカードが使える。 ---[1] !!*# : 任意の1トークンにマッチする(#は0~8までの数字)(これはHL-5のバージョンでも使えた) ---[2] !!**# : 任意の式にマッチする(#は0~8までの数字)(ただし式は1トークン以上の長さでなければいけない) ---[3] !!***# : 任意の式にマッチする(#は0~8までの数字)(ただし式は長さゼロでもよい) --void putIc(int op, IntP p1, IntP p2, IntP p3, IntP p4) ---引数で渡された内容を内部コードのic[]に書き込む関数。関数compile()を書きやすくするための便利関数。 --int tmpAlloc() ---未使用の一時変数を確保。変数名のトークンコードで返す。 ---compile()の下請け関数。 --void tmpFree(int i) ---iが一時変数を指すトークンコードであれば、その一時変数を未使用状態に戻す。 ---そうでなければ、何もしない。 ---compile()の下請け関数。 --int exprSub1(int i, int priority, int op) ---二項演算子処理の標準形。exprSub()の下請け関数。 --int exprSub(int priority) ---式の解釈の処理の主要部分。expr()の下請け関数。 --int expr(int j) ---式の解釈処理のための便利関数。 ---exprSub()が動けるように、変数epc、epc1などを準備して、その上でexprSub()を呼び出す。 ---exprSub()の中でphrCmp()やexpr()を呼び出すこともあり得るので、wpc[]などの退避・復元処理も行う。 ---引数jは、ワイルドカード番号で、そのワイルドカードにマッチした式をコンパイルしてic[]に書き込む。 --int compile(String s) ---与えられた文字列をプログラムだと解釈して、内部コードを生成しic[]へ出力する。 ---関数run()の下請け関数。 --void exec() ---ic[]に格納された内部コードを高速に実行する。 ---関数run()の下請け関数。 --int run(String s) ---言語処理の本体。HL-3までのmain()に相当。 ---内部的にはcompile()してrun()しているだけ。 --int main(int argc, const char **argv) ---REPLの処理をしている。 -変数: --String ts[] ---getTc()が管理している配列変数で、トークンコードからトークン文字列を得るために使う。 --int tl[] ---getTc()が管理している配列変数で、トークンコードからトークン文字列の長さを得るために使う。 --unsigned char tcBuf[] ---getTc()が管理している変数で、トークン文字列の実体を保存しておくための場所。 --int tcs, tcb ---どちらもgetTc()が管理している変数で、tcsは今までに発行したトークンコードの個数(0~tcs-1が発行済み)。 ---tcbはtcBuf[]の未使用領域を指している。 ---もしtcBuf[]やtcbの役割がピンとこない場合は、[[a21_txt01_2b]]を参照。 --int var[] ---変数の値を記憶しておくための変数。トークンコードをそのまま変数番号に転用している。 --int tc[] ---プログラムをトークンコード列に変換したものがここに入る。 --int phrCmp_tc[] ---phrCmp()が管理している変数で、phrCmp_tc[]にはフレーズのlexer()の結果を保存する。 --int ppc1, wpc[], wpc1[] ---フレーズが一致した場合、ppc1に一致したフレーズの次のトークンの位置が入る。 ---wpc[]にはワイルドカードで一致した位置が入る。 ---ワイルドカードが式の場合、wpc1[]には式の終端が入る(厳密には式の直後のトークンを指す) --IntP ic[], *icq ---ic[]は内部コード(internal-code)を格納しておくための変数。icqはputIc()関数が次にicのどこに書き込むのかを覚えておくための変数。 --int epc, epc1 ---exprのためのpc, pc1に相当。 ---- -HL-7の見どころは何といっても式の評価です。しかもそれをスタックの仕組みを一切使わず、それでいて難解にもならずに仕上げられたところが、私としては気に入っています。だからそこを中心に説明したいと思います。 ** (3) 式の評価について (exprSub(), exprSub1(), tmpAlloc(), tmpFree()) -ここでの式の評価というのは、つまり print a + b - c * d + e -みたいなプログラムをコンパイルした時に OpAdd(_t0, a, b ); // _t0 = a + b OpMul(_t1, c, d ); // _t1 = c * d OpSub(_t2, _t0, _t1); // _t2 = _t0 - _t1 OpAdd(_t0, _t2, e ); // _t0 = _t2 + e OpPrint(_t0); -みたいな内部コード列に変換することです。基本的には式を左から右へ評価しつつも(足し算・引き算)、途中で高い優先度を持つ演算子(掛け算)が来たときは、先にそれを計算して、その結果を一つのかたまりとして加減算を再開します。 -これが難なくできるようになることがゴールです。このことだけに集中すれば、式の評価なんて大したことはありません。 ---- -exprSub()という関数が、この式の評価の大半を処理しています。 -それではここで、exprSub(99)した場合を考えてみましょう。 -exprSub()では、変数epcを使って式を解釈していきます。 -関数に入ると、まずはepcの場所にカッコや前置演算子が来ていないかどうかを確認します。もしそれらがあれば、対応する処理をしなければいけません。でもいきなり最初からかっこや前置演算子の話をするとややこしくなるだけなので、今はそれらは全くない場合だけを考えます。 -そうすると処理は } else { // 変数もしくは定数. i = tc[epc]; epc++; } -ここに来ます。これで、iに変数もしくは定数のトークンコード番号が入ります。 -もし「print a;」のように、後続の演算子がなければ、このiの値(=aのトークンコード)がそのままreturnされます。何も難しいことはありません。 -さてもしこの後に演算子が来るとどうでしょうか。たとえば二項演算子の「+」がある場合を考えましょう。その場合、ここに来ることになります。 } else if (TcPlus <= tc[epc] && tc[epc] <= TcMinus && priority >= 5) { i = exprSub1(i, 4, tc[epc] - TcPlus + OpAdd); // 左結合なので5より1小さくする. -このif文の意味するところは、epcの場所に書いてあるトークンが「+」もしくは「-」で、かつexprSub()を呼ばれたときの引数が5よりも大きかったら、ということです。今は99で呼んでいるわけですから、ここは問題なく成立します。あとでこの条件の必要性も説明しますので、今は気にしないでください。 -このif文が成立するとどうなるのかというと、exprSub1()を使って二項演算子の処理をするのですが、それではその部分を説明のために上記の引数で展開してみます。 epc++; j = exprSub(4); k = tmpAlloc(); putIc(op, &var[k], &var[i], &var[j], 0); tmpFree(i); tmpFree(j); i = k; -やっていることは、まずepc++して、「+」を読み進めます。 -次に、exprSub(4)を呼び出して、その結果をjで受けます。これはつまり、演算子の後ろにある項を1つ取ってこいという意味です。そしてその際には、優先度が4以下の優先度の高い演算ついてはどんどん結合して演算して結果を出してから帰ってこい、と、そういうことなのです。しかし優先度5以上の優先度の低いものは勝手に計算してまとめてはいけません。ちなみに優先度5というのは「+」や「-」のことです。 -こうすることで、掛け算とか割り算を含む項が後続していれば、それについては演算した結果を渡してもらえることになります。そうでなければ、単に次のトークンコードが返ってくることになります。 -その次に tmpAlloc() を実行して、それをkに入れます。これはつまり、_t0みたいな変数をひとつ持ってくるだけです。とにかく加算結果をどこかの変数に入れなければいけないので、適当な一時変数を準備しているのです。 -次のputIc()で内部コードを生成しています。opの部分は、「+」だったらOpAdd、「-」だったらOpSubになります。今の例では加算命令を出力することになります。 -次の2つのtmpFree()で、もしiやjが一時変数であったら、未使用状態に戻します。なぜならもう演算のために使ったので、今後参照されることはないからです。もしtmpFree()の引数が一時変数でなければ特に何もしません。そういう仕様です(そうすることでif文を書く手間を減らしました)。 -そして最後に、iにkを代入します。これは、「ここまでの計算結果が入っている変数のトークンコード」はiにしておくのがこのループの前提で、そして今、加算結果が入っている変数はkになっているので、iを更新してから先に進むわけです。 -以降はこの処理を、式の終わりまでやるか、もしくは指定された優先順位より大きい演算子(=優先度の低い演算子)にぶつかるかするまで繰り返せば、私たちの欲しいものは得られるのです。 ** (4) 左結合と右結合について -C言語のほとんどの演算子は左結合ですが、一部右結合のものがあります。まずは結合の違いを説明します。 -「a + b - c」という式は、+も-も左結合の演算子なので、一番最初に実行されるのは、「_t0 = a + b」です。そしてその次に「_t1 = _t0 - c」が実行されます。優先度が同じものがあった場合、左を先に演算するという、ただそれだけのことです。これは当たり前に感じられるでしょう。 -意外なのは右結合の演算子です。「a = b = 3」の場合、=は右結合の演算子なので、最初に実行されるのは「a = b」ではありません。「b = 3」なのです。そのあとに「a = b」が実行されます。 -でもこれは、そうでなければ困るというのがわかるでしょうか。「a = b = 3」と書いた時は、aもbも3になることが期待されているのです。もし左結合だったら、bしか3にならず、aはbの古い値が入っているだけになってしまうのです。 -exprSub()でこの右結合を実現するにはどうすればいいでしょうか。それは、優先度15の=の処理の時に、exprSub(14)ではなくexprSub(15)をすることなのです。そうすれば、後続の項の中に=が含まれていれば、それを全部putIc()で出力してから帰ってくるからです。 -結局、左結合か右結合かは、exprSub()の再起呼び出しの際に、優先度を1引くか、そのままにするか、それだけの違いになります。 ** (5) その他のこまごまとした説明 (expr(), phrCmp(), comiple(), exec()) -関数expr()は、exprSub()を利用する際に必要な準備をして、exprSubを引数99で呼び出し、さらに呼び出し後の後片付けをしてくれる便利関数です。 --expr()の引数では、wpc[]の番号を指定します。この仕様にしておくと、compile()内で呼び出すのがすごく楽になるのでそうしました。 --そしてexpr()の処理中にphrCmp()やexpr()を利用するかもしれないことを考えて、epc値やepc[]値を保存しておき、それからepc, epc1に式の範囲をセットして、exprSub(99)を実行しています。 --その後は、保存した値をすべて復元して、終了しています。 -phrCmp()もHL-6aまでの内容に対してバージョンアップしています。 --主な変更点は、任意の式にマッチする !!** や !!*** というワイルドカードを追加したことです。 --ただし、phrCmp()での式の判定はすごく雑で、「a + b」や「-3*a」みたいな正しい式にマッチする一方「+ +」とか「a b c」など、意味不明なトークンの並びでも通してしまいます。これは何をもって式とするのかは、将来的に考えが変わるかもしれないので、とにかくルーズにしておこうと思ったのです(それに判定をまじめにやるとプログラムが長くて複雑になる)。現状では、カッコの対応関係を雑にみている程度です。まあそれでも、対象が正しいプログラムであれば、これで問題なくマッチができています。 --ただそれだけであまりにも心配だと思ったので、expr()内で、式がちゃんと最後まで評価できているかをチェックするようにはしています。変な式だと評価が途中で終わるので、その場合はエラーにしています。 -compile()では、print命令と最後の任意の式のところだけに「!!**」や「!!***」を使いました。いきなりたくさん導入しても混乱すると思ったからです。 -最後に任意の式の評価があるのだから、もう「!!*0 = !!*1 + !!*2;」とか「!!*0 = !!*1 - !!*2;」とかはいらないと思うかもしれません。でもこれはわざと残しました(まあ消すのが面倒だったということもありますが)。 --なぜなら、もしこれらの記述をなくしてしまうと、単純な「a = b + c;」が OpAdd(_t0, b, c); OpCpy(a, _t0); --という2命令に変換されてしまうからです。今はこういう余計な代入を減らすような最適化が入っていないので、これを避けることはできません。だからとりあえず残したのです。残しておけば、 OpAdd(a, b, c); --という1命令に変換されます。だからHL-6aに対しての速度低下はありません。 -exec()では、追加された演算に対する演算命令をたくさん追加しました。でも難しいところは特にないはずです。 ** 次回に続く -次回: [[a21_txt01_8]] --次回は ブロックif文やfor文をやります。 *こめんと欄 #comment
タイムスタンプを変更しない
* 川合のプログラミング言語自作のためのテキスト第三版#7 -(by [[K]], 2021.03.09) ** (1) HL-7 -まずC言語の演算子一覧を書きます。 |優先順位|演算子|形式|名前|結合方向|HL-7| |1|( )|func(x,y,z)|関数呼び出し演算子|左|×| |1|[ ]|a[i]|添え字演算子|左|×| |1|.|abc.x|ドット演算子|左|×| |1|->|p->x|アロー演算子|左|×| |1|++|i++|後置インクリメント演算子|左|〇| |1|--|j--|後置デクリメント演算子|左|×| |2|++|++i|前置インクリメント演算子|右|〇| |2|--|--j|前置デクリメント演算子|右|×| |2|sizeof|sizeof a|sizeof演算子|右|×| |2|&|&x|単項&演算子|右|×| |2|*|*p|単項*演算子|右|×| |2|+|+a|単項+演算子|右|×| |2|-|-b|単項-演算子|右|〇| |2|~|~i|補数演算子|右|×| |2|!|!j|論理否定演算子|右|×| |3|( )|(typ)obj|型キャスト演算子|右|×| |4|*|x * y|二項*演算子|左|〇| |4|/|x / y|除算演算子|左|〇| |4|%|x % y|剰余演算子|左|〇| |5|+|x + y|二項+演算子|左|〇| |5|-|x - y|二項-演算子|左|〇| |6|<< >>|i << j など|シフト演算子|左|△| |7|< <= > >=|x < y など|比較演算子|左|〇| |8|== !=|x == y など|比較演算子|左|〇| |9|&|i & j|ビットAND演算子|左|〇| |10|^|i ^ j|ビットXOR演算子|左|×| |11|||i | j|ビットOR演算子|左|×| |12|&&|i && j|論理AND演算子|左|×| |13||||i || j|論理OR演算子|左|×| |14|? :|x ? y : z|条件演算子|右|×| |15|=|x = y|単純代入演算子|右|〇| |15|+= -= など|x += y など|複合代入演算子|右|×| |16|,|x, y|コンマ演算子|左|×| -全部の演算子をサポートするとHL-7のプログラムが長くなってしまうので、この中の一部だけを実装することにします、残りは拡張したい人が拡張するということにします。 -この取り合わせだと「この演算子があって、あの演算子がないのはなぜだ!」みたいに思うかもしれませんが、それはこの先のHL-9aのサンプルアプリで必要になる演算子を入れるようにしたためです。だから深い理由はありません。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> typedef unsigned char *String; // こう書くと String は unsigned char * の代用になる. int loadText(String path, String t, int siz) → HL-4と同じなので省略 /////////////////////////////////////////////////////////////////////////////// #define MAX_TC 1000 // トークンコードの最大値. String ts[MAX_TC + 1]; // トークンの内容(文字列)を記憶. int tl[MAX_TC + 1]; // トークンの長さ. unsigned char tcBuf[(MAX_TC + 1) * 10]; // トークン1つ当たり平均10バイトを想定. int tcs = 0, tcb = 0; int var[MAX_TC + 1]; // 変数. int getTc(String s, int len) → HL-4と同じなので省略 /////////////////////////////////////////////////////////////////////////////// int isAlphabetOrNumber(unsigned char c) → HL-2と同じなので省略 int lexer(String s, int tc[]) → HL-2と同じなので省略 int tc[10000]; // トークンコード. enum { TcSemi = 0, TcDot, TcWiCard, Tc0, Tc1, Tc2, Tc3, Tc4, Tc5, Tc6, Tc7, Tc8, TcBrOpn, TcBrCls, TcSqBrOpn, TcSqBrCls, TcCrBrOpn, TcCrBrCls, TcEEq, TcNEq, TcLt, TcGe, TcLe, TcGt, TcPlus, TcMinus, TcAster, TcSlash, TcPerce, TcAnd, TcShr, TcPlPlus, TcEqu, TcComma, TcExpr, TcExpr0, TcTmp0, TcTmp1, TcTmp2, TcTmp3, TcTmp4, TcTmp5, TcTmp6, TcTmp7, TcTmp8, TcTmp9 }; char tcInit[] = "; . !!* 0 1 2 3 4 5 6 7 8 ( ) [ ] { } == != < >= <= > + - * / % & >> ++ = , !!** !!*** _t0 _t1 _t2 _t3 _t4 _t5 _t6 _t7 _t8 _t9"; /////////////////////////////////////////////////////////////////////////////// int phrCmp_tc[32 * 100], ppc1, wpc[9], wpc1[9]; // ppc1:一致したフレーズの次のトークンをさす, wpc[]:ワイルドカードのトークンの場所をさす. int phrCmp(int pid, String phr, int pc) // HL-5のとは違う(改造). { int i0 = pid * 32, i, i1, j, k, t; if (phrCmp_tc[i0 + 31] == 0) { i1 = lexer(phr, &phrCmp_tc[i0]); phrCmp_tc[i0 + 31] = i1; } i1 = phrCmp_tc[i0 + 31]; for (i = 0; i < i1; i++) { t = phrCmp_tc[i0 + i]; if (t == TcWiCard || t == TcExpr || t == TcExpr0) { i++; j = phrCmp_tc[i0 + i] - Tc0; // 後続の番号を取得. wpc[j] = pc; if (t == TcWiCard) { pc++; continue; } k = 0; // カッコの深さ. for (;;) { if (tc[pc] == TcSemi) break; if (tc[pc] == TcComma && k == 0) break; if (tc[pc] == TcBrOpn || tc[pc] == TcSqBrOpn) k++; // 手抜きで ( と [ を区別せずに数えている. if (tc[pc] == TcBrCls || tc[pc] == TcSqBrCls) k--; if (k < 0) break; pc++; } wpc1[j] = pc; // 式の終了位置を記憶. if (t == TcExpr && wpc[j] == pc) return 0; // "!!**"では、長さ0は不一致とする. if (k > 0) return 0; // カッコの深さがおかしい時も不一致とする. continue; } if (t != tc[pc]) return 0; // マッチせず. pc++; } ppc1 = pc; return 1; // マッチした. } /////////////////////////////////////////////////////////////////////////////// typedef int *IntP; // こう書くと IntP は int * の代わりに使えるようになる. enum { OpCpy = 0, OpCeq, OpCne, OpClt, OpCge, OpCle, OpCgt, OpAdd, OpSub, OpMul, OpDiv, OpMod, OpAnd, OpShr, OpAdd1, OpNeg, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpLop, OpPrint, OpTime, OpEnd }; IntP ic[10000], *icq; // ic[]:内部コード、icq:ic[]への書き込み用ポインタ. void putIc(int op, IntP p0, IntP p1, IntP p2, IntP p3) → HL-6と同じなので省略 /////////////////////////////////////////////////////////////////////////////// char tmp_flag[10]; // 一時変数の利用状況を管理. int tmpAlloc() // 未使用の一時変数を確保. { int i; for (i = 0; i < 10; i++) { if (tmp_flag[i] == 0) break; } if (i >= 10) { printf("tmpAlloc: error\n"); return -1; } tmp_flag[i] = 1; return i + TcTmp0; } void tmpFree(int i) // 一時変数を未使用に戻す. ただし、指定されたトークンコードが一時変数でないときは何もしない. { if (TcTmp0 <= i && i <= TcTmp9) { tmp_flag[i - TcTmp0] = 0; } } /////////////////////////////////////////////////////////////////////////////// int epc, epc1; // exprのためのpcとpc1. int exprSub(int priority); // exprSub1()が参照するので、プロトタイプ宣言. int expr(int j); int exprSub1(int i, int priority, int op) // 二項演算子の処理の標準形. { int j, k; epc++; j = exprSub(priority); k = tmpAlloc(); putIc(op, &var[k], &var[i], &var[j], 0); tmpFree(i); tmpFree(j); if (i < 0 || j < 0) return -1; return k; } int exprSub(int priority) { int i = -1, e0 = 0; // iはここまでの計算結果が入っている変数のトークンコード番号. ppc1 = 0; if (phrCmp(99, "( !!**0 )", epc)) { // かっこ. i = expr(0); } else if (tc[epc] == TcPlPlus) { // 前置インクリメント. epc++; i = exprSub(2); putIc(OpAdd1, &var[i], 0, 0, 0); } else if (tc[epc] == TcMinus) { // 単項マイナス. epc++; e0 = exprSub(2); i = tmpAlloc(); putIc(OpNeg, &var[i], &var[e0], 0, 0); } else { // 変数もしくは定数. i = tc[epc]; epc++; } if (ppc1 > 0) epc = ppc1; for (;;) { tmpFree(e0); if (i < 0 || e0 < 0) return -1; // ここまででエラーがあれば、処理を打ち切り. if (epc >= epc1) break; e0 = 0; if (tc[epc] == TcPlPlus) { // 後置インクリメント. epc++; e0 = i; i = tmpAlloc(); putIc(OpCpy, &var[i], &var[e0], 0, 0); putIc(OpAdd1, &var[e0], 0, 0, 0); } else if (TcAster <= tc[epc] && tc[epc] <= TcPerce && priority >= 4) { // * / % i = exprSub1(i, 3, tc[epc] - TcAster + OpMul); // 左結合なので4より1小さくする. } else if (TcPlus <= tc[epc] && tc[epc] <= TcMinus && priority >= 5) { i = exprSub1(i, 4, tc[epc] - TcPlus + OpAdd); // 左結合なので5より1小さくする. } else if (tc[epc] == TcShr && priority >= 6) { i = exprSub1(i, 5, OpShr); // 左結合なので6より1小さくする. } else if (TcLt <= tc[epc] && tc[epc] <= TcGt && priority >= 7) { i = exprSub1(i, 6, tc[epc] - TcLt + OpClt); // 左結合なので7より1小さくする. } else if (TcEEq <= tc[epc] && tc[epc] <= TcNEq && priority >= 8) { i = exprSub1(i, 7, tc[epc] - TcEEq + OpCeq); // 左結合なので8より1小さくする. } else if (tc[epc] == TcAnd && priority >= 9) { i = exprSub1(i, 8, OpAnd); // 左結合なので9より1小さくする. } else if (tc[epc] == TcEqu && priority >= 15) { epc++; e0 = exprSub(15); // 右結合なので15のまま. putIc(OpCpy, &var[i], &var[e0], 0, 0); } else break; } return i; } int expr(int j) { int i, k, old_epc = epc, old_epc1 = epc1, s[19]; // epc, epc1を保存する. if (wpc[j] == wpc1[j]) return 0; for (k = 0; k < 9; k++) { // wpc[], wpc1[]を保存する. s[k] = wpc [k]; s[k + 9] = wpc1[k]; } s[18] = ppc1; // ppc1を保存する. epc = wpc [j]; // epc, epc1を準備してexprSub()を呼び出す. epc1 = wpc1[j]; i = exprSub(99); if (epc < epc1) return -1; // 式を最後まで解釈できなかったらエラー. epc = old_epc; // 保存しておいた変数をすべて復元する. epc1 = old_epc1; for (k = 0; k < 9; k++) { wpc [k] = s[k]; wpc1[k] = s[k + 9]; } ppc1 = s[18]; return i; } /////////////////////////////////////////////////////////////////////////////// int compile(String s) { int pc, pc1, i; IntP *icq1; pc1 = lexer(s, tc); tc[pc1++] = TcSemi; // 末尾に「;」を付け忘れることが多いので、付けてあげる. tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = TcDot; // エラー表示用のために末尾にピリオドを登録しておく. icq = ic; for (i = 0; i < 10; i++) { ・// 一時変数をすべて未使用にする. tmp_flag[i] = 0; } for (pc = 0; pc < pc1; ) { // コンパイル開始. int e0 = 0; if (phrCmp( 1, "!!*0 = !!*1;", pc)) { // 単純代入. putIc(OpCpy, &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0); } else if (phrCmp(10, "!!*0 = !!*1 + 1; if (!!*2 < !!*3) goto !!*4;", pc) && tc[wpc[0]] == tc[wpc[1]] && tc[wpc[0]] == tc[wpc[2]]) { putIc(OpLop, &var[tc[wpc[4]]], &var[tc[wpc[0]]], &var[tc[wpc[3]]], 0); } else if (phrCmp( 9, "!!*0 = !!*1 + 1;", pc) && tc[wpc[0]] == tc[wpc[1]]) { // 高速化のために+1専用の命令を用意(せこくてすみません). putIc(OpAdd1, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算. putIc(OpAdd, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 3, "!!*0 = !!*1 - !!*2;", pc)) { // 減算. putIc(OpSub, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); ! } else if (phrCmp( 4, "print !!**0;", pc)) { // print. + e0 = expr(0); ! putIc(OpPrint, &var[e0], 0, 0, 0); } else if (phrCmp( 0, "!!*0:", pc)) { // ラベル定義命令. var[tc[wpc[0]]] = icq - ic; // ラベルに対応するicqを記録しておく. } else if (phrCmp( 5, "goto !!*0;", pc)) { // goto. putIc(OpGoto, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 6, "if (!!*0 !!*1 !!*2) goto !!*3;", pc) && TcEEq <= tc[wpc[1]] && tc[wpc[1]] <= TcLt) { putIc(OpJeq + (tc[wpc[1]] - TcEEq), &var[tc[wpc[3]]], &var[tc[wpc[0]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 7, "time;", pc)) { putIc(OpTime, 0, 0, 0, 0); ! } else if (phrCmp( 8, "!!***0;", pc)) { // これはかなりマッチしやすいので最後にする. ! e0 = expr(0); } else goto err; tmpFree(e0); if (e0 < 0) goto err; pc = ppc1; } putIc(OpEnd, 0, 0, 0, 0); icq1 = icq; for (icq = ic; icq < icq1; icq += 5) { // goto先の設定. i = (int) icq[0]; if (OpGoto <= i && i <= OpLop) { icq[1] = (IntP) (*icq[1] + ic); } } return icq1 - ic; err: printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[pc + 3]]); return -1; } void exec() { clock_t t0 = clock(); IntP *icp = ic; int i; for (;;) { switch ((int) icp[0]) { case OpNeg: *icp[1] = - *icp[2]; icp += 5; continue; case OpAdd1: (*icp[1])++; icp += 5; continue; case OpMul: *icp[1] = *icp[2] * *icp[3]; icp += 5; continue; case OpDiv: *icp[1] = *icp[2] / *icp[3]; icp += 5; continue; case OpMod: *icp[1] = *icp[2] % *icp[3]; icp += 5; continue; case OpAdd: *icp[1] = *icp[2] + *icp[3]; icp += 5; continue; case OpSub: *icp[1] = *icp[2] - *icp[3]; icp += 5; continue; case OpShr: *icp[1] = *icp[2] >> *icp[3]; icp += 5; continue; case OpClt: *icp[1] = *icp[2] < *icp[3]; icp += 5; continue; case OpCge: *icp[1] = *icp[2] >= *icp[3]; icp += 5; continue; case OpCle: *icp[1] = *icp[2] <= *icp[3]; icp += 5; continue; case OpCgt: *icp[1] = *icp[2] > *icp[3]; icp += 5; continue; case OpCeq: *icp[1] = *icp[2] == *icp[3]; icp += 5; continue; case OpCne: *icp[1] = *icp[2] != *icp[3]; icp += 5; continue; case OpAnd: *icp[1] = *icp[2] & *icp[3]; icp += 5; continue; case OpCpy: *icp[1] = *icp[2]; icp += 5; continue; case OpPrint: printf("%d\n", *icp[1]); icp += 5; continue; case OpGoto: icp = (IntP *) icp[1]; continue; case OpJeq: if (*icp[2] == *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJne: if (*icp[2] != *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJlt: if (*icp[2] < *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpTime: printf("time: %.3f[sec]\n", (clock() - t0) / (double) CLOCKS_PER_SEC); icp += 5; continue; case OpEnd: return; case OpLop: i = *icp[2]; i++; *icp[2] = i; if (i < *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; } } } int run(String s) → HL-6と同じなので省略 /////////////////////////////////////////////////////////////////////////////// int main(int argc, const char **argv) → HL-5と同じなので省略 -トータルの行数は445行になっています。かなり増えました。しかしかっこよさもかなり増しています。 ---- -まず、print命令で、単に変数や定数を指定するだけではなく、式が書けるようになりました。 >print 1+2*3 7 >print (1+2)*3 9 -こんなふうに、ちゃんと演算子の優先順位も反映されます。 -次に、連続代入ができるようになりました。「x = y = z = 0;」とかそういうやつです。 -インクリメントもできます。 >a = 0; print ++a; print a 1 1 >a = 0; print a++; print a 0 1 -この違いがわかるでしょうか。C言語では、前置インクリメントと後置インクリメントは意味が違うのです。それもきちんと真似できています。 -HL-6aまでは、なんかこう「おもちゃ言語」の感じがしていた気がするのですが、一気にまともになった気がします! ** (2) HL-7の簡単な説明 -関数: --void loadText(String path, String t, int siz) ---ファイルパスpathで指定されたソースファイルをtに読み込む。sizはtの最大サイズを表す(これを超える長さのファイルは途中で打ち切られる)。 --int getTc(String s, int len) ---トークン(単語)をsに渡すと、それに対応するトークンコード(整数)を返す。 --int isAlphabetOrNumber(unsigned char c) ---引数で渡された文字コードが、英数字であれば1を返す。それ以外なら0を返す。 ---アンダースコアもHL-6の中ではアルファベットということにしておく。そうすることで、変数の一文字目に使えるようになる。 ---この関数は以下のlexer()の下請け。 --int lexer(String s, int tc[]) ---sにプログラムのソースコードを渡す。すると、tc[]にトークンコード(単語番号)に変換させられた数列が入って返される。 ---より詳しい動作は、[[a21_txt01_2a]]を参照のこと。 --int phrCmp(int pid, String phr, int pc) ---tc[pc]からのトークンコード列がphrで指定されたトークン列と一致するかどうか調べる。 ---pidはフレーズIDで、この番号を使ってphrCmp_tc[]のどこにphrのlexer結果をしまっておくかを決めている。 ---なお、処理できるフレーズの最大長はこのプログラムの場合は31トークンである。 ---HL-7以降のphrCmpでは、以下の3種類のワイルドカードが使える。 ---[1] !!*# : 任意の1トークンにマッチする(#は0~8までの数字)(これはHL-5のバージョンでも使えた) ---[2] !!**# : 任意の式にマッチする(#は0~8までの数字)(ただし式は1トークン以上の長さでなければいけない) ---[3] !!***# : 任意の式にマッチする(#は0~8までの数字)(ただし式は長さゼロでもよい) --void putIc(int op, IntP p1, IntP p2, IntP p3, IntP p4) ---引数で渡された内容を内部コードのic[]に書き込む関数。関数compile()を書きやすくするための便利関数。 --int tmpAlloc() ---未使用の一時変数を確保。変数名のトークンコードで返す。 ---compile()の下請け関数。 --void tmpFree(int i) ---iが一時変数を指すトークンコードであれば、その一時変数を未使用状態に戻す。 ---そうでなければ、何もしない。 ---compile()の下請け関数。 --int exprSub1(int i, int priority, int op) ---二項演算子処理の標準形。exprSub()の下請け関数。 --int exprSub(int priority) ---式の解釈の処理の主要部分。expr()の下請け関数。 --int expr(int j) ---式の解釈処理のための便利関数。 ---exprSub()が動けるように、変数epc、epc1などを準備して、その上でexprSub()を呼び出す。 ---exprSub()の中でphrCmp()やexpr()を呼び出すこともあり得るので、wpc[]などの退避・復元処理も行う。 ---引数jは、ワイルドカード番号で、そのワイルドカードにマッチした式をコンパイルしてic[]に書き込む。 --int compile(String s) ---与えられた文字列をプログラムだと解釈して、内部コードを生成しic[]へ出力する。 ---関数run()の下請け関数。 --void exec() ---ic[]に格納された内部コードを高速に実行する。 ---関数run()の下請け関数。 --int run(String s) ---言語処理の本体。HL-3までのmain()に相当。 ---内部的にはcompile()してrun()しているだけ。 --int main(int argc, const char **argv) ---REPLの処理をしている。 -変数: --String ts[] ---getTc()が管理している配列変数で、トークンコードからトークン文字列を得るために使う。 --int tl[] ---getTc()が管理している配列変数で、トークンコードからトークン文字列の長さを得るために使う。 --unsigned char tcBuf[] ---getTc()が管理している変数で、トークン文字列の実体を保存しておくための場所。 --int tcs, tcb ---どちらもgetTc()が管理している変数で、tcsは今までに発行したトークンコードの個数(0~tcs-1が発行済み)。 ---tcbはtcBuf[]の未使用領域を指している。 ---もしtcBuf[]やtcbの役割がピンとこない場合は、[[a21_txt01_2b]]を参照。 --int var[] ---変数の値を記憶しておくための変数。トークンコードをそのまま変数番号に転用している。 --int tc[] ---プログラムをトークンコード列に変換したものがここに入る。 --int phrCmp_tc[] ---phrCmp()が管理している変数で、phrCmp_tc[]にはフレーズのlexer()の結果を保存する。 --int ppc1, wpc[], wpc1[] ---フレーズが一致した場合、ppc1に一致したフレーズの次のトークンの位置が入る。 ---wpc[]にはワイルドカードで一致した位置が入る。 ---ワイルドカードが式の場合、wpc1[]には式の終端が入る(厳密には式の直後のトークンを指す) --IntP ic[], *icq ---ic[]は内部コード(internal-code)を格納しておくための変数。icqはputIc()関数が次にicのどこに書き込むのかを覚えておくための変数。 --int epc, epc1 ---exprのためのpc, pc1に相当。 ---- -HL-7の見どころは何といっても式の評価です。しかもそれをスタックの仕組みを一切使わず、それでいて難解にもならずに仕上げられたところが、私としては気に入っています。だからそこを中心に説明したいと思います。 ** (3) 式の評価について (exprSub(), exprSub1(), tmpAlloc(), tmpFree()) -ここでの式の評価というのは、つまり print a + b - c * d + e -みたいなプログラムをコンパイルした時に OpAdd(_t0, a, b ); // _t0 = a + b OpMul(_t1, c, d ); // _t1 = c * d OpSub(_t2, _t0, _t1); // _t2 = _t0 - _t1 OpAdd(_t0, _t2, e ); // _t0 = _t2 + e OpPrint(_t0); -みたいな内部コード列に変換することです。基本的には式を左から右へ評価しつつも(足し算・引き算)、途中で高い優先度を持つ演算子(掛け算)が来たときは、先にそれを計算して、その結果を一つのかたまりとして加減算を再開します。 -これが難なくできるようになることがゴールです。このことだけに集中すれば、式の評価なんて大したことはありません。 ---- -exprSub()という関数が、この式の評価の大半を処理しています。 -それではここで、exprSub(99)した場合を考えてみましょう。 -exprSub()では、変数epcを使って式を解釈していきます。 -関数に入ると、まずはepcの場所にカッコや前置演算子が来ていないかどうかを確認します。もしそれらがあれば、対応する処理をしなければいけません。でもいきなり最初からかっこや前置演算子の話をするとややこしくなるだけなので、今はそれらは全くない場合だけを考えます。 -そうすると処理は } else { // 変数もしくは定数. i = tc[epc]; epc++; } -ここに来ます。これで、iに変数もしくは定数のトークンコード番号が入ります。 -もし「print a;」のように、後続の演算子がなければ、このiの値(=aのトークンコード)がそのままreturnされます。何も難しいことはありません。 -さてもしこの後に演算子が来るとどうでしょうか。たとえば二項演算子の「+」がある場合を考えましょう。その場合、ここに来ることになります。 } else if (TcPlus <= tc[epc] && tc[epc] <= TcMinus && priority >= 5) { i = exprSub1(i, 4, tc[epc] - TcPlus + OpAdd); // 左結合なので5より1小さくする. -このif文の意味するところは、epcの場所に書いてあるトークンが「+」もしくは「-」で、かつexprSub()を呼ばれたときの引数が5よりも大きかったら、ということです。今は99で呼んでいるわけですから、ここは問題なく成立します。あとでこの条件の必要性も説明しますので、今は気にしないでください。 -このif文が成立するとどうなるのかというと、exprSub1()を使って二項演算子の処理をするのですが、それではその部分を説明のために上記の引数で展開してみます。 epc++; j = exprSub(4); k = tmpAlloc(); putIc(op, &var[k], &var[i], &var[j], 0); tmpFree(i); tmpFree(j); i = k; -やっていることは、まずepc++して、「+」を読み進めます。 -次に、exprSub(4)を呼び出して、その結果をjで受けます。これはつまり、演算子の後ろにある項を1つ取ってこいという意味です。そしてその際には、優先度が4以下の優先度の高い演算ついてはどんどん結合して演算して結果を出してから帰ってこい、と、そういうことなのです。しかし優先度5以上の優先度の低いものは勝手に計算してまとめてはいけません。ちなみに優先度5というのは「+」や「-」のことです。 -こうすることで、掛け算とか割り算を含む項が後続していれば、それについては演算した結果を渡してもらえることになります。そうでなければ、単に次のトークンコードが返ってくることになります。 -その次に tmpAlloc() を実行して、それをkに入れます。これはつまり、_t0みたいな変数をひとつ持ってくるだけです。とにかく加算結果をどこかの変数に入れなければいけないので、適当な一時変数を準備しているのです。 -次のputIc()で内部コードを生成しています。opの部分は、「+」だったらOpAdd、「-」だったらOpSubになります。今の例では加算命令を出力することになります。 -次の2つのtmpFree()で、もしiやjが一時変数であったら、未使用状態に戻します。なぜならもう演算のために使ったので、今後参照されることはないからです。もしtmpFree()の引数が一時変数でなければ特に何もしません。そういう仕様です(そうすることでif文を書く手間を減らしました)。 -そして最後に、iにkを代入します。これは、「ここまでの計算結果が入っている変数のトークンコード」はiにしておくのがこのループの前提で、そして今、加算結果が入っている変数はkになっているので、iを更新してから先に進むわけです。 -以降はこの処理を、式の終わりまでやるか、もしくは指定された優先順位より大きい演算子(=優先度の低い演算子)にぶつかるかするまで繰り返せば、私たちの欲しいものは得られるのです。 ** (4) 左結合と右結合について -C言語のほとんどの演算子は左結合ですが、一部右結合のものがあります。まずは結合の違いを説明します。 -「a + b - c」という式は、+も-も左結合の演算子なので、一番最初に実行されるのは、「_t0 = a + b」です。そしてその次に「_t1 = _t0 - c」が実行されます。優先度が同じものがあった場合、左を先に演算するという、ただそれだけのことです。これは当たり前に感じられるでしょう。 -意外なのは右結合の演算子です。「a = b = 3」の場合、=は右結合の演算子なので、最初に実行されるのは「a = b」ではありません。「b = 3」なのです。そのあとに「a = b」が実行されます。 -でもこれは、そうでなければ困るというのがわかるでしょうか。「a = b = 3」と書いた時は、aもbも3になることが期待されているのです。もし左結合だったら、bしか3にならず、aはbの古い値が入っているだけになってしまうのです。 -exprSub()でこの右結合を実現するにはどうすればいいでしょうか。それは、優先度15の=の処理の時に、exprSub(14)ではなくexprSub(15)をすることなのです。そうすれば、後続の項の中に=が含まれていれば、それを全部putIc()で出力してから帰ってくるからです。 -結局、左結合か右結合かは、exprSub()の再起呼び出しの際に、優先度を1引くか、そのままにするか、それだけの違いになります。 ** (5) その他のこまごまとした説明 (expr(), phrCmp(), comiple(), exec()) -関数expr()は、exprSub()を利用する際に必要な準備をして、exprSubを引数99で呼び出し、さらに呼び出し後の後片付けをしてくれる便利関数です。 --expr()の引数では、wpc[]の番号を指定します。この仕様にしておくと、compile()内で呼び出すのがすごく楽になるのでそうしました。 --そしてexpr()の処理中にphrCmp()やexpr()を利用するかもしれないことを考えて、epc値やepc[]値を保存しておき、それからepc, epc1に式の範囲をセットして、exprSub(99)を実行しています。 --その後は、保存した値をすべて復元して、終了しています。 -phrCmp()もHL-6aまでの内容に対してバージョンアップしています。 --主な変更点は、任意の式にマッチする !!** や !!*** というワイルドカードを追加したことです。 --ただし、phrCmp()での式の判定はすごく雑で、「a + b」や「-3*a」みたいな正しい式にマッチする一方「+ +」とか「a b c」など、意味不明なトークンの並びでも通してしまいます。これは何をもって式とするのかは、将来的に考えが変わるかもしれないので、とにかくルーズにしておこうと思ったのです(それに判定をまじめにやるとプログラムが長くて複雑になる)。現状では、カッコの対応関係を雑にみている程度です。まあそれでも、対象が正しいプログラムであれば、これで問題なくマッチができています。 --ただそれだけであまりにも心配だと思ったので、expr()内で、式がちゃんと最後まで評価できているかをチェックするようにはしています。変な式だと評価が途中で終わるので、その場合はエラーにしています。 -compile()では、print命令と最後の任意の式のところだけに「!!**」や「!!***」を使いました。いきなりたくさん導入しても混乱すると思ったからです。 -最後に任意の式の評価があるのだから、もう「!!*0 = !!*1 + !!*2;」とか「!!*0 = !!*1 - !!*2;」とかはいらないと思うかもしれません。でもこれはわざと残しました(まあ消すのが面倒だったということもありますが)。 --なぜなら、もしこれらの記述をなくしてしまうと、単純な「a = b + c;」が OpAdd(_t0, b, c); OpCpy(a, _t0); --という2命令に変換されてしまうからです。今はこういう余計な代入を減らすような最適化が入っていないので、これを避けることはできません。だからとりあえず残したのです。残しておけば、 OpAdd(a, b, c); --という1命令に変換されます。だからHL-6aに対しての速度低下はありません。 -exec()では、追加された演算に対する演算命令をたくさん追加しました。でも難しいところは特にないはずです。 ** 次回に続く -次回: [[a21_txt01_8]] --次回は ブロックif文やfor文をやります。 *こめんと欄 #comment
テキスト整形のルールを表示する