AIに頼って自作プログラミング言語を作る 第１回

字句解析器編です。

はじめに

第1回目ということで今回は字句解析器を作成していきます。
前回のコンセプト確認では見た目がわかりやすくpython風の言語で最初は四則演算や代入が行えるくらいのものということで開発することにしました。

四則演算をするといっても、例えば

a = 1 + 2

といったようなコードでもそこに変数を表す文字、数字、演算子などの要素があります。それをプログラムが理解するために、まずはそれぞれのトークンに分けて、どんな要素が含まれているのかを確認する必要があります。そのためのプログラムが字句解析器です。(たぶん)

字句解析とは？

プログラミング言語の処理は大きく分けて3段階あります。
字句解析→構文解析→実行（インタプリタ/コンパイラなど）

この中の字句解析では「連続した文字列」を「意味のある語（トークン）」に分ける必要があります。
例えば先ほどの

a = 1 + 2

であれば、

INDENT(a),ASSIGN(=),NUMBER(1),PLUS(+),NUMBER(2)

といったようにタイプが分類され、それぞれに値が収納されます。これが字句解析です。

コード

最初のコードは以下の通りです。

import re  # 正規表現ライブラリ（文字列のパターンを使って抽出できる）
from typing import List, NamedTuple


# トークンを表す構造。1つのトークンには type（種類）と value（実際の値）がある
class Token(NamedTuple):
    type: str  # 例: "IDENT", "NUMBER", "PLUS"
    value: str  # 例: "a", "123", "+"


TOKEN_SPEC = [
    # キーワードはインデントの前に書く
    ("IF",        r'\bif\b'),
    ("WHILE",     r'\bwhile\b'),
    
    #その他のトークン
    ("NUMBER",    r'\d+'),                  # 1つ以上の数字
    ("IDENT",     r'[A-Za-z_][A-Za-z0-9_]*'),  # 識別子: 変数名や関数名など
    ("ASSIGN",    r'='),                    # 代入演算子
    ("PLUS",      r'\+'),                   # 足し算演算子
    ("MINUS",     r'-'),
    ("MULT",      r'\*'),
    ("DIV",       r'/'),
    ("LPAREN",    r'\('),                   # 左括弧
    ("RPAREN",    r'\)'),
    ("NEWLINE",   r'\n'),                   # 改行（必要なら）
    ("SKIP",      r'[ \t]+'),               # 空白やタブは無視する
    ("MISMATCH",  r'.'),                    # 上記以外 → エラー
]



# 正規表現の各パターンを結合して1つの巨大なパターンにする
token_re = re.compile(
    "|".join(f"(?P<{name}>{pattern})" for name, pattern in TOKEN_SPEC)
)


def tokenize(code: str) -> List[Token]:
    tokens = []
    for mo in token_re.finditer(code):  # 1つ1つマッチするものを順に探す
        kind = mo.lastgroup             # どの名前（type）にマッチしたか
        value = mo.group()              # 実際に一致した文字列
        if kind == "SKIP":
            continue                    # 空白・タブは無視
        elif kind == "MISMATCH":
            raise RuntimeError(f'不正な文字: {value!r}')  # 想定外の文字はエラー
        else:
            tokens.append(Token(kind, value))  # トークンとして追加
    return tokens

Tokenクラスは種類(type)と値(value)を持つ構造体になっています。

TOKEN_SPECはトークンごとに分けるキーワードや文字などを設定します。必要な要素はここに正規表現で追加していくことで増やせます。"SKIP"や"MISMATCH"などで無視やエラー処理を指定します。

ifやwhileなどはINDENTと被るため、先に定義する必要があるそうです。

これで試しにa = 1 + 2をかけてみると、

Token(type='IDENT', value='a')
Token(type='ASSIGN', value='=')
Token(type='NUMBER', value='1')
Token(type='PLUS', value='+')
Token(type='NUMBER', value='2')

といった感じに出力されます。

次回

次回はこれをもとに構文解析器(Parser)を作っていきます。
たとえば、a = 1 + 2を代入ノードであるといったように解釈するような仕組みを作成します。

ソースコードは文字列でできていますが、プログラムにとっては「言葉の並び」として理解する必要があるということで、今回は「言葉」を理解するための字句解析器を作りました。構文解析ではこの言葉の並びを「文の構造」として理解できるようにするそうです。

作っている側がまだ、完全には理解していませんが今回はここで終わりになります。
ありがとうございました。