ぱたへね

はてなダイアリーはrustの色分けができないのでこっちに来た

Python+JSON データ活用の奥義

Python+JSON データ活用の奥義が面白かったので紹介します。

Python+JSON データ活用の奥義 | クジラ飛行机 |本 | 通販 | Amazon

JSONを使ってあんなこと、こんなことをやってみようという本です。 とにかく扱っているトピックが広い。JSONを読み込んでグラフにして見る所から入り、ラズパイからの情報収集や、Webのスクレイピング、SNSの分析、QRコードを使ったクーポンサービス等、これでもかというくらいの事例が載っています。そのために必要なライブラリについても分かりやすくかいてあります。ラズパイ買うときの注意点や、スクレイピング時の注意点(岡崎市立中央図書館事件)等もしっかり書いてあります。素晴らしい。

表紙の雰囲気から、JSONの規格の細かいところとか、知られていないJSONテクニックとか、複数のプロセスで上手く読み書きする方法とかそういうのを期待して買ったのですが、期待と違う方向に突き抜けていて良かったです。ラズパイのLEDをJSONで制御するという文字を見たときに、狂気を感じました。とにかくJSONです。何をやるにもJSONです。

Pythonでどんなことが出来るかを知りたい人にお勧めです。ちょっと最近趣味プログラミングが進まないなという人にも、やってみよう的なアイデアが詰まっていました。

Pythonでセグメンテーションの領域を一回り大きく切り抜く

社内勉強会のネタにしようと思ったけど、せっかくなのでブログに書く。 既についているアノーテーションを一回り大きく取って、別の画像に張りつけるやりかたをまとめました。

Instance Segmatationのアノテーションを、一回り大きくくりぬきたいって時よくありますよね。 領域をくりぬいて資料に貼り付けるとか別の使い方をしたいときにギリで囲ってあると領域が見えなかったり、アノテーション雑すぎて対象物の境界情報がなくなってるとか。 ここで一回り大きくの定義を厳密に決めようすると難しいので、なんとなく一回り大きく取れていればOKくらいの感覚で先に進む。

入力データ

雑なアノーテーションで困ってます。

真面目な戦略

囲っている領域の点を全体的に外側に移動させれば良い。

ここで一つ問題がでてくる。

左側のような図形であれば真ん中から外側がなんとでも計算できるけど、右側のように凹凸がでてくると外側はどっちかをアルゴリズムで決める必要がある。

教科書的にやろうとすると多分こうなる。

  • 注目している点の2つの隣の点から線分を2つ作る。
  • 線分のなす角から真ん中の角度を求める。ここから点を動かす方向が2点に絞られる。
  • 両方の方向について、Segmentationで囲んだ領域の内側か外側かを判定する。これは専用のアルゴリズムがある。
  • 領域の外側に向かっている方向に、点を一定量移動させる。

だいぶ面倒。

画像処理のライブラリ使おう

手っ取り早く領域を広くする方法として、太い線で領域を描く方法と、領域に対してぼかす系のフィルターをかける方法がある。 太い線で十分だけど、そのあと別の画像に貼り付ける時はガウシアンフィルターが有効だったので両方紹介する。

左上が元々の領域。この領域を太い線で描画して、元の領域と重ね合わせると左中の領域になる。 線の太さ分だけ領域が大きくなっている。角が気になる場合は、角に丸を描画すると良い。

さらにぼかす系のフィルターとしてガウシアンフィルターをかけたものが左下の画像。ガウシアンフィルターの半径分だけ領域が増えている。これを合成用のアルファとして使う事で、合成を少しましにしている。ただ領域を増やしたいだけなら2値化すればよい。

どちらにしても広くする量をピクセルの単位で指定できるのがメリット。

何もしない場合

画像を読み込んで、背景画像を用意した後、マスク用の画像を用意する。 draw.polygon()で切り抜く領域をマスク用の画像に描画し、そのマスク用画像を使って合成する。

    bg = Image.new('RGB', (width, height), (0, 0, 255))

    # mask 画像を用意
    mask = Image.new("L", (width, height), 0)
    draw = ImageDraw.Draw(mask)
    draw.polygon(segment, fill=255)

    # maskを使って、背景に合成
    composite = Image.composite(im, bg, mask)

