レポート提出ボックス

遅れて提出済み

Lyxでレポートを書こう

はじめに

この記事はUEC Advent Calendar 2023の11日目の記事です.ドイツ語について書くと言っていましたが予定を変更してLyxについて書きます.

10日目の記事は型推論さんのMeCab で形態素解析をしよう、あとゴママヨ - ミシシッピ川以東のルイジアナでした.

ところで一昨日彼と飲みに行ったときの話によれば、mankiはアイスランド語の弱変化男性名詞の単数不定形と解釈できるそうです。mankiなのに男性?

多分酔ってて私が適当なことを言ってるんですが,単数不定形じゃなくて単数主格です.印欧語において動詞の無標の形である不定形と名詞の無標の形である主格が混ざったんだと思います.ちなみにmankiを前述したとおりに解釈すると格変化は次のようになります.アイスランド語や古ノルド語でmankiを使った文を作るときに参考にしてください.

単数 複数
主格 manki mankar
対格 manka manka
与格 manka mönkum
属格 manka manka

複数与格で格語尾の-umによるu-umlautが起きていますね.

Lyxって何?

www.lyx.org

LaTeXGUIフロントエンドです.使いましょう.

インストールと設定

LaTeXのインストール

LaTeXを入れないことには話が始まりません.

Windowsの場合

www.tug.org

上記のURLからinstall-tl-windows.exeをダウンロードしてインストールしましょう.インターネット環境にもよりますが大体50分くらいかかるのでお風呂に入ったりご飯を食べたり寝る前にインストールを仕掛けたりすると良いでしょう.インストール先はデフォルトのC:/texlive/2023にしておくとLyxのインストーラーがlatex.exeを見けてくれます(別の場所にしても見つけてくれるかも).Cドライブの空き容量の関係で別のドライブにインストールした場合はその場所を覚えておきましょう.

Linuxの場合

Ubuntuの場合aptリポジトリにtexlive-fullがありますがなんか古いのでtexlive公式のインストール方法に従ったほうがいいかもしれません.次のコマンドを1行ずつ実行してください:

cd /tmp
curl -L https://mirror.ctan.org/systems/texlive/tlnet/install-tl-unx.tar.gz|tar xz
cd install-tl-*
sudo ./install-tl --no-interaction

この場合もWindowsと同じく最後のコマンドで50分くらいかかります.気長に待ちましょう.

インストールが終わったらお使いの環境に合わせて/usr/local/texlive/YYYY/bin/PLATFORMをPATHに追加しましょう.例えばこの記事が書かれた時点(2023/12/11)でx86_64 linuxを使っているなら追加するのは/usr/local/texlive/2023/bin/x86_64-linuxとなります.追加するべきパスがよくわからない場合はインストーラーのログの最後の方にあるMost importantly, add /usr/local/texlive/2023/bin/x86_64-linux to your PATH for current and future sessions.みたいな文を参考にしましょう.

macOSの場合

homebrewからMacTeXをインストールしましょう.homebrewが入っていない場合は次のコマンドでインストールしてください:

/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

終わったら/opt/homebrew/bin(AArch64)または/usr/local/bin/brew(x86_64)をPATHに追加しましょう.

次のコマンドを実行してhomebrewでMacTeXをインストールしましょう:

brew install --cask mactex-no-gui

Lyxのインストール

www.lyx.org

上記のURLから環境に合ったインストーラーをダウンロードしてください.macOSの場合はhomebrewで(brew install --cask lyx),Linuxの場合は大抵の場合標準のパッケージマネージャーでインストールできます(sudo apt-get install lyxsudo pacman -S lyxなど).

設定

最低限使うために必要なものは長くなるのでここでは割愛します.以下のサイトを参照してください

texwiki.texjp.org

Windows

texwiki.texjp.org

macOS

zenn.dev


また,文書作成後にしか行えない設定ですが,次のことを設定して文書の既定値とするといいでしょう.

文書->設定から

  • 文書クラス->文書クラスを日本語Article (JSクラス)に変更
  • 文書クラス->扉に表示される既定の日付を抑制にチェックを入れる
  • フロートの配置の"既定の配置を利用する"から"何としても現在位置に置く"に変更

文書の既定値として保存->適用->OKで設定を保存します.

公式ドキュメント

www.lyx.org

公式チュートリアルです.途中から日本語訳されていませんが役に立つでしょう.

https://fd.kuaero.kyoto-u.ac.jp/sites/default/files/Lyx-Math.pdf

