Pythonで簡易PL/0処理系

はじめに

PL/0処理系を、Python 3.10.6 で簡易実装する。
ここではコードの説明しかしないので、用語や概念の説明については別ページを参照(字句解析、構文解析など)。

字句解析

トークンは、数値、識別子、キーワードの3種とする。それぞれに別のクラスを割り当てて区別できるようにする。数値はint、キーワードはstr、識別子は専用クラスを準備。

@dataclass
class Ident:
    id: str

字句解析は、正規表現で分割して、該当クラスに変換して、yieldで1つずつ返している。キーワードは大文字小文字区別しない仕様とする。

def scan(text: str) -> Iterator[int | str | Ident]:
    pattern = re.compile(r'\s*(?:((?:const|var|procedure|call|begin|end|if|then|while|do|odd)\b|[-.=,;?!#+*/()]|:=|<=?|>=?)|([0-9]+)|(\w+))', re.I)
    for m in pattern.finditer(text):
        if m[2]:
            yield int(m[2])
        elif m[3]:
            yield Ident(m[3])
        else:
            yield m[1].lower()

構文解析

LL(1)文法なので、再帰下降構文解析を使う。WikipediaにPL/0の構文解析コードが載っているので、必要な処理を追加しつつ流用する。

1回先読みができる必要があるので、字句解析の結果にmore_itertools.peekableをかぶせて使う。ast.fix_missing_locationsは、コンパイル時にエラーにならないようにするおまじない。

def parse(i: Iterable[int | str | Ident]) -> ast.Module:
    return ast.fix_missing_locations(program(more_itertools.peekable(i)))

先読み可能イテレータの型に別名をつけておく。実行時は要素型指定できないので、型チェック時のみ。

if TYPE_CHECKING:
    Scanner: TypeAlias = more_itertools.more.peekable[int | str | Ident]

accept、expectを移植。型指定とキーワード指定を別関数にする。キーワードは想定値の候補を引数でまとめて指定できるようにする。

T = TypeVar('T')

def accept_t(s: 'Scanner', t: type[T]) -> T | None:
    if isinstance(s.peek(), t):
        return cast(T, next(s))
    return None

def expect_t(s: 'Scanner', t: type[T]) -> T:
    if (a := accept_t(s, t)) is not None:
        return a
    raise SyntaxError

def accept(s: 'Scanner', *ss: str) -> str | None:
    if s.peek() in ss:
        return cast(str, next(s))
    return None

def expect(s: 'Scanner', *ss: str) -> str:
    if a := accept(s, *ss):
        return a
    raise SyntaxError

ここから先は、ASTが絡むので次で説明。

AST(抽象構文木)に変換

構文解析の結果を、PythonのASTに変換してしまう。

factorからconditionは、ほぼ素直に変換できる。

def factor(s: 'Scanner') -> ast.expr:
    if i := accept_t(s, Ident):
        return ast.Name(i.id, ast.Load())
    elif (n := accept_t(s, int)) is not None:
        return ast.Constant(n, None)
    elif accept(s, '('):
        e, _ = expression(s), expect(s, ')')
        return e
    else:
        raise SyntaxError

def term(s: 'Scanner') -> ast.expr:
    ret = factor(s)
    while o := accept(s, '*', '/'):
        ret = ast.BinOp(ret, {'*': ast.Mult, '/': ast.FloorDiv}[o](), factor(s))
    return ret

def expression(s: 'Scanner') -> ast.expr:
    if o := accept(s, '+', '-'):
        ret: ast.expr = ast.UnaryOp({'+': ast.UAdd, '-': ast.USub}[o](), term(s))
    else:
        ret = term(s)
    while o := accept(s, '+', '-'):
        ret = ast.BinOp(ret, {'+': ast.Add, '-': ast.Sub}[o](), term(s))
    return ret