結果。アノーテーションの領域がそのまま貼り付けられる。

太い線で描く方法

draw.polygon()に引数widthがあるが、期待通りの動きをしないのでdraw.line()に太さを指定してマスク用画像を描画する。 draw.line()は塗りつぶしをしないので、線を引いた後、draw.polygon()で元々の領域を塗りつぶす。

    # 画像を太い線で広くする
    line_width = 30
    for i in range(len(segment)-1):
        draw.line((segment[i], segment[i+1]), fill=255, width=line_width)
    else:
        draw.line((segment[0], segment[-1]), fill=255, width=line_width)
    # 本来の場所の塗りつぶし
    draw.polygon(segment, fill=255)

結果。ちょっと領域が広くなっている。

ガウシアンフィルター

太い線を描いた後ガウシアンフィルターをかければOK。

    # 画像を太い線で広くする
    line_width = 30
    for i in range(len(segment)-1):
        draw.line((segment[i], segment[i+1]), fill=255, width=line_width)
    else:
        draw.line((segment[0], segment[-1]), fill=255, width=line_width)

    # ガウシアンフィルターをかける。
    mask = mask.filter(ImageFilter.GaussianBlur(radius=10))

結果。合成の境目にぼかしが入った。ぼかしは領域を広くする方向にのみ入る。(領域の内側はぼかしが聞いていない)。

効果が分かりやすいように単色背景にしているが、自然画像を背景にするとちょっと良さが分かると思う。やってみて。

ソースコード

import os
import PIL
from PIL import Image, ImageDraw, ImageFilter

input_file = 'img/sta.jpg'

# segmentationの座標リスト
segment = [(8, 1665), (98, 1515), (248, 1334), (430, 1187), (705, 1112), (1202, 1250), (1345, 1390), (1467, 1559), (1505, 1687), (736, 1965), (14, 2000)]


# 1. そのまま背景に合成する
def proc1():
    im = PIL.Image.open(input_file)

    # 画像のサイズを取得
    width, height = im.size
    # 青の背景を用意
    bg = Image.new('RGB', (width, height), (0, 0, 255))

    # mask 画像を用意
    mask = Image.new("L", (width, height), 0)
    draw = ImageDraw.Draw(mask)
    draw.polygon(segment, fill=255)

    # maskを使って、背景に合成
    composite = Image.composite(im, bg, mask)

    # 保存
    composite.save('img/proc1.jpg')

def proc2():
    im = PIL.Image.open(input_file)

    # 画像のサイズを取得
    width, height = im.size
    # 青の背景を用意
    bg = Image.new('RGB', (width, height), (0, 0, 255))

    # mask 画像を用意
    mask = Image.new("L", (width, height), 0)
    draw = ImageDraw.Draw(mask)

    # 画像を太い線で広くする
    line_width = 30
    for i in range(len(segment)-1):
        draw.line((segment[i], segment[i+1]), fill=255, width=line_width)
    else:
        draw.line((segment[0], segment[-1]), fill=255, width=line_width)
    # 本来の場所の塗りつぶし
    draw.polygon(segment, fill=255)

    # maskを使って、背景に合成
    composite = Image.composite(im, bg, mask)

    # 保存
    composite.save('img/proc2.jpg')

def proc3():
    im = PIL.Image.open(input_file)

    # 画像のサイズを取得
    width, height = im.size
    # 青の背景を用意
    bg = Image.new('RGB', (width, height), (0, 0, 255))

    # mask 画像を用意
    mask = Image.new("L", (width, height), 0)
    draw = ImageDraw.Draw(mask)

    # 画像を太い線で広くする
    line_width = 30
    for i in range(len(segment)-1):
        draw.line((segment[i], segment[i+1]), fill=255, width=line_width)
    else:
        draw.line((segment[0], segment[-1]), fill=255, width=line_width)

    # ガウシアンフィルターをかける。
    mask = mask.filter(ImageFilter.GaussianBlur(radius=10))
    draw = ImageDraw.Draw(mask)

    # 本来の場所の塗りつぶし
    draw.polygon(segment, fill=255)

    # maskを使って、背景に合成
    composite = Image.composite(im, bg, mask)

    # 保存
    composite.save('img/proc3.jpg')