Lyxの数式エディタの説明書の日本語訳です.数式を書いていて困ったことがあったら参照するといいと思います.

使い方

スクリーンショットはLyx 2.3.7でmacOSのものです(Windowsのものは汚いので).

はじめに

起動直後のLyx

このアイコンから書類を新規作成しましょう.

新規作成できたらこのようになるはずです.

ここに色々と書き加えて文章を作っていきます.

文書構造

LaTeXにおける\part{}\section{}\subsection{}\title{}\author{}などは左上のドロップダウンメニューから選択します.

図表

ツールバーの挿入->フロートから図または表のフロートを挿入します.

表の挿入

表を挿入するにはツールバー上段のをクリックして所望のサイズの表を作成してください.表サイズの調整や罫線の設定などは表の中にカーソルを合わせた時に下に出てくる表ツールバーを用いて行えます.

図の挿入

画像の挿入は表と同様にをクリックすることによって行います.画像の挿入に限らずVentura以降のmacOSにおいてはファイル選択ダイアログからファイルを選択してもダイアログ自体が落ちてしまうのでファイルパスを直打ちする必要があります*1.Finderではoptionを押しながらファイルを右クリックすることでファイルパスをコピーできます.

中央揃え

画像や表がある行で右クリックをし段落設定から配置を中央揃えにしましょう.

ラベルの挿入

キャプションにカーソルを合わせてツールバーの挿入->ラベルを選択するとラベル挿入のダイアログが出てきます.適当な名前を設定しましょう.あらかじめキャプションに何か書いておくとラベルを挿入する時にラベル名を自動で決めてくれるのでキャプションに何か文字列を入れてからラベルを挿入するといいでしょう.

数式

このためにLyxを使っていると言っても過言ではないでしょう.数式がリアルタイムにプレビューされるため複雑な数式でも難なく書くことができます.

ツールバーから挿入->行内数式またはCtrl+M(macOSの場合はcommand+M)で数式を挿入できます.

数式の記述にはLaTeXと同じコマンドを使います.行内数式ではなく番号付きの数式や他の環境を使いたい場合は挿入->数式から使いたいものを選びましょう.

Tabでコマンドを補完できたりツールバーから記号を挿入できたりするのでLaTeXの数式コマンドをあまり知らなくてもいい感じに数式が書けます.詳しくは先に挙げた数式マニュアルを参照してください.

TeXコード

TikZなどを使いたい場合に使います.Ctrl+L(macOSの場合はcommand+L)を押すとTeXコードを挿入するためのテキストボックスが出てきます.

その他

Ctrl+R(macOSの場合はcommand+R)でプレビューを表示できます.ショートカットキーはこれを一番使うかも.

またコマンドラインツールとしてtexをlyxに変換できるtex2lyxというものが付いてきます.レポートの雛形としてtexファイルが配られたときに使いましょう.

Lyxには他にもListingsやMintedによるソースコードの挿入などができます.色々英語で調べてみるといいでしょう.

おまけ

少しだけドイツ語の話をします.

分離動詞

ドイツ語やオランダ語には前綴りと基礎動詞からなる分離動詞というものがあります.普通の動詞と違って

  • 平叙文で定動詞となるときに基礎動詞の部分が文の2番目の要素に来るが前綴りは文末に置いていかれる*2

  • 過去分詞やzu不定詞を作る時に前綴りと基礎動詞の間に接頭辞が挟まる

という特徴があります.分離動詞über|gehen "to transition"を例にとると,

Ein Narr geht zum Angriff über, wenn er seinen Widerstand aufgibt.

"愚か者は抵抗を諦めた時攻撃に移行する."

主語Ein Narrの直後の文の第2要素にübergehenの基礎動詞の部分が人称変化をした形で存在し,また文末に前綴りが存在していることがわかると思います.

Der Regen ist spät in der Nacht im Schnee übergegangen.

"雨は夜更け過ぎに雪へと変わってしまった."

ドイツ語では過去分詞を作る時基本的にge-という接頭辞を動詞の頭につけますが,前綴りと基礎動詞の間にその接頭辞が挟まっているのがわかると思います.


先ほどのツイートは英語のshitpostのshitの部分が分離前綴りとして解釈され,その過去分詞形のshitgepostetという用法が少なからず存在していて笑い止まらんwみたいな意味だと思われます.実際面白い.

おわりに

学内で他に使っている人を見たことがありませんが数式編集機能が強力なので環境構築とトラブルシューティングの手間にかける暇があるならぜひ使ってみてください.