def condition(s: 'Scanner') -> ast.expr:
    if accept(s, 'odd'):
        return ast.BinOp(expression(s), ast.BitAnd(), ast.Constant(1, None))
    else:
        e1, o, e2 = expression(s), expect(s, '=', '#', '<', '<=', '>', '>='), expression(s)
        return ast.Compare(e1, [{'=': ast.Eq, '#': ast.NotEq, '<': ast.Lt, '<=': ast.LtE, '>': ast.Gt, '>=': ast.GtE}[o]()], [e2])

statementは、英語版のWikipediaの構文規則をベースに実装している。入出力(?,!)を追加しないと、実行結果を確認できないため。

def statement(s: 'Scanner') -> Iterator[ast.stmt]:
    if i := accept_t(s, Ident):
        _, e = expect(s, ':='), expression(s)
        yield ast.Assign([ast.Name(i.id, ast.Store())], e, None)
    elif accept(s, 'call'):
        yield ast.Expr(ast.Call(ast.Name(expect_t(s, Ident).id, ast.Load()), [], []))
    elif accept(s, '?'):
        yield ast.Assign([ast.Name(expect_t(s, Ident).id, ast.Store())], ast.Call(ast.Name('int', ast.Load()), [ast.Call(ast.Name('input', ast.Load()), [], [])], []))
    elif accept(s, '!'):
        yield ast.Expr(ast.Call(ast.Name('print', ast.Load()), [expression(s)], []))
    elif accept(s, 'begin'):
        while True:
            yield from statement(s)
            if not accept(s, ';'): break
        expect(s, 'end')
    elif accept(s, 'if'):
        c, _, t = condition(s), expect(s, 'then'), list(statement(s))
        yield ast.If(c, t, [])
    elif accept(s, 'while'):
        c, _, t = condition(s), expect(s, 'do'), list(statement(s))
        yield ast.While(c, t, [])

ここでblockの実装となるが、大きな問題がある。PL/0だと、ネストした関数の外側にある変数に直接代入できるが、Pythonだとできない。nonlocalで事前に指定すれば可能だが、実際に代入を行っている変数のみ指定しないとエラーとなる。仕方ないので、ASTをたどって代入を行っている変数を抽出する関数を作っておく。

def collect_store(exprs: Iterable[ast.AST]) -> Iterator[str]:
    for expr in exprs:
        for node in ast.walk(expr):
            if isinstance(node, ast.Name) and isinstance(node.ctx, ast.Store):
                yield node.id

また、nonlocalは事前に定義された変数にしか使えないので、関数の先頭でNoneを代入しておく。これでようやくblockが書ける。

def block(s: 'Scanner') -> Iterator[ast.stmt]:
    c, v, p, t = list(const(s)), list(var(s)), list(procedure(s)), list(statement(s))
    if nonlocal_vars := set(collect_store(t)) - set(collect_store(v)):
        yield ast.Nonlocal(list(nonlocal_vars))
    yield from c
    yield from v
    yield from p
    yield from t

def const(s: 'Scanner') -> Iterator[ast.stmt]:
    if accept(s, 'const'):
        while True:
            i, _, e = expect_t(s, Ident), expect(s, '='), expression(s)
            yield ast.Assign([ast.Name(i.id, ast.Store())], e, None)
            if not accept(s, ','): break
        expect(s, ';')

def var(s: 'Scanner') -> Iterator[ast.stmt]:
    if accept(s, 'var'):
        targets = []
        while True:
            targets.append(ast.Name(expect_t(s, Ident).id, ast.Store()))
            if not accept(s, ','): break
        expect(s, ';')
        yield ast.Assign(targets, ast.Constant(None, None))

def procedure(s: 'Scanner') -> Iterator[ast.stmt]:
    while accept(s, 'procedure'):
        i, _, b, _ = expect_t(s, Ident), expect(s, ';'), list(block(s)), expect(s, ';')
        yield ast.FunctionDef(i.id, ast.arguments([], [], None, [], [], None, []), b, [], None, None)

最後に、programを実装する。nonlocalはグローバル変数には使えないので、全体をmain関数定義で囲ったうえで、mainを呼び出す形とする。