if __name__ == '__main__':
    # 3つのアルゴリズムを比較する
    # 1. そのまま背景に合成する
    # 2. 画像を太い線で広くしてから合成する
    # 3. 2.に加え、ガウシアンフィルターをかけて合成する。

    # 1. そのまま背景に合成する
    proc1()
    # 2. 画像を太い線で広くしてから合成する
    proc2()

    # 3. 2.に加え、ガウシアンフィルターをかけて合成する。
    proc3()

初めての逆運動学

実践ロボット制御を読みながら、三章の脚ロボットの逆運動学をプログラミングしてみた。

実践 ロボット制御: 基礎から動力学まで | アールティ, 耕, 細田 |本 | 通販 | Amazon

数式は本を見てもらうとして、素直にコーディングするとこんな感じ。

まあまあそれっぽくは動いている。

ただ、このプログラムは、この範囲でしか上手く動かない。 少し範囲を変えるとこうなってしまう。

多分緑の角度を決めているθの符号が逆。

ここの角度にarccosを使っていて、cos(θ)=cos(-θ)だからかなと思ってる。

課題は2つ

  • θの符号はどう決めるか。
  • 単純にIKを解くだけだと、ロボがワープするから今の姿勢から最終姿勢までの連続として解かないといけない

4章以降で運動学の一般化の説明があるから、勉強続ければ分かると思う。

以下、コード。 アニメgif化するところはcopilotがだいたい書いてくれた。

import PIL
from PIL import Image, ImageDraw
import math
import numpy as np
import os
import glob

import matplotlib.pyplot as plt
import matplotlib.animation as animation

# キャンパスの大きさ
CANVAS_WIDTH = 300
CANVAS_HEIGHT = 300

GROUND = -80

PI = math.pi


class Robo1leg:
    def __init__(self):
        self.theta1 = PI / 8
        self.theta2 = - PI / 8
        self.theta3 = PI / 2
        self.l1 = 50
        self.l2 = 40
        self.l3 = 20

    def draw(self, canvas):
        draw = ImageDraw.Draw(canvas)
        # 本体
        cx0, cy0, cz0 = robo2canvas(0, 0, 0)
        draw.ellipse((cx0 - 10, cy0 - 10, cx0 + 10, cy0 + 10), fill=(0, 0, 0))

        # 足1
        x1 = self.l1 * math.sin(self.theta1)
        z1 = - self.l1 * math.cos(self.theta1)
        cx1, cy1, cz1 = robo2canvas(x1, 0, z1)
        draw.line((cx0, cy0, cx1, cy1), fill=(255, 0, 0), width=3)

        # 関節
        draw.ellipse((cx1 - 5, cy1 - 5, cx1 + 5, cy1 + 5), fill=(0, 0, 0))

        # 足2
        x2 = x1 + self.l2 * math.sin(self.theta2 + self.theta1)
        z2 = z1 - self.l2 * math.cos(self.theta2 + self.theta1)
        cx2, cy2, cz2 = robo2canvas(x2, 0, z2)
        draw.line((cx1, cy1, cx2, cy2), fill=(0, 255, 0), width=3)

        # 関節
        draw.ellipse((cx2 - 5, cy2 - 5, cx2 + 5, cy2 + 5), fill=(0, 0, 0))

        # 足3
        x3 = x2 + self.l3 * math.sin(self.theta3 + self.theta2 + self.theta1)
        z3 = z2 - self.l3 * math.cos(self.theta3 + self.theta2 + self.theta1)
        cx3, cy3, cz3 = robo2canvas(x3, 0, z3)
        draw.line((cx2, cy2, cx3, cy3), fill=(0, 0, 255), width=3)

    def get_leg_pos(self):
        x1 = self.l1 * math.sin(self.theta1)
        z1 = - self.l1 * math.cos(self.theta1)
        x2 = x1 + self.l2 * math.sin(self.theta2 + self.theta1)
        z2 = z1 - self.l2 * math.cos(self.theta2 + self.theta1)
        x3 = x2 + self.l3 * math.sin(self.theta3 + self.theta2 + self.theta1)
        z3 = z2 - self.l3 * math.cos(self.theta3 + self.theta2 + self.theta1)

        return x3, z3

    def inverse_kinematics(self, x, y, z):
        theta1 = math.atan2(
            (self.l1 + self.l2 * math.cos(self.theta2)) * x + self.l2 * math.sin(self.theta2) * z,
            (self.l2 * math.sin(self.theta2) * x - (self.l1 + self.l2 * math.cos(self.theta2)) * z)
        )
        tmp = (x**2 + z**2 - self.l1**2 - self.l2**2) / (2 * self.l1 * self.l2)
        theta2 = math.acos(tmp)
        theta3 = (PI / 2) - theta1 - theta2

        return theta1, theta2, theta3