明日はレプリカくんが 47都道府県のゲームセンターに行った話をするらしいです.ゲームセンターといえば音ゲー,弊学で音ゲーといえば徒歩部なので徒歩で47都道府県回ったのでしょうか.楽しみですね.

*1:macOSPythonが同梱されなくなったかららしい

*2:「置いていかれる」と表現したのはドイツ語の語順はSOV-V2で平叙文を作るときは文末にある本動詞が文の第2要素の位置に置かれるからです.

C言語で正規表現エンジンを作る

文字列処理の自作したくないですか?私はしたいので簡単な正規表現エンジンをCで書きました.これはそのアウトプットです.Advent Calendar 2022と日付がかぶってますが全く関係ありません.

github.com

↑成果物です

正規表現の仕組み

正規表現の実現方法はDFA型とVM型があります.

DFA

正規表現をNFAに変換し更にそれをDFAに変換してマッチングさせたい文字列をそのDFAに入力していく方法.GNU grepとかが使ってるらしいです.

VM

正規表現を仮想機械の命令のバイト列に変換してマッチング処理をする方法.sedとかPerlとかPythonとかが使ってるらしいです.


DFA型は線形時間でのマッチングでVM型は指数時間でのマッチングらしいです.


今回はVM型の正規表現エンジンを作りました(CでDFAをどうやって実装するか思いつかなかったため(形式言語理論とか受けたほうが良い?))

仕様

今回は

  • 連接 (AB)
  • 選択 (A|B)
  • 繰り返し (A*)

を含む最小限の正規表現を実装します

実装

このサイト*1を参考にしました.今回作成する仮想機械はプログラムの現在地を示すPCと文字列の現在位置のポインタSPの2つのレジスタと下に示す4つの命令を持ちます.

  • char c: SPが指す文字とcが一致していたらPCSPを先に進め,一致していなかったらマッチング失敗として終了します.
  • jmp x: xが指すプログラムの位置に飛びます. \mathrm{PC} \leftarrow xです.
  • split x, y: xが指すプログラムの位置とyが指すプログラムの位置から新しくスレッドを開始します.SPはその時の値を使います.
  • match: マッチングが成功したとして終了します.


処理の流れとしては字句解析→構文解析バイトコードの生成→仮想機械を動かしてマッチングというようになります

字句解析

正規表現文字列を構文解析する前に字句解析をしてトークン列にする必要があります.

トークンの種類を以下のように定義します.

enum Kind{
    TOKEN_UNDEFINED = 0,
    TOKEN_EOF,
    TOKEN_CHARACTER,
    TOKEN_ASTERISK,
    TOKEN_LPAR,
    TOKEN_RPAR,
    TOKEN_BAR
};

またトークンのデータ構造は次の単連結リストを用います.

typedef struct __token Token;

typedef struct __token{
    enum Kind kind;
    char* s;
    unsigned len;
    Token* next;
}_token;

トークン文字列の保持は入力文字列の該当箇所の先頭文字へのポインタ(メンバ変数s)と長さ(メンバ変数len)を用います(わざわざそれ用にメモリの確保したくないので)(結局1つのトークン文字列の長さを1文字にしたのでlenいらない).

あとはトークナイザをかくだけです.

void tokenize(char* s, Token* head){
    Token* cur;
    Token* tok;

    cur = head;
    while( *s != '\0'){
        if( isalnum(*s) ){
            tok = (Token*)malloc(sizeof(Token));
            tok->kind = TOKEN_CHARACTER;

            tok->s    = s;
            s++;

            tok->len = 1;
            tok->next = NULL;

            cur->next = tok;
            cur = tok;
        }

        else if(*s == '(' || *s == ')' || *s == '|' || *s == '*'){
            tok = (Token*)malloc(sizeof(Token));
            switch(*s){
                case '(':
                    tok->kind = TOKEN_LPAR;
                    break;
                case ')':
                    tok->kind = TOKEN_RPAR;
                    break;
                case '|':
                    tok->kind = TOKEN_BAR;
                    break;
                case '*':
                    tok->kind = TOKEN_ASTERISK;
                    break;                
            }
            tok->s    = s;
            s++;

            tok->len = 1;
            tok->next = NULL;

            cur->next = tok;
            cur = tok;
        }

        else if(*s == '\\'){
            s++;
            tok = (Token*)malloc(sizeof(Token));
            tok->kind = TOKEN_CHARACTER;
            tok->s    = s;
            s++;
            tok->len = 1;
            tok->next = NULL;

            cur->next = tok;
            cur = tok;
        }

        else{
            s++;
        }
    }
    tok = (Token*)malloc(sizeof(Token));
    tok->kind = TOKEN_EOF;
    tok->next = NULL;

    cur->next = tok;
}

