LoginSignup
11
14

More than 5 years have passed since last update.

@knoguchi(Kenji Noguchi)

Pythonでコンパイラ: PL/0構文木

Last updated at Posted at 2015-02-20

今回の目標

コンパイラ作成の一般的な流れは次の通りで、前回は1番まで行いました。今回は2番の構文木（一部のみ）を作ります。

  1. パーサーでトークンに分解する。
  2. トークンの構造を解析して構文木(parse tree)をつくる。
  3. 不要なトークを削除し、抽象構文木(AST)を作る。
  4. ASTノードを辿ってコードを生成する。

不要なトークンの抑制

pyparsingでは後にでてくる構造化の機能により、パース結果に';'などの記号を維持する必要がありません。Suppress()を使うと、結果に含まれないトークンになります。先に抑制を行わないと結果が見づらくて仕方がないので、まずこの話題から。

前回までのパース結果を再掲します。

['VAR', 'x', ',', 'squ', ';', 'PROCEDURE', 'square', ';', 'BEGIN', 'squ', ':=', 'x', '*', 'x', 'END', ';', 'BEGIN', 'x', ':=', '1', ';', 'WHILE', 'x', '<=', '10', 'DO', 'BEGIN', 'CALL', 'square', ';', 'x', ':=', 'x', '+', '1', ';', 'END', 'END', '.']

(),;.を抑制して効果を確かめてみましょう。

# 先頭に追加. 
LPAR, RPAR, COMMA, SEMICOLON, DOT = map(Suppress, "(),;.")

# 文字列を定数で置き換える
# before
# factor << (ident | number | "(" + expression + ")")
# after
factor << (ident | number | LPAR + expression + RPAR)

# 同様に, ; . も定数で置き換える

では前回同様サンプルプログラムをパースしてみましょう。記号が消えました。

$ python pl0_parser.py ex1.pl0
['VAR', 'x', 'squ', 'PROCEDURE', 'square', 'BEGIN', 'squ', ':=', 'x', '*', 'x', 'END', 'BEGIN', 'x', ':=', '1', 'WHILE', 'x', '<=', '10', 'DO', 'BEGIN', 'CALL', 'square', 'x', ':=', 'x', '+', '1', 'END', 'END']

Group()を使った木構造

今まで見てきたパース結果は１次元配列であり構造がありません。パーサーにグループの情報を付加して、構造を作ってみます。

静的に構造を与えるにはGroup()でトークンを一つにまとめます。具体例を見てみましょう。変数のリストをグループ化するには次のように変更します。

# 11. var
var = VAR + Group(ident + ZeroOrMore(COMMA + ident)) + SEMICOLON

再度パースした結果です。先頭の変数一覧がカッコの中に入りました！

['VAR', ['x', 'squ'], 'PROCEDURE', 'square', 'BEGIN', 'squ', ':=', 'x', '*', 'x', 'END', 'BEGIN', 'x', ':=', '1', 'WHILE', 'x', '<=', '10', 'DO', 'BEGIN', 'CALL', 'square', 'x', ':=', 'x', '+', '1', 'END', 'END']

ならば、Group()で括りまくれば?とも言えるわけですが、pyparsingでは.setParseActionを使う別の常套手段があります。

.setParseAction()を使う方法

pyparsingではパーサーがパースに成功した時にコールバックを呼ぶことが可能です。このコールバックにはトークンのリストが引き渡され、返り値でトークンを置き換えることができます。では先ほど同様に変数の宣言を[]の中に入れてみましょう。

# 11. var
def var_list(tokens):
    tokens = tokens.asList()
    return [tokens[0], tokens[1:]]
var = VAR + ident + ZeroOrMore(COMMA + ident) + SEMICOLON
var.setParseAction(var_list)

パースしたところ先ほどと同じ結果が得られました。

