Delphi for Lex(6)

メモです。

集合型の演算でマッチングの文字列を計算していることがわかり、Unicodeの多彩な文字をどうやって吸収するか検討しています。アイディアとしては、

• パターンを保持する集合型を文字列に変える
• パターンを保持する集合型を正規表現に変える
• 今のCClassを拡張して日本語の文字を識別する部分を作る

Unicodeの文字を判定する、IsControlやIsNumberを試してみたが、"１"も"1"同じ数値として判定されてしまう。if ByteType(S, i) <> mbSingleByte という条件判定で使うが、SをAnsiStringに型変換する必要がある。

Lex for Delphi(5)

忙しいなかやる気を持続させるために、まめにBlogに書き込んでします。いま一度、字句解析のコードを修正前後で比較します。文字の集合型で表している部分を、文字列に直します。元のプログラムはASCIIで#0...#255の範囲を想定しています。Unicode対応するときに、集合型から文字列に置き換えるだけでよいのか、検証していきます。

109行目の部分は、NOT(数字、英字、空白、改行（CR)）の文字を表しています。状態（STATE）0から3に遷移する文字セットを表していますが、255以上あるUnicodeの文字を表すためにはどうしたら良いのか？これNUL文字の判定が無いけど良いのか？

正規表現で「以下の文字を含まない」とか「改行以外の文字」を表すときに、Unicodeだとうまく集合型に収まらないのでなんらか工夫が必要だと認識しました。

Lex for Delphi(4)

考えを整理するために、修正すべきコードwriteccを貼り付けます。

view plainprint?

1. function charStr(c: char): string;  
2. begin  
3.   case c of  
4.     #0..#31,     (* nonprintable characters *)  
5.     #127..#255: Result := '#' + intStr(Ord(c));  
6.     '''': Result := '''''''''';  
7.     else  Result := '''' + c + '''';  
8.   end;  
9. end(*charStr*);  
10.   
11. procedure writecc(var f: Text; cc: CClass);  
12. (* print the given character class *)  
13. const  
14.   MaxChar = #255;  
15. var  
16.   c1, c2: char;  
17.   col:    integer;  
18.   tag:    string;  
19.   Quit:   boolean;  
20. begin  
21.   Write(f, '[ ');  
22.   col  := 0;  
23.   c1   := chr(0);  
24.   Quit := False;  
25.   while not Quit do  
26.   begin  
27.     if c1 in cc then  
28.     begin  
29.       if col > 0 then  
30.       begin  
31.         Write(f, ',');  
32.         Inc(col);  
33.       end;  
34.       if col > 40 then  
35.         { insert line break }  
36.       begin  
37.         writeln(f);  
38.         Write(f, ' ': 12);  
39.         col := 0;  
40.       end;  
41.       c2 := c1;  
42.       while (c2 < MaxChar) and (succ(c2) in cc) do  
43.         c2 := succ(c2);  
44.       if c1 = c2 then  
45.         tag := charStr(c1)  
46.       else if c2 = succ(c1) then  
47.         tag := charStr(c1) + ',' + charStr(c2)  
48.       else  
49.         tag := charStr(c1) + '..' + charStr(c2);  
50.       Write(f, tag);  
51.       col := col + length(tag);  
52.       c1  := c2;  
53.     end;  
54.     Quit := c1 = MaxChar;  
55.     if not Quit then  
56.       c1 := Succ(c1);  
57.   end; { of while }  
58.   Write(f, ' ]');  
59. end(*writecc*);  

  function charStr(c: char): string;
  begin
    case c of
      #0..#31,     (* nonprintable characters *)
      #127..#255: Result := '#' + intStr(Ord(c));
      '''': Result := '''''''''';
      else  Result := '''' + c + '''';
    end;
  end(*charStr*);

  procedure writecc(var f: Text; cc: CClass);
  (* print the given character class *)
  const
    MaxChar = #255;
  var
    c1, c2: char;
    col:    integer;
    tag:    string;
    Quit:   boolean;
  begin
    Write(f, '[ ');
    col  := 0;
    c1   := chr(0);
    Quit := False;
    while not Quit do
    begin
      if c1 in cc then
      begin
        if col > 0 then
        begin
          Write(f, ',');
          Inc(col);
        end;
        if col > 40 then
          { insert line break }
        begin
          writeln(f);
          Write(f, ' ': 12);
          col := 0;
        end;
        c2 := c1;
        while (c2 < MaxChar) and (succ(c2) in cc) do
          c2 := succ(c2);
        if c1 = c2 then
          tag := charStr(c1)
        else if c2 = succ(c1) then
          tag := charStr(c1) + ',' + charStr(c2)
        else
          tag := charStr(c1) + '..' + charStr(c2);
        Write(f, tag);
        col := col + length(tag);
        c1  := c2;
      end;
      Quit := c1 = MaxChar;
      if not Quit then
        c1 := Succ(c1);
    end; { of while }
    Write(f, ' ]');
  end(*writecc*);

引数ccで渡された集合型の文字を、印字可能なものならばそのまま出力、印字できない文字ならば数値化しています。 文字の範囲を0から255のコードを前提とした実装です。ASCIIで連続したコード値であれば、'A'...'Z'の形式で出力します。

