Pythonで簡易PL/0処理系

# はじめに

[PL/0](https://ja.wikipedia.org/wiki/PL/0)処理系を、Python 3.10.6 で簡易実装する。
ここではコードの説明しかしないので、用語や概念の説明については別ページを参照([字句解析](https://ja.wikipedia.org/wiki/%E5%AD%97%E5%8F%A5%E8%A7%A3%E6%9E%90)、[構文解析](https://ja.wikipedia.org/wiki/%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90)など)。

# 字句解析

トークンは、数値、識別子、キーワードの3種とする。それぞれに別のクラスを割り当てて区別できるようにする。数値は`int`、キーワードは`str`、識別子は専用クラスを準備。
```python
@dataclass
class Ident:
    id: str
```
字句解析は、正規表現で分割して、該当クラスに変換して、`yield`で1つずつ返している。キーワードは大文字小文字区別しない仕様とする。
```python
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](https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0%E4%B8%8B%E9%99%8D%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90#%E3%83%91%E3%83%BC%E3%82%B5%E3%81%AE%E4%BE%8B)にPL/0の構文解析コードが載っているので、必要な処理を追加しつつ流用する。

1回先読みができる必要があるので、字句解析の結果に`more_itertools.peekable`をかぶせて使う。[ast.fix_missing_locations](https://docs.python.org/ja/3/library/ast.html#ast.fix_missing_locations)は、コンパイル時にエラーにならないようにするおまじない。
```python
def parse(i: Iterable[int | str | Ident]) -> ast.Module:
    return ast.fix_missing_locations(program(more_itertools.peekable(i)))
```

先読み可能イテレータの型に別名をつけておく。実行時は要素型指定できないので、型チェック時のみ。
```python
if TYPE_CHECKING:
    Scanner: TypeAlias = more_itertools.more.peekable[int | str | Ident]
```

`accept`、`expect`を移植。型指定とキーワード指定を別関数にする。キーワードは想定値の候補を引数でまとめて指定できるようにする。
```python
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](https://docs.python.org/ja/3/library/ast.html)に変換してしまう。

`factor`から`condition`は、ほぼ素直に変換できる。
```python
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の構文規則](https://en.wikipedia.org/wiki/PL/0#Grammar)をベースに実装している。入出力(`?`,`!`)を追加しないと、実行結果を確認できないため。
```python
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をたどって代入を行っている変数を抽出する関数を作っておく。
```python
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`が書ける。
```python
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を呼び出す形とする。
```python
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](https://docs.python.org/ja/3/library/functions.html#compile)して[exec](https://docs.python.org/ja/3/library/functions.html#exec)するだけ。とりあえず標準入力からPL/0ソースを読む仕様とする。
```python
exec(compile(parse(scan(sys.stdin.read())), '', 'exec'))
```
ちなみに、以下のように書き換えると、実行する代わりに変換後のPythonコードを表示する。
```python
print(ast.unparse(parse(scan(sys.stdin.read()))))
```
ASTの表示も可能(コードが長いと見づらいが)。
```python
print(ast.dump(parse(scan(sys.stdin.read())), indent=2))
```
[Wikipediaにある使用例](https://ja.wikipedia.org/wiki/PL/0#%E4%BD%BF%E7%94%A8%E4%BE%8B)の最初のコードをPythonコードに変換した結果が以下。
```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`関数・構文解析用の関数を呼び出せてしまう。

# ソースコード
```python
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'))
```