class World:
    def __init__(self):
        # 画像内でxは右が正、zは上が正、yは手前が正
        self.origin_x = int(CANVAS_WIDTH / 2)
        self.origin_z = int(CANVAS_HEIGHT / 2)
        self.output_dir = 'result'

        self.robo_x = 0
        self.robo_y = 0
        self.robo_z = 0
        self.robo = None

    def add_robo(self, robo):
        self.robo = robo

    def draw(self, time):
        canvas = Image.new('RGB', (CANVAS_WIDTH, CANVAS_HEIGHT), (255, 255, 255))
        self.robo.draw(canvas)

        gx, gy, gz = robo2canvas(0, 0, GROUND)
        draw = ImageDraw.Draw(canvas)
        draw.line((0, gy, CANVAS_WIDTH, gy), fill=(0, 0, 0), width=1)

        file_name = os.path.join(self.output_dir, 'result_{0:03d}.png'.format(time))
        canvas.save(file_name, 'PNG')



def robo2canvas(robo_x, robo_y, robo_z):
    """ロボの座標を画像上のx, yに変換する。"""
    rot_mat = np.array([[1, 0, 0, CANVAS_WIDTH / 2],
                        [0, 0, -1, CANVAS_HEIGHT / 2],
                        [0, 0, 0, 0]])

    pos = rot_mat.dot(np.array([robo_x, robo_y, robo_z, 1]))
    return pos[0], pos[1], pos[2]

def create_animation(output):
    fig = plt.figure()

    pictures = glob.glob("result/*.png")

    ims = []
    for i in range(len(pictures)):
        # 読み込んで付け加えていく
        tmp = Image.open(pictures[i])
        ims.append([plt.imshow(tmp)])

    ani = animation.ArtistAnimation(fig, ims, interval=500)
    ani.save(os.path.join('result', output))


if __name__ == '__main__':
    robo = Robo1leg()
    world = World()
    world.add_robo(robo)

    px0, pz0 = 40, GROUND
    theta1, theta2, theta3 = robo.inverse_kinematics(px0, 0, pz0)
    robo.theta1 = theta1
    robo.theta2 = theta2
    robo.theta3 = theta3

    print("robo pos = ", px0, pz0)
    pxf = - px0
    pzf = pz0
    step = 16

    for t in range(0, step):

        # zを一定にして逆運動学で目標位置を求める
        px = px0 + (pxf - px0) * t / step
        pz = pz0 + (pzf - pz0) * t / step
        print("target pos = ", px, pz)

        theta1, theta2, theta3 = robo.inverse_kinematics(px, 0, pz)
        robo.theta1 = theta1
        robo.theta2 = theta2
        robo.theta3 = theta3
        world.draw(t)

    create_animation('result.gif')

初心者が言語モデルを勉強するための本(2023年6月版)

流行のLLMを勉強したくて沢山本を読みました。 この後もしばらくLLM(GPT)関係の出版が続きそうなので、現状の本でまとめてみました。

参考:

nowokay.hatenablog.com

まとめ。

  • Transformerの仕組みを知りたい人で、画像のDeep Learningなら分かるって人はVision Transformer入門
  • 言語モデルをデータセットを作る所からやってみたい人には、作ってわかる! 自然言語処理AI
  • とにかくすぐに動かしたい人には、機械学習エンジニアのためのTransformers
  • ビジネス的に何ができるのかを知りたい人はBERT入門

Vision Transformer入門