トークン文字列の長さが1文字なので基本的に1文字ずつ読み進めていけばいいです.あと一応エスケープにも対応しました.

トークンをメモリ領域の確保にmalloc()を使っているので後で開放しないといけません.開放するための関数freeToken()は次のように実装しました.

void freeToken(Token* head){
    Token* tok;
    Token* next;

    tok = head->next;

    while(tok != NULL){
        next = tok->next;
        free(tok);
        tok = next;
    }
}

最初から順にケツ要素(tok->next == NULLになる要素)まで開放します.

構文解析

codezine.jp

↑めちゃくちゃここを参考にしました(読むには無料の会員登録が必要です)

BNFはこんな感じになります

expr    := subexpr EOF
subexpr := seq '|' subexpr | seq
seq     := subseq | ''
subseq  := star subseq | star
star    := factor '*' | factor
factor  := '(' subexpr ')' | CHARACTER

ノードの種類とデータ構造はこれです.

enum NodeKind{
    NODE_UNION,
    NODE_ASTERISK,
    NODE_CONCAT,
    NODE_CHARACTER
};


struct __node{
    enum NodeKind kind;
    char c;
    Node* l;
    Node* r;
};

実装は上の記事をほぼそのままCで書いただけなので言うことないです.あるとすればメモリの確保とポインタ周りの話だと思います.

Node* expr(Token** ptok){
    // expr := subexpr EOF
    Node* node = subexpr(ptok);
    match(ptok, TOKEN_EOF);

    return node;
}

Node* subexpr(Token** ptok){
    // subexpr := seq '|' subexpr | seq
    Node* node = seq(ptok);

    if((*ptok)->kind == TOKEN_BAR){
        match(ptok, TOKEN_BAR);
        Node* node2 = subexpr(ptok);
        node = Union(node, node2);
    }

    return node;
}

Node* subseq(Token** ptok){
    Node* node1 = star(ptok);
    if((*ptok)->kind == TOKEN_LPAR ||
       (*ptok)->kind == TOKEN_CHARACTER){
        // subseq := star subseq
        Node* node2 = subseq(ptok);
        Node* node = Concat(node1, node2);
        return node;
    }
    else{
        // subseq := star
        return node1;
    }
}

Node* seq(Token** ptok){
    // seq     := subseq | ''
    if((*ptok)->kind == TOKEN_LPAR ||
       (*ptok)->kind == TOKEN_CHARACTER){
        // seq := subseq
        return subseq(ptok);
    }
    else{
        // seq := ''
        return Character('\0');
    }
}

Node* star(Token** ptok){
    // star    := factor '*' | factor
    Node* node = factor(ptok);
    if((*ptok)->kind == TOKEN_ASTERISK){
        match(ptok, TOKEN_ASTERISK);
        node = Asterisk(node);
    }

    return node;
}

Node* factor(Token** ptok){
    // factor := '(' subexpr ')'
    if((*ptok)->kind == TOKEN_LPAR){
        match(ptok, TOKEN_LPAR);
        Node* node = subexpr(ptok);

        match(ptok, TOKEN_RPAR);

        return node;
    }

    // factor := CHARACTER
    else {
        Node* node = Character( *(*ptok)->s);

        match( ptok, TOKEN_CHARACTER);

        return node;
    }
}

int match(Token** ptok, enum Kind k){
    if ((*ptok)->kind == k){
        *ptok = (*ptok)->next;
        return 1;
    }
    fprintf(stderr, "syntax error\n");
    exit(1);
}

Node* Character(const char c){
    Node* node = malloc(sizeof(Node));

    node->kind = NODE_CHARACTER;
    node->c = c;
    node->l = NULL;
    node->r = NULL;

    return node;
}

Node* Concat(Node* node1, Node* node2){
    Node* node = malloc(sizeof(Node));

    node->kind = NODE_CONCAT;
    node->l = node1;
    node->r = node2;

    return node;
}

Node* Asterisk(Node* node1){
    Node* node = malloc(sizeof(Node));

    node->kind = NODE_ASTERISK;
    node->l = node1;
    node->r = NULL;

    return node;
}