def program(s: 'Scanner') -> ast.Module:
    b, _ = list(block(s)), expect(s, '.')
    return ast.Module([ast.FunctionDef('main', ast.arguments([], [], None, [], [], None, []), b, [], None, None),
                       ast.Expr(ast.Call(ast.Name('main', ast.Load()), [], []))], [])

実行

PythonのASTに変換できてしまえば、あとはcompileしてexecするだけ。とりあえず標準入力からPL/0ソースを読む仕様とする。

exec(compile(parse(scan(sys.stdin.read())), '', 'exec'))

ちなみに、以下のように書き換えると、実行する代わりに変換後のPythonコードを表示する。

print(ast.unparse(parse(scan(sys.stdin.read()))))

ASTの表示も可能(コードが長いと見づらいが)。

print(ast.dump(parse(scan(sys.stdin.read())), indent=2))

Wikipediaにある使用例の最初のコードをPythonコードに変換した結果が以下。

def main():
    x = squ = None

    def square():
        nonlocal squ
        squ = x * x
    x = 1
    while x <= 10:
        square()
        print(squ)
        x = x + 1
main()

問題点

• 行番号などを保存していないので、エラーが起きても、どこでエラーになったのか分からない。
• print、input、intという定数・変数・関数を定義すると、入出力ができなくなる。
• 未定義定数・変数・関数のチェックをしていない。未定義のmain関数・構文解析用の関数を呼び出せてしまう。

ソースコード

import re
import ast
import sys
import more_itertools
from dataclasses import dataclass
from collections.abc import Iterator, Iterable
from typing import TYPE_CHECKING, TypeAlias, TypeVar, cast

@dataclass
class Ident:
    id: str

def scan(text: str) -> Iterator[int | str | Ident]:
    pattern = re.compile(r'\s*(?:((?:const|var|procedure|call|begin|end|if|then|while|do|odd)\b|[-.=,;?!#+*/()]|:=|<=?|>=?)|([0-9]+)|(\w+))', re.I)
    for m in pattern.finditer(text):
        if m[2]:
            yield int(m[2])
        elif m[3]:
            yield Ident(m[3])
        else:
            yield m[1].lower()

def parse(i: Iterable[int | str | Ident]) -> ast.Module:
    return ast.fix_missing_locations(program(more_itertools.peekable(i)))

if TYPE_CHECKING:
    Scanner: TypeAlias = more_itertools.more.peekable[int | str | Ident]

T = TypeVar('T')

def accept_t(s: 'Scanner', t: type[T]) -> T | None:
    if isinstance(s.peek(), t):
        return cast(T, next(s))
    return None

def expect_t(s: 'Scanner', t: type[T]) -> T:
    if (a := accept_t(s, t)) is not None:
        return a
    raise SyntaxError

def accept(s: 'Scanner', *ss: str) -> str | None:
    if s.peek() in ss:
        return cast(str, next(s))
    return None

def expect(s: 'Scanner', *ss: str) -> str:
    if a := accept(s, *ss):
        return a
    raise SyntaxError

def factor(s: 'Scanner') -> ast.expr:
    if i := accept_t(s, Ident):
        return ast.Name(i.id, ast.Load())
    elif (n := accept_t(s, int)) is not None:
        return ast.Constant(n, None)
    elif accept(s, '('):
        e, _ = expression(s), expect(s, ')')
        return e
    else:
        raise SyntaxError

def term(s: 'Scanner') -> ast.expr:
    ret = factor(s)
    while o := accept(s, '*', '/'):
        ret = ast.BinOp(ret, {'*': ast.Mult, '/': ast.FloorDiv}[o](), factor(s))
    return ret

def expression(s: 'Scanner') -> ast.expr:
    if o := accept(s, '+', '-'):
        ret: ast.expr = ast.UnaryOp({'+': ast.UAdd, '-': ast.USub}[o](), term(s))
    else:
        ret = term(s)
    while o := accept(s, '+', '-'):
        ret = ast.BinOp(ret, {'+': ast.Add, '-': ast.Sub}[o](), term(s))
    return ret