Vison Transformerになっていますが、Transformerの説明がとても詳しくお勧めです。実際に写経してパーツパーツで動かせるのはこの本だけ。Transformer一点突破なので、一般的な言語処理の説明は弱いのですが、それを差し引いてもTransformerの説明が一番分かりやすかったです。特にDeep Learningが画像から入った人には、CNNとの比較もありすごく分かりやすかったです。

後半は事例になっていて、実際にTransformerを記述するところはボリューム無いので動かして見るにはちょうど良いと思います。

言語モデルを動かさないと意味が無いって人には、次の作ってわかる! 自然言語処理AIがお勧め。

gihyo.jp

作ってわかる! 自然言語処理AI

写経してTransformerを理解した人にお勧め。word2vecとそれ以降の言語モデルの違い等、理論的な所もしっかり押さえてあります。自分でwikipediaのデータをダウンロードして学習して行きます。Transformerのアーキテクチャだけでなく、学習データの作り方までしっかりわかるのはこの本だけ。いろいろあるAttentionの違いがちゃんと説明してあるのもこの本だけでした。

自分で言語モデルを1から学習したい人にお勧めです。

www.c-r.com

機械学習エンジニアのためのTransformers

何か動かしたくて、一冊だけ買うならこの本です。Transformersはライブラリの名前です。複数形なので区別がつくはず。

Transformers(ライブラリ)の使い方、Transfsormersで解けるタスクの紹介と実際の動かし方、ONNXやプルーニングを使った高速化手法まで、盛りだくさんの内容になっています。

Transformer自体の説明もちゃんとあります。個々の説明が駆け足にも関わらず、要所要所で技術的な鋭い補足が入っています。

具体的にやりたいことがあって最短距離進みたいならこの本しか無いですね。

www.oreilly.co.jp

ディープラーニングによる自然言語処理

Transformerメインではなく、自然言語処理全般について書かれている本。 AllenNLPというライブラリを使っていて、取り扱っているトピックの割には本が薄めになっていて読みやすいです。最後はBERTまで。薄いながらも評価基準がしっかり書いてあって、しれっとoptunaも使っています。

LSTMの説明もしっかりしてあり、Transformerを動かすのではなく、Deep Learningを使った言語処理の研究をしたい人向けでした。

www.kyoritsu-pub.co.jp

BERT入門

言語モデルが解くべきタスクの説明や、データアセスメントについてよくまとまっていました。本格的に動かす前に、言語モデルが何できるのかを知りたいビジネス寄りの人にお勧め。実装に関しては、Vision Transformer入門 (Computer Vision Library) が分かりやすいと思う。

www.nttdata.com

深層学習からマルチモーダル情報処理

not for meだった本。 深層学習について、誤差関数とか基本的な所から詳しく説明されています。ただ、JDLAのE資格もっていれば全部知っている内容でした。

また、期待していたマルチモーダル部分についてもあまり記載がなく残念でした。もう少し、マルチモーダル故の課題とか、解決策が載っていて欲しかった。

www.saiensu.co.jp

ChatGPTで中国語の勉強をしている

ChatGPTが中国語の勉強にとても役に立っているという話。

読んでいる本は機械学習 周 志華、最近翻訳も出てます。

機械学習 | 周 志華, 大和田 勇人, 玄 光男, 下川 朝有, 郝 新厂, 張 聞強 | コンピュータ・IT | Kindleストア | Amazon

このアンサンブル学習の章で「而基学习器有时也被直接称为弱学习器」という文が出てきて、僕の中国語レベルだとかなり難しい。 更に悪いことに呼ぶ(称する)という意味の称を、あなたという意味の你だと思ってしまって全く意味が取れない。

まずはChatGPTに聞いてみると、間違いを指摘してくれた上で意味を教えてくれる。

ここまでやってもらっても文の構造がわからないので、更に聞いてみる。

これはすごい。

  • 機械学習の文脈と専門用語が分かってる
  • 動詞フレーズなど学習者向けの表現で文法が説明できる
  • ピン音が全部振ってある

これを同時に満たしてくれる中国語の先生は僕の近くにはいないんじゃないかと思う。 勉強はかどる。

エンジニアのためのドキュメントライティング

エンジニアのためのドキュメントライティング読みました。 最近の仕事の悩みに対して、方向性を示してくれた良い本でした。