Node* Union(Node* node1, Node* node2){
    Node* node = malloc(sizeof(Node));

    node->kind = NODE_UNION;
    node->l = node1;
    node->r = node2;

    return node;
}

(BNFの定義順と合わせるために実際のソースと順番を変えています)

regex/parser.c at main · ouharetaso/regex · GitHub

バイトコードへの変換

抽象構文木から仮想機械のバイトコードへの変換は次のように機械的に行なえます

  • NODE_CHARACTER (文字)c:
    char c
  • NODE_CONCAT (連接) e_1 e_2:
    e1 # bytecodes of e1
    e2 # bytecodes of e2
  • NODE_UNION (選択)(e_1|e_2):
    split L1, L2
L1: e1 # bytecodes of e1
    jmp L3
L2: e2 # bytecodes of e2
L3:
  • NODE_ASTERISK (繰り返し) e*:
L1: split L2, L3
L2: e # bytecodes of e
    jmp L1
L3: 

これに従って抽象構文木を命令列に変換します.私は再帰を使いました.

int convert(Node* node, Inst* inst, int* pos){
    switch(node->kind){
        case NODE_CHARACTER:
            (inst + *pos)->opcode = Char;
            (inst + *pos)->c      = node->c;
            (*pos)++;
            break;
        case NODE_CONCAT:
            convert(node->l, inst, pos);
            convert(node->r, inst, pos);
            break;
        case NODE_UNION:{
            int L1, L2, L3, L_Split, L_Jmp;

            (inst + *pos)->opcode = Split;
            L_Split = *pos;
            (*pos)++;
            L1 = *pos;

            convert(node->l, inst, pos);
            (inst + *pos)->opcode = Jmp;
            L_Jmp = *pos;
            (*pos)++;
            L2 = *pos;

            convert(node->r, inst, pos);
            L3 = *pos;
            (inst + L_Jmp)->x  = inst + L3;
            (inst + L_Split)->x = inst + L1;
            (inst + L_Split)->y = inst + L2;
            }
            break;
        case NODE_ASTERISK:{
            int L1, L2, L3;

            L1 = *pos;
            (inst + *pos)->opcode = Split;
            (*pos)++;
            L2 = *pos;

            convert(node->l, inst, pos);

            (inst + *pos)->opcode = Jmp;
            (inst + *pos)->x = inst + L1;
            (*pos)++;
            L3 = *pos;

            (inst + L1)->x = inst + L2;
            (inst + L1)->y = inst + L3;
            }
            break;
    }

    (inst + *pos)->opcode = Match;

    return 0;
}

case NODE_UNION:のところでsplitjmpを命令列に書き込むとき,その時点では引数の値(分割して実行する先や飛び先のアドレス)が決定していないのであとからどうにかする必要があります.

あとアロー演算子->を使いたくてキモい書き方をしています.ゆるして.

仮想機械を動かしてマッチング

仮想機械のシミュレートは例のサイト*2を参考にしました.Cでsplit命令をシミュレートするのめんどくさそうですよね.私はどうすれば良いのかよくわからなかったので例のサイトの実装をほぼそのまんま実装しました.本当に参考程度か? 違うのはchar '\0'(空文字)のとき任意の文字とマッチングさせるところです.(そうしないと拡張正規表現のa?を(|a)として表現できない)

int recursive(Inst* pc, char* sp){
    switch(pc->opcode){
        case Char:
            if(*sp != pc->c) {
                if( pc->c != '\0' ){
                    return 0;
                }
            }
            return recursive(pc+1, sp+1);
            break;
        case Match:
            return 1;
            break;
        case Jmp:
            return recursive(pc->x, sp);
            break;
        case Split:
            if(recursive(pc->x, sp)) return 1;
            return recursive(pc->y, sp);
            break;
    }
    return 0;
}

あとは生成した命令列とマッチングさせたい文字列をrecursive()に渡すと判定が出てきます.

感想

こうやって書き出してみると写経ばっかでほんとに自作か?って思うけどトークナイズと命令列の生成はじぶんでかけたし楽しかったのでOKだと思います.

あとは動的なメモリ確保がめんどくさいしガベージコレクタないしポインタの文法がクソだしで辛かったです.

おま○け

実行速度を測ってみます.ここ*3を参考に「正規表現a?ⁿaⁿつまり(|a)ⁿaⁿと,文字列aⁿ のマッチングにかかった時間 」を測定します.

環境
結果

nに対する実行時間のブラフ

ほぼ指数時間になりました.

参考文献

swtch.com qiita.com codezine.jp