天泣記

2002/10/01

#1

Parsers: Theory and Implementation

#2

google:

台風 大好き 93400
台風 ドキドキ 47700
台風 ワクワク 28900
台風 ウキウキ 11100
台風 わくわく 21900
台風 どきどき 15000
台風 うきうき 5440
台風 高揚 4680
台風 昂揚 497
台風 血湧き肉踊る 118

2002/10/03

#1

左再帰の除去は機械的にできるはずなのに、 ANTLR はなぜやらないのだろう?

継承属性の使いかたに制約が出るから?

#2

(LL や LR では) 文法が self-terminating かどうかを判断することはじつは難しくないのかも?

2002/10/04

#1

昼頃までに新三田につくには?

... それなりに早起き。

#2
関連 7630000
連関 26500

2002/10/05

#1

昔印刷した Parsing Techniques の発掘に挑戦。

... 成功。

2002/10/06

#1

そーか。lexical analysis と syntax analysis をいっしょくたに考えると non-canonical になるわけか。

2002/10/07

#1

Manuel E. Bermudez and George Logothetis, Simple Computation of LALR(1) lookahead-sets, Inform. Process. Lett., vol. 31, no. 5, p. 233-238, 1989

を眺める。

うぅむ。FOLLOW で済むのか...

#2

bison-1.50

なんと GLR とは。

2002/10/08