www.amazon.co.jp

自分のチーム内にドキュメントの文化が無い人にお勧めします。 全体のざっくりした感想だと、この手の本にありがちな小言っぽいことは書いてなく、作って意味のあるドキュメントはどうあるべきかを書いてあります。仕事のドキュメントで悩んでいる人には、具体的な取り組みのアイデアがいっぱい見つかるでしょう。

背景

うちの会社は転職者が多く、開発への考え方がバラバラ。当然、ドキュメントに対する考え方もバラバラで必要なドキュメントがなかなか揃わない。今の仕事は各部署からの寄せ集めチームでもあり、ドキュメントのテンプレートみたいなものもない。

世代間の格差も結構ある。ベテラン勢はドキュメントは印刷され保管される前提であり、表示にバージョン、日付、部署、作成者などを明記するべきだと思ってる。ドキュメントの承認印的な物が欲しい人もいる。一方若い人はドキュメントはVCSに組み込まれる物であって、作成日や作成者の情報はVCSで持っておけば良いという考え方があり、ドキュメントに作成者などを書かない。

若手の言い分もわかるけど、社外に出て行く文章はバージョン管理いるでしょう・・・みたいな悩みを抱えていたところ、この本を見つけました。この前に、Googleのソフトウェアエンジニアリングを読んで、ドキュメントについて考えることがあったけど、googleの本に書いてある事は大概の会社には当てはまらない。Googleのようにドキュメントの作成や管理をスケールさせる意味はまずない。

そんな感じでもやもやしているところでこの本を買って読むことにしました。

良いところ

ドキュメントの作り方みたいな本は、結構小難しいことがかいてあります。ドキュメントには承認プロセスが必要とかなんやらかんやら、用語の定義はこうしろ、フォントはこう使い分けようなんやらかんやら。こういうのは大企業のドキュメント管理を専用にする部署向けであったり正しいドキュメントを書くためのルールだったりします。エンジニアの気持ちやそれが何の役に立つのという観点はあまり考慮されないパターンが多いです。そもそもドキュメントを書きたくないという気持ちから目を背けてます。

この本はスタートアップの会社がWebサービスを公開するというシチュエーションでドキュメントの書き方と運用について書かれています。アメリカの本にありがちな謎の寸劇っぽい部分がすごく短く読みやすいです。堅い本に比べると、なぜ正確なドキュメントが必要なのかという点は説明少なめです。まあ、この本を読んでいる時点で何かしらの課題を持っているはずなので、ドキュメントの重要性をくどくどと書いてないのは良い。

書く側の気の持ちよう的な所が書いてあって、レビューする側、される側の心構えも書いてありました。作成したドキュメントがどれだけ役に立ったかの計測についても結構な量があり、お堅い本にはでてこないトピックで勉強になりました。

とにかく「ドキュメントを書く」事を目的とせず「ドキュメントを運用する」事にフォーカスされています。

関心した所

ドキュメントを書くに当たって

ドキュメントは開発していく物。コードと同じ。 大事なのは一貫性。用語、見出し等、一貫性があると読みやすい。 ドキュメントは流し読みしやすいように書く。 一回で良い物を作ろうとしない、文章で悩むくらいならレビューしてもらって他人に指摘してもらった方が早い。

手順書

一度開発者が正確に書いてから、ユーザー目線で改善していく。このやり方を作成者も意識していると、頑張って書いた手順書に対してわかりにくいという指摘も受け入れやすい。ユーザーの立場で正確に手順を書くというのはできないので正確に書くのは開発者、その後分かりやすい手順書にするのはユーザーの立場の人という分担は直ぐにでもチームに投入したい。

API

APIのドキュメントは大事だ。この本はWebサービス前提だが、何か開発した物に対して使い方がわかるドキュメントが大事なことはWebサービスに限らない。

APIのドキュメントを書くための専用のトレーニングコースまである。 https://idratherbewriting.com/learnapidoc/

サンプルコード

サンプルコードは、説明したいこと(もしくは動かしたいこと)に特化する。小粋なアルゴリズムは不要。 クラス名や変数名は、your_password等普段使わない説明的な名前をつかってもOK。

まとめ