['VAR', ['x', 'squ'], 'PROCEDURE', 'square', 'BEGIN', 'squ', ':=', 'x', '*', 'x', 'END', 'BEGIN', 'x', ':=', '1', 'WHILE', 'x', '<=', '10', 'DO', 'BEGIN', 'CALL', 'square', 'x', ':=', 'x', '+', '1', 'END', 'END']

ちょっと高度な使い方。

関数を呼ぶかわりにクラスのコンストラクタを呼んでみます。Group()で前処理をしておくとクラスがすっきり書けます。

# 11. var
class Var(object):
    def __init__(self, tokens):
        tokens = tokens.asList()
        self.variables = tokens[1]
var = VAR + Group(ident + ZeroOrMore(COMMA + ident)) + SEMICOLON
var.setParseAction(Var)

結果。おぉ！オブジェクトが入りました。これを使えばパーサー実行時に直接ASTを生成することができます。

[<__main__.Var object at 0x10d418710>, 'PROCEDURE', 'square', 'BEGIN', 'squ', ':=', 'x', '*', 'x', 'END', 'BEGIN', 'x', ':=', '1', 'WHILE', 'x', '<=', '10', 'DO', 'BEGIN', 'CALL', 'square', 'x', ':=', 'x', '+', '1', 'END', 'END']

コールバックは呼び出し可能なら関数でもクラスでもいいのですが。引数の数によって引数の意味が異なりますので、気をつけましょう。

  • 引数三つ fn(original_string, location, tokens)
  • 引数二つ fn(location, tokens)
  • 引数一つ fn(tokens)
  • 引数なし fn()

original_string = 現在パース中の元の文字列
location = マッチした文字列の位置
tokens = マッチしたトークンの配列。トークンはParseResultsオブジェクトになっている

式の木構造

式には複雑な計算順序がありますが、突き詰めると項と演算子が基本です。演算子の優先順位を考慮すると入れ子が必須です。自分で書くと面倒くさいですが、pyparsingではinfixNotationというユーティリティーがあり、演算子の順位を定義するだけで自動的にパーサーができあがります。オリジナルのBNFに基づいたパーサーは削除します。

