yacc
DBM
突然ですが、DBMとかけて何と解く？
そりゃ、出身によるわな。ソフト屋さんなら、永続版のhashであるndbmとかgdbmとかを連想するだろう。何せhashですから。。。
電子屋さん、しかも貧乏人は、ダブル・バランスド・ミクサーを思い出すだろう。ミクサーってのは、早い話、かけ算器だ。それが二重にバランスしてる？？？ 水晶フィルターを購入する亊が出来無い、貧乏中学生が夢みたSSBのジェネレータ。の心臓部だ。
信号Sと搬送波Cのかけ算と和(もしくは差)で出来上がっている。
[sakae@fb /tmp]$ maxima
(%i1) trigreduce(sin(S)*cos(C)) + trigreduce(cos(S)*sin(C));
(%o1) sin(S + C)
(%i2) trigreduce(sin(S)*cos(C)) - trigreduce(cos(S)*sin(C));
(%o2) sin(S - C)
(%i3) trigreduce(sin(S)*cos(C));
sin(S + C) sin(S - C)
(%o3) ---------- + ----------
2 2
信号も搬送波も、90度位相がずれた信号が必要なのが難点。
普通に三角関数をかけ算すると、積和公式(上の%3)により、キャリアーに対して上側波帯と下側波帯が発生する。位相差をもった波をミックスして、加算もしくは減算すると、側波帯のどちらかが得られる。これが、数学的な原理。
キャリアー信号を90度ずらすのは簡単だけど、信号になるオーディオを90度ずらすのは至難の技。抵抗とコンデンサーで移相器を作ったものだ。今だと、ディジタル的に出来ちゃうのかな。
z変換とかね。これって、ラプラス変換の離散的な表現らしい。いつか首を突っ込んでみたいものだ。
数理モデルと微分方程式
前回のSDRのYoutubeで、未来を予測するなんて言う刺激的な文言が飛びかった。そうか、微分方程式を立てられば、天下無敵、競馬で億万長者間違いなしなんだな。
微分方程式をたてるって、数学の分野をちょっぴり外れる話題なんだな。ぐぐってみたら数理モデルって分野になるっぽい。
yacc
rubyの肝は、その仕様をプログラムの落とし込む部分にあるらしい。
LoveRuby.Net こちらのRHGに詳しい説明がある。
Cとyacc/lex いきなりのrubyがキツいという場合は、やさしいのから手を出すのが良かろう。
bc
FreeBSDのbcがどうなってるか、視察してみる。記録が残る電卓ですから、後で検証が容易ですよ。そんじょそこらの(GUI)電卓とは違うんです。
まず軽く、コンパイルしてみる。
yacc -d -o bc.c bc.y yacc: 1 shift/reduce conflict, 16 reduce/reduce conflicts. lex -oscan.c scan.l : cc -O2 -pipe -I. -I/tmp/bc -g -std=gnu99 -Wno-format-zero-length -nobuiltininc -idirafter /usr/lib/clang/13.0.0/include -fstack-protector-strong -Qunused-arguments -o bc.full bc.o scan.o tty.o -ledit objcopy --only-keep-debug bc.full bc.debug objcopy --strip-debug --add-gnu-debuglink=bc.debug bc.full bc
yacc/lexがちゃんと使われていた。しかも編集機能付きです。
軽く bc -hして、試用説明書をみておく。
-l --mathlib
Use predefined math routines:
s(expr) = sine of expr in radians
c(expr) = cosine of expr in radians
a(expr) = arctangent of expr, returning radians
l(expr) = natural log of expr
e(expr) = raises e to the power of expr
j(n, x) = Bessel function of integer order n of x
着本的には、関数電卓。関数機能をONして使ってみる。
[sakae@fb ~]$ bc -l
e(1)
2.71828182845904523536
s(1.0)
.84147098480789650665
scale = 50
4 * a(1)
3.14159265358979323846264338327950288419716939937508
pi(50)
3.14159265358979323846264338327950288419716939937510
print("Hello BC\n")
Hello BC
define myadd(a,b) { a + b }
myadd(10,3)
13
0
define mymul(a,b) { return (a * b) }
mymul(3,4)
12
プログラマブル電卓なのね。じゃ、その核心をみる。
[sakae@fb /tmp/bc]$ yacc -v bc.y yacc: 1 shift/reduce conflict, 16 reduce/reduce conflicts. [sakae@fb /tmp/bc]$ grep conflicts y.output State 102 contains 4 reduce/reduce conflicts. State 161 contains 2 reduce/reduce conflicts. State 162 contains 2 reduce/reduce conflicts. State 163 contains 2 reduce/reduce conflicts. State 164 contains 2 reduce/reduce conflicts. State 165 contains 2 reduce/reduce conflicts. State 166 contains 2 reduce/reduce conflicts.
これぐらいになると、どうしたらいいの、が出てくるのね。
bc.libraryに、sin関数等のdefineが定義されてた。マクローリン展開ではなさそうだし、収束の早い計算方法って、どんなのが有るのだろう？
First, if a function is called on startup to turn bc(1) into a
number converter, it is possible to replace that capability with
various shell aliases. Examples:
alias d2o="bc -e ibase=A -e obase=8"
alias h2b="bc -e ibase=G -e obase=2"
進数変換はdcと言うRPNカリキュレータの得意技かと思っていたら、36進数までは上のようにして自由に定義出来るのね。
ついでにHP電卓の心臓部であるdcをみたら、yacc/lexは使っていなかった。スタックが主戦場だから、無理して使う亊は無いのか。
[sakae@fb /tmp/t]$ cat mye.bc
scale = 10
define mye(x){
auto a, b, c, i, s
a = 1
b = 1
s = 1
for(i=1; 1==1; i++){
a = a*x
b = b*i; print "b= "; b
c = a/b; c
if(c == 0) return(s)
s = s+c
s
}
}
mye(1)
quit
autoは、ローカル変数の宣言なんだな。それから、どんな風に計算が進行するか、主な変数をモニターしてみた(単に変数名を列挙すると、値が表示される)。
[sakae@fb /tmp/t]$ bc mye.bc b= 1 1.0000000000 ;; c 2.0000000000 ;; s b= 2 .5000000000 2.5000000000 b= 6 .1666666666 2.6666666666 b= 24 .0416666666 2.7083333332 : b= 87178291200 0 2.7182818277
関数のマクローリン展開 を、愚直に実行しているんだね。
like ruby
関数定義が、defineで始める亊になっている。ちょいと気にいらない。defineはschemeのものだろう。rubyに似せて、defでいけるようにしたい。どこを改造すればいい？
[sakae@fb /tmp/bc]$ grep -n define bc.y scan.l : bc.y:128:#define MAX_VARIABLES (VAR_BASE * VAR_BASE) bc.y:400: LBRACE NEWLINE opt_auto_define_list bc.y:459:opt_auto_define_list bc.y:461: | AUTO define_list NEWLINE bc.y:462: | AUTO define_list SEMICOLON bc.y:466:define_list : LETTER bc.y:476: | define_list COMMA LETTER bc.y:481: | define_list COMMA LETTER LBRACKET RBRACKET scan.l:53:#define YY_DECL int yylex(void) scan.l:54:#define YY_NO_INPUT scan.l:56:#define YY_INPUT(buf,retval,max) \ scan.l:132:"define" return DEFINE;
ふむ、scan.l を変更すればいいのかな。そんなの、すぐに気付よ。lexが処理するソースに対応が定義されてるに決っているだろ。まれに規模が小さいと、parse.yに押し込んでしまう亊もあるようだけど。
実際にやってみるとこんなエラー。元に戻しても同様。
[sakae@fb /tmp/bc]$ ./bc mye.bc
Parse error: bad character
<stdin>:2
ええい、面倒だって亊で、rootになって本家本元を修整してインストール。でも、同様のエラーが発生。諦めるか、何か見落としが有るんだろう。まて、河岸を変えてOpenBSDでチャレンジングって手もあるな。
早速やってみたら、bcのコンパイラーの所でdcも必要って言われた。どうもdcに定義されてるソースの一部を利用してるみたいだ。bcとdcは、同じ血をわけた兄弟なんだな。なんとなく名前が簡潔なわりには似てる雰囲気を醸し出していたけど、そういう繋がりがある訳ね。
で、結果は、大成功。rubyぽくなったよ。よかった、よかった。 じゃ、FreeBSDで失敗した原因は何？ コンパイル・ログを見るとobjcopyとか変な亊をやってるし。。。これにて、打ち止め。
後日、/usr/portsをアップデートしようとしたら、何時まで待っても終了しない亊に気が付いた。こういう時は、プロセスがどういう状態になってるか確認するのが鉄則。
1716 3 I+ 0:00.01 make update 1779 3 I+ 0:00.02 /bin/sh /usr/sbin/portsnap -p /usr/ports fetch 1945 3 I+ 0:00.00 xargs /usr/libexec/phttpget ipv4.aws.portsnap.freebsd.org 1946 3 I+ 0:00.00 /bin/sh /usr/sbin/portsnap -p /usr/ports fetch 1947 3 I+ 0:00.00 /bin/sh /usr/sbin/portsnap -p /usr/ports fetch 1949 3 I+ 0:00.04 /usr/libexec/phttpget ipv4.aws.portsnap.freebsd.org bp/dd 1950 3 I+ 0:00.00 bc 1951 3 I+ 0:00.00 dc -x
がーん、全く関係ないと思っていたbcと、兄弟のdcが顔を出しているよ。rootでインストールしてしまったbcがちゃんと機能してない予測がたつな。さー、困った、どうする？
bc == dc ?
普通に考えたら、修復CDなりを使って、bcを上書きだな。ISOを取ってくる亊にしよう。
リナでISOをDLしてたので、取り敢えずリナで確認。
sakae@deb:~$ sudo mount -o loop -t iso9660 /meet/FreeBSD-13.1-RELEASE-i386-disc1.iso /mnt
mount: /mnt: WARNING: source write-protected, mounted read-only.
sakae@deb:~$ ls -l /mnt/usr/bin/{bc,dc}
-r-xr-xr-x 2 root root 211672 May 12 18:06 /mnt/usr/bin/bc*
-r-xr-xr-x 2 root root 211672 May 12 18:06 /mnt/usr/bin/dc*
兄弟のbcとdcを、取り敢えず確認。何と瓜二つですよ。 これはもう、 FreeBSDにいって、コピペだな。その前に、現状の確認をしとく。
[sakae@fb /usr/bin]$ ls -l bc dc -r-xr-xr-x 1 root wheel 58540 Jun 4 09:14 bc* -r-xr-xr-x 1 root wheel 211672 May 19 07:08 dc*
壊れた(壊した)bcがインストールされてるよ。
下記のように一手間かけてマウント
mdconfig -a -f /meet/FreeBSD-13.1-RELEASE-i386-disc1.iso -u 0 mount_cd9660 /dev/md0 /mnt
解除も一手間必要。
umount /mnt mdconfig -d -u 0
bcをcpして、無事に修復完了。なお、bcでファイルにあるスクリプトを実行するには、-f を付ける必要があるみたい。これって、dc由来なんだな。 なんか、そんな亊bc(1)には説明が無いし、兄弟関係が分っていないと面くらうぞ。
/usr/src/usr.bin/Makefile
.if ${MK_GH_BC} == "yes"
SUBDIR+= gh-bc
.else
SUBDIR.${MK_OPENSSL}+= bc
SUBDIR.${MK_OPENSSL}+= dc
.endif
これを見ると、/usr/src/contrib/bcにある寄贈品が元本になってた。まさに兄弟でした。 そんな亊、しらんかったぞ。
[sakae@fb /tmp/t/bc/src]$ ls args.c dc.c lang.c opt.c vector.c bc.c dc_lex.c lex.c parse.c vm.c bc_lex.c dc_parse.c library.c program.c bc_parse.c file.c main.c rand.c data.c history.c num.c read.c
寄贈品はC言語のみの提供になってた。時代は変わるのね。
doas
parse.yというファイルをOpenBSDから探し出してみた。複数見付かったけど、日頃お世話になってる、doasに敬意を表して、これにターゲットを絞ってみる。doasコマンドはsudoからBUGを取り除いて整理したものだ(ちょっとその言は飛躍しすぎ？)。
機能を絞ってBUGが少くなるようにしましたって亊だ。設定は、これしかない。 doas.confの説明より引用。
The rules have the following format:
permit|deny [options] identity [as target] [cmd command [args ...]]
options Options are:
nopass The user is not required to enter a password.
nolog Do not log successful command execution to
syslogd(8).
:
identity The username to match. Groups may be specified by
prepending a colon (‘:’). Numeric IDs are also accepted.
as target The target user the running user is allowed to run the
command as. The default is all users.
example
permit persist setenv { PKG_CACHE PKG_PATH } aja cmd pkg_add
permit setenv { -ENV PS1=$DOAS_PS1 SSH_AUTH_SOCK } :wheel
この設定を解析してソースに反映させるのにparse.yが使われている。 コンパイルは、下記のように進んでいく。
vbox$ make yacc -o parse.c parse.y cc -O2 -pipe -I/tmp/doas -Wall -MD -MP -c parse.c cc -O2 -pipe -I/tmp/doas -Wall -MD -MP -c doas.c cc -O2 -pipe -I/tmp/doas -Wall -MD -MP -c env.c cc -o doas parse.o doas.o env.o
-o で変換後のソース名を指定してるけど、普通にyacc すると、デフォのファイル y.tab.cが作成される。
vbox$ wc parse.y parse.c y.tab.c
354 1085 7063 parse.y
840 2763 20331 parse.c
840 2763 20331 y.tab.c
それから、yaccに -v を付けると、ユーザーに易しい文法を出力してくれる。
vbox$ yacc -v parse.y
vbox$ cat y.output
0 $accept : grammar $end
1 grammar :
2 | grammar '\n'
3 | grammar rule '\n'
4 | error '\n'
5 rule : action ident target cmd
6 action : TPERMIT options
7 | TDENY
8 options :
9 | options option
10 option : TNOPASS
11 | TNOLOG
12 | TPERSIST
13 | TKEEPENV
14 | TSETENV '{' strlist '}'
:
state 31
strlist : strlist . TSTRING (16)
args : TARGS strlist . (23)
TSTRING shift 27
'\n' reduce 23
16 terminals, 11 nonterminals
24 grammar rules, 32 states
これで、別の角度から、間違いを検出しましょって言う、二重安全化が施されている。
doas.conf(5)
persist After the user successfully authenticates, do not
ask for a password again for some time.
に、こんな説明が有った。some timeって何よ？ ソース嫁。
static void
authuser(char *myname, char *login_style, int persist)
{
:
if (persist)
fd = open("/dev/tty", O_RDWR);
if (fd != -1) {
if (ioctl(fd, TIOCCHKVERAUTH) == 0)
goto good;
}
:
good:
if (fd != -1) {
int secs = 5 * 60;
ioctl(fd, TIOCSETVERAUTH, &secs);
close(fd);
}
一度認証に成功すると、それから5分以内は、再認証(passwdの入力)無しに、認証が継続されるって読めるんだけど。元に遡ってみる。
tty(4)
TIOCSETVERAUTH int *secs
Indicate that the current user has successfully authenticated
to this session. Future authentication checks may then be
bypassed by performing a TIOCCHKVERAUTH check. The verified
authentication status will expire after secs seconds. Only
root may perform this operation.
ああ、いきなり、興味が有る所を調べちゃったけど、parse.yとの連携は、
struct rule {
int action;
int options;
const char *ident;
const char *target;
const char *cmd;
const char **cmdargs;
const char **envlist;
};
rouleの個数は、parse.y にmaxrules=32って風に定義されてた。それから、doas.cに
static void
parseconfig(const char *filename, int checkperms)
{
:
yyparse();
yyparse()は、parse.yを変換したparse.cに、勿論定義されてる。これで臍の緒が繋った。
case 14:
#line 150 "parse.y"
{
yyval.options = 0;
yyval.envlist = yyvsp[-1].strlist;
}
break;
case 15:
:
こんなのがズラーと並んでいる。見るものでは無いな。
もう、yaccは古い技術だ。今なら、rust時代にやった、パーサー・コンビネータが主流になるか。次、何やろう？ しばし考え中。。。。
おまけでbcの小粋な機能
OpenBSDのbc(1)に、-cなんてオプションが提供されてた。何これと思ったら、bc語をdc語に翻訳してくれるみたいだ。そもそも最初にdcが有りき。このRPN型計算器に馴染めない人向けに、中置記法のbcが出来たみたい。
だから、bcはdcのプリプロセッサーの位置付。中置記法で入力すると、それをdc用のコマンド列に変換してくれる。
ob$ bc -c (1 + 2) * 5 1 2+ 5*ps.
qob$ dc 1 2+ 5*ps. 15
1と2を加算、それに5をかけ算、結果をpで印字。s. で、stackのTOPを取出しdot-regに格納。
[la1+dsa*pla10>y]sy 0sa1 lyx 1 2 6 24 120 720 5040 40320 362880 3628800
最初の10までの階乗を計算。まさに判じもの。ブラケット内が文字列としてスタックに詰れる。