本の章立てはドキュメントを作るところが前半、後半は運用について書かれています。 今、自分のプロジェクトでドキュメントについて悩みがあるなら、該当する箇所、もしくは今後ぶつかるであろう課題について書いてあります。

ドキュメントもチームの文化なので、良いチーム文化を作るためにも、みんなで納得しながらドキュメント作りたいですね。

自作コンパイラで演算子の優先順位をつけた

自作コンパイラでC言語の演算子に優先順位をつけました。

これの続き

natsutan.hatenablog.com

低レイヤを知りたい人のためのCコンパイラ作成入門には詳しい説明がなく、テキストの範囲ではバイナリオペレータに優先順位はほとんどついてないと思います。足し算よりかけ算優先くらい。 手持ちの教科書にあんまり詳しく載っていないのは、足し算とかけ算の優先順位付けられるなら後は分かるでしょって事だと思う。

2023/03/18追記 すいません。理解してから低レイヤを知りたい人のためのCコンパイラ作成入門を見たら、ちゃんと優先順位ついてました。論理AND等が無いこととごっちゃになってました。

自作コンパイラで優先順位がつくようになったでまとめました。

そもそも優先順位をどうつけているか

かけ算と足し算の優先順位付けは、この文法から来ています。

expr : term { + term }
term : factor { * factor }
factor : ID | '(' expr ')'

一般的にk個の優先順位をつけるためには、非終端のルールがk+1個必要になります。かけ算と足し算で2つの優先順位があるので、非終端の文法が3つ必要になります。

C言語の演算子

Retargetable C Compilerに実装方法が載ってました。

www.amazon.com

C言語の演算子の優先順位は15段階になっています。 パース関数については後述。優先順位は値が大きい方(表の下)が優先順位が高い。

優先順位 結合 演算子 パース関数
1 , expr
2 = += -= *= /= %= &= ^= |= <<= >>= expr1
3 ?: expr2
4 || expr3
5 && expr3
6 | expr3
7 ^ expr3
8 & expr3
9 == != expr3
10 < > <= >= expr3
11 << >> expr3
12 + - expr3
13 * / % expr3
14 * & - + ! ~ ++ -- sizeof (type-cast) unary
15 ++ -- postfix

今、バイナリオペレータの優先順位をつけたいので、優先順位4から13までを処理したい。 ざっくりというと、優先順位が15レベルあれば文法を16個作れば優先順位をつけてパースできる理屈になります。

優先順位の数だけ関数を作っても良いけど、ほとんど同じ内容の関数がたくさん出てきて面倒だよねということで、Retargetable C Compilerにでてくるパーサは優先順位4から13までを、expr3という一つの関数で捌いています。

LCCの実装

Retargetable C Compilerに出てくるLCCの実装はこうなっています。 exprで再帰するときに優先順位を渡して、その優先順位を使って一つの関数でパースしています。

void expr(int k) {
 if (k > 13) 
     factor();
  else {
    expr(k+1);
    while(prec[t] == k) {
      t - gettok();
      expr(k + 1);
  }
}

precが優先順位のテーブルになっていて、prec['+']だと12を返します。

なるほど、わからない。

実装してみた

F#でwhileを使うのが苦手なので、愚直に文法増やして対応しました。 こんな感じです。

 expr = logicaland { || logicaland }
 logicaland = bitwiseor { && bitwiseor }
 bitwiseor = bitwisexor { | bitwisexor }
 bitwisexor = bitwiseand { ^ bitwiseand }
 bitwiseand = equality { & equality }
 equality = relational { == relational }
            relational { != relational }
 relational = shifting { < shifting }
              shifting { > shifting }
              shifting { >= shifting }
              shifting { <= shifting }
 shifting = additive { << additive }
            additive { >> additive }
 (省略)
 factor = num
        | ( expr )

ソースのコピペ連発でしたが、低レイヤを知りたい人のためのCコンパイラ作成入門の経験から、ここは一度作ればあとから直したくなることがないと判断しました。まずは動く物を作ろう。

こうやって文法を足した結果、こういう計算がgccの結果と一致するようになりました。

int main(void) {
  putd(15 << 2 == 15 >> 2);
  return 0;
}

次は変数とアサインの実装。

ソースはここ

github.com