項の前についている符号は単項演算子(unary operator)、通常の四則演算は二項演算子(binary operator)です。比較演算子(< <= > >= = #)も二項演算子の仲間です。では実際に定義してみましょう。

oneOfを使っているのは演算子が同位の意味です。これをうっかり２行に分けて書いてしまうと"同位の演算子は左から計算する"というルールに反した結果になってしまいますので注意。

opAssoc.RIGHTとLEFTはその演算子が右辺あるいは左辺のどちらに結びついているかを示すものです。演算子#はPL/0では!=の意味です。

# term = Forward()
# factor = Forward()
# expression = Optional(oneOf("+ -")) + term + ZeroOrMore(oneOf("+ -") + term)
# term << (factor + ZeroOrMore(oneOf("* /") + factor))
# factor << (ident | number | LPAR + expression + RPAR)

# infixNotationは演算子の優先順位を定義する。
# 同位の演算子は１行で書くこと。
UNARY, BINARY, TERNARY = 1, 2, 3
factor = ident | number
expression = infixNotation(
    factor,
    [
        (oneOf("+ -"), UNARY, opAssoc.RIGHT),  # 符号は最優先。
        (oneOf("* /"), BINARY, opAssoc.LEFT),  # 掛け算割り算は足し算引き算より優先
        (oneOf("+ -"), BINARY, opAssoc.LEFT),
    ]
)

同様にconditionについても書き換えます。

# 4. condition
#condition = ODD + expression | expression + oneOf('= # < <= > >=') + expression
condition = infixNotation(
    expression,
    [
        (ODD, UNARY, opAssoc.RIGHT),
        (oneOf("< <= > >="), BINARY, opAssoc.LEFT),
        (oneOf("= #"), BINARY, opAssoc.LEFT),
    ]
)

実行結果。式が[]の中に括られたことがわかります。

['VAR', ['x', 'squ'], 'PROCEDURE', 'square', 'BEGIN', 'squ', ':=', ['x', '*', 'x'], 'END', 'BEGIN', 'x', ':=', '1', 'WHILE', ['x', '<=', '10'], 'DO', 'BEGIN', 'CALL', 'square', 'x', ':=', ['x', '+', '1'], 'END', 'END']

ちなみに四則演算も正しくパースできます。

>>> print expression.parseString('1 + 2 * 3 + 4')
[['1', '+', ['2', '*', '3'], '+', '4']]
>>> print expression.parseString('1 + 2 / 3 * 4 - -5')
[['1', '+', ['2', '/', '3', '*', '4'], '-', ['-', '5']]]

まとめ

トークンの羅列から、構文木を作りました。BNFで定義されている文法の一部と、演算子の優先順位を考慮した、式の構文木の生成も行いました。一部しか実装しなかったのは、pyparsingではASTを直接生成する方法があり、実装しても捨てることになるので。次回は全文法をサポートしたASTの生成を行います。

ソース

pl0_parser.py
# -*- coding: utf-8 -*-
from pyparsing import *

LPAR, RPAR, COMMA, SEMICOLON, DOT = map(Suppress, "(),;.")

# 1. reserved keyword
(CONST, VAR, PROCEDURE, CALL, BEGIN, END, IF, THEN, WHILE, DO, ODD) = map(CaselessKeyword,
"CONST, VAR, PROCEDURE, CALL, BEGIN, END, IF, THEN, WHILE, DO, ODD".replace(",", "").split())
keyword = MatchFirst((CONST, VAR, PROCEDURE, CALL, BEGIN, END, IF, THEN, WHILE, DO, ODD))

# 2. identifier
ident = ~keyword + Word(alphas, alphanums + "_")

# 3. expression
number = Regex(r"\d+(\.\d*)?([eE][+-]?\d+)?")
UNARY, BINARY, TERNARY = 1, 2, 3
factor = ident | number
expression = infixNotation(
    factor,
    [
        (oneOf("+ -"), UNARY, opAssoc.RIGHT),  # 符号は最優先
        (oneOf("* /"), BINARY, opAssoc.LEFT),  # 掛け算割り算は足し算引き算より優先
        (oneOf("+ -"), BINARY, opAssoc.LEFT),
    ]
)


# 4. condition
#condition = ODD + expression | expression + oneOf('= # < <= > >=') + expression
condition = infixNotation(
    expression,
    [
        (ODD, UNARY, opAssoc.RIGHT),
    (oneOf("< <= > >="), BINARY, opAssoc.LEFT),
    (oneOf("= #"), BINARY, opAssoc.LEFT),
    ]
)

# 5. assignment
assign_statement = ident + ":=" + expression

# 6. call
call_statement = CALL + ident

# 7. if-then
statement = Forward()
if_statement = IF + condition + THEN + statement

# 8. while-do
while_statement = WHILE + condition + DO + statement

# 9. statement
statement << Optional(assign_statement
                      | call_statement
                      | BEGIN + statement + ZeroOrMore(SEMICOLON + statement) + END
                      | if_statement
                      | while_statement
)

# 10. const
const = CONST + Group(Group(ident + "=" + number) + ZeroOrMore(COMMA + ident + "=" + number)) + SEMICOLON

# 11. var
var = VAR + Group(ident + ZeroOrMore(COMMA + ident)) + SEMICOLON

# 12. procedure
block = Forward()
procedure = PROCEDURE + ident + SEMICOLON + block + SEMICOLON

# 13. block
block << Optional(const) + Optional(var) + ZeroOrMore(procedure) + statement

# 14. program
program = block + DOT

if __name__ == '__main__':
    import sys
    with open(sys.argv[1], 'r') as fp:
        txt = fp.read()
        print program.parseString(txt)
11
14
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
11
14