#1
%r{(?:[A-Za-z][\x2b\x2d\x2e0-9A-Za-z]*:
      (?:(?://
            (?:(?:(?:(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-;=A-Z_a-z~])*@)?
                  (?:(?:(?:[0-9A-Za-z]|[0-9A-Za-z][\x2d0-9A-Za-z]*[0-9A-Za-z])
                        \x2e)*(?:[A-Za-z]|[A-Za-z][\x2d0-9A-Za-z]*[0-9A-Za-z])
                     \x2e?|
                     \d+\x2e\d+\x2e\d+\x2e\d+)(?::\d*)?)?|
               (?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-;=@-Z_a-z~])+)
            (?:/(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
               (?:;(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*)*
               (?:/(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
                  (?:;
                     (?:%[0-9A-Fa-f][0-9A-Fa-f]|
                        [!\x24&-\x2e0-:=@-Z_a-z~])*)*)*)?|
            /(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
            (?:;(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*)*
            (?:/(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
               (?:;(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*)*)*)
         (?:\x3f(?:[!\x24&-;=\x3f-Z_a-z~]|%[0-9A-Fa-f][0-9A-Fa-f])*)?|
         (?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-;=\x3f-Z_a-z~])
         (?:[!\x24&-;=\x3f-Z_a-z~]|%[0-9A-Fa-f][0-9A-Fa-f])*)|
      (?://
         (?:(?:(?:(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-;=A-Z_a-z~])*@)?
               (?:(?:(?:[0-9A-Za-z]|[0-9A-Za-z][\x2d0-9A-Za-z]*[0-9A-Za-z])
                     \x2e)*(?:[A-Za-z]|[A-Za-z][\x2d0-9A-Za-z]*[0-9A-Za-z])
                  \x2e?|
                  \d+\x2e\d+\x2e\d+\x2e\d+)(?::\d*)?)?|
            (?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-;=@-Z_a-z~])+)
         (?:/(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
            (?:;(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*)*
            (?:/(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
               (?:;
                  (?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*)*)*)?|
         /(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
         (?:;(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*)*
         (?:/(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
            (?:;(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*)*)*|
         (?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-9;=@-Z_a-z~])+
         (?:/(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
            (?:;(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*)*
            (?:/(?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*
               (?:;
                  (?:%[0-9A-Fa-f][0-9A-Fa-f]|[!\x24&-\x2e0-:=@-Z_a-z~])*)*)*)?)
      (?:\x3f(?:[!\x24&-;=\x3f-Z_a-z~]|%[0-9A-Fa-f][0-9A-Fa-f])*)?)?
   (?:\x23(?:[!\x24&-;=\x3f-Z_a-z~]|%[0-9A-Fa-f][0-9A-Fa-f])*)?}x
#2

パターンを自動生成してインデントをつける場合、 2項演算子でつながったものはどんな基準でインデントするべきか。

#3

AspectJ を使ったデザインパターンの改善と支援

2002/10/09

#1
n = "a" | m "b"
m = n

の n を求めるのに、

n = "a" | n "b" = "a" "b"*

というように最初に m を消去して解くか、

m = "a" | m "b" = "a" "b"*
n = "a" | ("a" "b"*) "b" = "a" | "a" "b"* "b"

というように最初に n を消去して解くか。

前者の方が短いので好ましいが、前者を確実に選ぶ方法はあるか。

なるべく短いものを選ぶ方法はあるか。 むろん現実的な計算時間で。

2002/10/12

#1

enscript が ansi escape sequence で色をつけられることに気がつく。

うぅむ。背景が暗いのを仮定している配色だなぁ。黄色が見にくい。

2002/10/14

#1

DFA は BNF に簡単に変換できる、 とゆーことは ABNF でもって DFA から Regexp に変換できるということだ。

例によって 3の倍数を変換してみる。

% ruby -rabnf -rpp -e '
pp ABNF.regexp_tree(<<"End")
s0 = n0 s0 / n1 s2 / n2 s1 / ""
s1 = n0 s1 / n1 s0 / n2 s2
s2 = n0 s2 / n1 s1 / n2 s0
n0 = "0" / "3" / "6" / "9"
n1 = "1" / "4" / "7"
n2 = "2" / "5" / "8"
End
'
%r{[0369]*
   (?:[147](?:[0369]|[258][0369]*[147])*
      (?:[147]
         (?:[0369]|
            [147][0369]*
            (?:[147](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258])|
               [258])|
            [258](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258]))*
         (?:[147][0369]*(?:[147](?:[0369]|[258][0369]*[147])*[258][0369]*|)|
            [258](?:[0369]|[258][0369]*[147])*[258][0369]*)|
         [258][0369]*
         (?:[258]
            (?:[0369]|
               [147][0369]*
               (?:[147](?:[0369]|[258][0369]*[147])*
                  (?:[147]|[258][0369]*[258])|
                  [258])|
               [258](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258]))*
            (?:[147][0369]*(?:[147](?:[0369]|[258][0369]*[147])*[258][0369]*|)|
               [258](?:[0369]|[258][0369]*[147])*[258][0369]*)|
            ))|
      [258]
      (?:[0369]|
         [147][0369]*
         (?:[147](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258])|
            [258])|
         [258](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258]))*
      (?:[147][0369]*(?:[147](?:[0369]|[258][0369]*[147])*[258][0369]*|)|
         [258](?:[0369]|[258][0369]*[147])*[258][0369]*)|
      )}xi

が、これまた例によって十分に短いのが出てくるとは限らないのが問題ではある。

#2
%r{(?:[0369]|
      [147](?:[0369]|[147][0369]*[258])*(?:[147][0369]*[147]|[258])|
      [258][0369]*
      (?:[147]|
         [258](?:[0369]|[147][0369]*[258])*(?:[147][0369]*[147]|[258])))*}xi

というくらいでも済むんだよなぁ。

2002/10/15

#1

Manuel E. Bermudez の Practical Arbitrary Lookahead LR Parsing だの A Unifying Model for Lookahead LR Parsing だの Suffix Languages in LR Parsing だのを探してみるが、 見当たらない。

2002/10/17

#1

COCOMMSTA は なかなかだなぁ。

#2

東へいって Practical Arbitrary Lookahead LR Parsing を入手してくる。

#3

夜、東京

#4

正規表現の(backtracking な)照合には入力の長さに対して最悪指数関数的な時間がかかる。

正規表現から DFA へ変換するとサイズは最悪指数関数的に膨れる。

DFA の照合は入力の長さに対して線形時間ですむ。

もしかして、照合に指数関数的な時間がかかる正規表現を DFA に変換した場合に指数関数的にサイズが膨れるのだろうか?

#5

もし、そうだとすれば、 DFA から正規表現に変換する時に、 最小の正規表現を求めるのはむしろ不適切なのかも知れない。 おそらく、いくら小さいのが出てきても、 照合に指数関数的な時間がかかるのはあまり嬉しくないであろう。

そんなに遅くならなさそうな 範囲でなるべく小さいものを狙うのがいいのかも。

2002/10/18

#1

いや? 本当に正規表現の backtracking な照合が指数関数になり得るか?

#2

兵庫

#3

ライトバリア自動挿入というのは面白い。

#4

発表

#5

#6

2002/10/19

#1

兵庫

#2

DFA を正規表現に変換する場合、どこで爆発がおこるか?

とりあえず、DFA は最小化済みであるとする。

DFA が tree の場合を考える。 たとえば、

start--+-a->+-b--final
       |    |
       |    +-c--final
       |
       +-d->+-e--final
            |
            +-f--final

は、a(b|c)|d(e|f) に変換できる。 一般に、tree の分岐を alternation, 親子関係を concatenation に対応させれば正規表現に変換でき、 この変換ではひとつの state に対し、正規表現中に対応する場所は一ヶ所しか出てこないので、 爆発はおきない。

DFA が tree でなく DAG だったとする。 DAG は biconnected component に分解して、 biconnected component を node とする tree にできる(と思う)ので、 個々の biconnected component について考える。

start--+-a--+
       |    |
       |    V
       +-b->+--final

というようなものだと a|b と変換できるので、爆発は起きない。 しかし、

start--+-a->+-d--+
       |    |    |
       |    c    |
       |    |    |
       |    V    V
       +-b->+-e->+--final

で、a(ce|d)|be と変換すると e が 2回出てきて爆発の原因になる。 また、ad|(ac|b)e とも変換できるが、この場合は a が 2回出てきて爆発の原因になる。

DFA が DAG でもなく cycle があったとする。 strongly connected component に分解して strongly connected component を node とする DAG にできるので、 個々の strongly connected component について考える。

start->+-a--+
       A    |
       |    V
       +-b--+--final

は (ab)*a や a(ab)* に変換できるが、 どちらも a が 2回出てきて爆発の原因になる。

つまり、biconnected component や strongly connected component を変換するときに、 コピーが起こるのが爆発の原因である。

しかし、上記の DAG の例のように、変換のしかたには自由度があり、 DFA のどこをコピーするか選択可能な場合がある。 そのようなときに、コピーによって増える量が少ないものを選ぶことによって 小さな正規表現を目指せるのではないか。

ただ、(a|bc)d|be は ad|b(cd|e) より遅いだろうから、 なかなか難しいところではある。

#3

tree な DFA は、各 final state が merge 可能なので、 最小 DFA ではないことに気がつく。 つまり、最小 DFA は tree にはなり得ない?

いや、分岐しない一直線という可能性はあるか。

#4

帰還

2002/10/20

#1

昨日、(筑波大の)前田さんに、 コンパイラの(gcc の)最適化は いろんな最適化を繰り返し適用するのだが 最後に得られたものが必ずしも適切ではないという問題を、 最適化を TRS で表現して完備化することによって解決できないか、 という話を振られた。 実際、スケジューリングをした後に他の最適化をかけると スケジュールが壊れるなどの問題があるそうな。 (この最適化の問題は最近 fj でも読んだ気がする。)

問題は、最適化が TRS で表現可能であるかどうかと、 表現したとして完備化が可能(Knuth-Bendix の完備化がちゃんと止まる)かどうかである。

餅は餅屋ということで、 (東北大の)草刈さんに相談すると、 少なくとも完備な TRS が存在しない時には止まらなくて、 とくに commutative な規則があると危ないということであった。 linear (ひとつの変数がパターンに 1回しか出てこない性質)かどうかや、 associative な規則はとくに問題ないとのこと。

実際にやればそれなりに肯定的な結果が出てきそうな印象。

やる気になったら草刈さんに Knuth-Bendix の完備化の資料をもらうということにする。 ML を覚えていれば半日で済むだろうとか。 (外山研は毎年、配属された学部の 4年生に完備化を書かせるそうで、 4年生用の資料を保守しているそうな。)

前田さんはとりあえず Ruby で Knuth-Bendix の完備化手続きを書けと 焚きつけてくる。

#2

httptunnel のようなもの(GET/POST による tunnel)を CGI で作ることが無理なのは判明しているが、 mod_ruby なら作れるだろうか?

#3

なんか、すでにあるか。

いや、これはコードを等式に変換するのか?

#4

(a|bc)d|be が ad|b(cd|e) より遅いだろうと思うのは、 backtrack が長くなるためである。 最初に b を読んだ時、 後者はトップレベルのどの分岐に進めばいいか決定されるが、 前者は決定できず、もう 1文字必要である。 進んだ結果失敗すれば戻る長さは長くなる。

結局、前者は LL(2) であり、後者は LL(1) なわけである。

一方、LL(k) (や LR(k))で k が大きいほど文法は書きやすいという話がある。 文法が書きやすいというのは短い文法が書けるということだろうから、 短い正規表現を生成しようとすると、 k が大きくなって遅くなる傾向があるのかも知れない。

2002/10/21

#1
% ruby -e '
100.times {|i|
t1 = Time.now
/\A(?:a*)*\z/ =~ "a" * i + "b"
t2 = Time.now
t = t2 - t1
print i, " ", t, "\n"
}
'
0 7.3e-05
1 3.5e-05
2 2.7e-05
3 3.3e-05
4 4.6e-05
5 7.099999999999999e-05
6 0.000159
7 0.000219
8 0.000421
9 0.000815
10 0.00162
11 0.003193
12 0.006382
13 0.012768
14 0.025616
15 0.05263
16 0.113844
17 0.204058
18 0.408431
19 0.8134859999999999
20 1.661368
21 3.356856
22 6.71079
23 13.334479
24 26.431579
^C-e:4: Interrupt
        from -e:2:in `times'
        from -e:2

さて、これはどんなオーダか?

y を対数軸にすると直線に漸近しているように見えるので、指数関数的の模様。

#2

(a*)* は a* と等価なわけで、 a* は当然線形時間で照合できるだろうし、 DFA にしてもサイズはたいして膨れないだろう。

ということは、 「照合に指数関数的な時間がかかる正規表現を DFA に変換した場合に指数関数的にサイズが膨れる」という予想は外れである。 すくなくとも全部ではない。

では、全部ではないとすれば、そういうのは存在するか?

#3

パターンの(正規表現な)一部分を DFA に変換する、 という指定ができてもいいかもしれない。

DFA にすると、マッチの順番が変化することもあるわけだし、 最適化というよりは、ユーザが指定すべきものという見方もできる。

#4

The tardy program is a tar(1) post-processor. It may be used to manipulate the file headers in tar(5) archive files in various ways.

#5

やはり mod_ruby を使えばできるようだ。

% cat echo.rbx 
Apache.request.sync = true

print "ECHO:\n"

until (s = Apache.request.get_client_block(8192)).empty?
  p s
end

というのを動かすと、HTTP 経由で対話的な動作ができる。

C>POST /akr/echo.rbx HTTP/1.0
C>Content-Length: 10
C>
S>HTTP/1.1 200 OK
S>Date: Mon, 21 Oct 2002 09:03:02 GMT
S>Server: Apache/2.0.43 (Unix) mod_ruby/1.0.0 Ruby/1.7.3
S>Connection: close
S>Content-Type: text/plain; charset=ISO-8859-1
S>
S>ECHO:
C>abc
S>"abc\r\n"
C>def
S>"def\r\n"

HTTP/1.0 だと Content-Length で前もって長さを指定しないといけないが、 HTTP/1.1 なら chunked が使えるので不定長を扱える。 (手では入力しにくいし、proxy が chunked をサポートしているとも限らないわけだが...)

C>POST /akr/echo.rbx HTTP/1.1
C>Host: localhost
C>Transfer-Encoding: chunked
C>
S>HTTP/1.1 200 OK
S>Date: Mon, 21 Oct 2002 09:04:44 GMT
S>Server: Apache/2.0.43 (Unix) mod_ruby/1.0.0 Ruby/1.7.3
S>Transfer-Encoding: chunked
S>Content-Type: text/plain; charset=ISO-8859-1
S>
S>6
S>ECHO:
S>
C>3
C>abc
S>5
S>"abc"
S>1
S>
S>
C>3
C>def
S>5
S>"def"
S>1
S>
S>
C>0
C>
S>0
S>
C>GET ... (次のリクエスト)

こういう対話的な動作ができるんなら、 怪しいことができそうである。

tunnel はもちろんなのだが、 proxy の bufferring などの挙動を測定するなんていうのはどうだろう?

#6

Cマガを眺める。

fmmin と fmminrev の違いはアルゴリズムだった気がする。

2002/10/22

#1
require 'socket'

req = Apache.request
req.sync = true

#req.send_http_header
req.print ''

TCPSocket.open('localhost', '22') {|sock|
  t1 = Thread.new {
    loop {
      begin 
        buf = sock.sysread(8192)
      rescue EOFError
        break
      end
      print buf
    }
  }
  until (buf = req.get_client_block(8192)).empty?
    sock.print buf
  end
  t1.join
}

というくらい書けば簡単な tunnel ができるのではないか... と思ったのは甘かった。 get_client_block がもう一方の thread も block してしまう模様。 考えてみりゃそりゃそうか。

解決法としては、 httptunnel みたいに、行き(POST)と帰り(GET)を別リクエストにするか、 Apache を調べて select みたいな入出力の多重化のやりかたを調べるか、 半二重な通信路上で polling して全二重を実現するか、 あたりが考えられる。

どれもそれなりにちゃれんじんぐ。

#2

ふと、EUC と UTF-8 の共通部分を調べる。

Grail を使うので、まず、各バイトを適当に Grail で使える文字にエンコードしなければならない。 以前、EUC と SJIS でやった時は手作業でやったが、 今回は遥かに複雑で、手作業はすぐにあきらめて NatSet を使う。

[[#<NatSet: 0..127>, "a"],
 [#<NatSet: 128..131>, "b"],
 [#<NatSet: 132..135>, "c"],
 [#<NatSet: 136..141>, "d"],
 [#<NatSet: 142>, "e"],
 [#<NatSet: 143>, "f"],
 [#<NatSet: 144..159>, "g"],
 [#<NatSet: 160>, "h"],
 [#<NatSet: 161..191>, "i"],
 [#<NatSet: 192..193 254>, "j"],
 [#<NatSet: 194..223>, "k"],
 [#<NatSet: 224>, "l"],
 [#<NatSet: 225..236>, "m"],
 [#<NatSet: 237>, "n"],
 [#<NatSet: 238..239>, "o"],
 [#<NatSet: 240>, "p"],
 [#<NatSet: 241..247>, "q"],
 [#<NatSet: 248>, "r"],
 [#<NatSet: 249..251>, "s"],
 [#<NatSet: 252>, "t"],
 [#<NatSet: 253>, "u"],
 [#<NatSet: 255>, "v"]]

という対応になった。 この対応に従えば、EUC は

((o+l+i+q+p+m+k+j+n+t+s+u+r)(o+l+i+q+p+m+k+j+n+t+s+u+r)+(e)(o+l+i+q+p+m+k+j+n+t+s+u+r)+(f)(o+l+i+q+p+m+k+j+n+t+s+u+r)(o+l+i+q+p+m+k+j+n+t+s+u+r))*

と表現され、UTF-8 は

((k)(h+b+i+g+d+c+f+e)+(l)(h+i)(h+b+i+g+d+c+f+e)+(m)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)+(n)(b+g+d+c+f+e)(h+b+i+g+d+c+f+e)+(o)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)+(p)(h+i+g)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)+(q)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)+(r)(h+i+g+d+f+e)(o+l+q+p+m+k+j+n+t+s+v+u+r)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)+(s)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)+(t)(h+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)+(u)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e)(h+b+i+g+d+c+f+e))*

となる。 ただし、0..127 はどっちでも ASCII で意味が同じなので除いてある。

あとは、Grail に食わせて、最小 DFA に変換して共通部分をとればいい。 その結果、22状態の DFA が求まる。

(START) |- 0
0 k 1
0 l 2
0 m 2
0 o 2
0 p 3
0 q 3
0 r 4
0 s 5
0 t 6
0 u 6
1 i 0
2 i 7
3 i 8
4 i 9
5 i 10
6 i 11
7 e 12
7 f 13
7 i 12
8 e 1
8 f 14
8 i 1
9 j 2
9 k 2
9 l 2
9 m 2
9 n 2
9 o 2
9 p 2
9 q 2
9 r 2
9 s 2
9 t 2
9 u 2
10 e 2
10 f 15
10 i 2
11 e 3
11 f 16
11 i 3
12 k 7
12 l 15
12 m 8
12 n 17
12 o 8
12 p 16
12 q 10
12 r 18
12 s 11
12 t 19
12 u 19
13 k 1
13 l 2
13 m 2
13 o 2
13 p 3
13 q 3
13 r 4
13 s 5
13 t 6
13 u 6
14 i 12
15 i 1
16 i 2
17 e 1
17 f 14
18 e 20
18 f 9
18 i 20
19 e 5
19 f 21
19 i 5
20 j 8
20 k 8
20 l 8
20 m 8
20 n 8
20 o 8
20 p 8
20 q 8
20 r 8
20 s 8
20 t 8
20 u 8
21 i 3
0 -| (FINAL)

でもなんだかよくわからない。

しょうがないのでびじゅあらいずというわけで、 GraphViz の dot に食わせるために fmtodot を書く。

なんか出てきた、が、やっぱりよくわからないことには違いない。 ただ、8byte のサイクルが見えるので、 EUC 4文字と UTF-8 などという組合せがある模様。

例示させよう、というわけで fmenum で短いほうから生成させる。

ki
kiki
piei
piii
qiei
qiii
lifki
mifki
oifki
sifii
kikiki
kipiei
kipiii
kiqiei
kiqiii
lielii
liemei
liemii
lienei
lieoei
lieoii
liilii
liimei
liimii
liinei
liioei
liioii
mielii
miemei
miemii
mienei
mieoei
mieoii
miilii
miimei
miimii
miinei
miioei
miioii
oielii
oiemei
oiemii
oienei
oieoei
oieoii
oiilii
oiimei
oiimii
oiinei
oiioei
oiioii
pieiki
piiiki
qieiki
qiiiki
tieiei
tieiii
tiiiei
tiiiii
uieiei
uieiii
uiiiei
uiiiii
kilifki
kimifki
kioifki
kisifii
liekfki
lieqfii
lifkiki
lifpiei
lifpiii
lifqiei
lifqiii
liikfki
liiqfii
miekfki
mieqfii
mifkiki
mifpiei
mifpiii
mifqiei
mifqiii
miikfki
miiqfii
oiekfki
oieqfii
oifkiki
oifpiei
oifpiii
oifqiei
oifqiii
oiikfki
oiiqfii
pifilii
pifimei
pifimii
pifinei
pifioei

空でない最初の奴は 2byte の ki で、 194..223 161..191 つまり [\xc2-\xdf][\xa1-\xbf] である。

EUC-JP 側でいえば、JIS X 0208 の 94x94 のコード表で 「臓」「多」「漾」「濘」の 4文字で括られた矩形に含まれる文字は UTF-8 としても解釈可能なバイト列になる、と。

UTF-8 側だと... Unicode で XXXXY1ZZZZZ というパターンで、 XXXX は 0001 から 1111 まで、 Y は 0 から 1 まで、 ZZZZZ は 0001 から 11111 までの組合せである。 XXXX が 0001 なところは Latin-1 Supplement で、 row が 0b1010=0xa, 0b1011=0xb, 0b1110=0xe, 0x1111=0xf なところ、つまり ISO-8859-1 で [\xa1-\xaf\xb1-\bf\xe1-\xef\xf1-\ff] は UTF-8 で表現した時に EUC としても解釈可能になる、と。 むろん、Latin-1 Supplement 以外にもたくさんあるはずである。

まぁ、UTF-8 全体じゃなくて、 日本語レパートリとの共通部分を考えるべきかも知れない。

日本語レパートリって、どこに定義されてたっけか...

2002/10/23

#1

vim6+im_custom+canna を試す。 ついに jvim3+onew+wnn4 から乗り換えられるか?

うぅむ。C-o から C-space に変えるやりかたがわからない。

#2

Makefile 以外では expandtab するやりかたを見つける。

2002/10/24

#1

半日がかりで acroread が Invalid font '...' was removed from the document. と叫ぶ条件をつめる。

結局のところ、gs の CIDFnmap で TrueType フォントを参照して生成した フォントを使う文書を ps2pdf(=ps2pdf12) で変換すると起きるようだ。

(TrueType ではない)CIDFont を使うか、 ps2pdf13/ps2pdf14 を使うか、 %PDF-1.2 を %PDF-1.3 に書き換えるか、 回避方法はいろいろある模様。

2002/10/25

#1

おぉ、これが自分が開発しているわけでもないものに関する 知らない人からの 唐突な質問メールというやつか。 初めてな気がする。

無視。

#2

kterm 上の vim で色をつけることにする。

そのために、普段使っているシステムの app-defaults/KTerm に *termName: kterm-color と設定したまではいいのだが、 他のところに ssh して、 そこの端末機能データベースに kterm-color が存在しないと悲しい。

しょうがないので、dot-zsh に TERM の変換機構を仕込む。

しかし... 醜い。dot-zsh はそのうち作り直したいよなぁ。

#3

kterm 上の vim で、日本語を paste するにはどうしたらいいか?

kterm を euc で動かして、 vim で termencoding=euc-jp とすればいいというのは一つの方法である。

が、しかし、termencoding=euc-jp にすると、 (はぁとまぁくが入った)シグネチャファイルを表示できない。 まぁ、はぁとまぁくを paste する必要はないが、表示はしたい。 (せっかく、vim の内部コードを utf-8、 デフォルト/新規ファイルの fileencoding を iso-2022-jp-2 にして、 扱えるようにしたのに。)

paste とはぁとまぁくを両方扱える方法はあるか?

端末からの入力は euc-jp、出力は iso-2022-jp-2 と非対称にできればいいのだが、 そういう設定は可能か?

kterm に拘らずに、utf-8 な端末に乗り換えろと言うことかも知れない...

#4

うぅむ。 termencoding=iso-2022-jp-2 だと、 はぁとまぁく周辺での動きが変だなぁ。 termencoding は euc-jp で我慢しとくか。

#5

Mark-Jan Nederhof, Practical experiments with regular approximation of context-free languages, Computational Linguistics, vol. 26, no. 1, pp. 17-44, 2000.

というものを見つける。 本題にはいる前の、正確に regular set になる場合の話は、 ABNF でやったことに非常に近くて面白い。

#6

Mark-Jan Nederhof の論文のリスト

#7

温泉にいこう。

2002/10/26

#1

Practical Arbitrary Lookahead LR Parsing をざっと読む。

ふむ。 ここでいうところの Continuation (Scheme のあれではなく FOLLOW みたいなもの) を表現する文法を作って正規集合で近似すればもう少し改善できるんじゃないかという気がする。 (むろん、Simple Computation of LALR(1) lookahead-sets の LR(0) オートマトンに対応する文法に対して)

#2

gvim を試す。

ふむ。encoding(内部コード)が locale のコードと一致してないと日本語が出ないか。 ということは、今の環境では utf-8 な locale はないから、 gvim では encoding=euc-jp にせざるを得ない、と。

まぁ、たとえ utf-8 な locale が使えても、 locale をそう設定するのは影響が大きすぎそうだが。

2002/10/27

#1

LALR(1) の state を split して、 LR(1) にしてしまうという話がある。

LR-regular の state を split する意味はあるか? どうすればできるか?

#2

cut buffer と selection を両方扱えて、 STRING だけじゃなくて、COMPOUND_TEXT も扱える command line な tool はないものか。

#3

意味が無いわけはないか。

E = a A d
  | a B c
  | b A c
  | b B d
A = e
B = e

という、LALR(1) ではないが、LR(1) な文法を考えると、 いくら先読みを長くしてもしょうがないわけである。 conflict が起こる state から入力の終端までは どうせ 1文字しかないというか。

conflict をどうにかするには、右を詳しく調べるのではダメで、 左を詳しく調べないといけない。

state の split というのは左の情報をより詳しく保持する方法で、 先読みを長くするのは右の情報をより詳しく調べる方法なんだから、 どちらかがもう一方を無意味にするわけはないのであった。

ただ、右か左か、どちらでも解決できるときは選択肢があるわけで、 そのへんの匙加減は考えどころかもしれない。

2002/10/28

#1

vim で、foldmethod=indent としてみる。

2002/10/29

#1

Karel Culik II, Rina S. Cohen, LR-Regular Grammars - an Extension of LR(k) Grammars, Journal of Computer and System Sciences, 7, (1973), 66-96.

をざっと眺める。

補集合と共通集合について閉じているというのを読んで目を見張るが、 和集合について閉じていないのであまり使えないことにすぐ気がついた。

#2

はじめて ar の中身をいじくる。

ar の生成は簡単でよろしい。

2002/10/30

#1

shell と shell script や elisp と elisp program の区別を気にするなら、 ar と ar archive も使い分けなければいけないだろうか?

しかし、ar archive というのは馬から落馬という感じだ。

そのものずばりな名前もやりすぎはよくないのかもしれない。

#2

tar と tar archive も?

#3

Exploring alternative syntaxes for XML

2002/10/31

#1

今日の失敗: make で全部の HTML ファイルを作り直そうと思って、

touch -t 197001010000 *.html

として make したら、

gmake: *** Warning: File `...' has modification time in the future (1970-01-01 00:00:00 > 2002-10-31 16:42:16)

などといわれてしまった。

根本的には依存関係を全部書いてないのが悪いといえばそうなのだが、 それはそれとしておくと、まぁ、負の time_t は使うなということか。


[latest]


田中哲