実装でわかっていないのは、字句定義で"\t"としたときに、引数ccにはどのようなコード値で表されるかです。集合型から文字列に変えるのですが、ASCIIのコード値(#9)は、そのままUnicodeのコード値と同じで良いのか？BOMとか、非表示の文字を読み込んだらどうなるのか？さっぱりわかっていません。週末にでも、テストコードを書いて検証します。

Lex for Delphi(3)

連休の合間を使って字句解析のプログラム(dlex.exe)を調べています。
文字を保持する型が集合型(CClass)なので、Unicodeの文字を格納することができません。ここは、安直にString型に置き換えてみます。問題なのが、以下の部分です。

• 集合型の演算（和集合、差集合、積集合）
• 定数の連続値（1...128)

集合型であれば要素の順番に気を配る必要はありません。しかし、文字列に置き換えると、重複を除く必要があります。また、集合型であれば、#1...#128と短く書けますが、文字列で扱うとなると記述が長くなり、文字列定数の長さ制限に引っかかります。

騙しだましにプログラムを直して字句解析のパーサ(dlex.exe)をビルドして、サンプルの字句解析プログラムを生成してみました。しかし、サンプルとして出力されたコードと比較すると、微妙に差が出ています。惜しい！

文字列の重複を排除するためにTStringListを使っていますが、英字の大文字/小文字を無視しているように見えます。CaseSensitiveのプロパティをTrueにして、まだコード生成、比較をします。これで差異を生じている部分は残り2箇所になりました。

さらに、Unicodeの字句定義が通るか検証します。exprlex,lを修正して、指数表現の[eE]の部分をひらがなの”あ”に置き換えます。

dlex.exeで字句定義からコードを生成します。

字句定義を修正する前後で、コードと比較します。 右側の集合型の定数部部分にひらがな”あ”の文字がありません。うまくすれば、"あ"の文字が入るかと思いましたが、いずれにしろ集合型だと日本語の判定は正しく判定されないので、これで当面はOKです。

残りの作業を整理します。

• コード生成でcc:の集合型の部分を出力している箇所を突き止める。
• サンプルの出力コードと一致するように調整する。
• 出力されるコードを集合型から文字列に直す。
• 文字コードの判定で#128...#255までの指定が意味あるか調べる。

続きはまた来週

Lex for Delphi(2)

字句解析のプログラム生成を検討し始めたばかりで、考えを整理します。生成されたコードを改変して動きを検証した後は、コードを生成するツールの直し方を考えます。生成されたコードと同じく課題は集合型で実装されたコードです。字句の情報を保持するlexbase.pasの中で、修正すべき部分を示します。

view plainprint?

1. type  
2.   (* String and character class pointers: *)  
3.   StrPtr    = PString;  
4.   CClass    = set of char;  
5.   CClassPtr = ^CClass;  

type
  (* String and character class pointers: *)
  StrPtr    = PString;
  CClass    = set of char;
  CClassPtr = ^CClass;

この集合型を使うと重複無く文字を足し引き出来るのが利点です。dlex.exeの実装を調べると、集合型を使った演算がいくつかあります。

• 和集合(+)
• 差集合(-)
• 積集合(*)

しかしながら、Unicodeの文字を保持できない。型CClassをString型に変えて、参照、操作の仕方を片っ端から変えればいけるのか試してみます。

Lex for Delphi(1)

ぼちぼち、Delphiで使える字句解析のコードが必要になってきました。ツールを使っていくうちに、処理の遅さが気になってきました。原因パターンマッチの遅さです。このパターンをコンパイルして速度を稼ぐために、字句解析のプログラムが必要になってきたのです。

調べてみると、Unicode未対応のプログラム(dyacclex-1.4)を見つけました。これを自分で直せないか思案しています。 いきなりLexのコードを修正するまえに、出力された字句解析のコードをどのように変えたら、Unicode対応できるか考えます

。課題は集合型で実装している部分です。集合型で文字のパターンを保持すると、Unicodeの文字列はcharに切り捨てられてしまいます。Lexが生成しコードのうち、判定の文字列を保持するレコード型を示します。

view plainprint?

1. type YYTRec = record  
2.                 cc : set of char;  
3.                 s  : Integer;  
4.               end;  

type YYTRec = record
                cc : set of char;
                s  : Integer;
              end;

ccの型を集合型から文字列に変え、ccを参照するときの方法を変えてあげればUnicode対応のコードになりそうだ。

view plainprint?

1. type YYTRec = record  
2.                 cc : String;  
3.                 s  : Integer;  
4.               end;  

type YYTRec = record
                cc : String;
                s  : Integer;
              end;

検証するためにサンプルプログラムを改変しました。サンプルプログラム(expr.exe)は数値を入力して、小数点の形式で数値を表示するプログラムです。指数表現1.25E+3のEの文字を無理くり、”あ”に変えます。つまり、1.25あ+3と入力します。"あ"には特別な意味はありません。ただ生成された字句解析のコードで、指数表現の部分が簡単に特定できたからです。

試してみると、字句解析はすんなり通りました。字句が切り出せて、コード値が帰ればOKです。実装がうまい具合に１つのモジュールに閉じていて、型と判定の修正だけでうまくいきます。

次なる課題は、字句解析のコードを生成するプログラムの方です。これも集合型を使っているため、Unicodeの文字はbyte charに縮小されてしまいます。