def condition(s: 'Scanner') -> ast.expr:
    if accept(s, 'odd'):
        return ast.BinOp(expression(s), ast.BitAnd(), ast.Constant(1, None))
    else:
        e1, o, e2 = expression(s), expect(s, '=', '#', '<', '<=', '>', '>='), expression(s)
        return ast.Compare(e1, [{'=': ast.Eq, '#': ast.NotEq, '<': ast.Lt, '<=': ast.LtE, '>': ast.Gt, '>=': ast.GtE}[o]()], [e2])

def statement(s: 'Scanner') -> Iterator[ast.stmt]:
    if i := accept_t(s, Ident):
        _, e = expect(s, ':='), expression(s)
        yield ast.Assign([ast.Name(i.id, ast.Store())], e, None)
    elif accept(s, 'call'):
        yield ast.Expr(ast.Call(ast.Name(expect_t(s, Ident).id, ast.Load()), [], []))
    elif accept(s, '?'):
        yield ast.Assign([ast.Name(expect_t(s, Ident).id, ast.Store())], ast.Call(ast.Name('int', ast.Load()), [ast.Call(ast.Name('input', ast.Load()), [], [])], []))
    elif accept(s, '!'):
        yield ast.Expr(ast.Call(ast.Name('print', ast.Load()), [expression(s)], []))
    elif accept(s, 'begin'):
        while True:
            yield from statement(s)
            if not accept(s, ';'): break
        expect(s, 'end')
    elif accept(s, 'if'):
        c, _, t = condition(s), expect(s, 'then'), list(statement(s))
        yield ast.If(c, t, [])
    elif accept(s, 'while'):
        c, _, t = condition(s), expect(s, 'do'), list(statement(s))
        yield ast.While(c, t, [])

def collect_store(exprs: Iterable[ast.AST]) -> Iterator[str]:
    for expr in exprs:
        for node in ast.walk(expr):
            if isinstance(node, ast.Name) and isinstance(node.ctx, ast.Store):
                yield node.id

def block(s: 'Scanner') -> Iterator[ast.stmt]:
    c, v, p, t = list(const(s)), list(var(s)), list(procedure(s)), list(statement(s))
    if nonlocal_vars := set(collect_store(t)) - set(collect_store(v)):
        yield ast.Nonlocal(list(nonlocal_vars))
    yield from c
    yield from v
    yield from p
    yield from t

def const(s: 'Scanner') -> Iterator[ast.stmt]:
    if accept(s, 'const'):
        while True:
            i, _, e = expect_t(s, Ident), expect(s, '='), expression(s)
            yield ast.Assign([ast.Name(i.id, ast.Store())], e, None)
            if not accept(s, ','): break
        expect(s, ';')

def var(s: 'Scanner') -> Iterator[ast.stmt]:
    if accept(s, 'var'):
        targets = []
        while True:
            targets.append(ast.Name(expect_t(s, Ident).id, ast.Store()))
            if not accept(s, ','): break
        expect(s, ';')
        yield ast.Assign(targets, ast.Constant(None, None))

def procedure(s: 'Scanner') -> Iterator[ast.stmt]:
    while accept(s, 'procedure'):
        i, _, b, _ = expect_t(s, Ident), expect(s, ';'), list(block(s)), expect(s, ';')
        yield ast.FunctionDef(i.id, ast.arguments([], [], None, [], [], None, []), b, [], None, None)

def program(s: 'Scanner') -> ast.Module:
    b, _ = list(block(s)), expect(s, '.')
    return ast.Module([ast.FunctionDef('main', ast.arguments([], [], None, [], [], None, []), b, [], None, None),
                       ast.Expr(ast.Call(ast.Name('main', ast.Load()), [], []))], [])

exec(compile(parse(scan(sys.stdin.read())), '', 'exec'))