Clever Geek Handbook

Pythonのゼロからのシンプルなインタープリター（パート3）

画像



内容
Python＃1のゼロからのシンプルなインタープリター

Python＃2のゼロからのシンプルなインタープリター

Python＃3のゼロからのシンプルなインタープリター

Python＃4のゼロからのシンプルなインタープリター



出版の明確化
ユーザー@duseは以前に2つの以前の記事の翻訳を投稿しており、シリーズ全体を翻訳することを明確に意図しています。 このトピックは私にとって非常に興味がありますが、新しい翻訳はないので、元のソースに戻りました。 彼は英語にあまり強くないので、本質を失わないように、彼はロシア語に翻訳し始めました。 そして、この翻訳が生まれました。 もう少し苦労した場合は、@ duseに謝罪します。 しかし、いずれにしてもコミュニティにとっては利益になるはずです。





そこで、インタプリタ用のレクサーパーサコンビネータライブラリを作成しました。 このパートでは、抽象構文ツリー（AST）の構造データを作成し、レクサーによって返されたトークンのリストを抽象構文ツリー（AST）に変換するコンビネーターのライブラリを使用してパーサーを記述します。 ASTを解析したら、プログラムの開始は非常に簡単です。





ASTを決定する



パーサーの作成を開始する前に、パーサーが返すデータ構造を定義する必要があります。 クラスを使用してそれらを定義します。 各IMP構文要素には、対応するクラスがあります。 このクラスのオブジェクトは、ASTにノードを表示します。



IMPには、算術式（数値の計算に使用）、論理式（ifおよびwhileステートメントの条件の計算に使用）、および状態の3つの構造しかありません。 残りの2つはそれに依存しているため、算術式から始めましょう。

算術式は、次の3つの形式のいずれかを取ることができます。





式を角かっこでグループ化することもできます（ (x+2)*3



）。 これは、それほど異なるタイプの式ではなく、式を解析する異なる方法です。

これらのフォームに3つのクラスを定義し、さらに基本的な算術式の基本クラスを定義します。 これまでのところ、クラスは情報を保存するだけです。 __repr__



メソッドを使用すると、デバッグ中にAST



が出力できます。 すべてのAST



クラスはEquality



を継承するため、2つのAST



オブジェクトのIDを確認できます。これはテスト時にも役立ちます。 



 from equality import * class Aexp(Equality): pass class IntAexp(Aexp): def __init__(self, i): self.i = i def __repr__(self): return 'IntAexp(%d)' % self.i class VarAexp(Aexp): def __init__(self, name): self.name = name def __repr__(self): return 'VarAexp(%s)' % self.name class BinopAexp(Aexp): def __init__(self, op, left, right): self.op = op self.left = left self.right = right def __repr__(self): return 'BinopAexp(%s, %s, %s)' % (self.op, self.left, self.right)


論理式はもう少し複雑です。 論理式には4つのタイプがあります。





関係式の左側と右側は算術式です。 and



、 or



、またはnot



式の左側と右側は論理式です。 このタイプの区別は、 x < 10 and 30



ような無意味な表現を避けるのに役立ちます。 



 class Bexp(Equality): pass class RelopBexp(Bexp): def __init__(self, op, left, right): ... class AndBexp(Bexp): def __init__(self, left, right): ... class OrBexp(Bexp): def __init__(self, left, right): ... class NotBexp(Bexp): def __init__(self, exp): ...


ステートメント（ステートメント）には、算術式と論理式を同時に含めることができます。 式には、割り当て、結合、条件、ループの4種類があります。 



 class Statement(Equality): pass class AssignStatement(Statement): def __init__(self, name, aexp): ... class CompoundStatement(Statement): def __init__(self, first, second): ... class IfStatement(Statement): def __init__(self, condition, true_stmt, false_stmt): ... class WhileStatement(Statement): def __init__(self, condition, body): ...


プリミティブ



これで、 AST



クラスと適切なコンビネーターのセットができました。パーサーを作成するときです。 パーサーを作成するときは、言語の基本構造から開始する方が簡単で、徐々に複雑なものに進みます。



最初に調べるパーサーは、 keyword



パーサーです。 これは、すべてのキーワードをマークするRESERVED



タグを使用したReserved



コンビRESERVED



特別なバージョンです。 Reserved



は単一のトークンに対応し、その値とタグは転送されたものと同じであることを忘れないでください。 



 def keyword(kw): return Reserved(kw, RESERVED)


keyword



は、パーサーを返す関数であるため、実際のコンビネーターです。 他のパーサーで直接使用します。



id



パーサーは、変数名を照合するために使用されます。 指定されたタグとトークンを照合するTag



コンビネーターを使用します。 



 id = Tag(ID)


num



パーサーは、整数の照合に使用されます。 Process



コンビネーター（より正確には、 Process



を呼び出す^



演算子）を使用してトークンを特定の整数に変換することを除いて、 id



とほぼ同じように機能します。 



 num = Tag(INT) ^ (lambda i: int(i))


算術式の解析



算術式の解析は簡単ではありませんが、論理式またはステートメントを解析するために算術式を解析する必要があるため、それらから始める必要があります。



最初に、 num



とid



によって返される値を実際の式に変換するaexp_value



パーサーを定義します。 



 def aexp_value(): return (num ^ (lambda i: IntAexp(i))) | \ (id ^ (lambda v: VarAexp(v)))


演算子を使用しました|



これは、 Alternate



コンビAlternate



略です。 これにより、最初に整数式を解析できるようになります。 それらが失敗した場合、変数を使用して式を解析しようとします。



id



とnum



行ったように、 aexp_value



をグローバル値ではなく引数なしの関数として定義したことに注意してください。 残りのすべてのパーサーについても同じことを行います。 そして、各パーサーのコードをすぐに計算したくないため、これを行いました。 各パーサーをグローバルとして定義した場合、各パーサーはまだ宣言されていないため、同じソースファイル内でさらに後続する他のパーサーを参照できません。 これにより、再帰的なパーサーを定義できなくなり、ソースコードが読みにくくなります。



さらに、算術式に括弧を使用したグループ化を実装したいと思います。 グループ化式には独自のAST



クラスは必要ありませんが、それらを処理する別のパーサーが必要です。 



 def process_group(parsed): ((_, p), _) = parsed return p def aexp_group(): return keyword('(') + Lazy(aexp) + keyword(')') ^ process_group


process_group



関数は、 Process



コンビprocess_group



（ ^



演算子）で使用されます。 単に角括弧のトークンを破棄し、内部の式を返します。 実際、 aexp_group



パーサーaexp_group



もあります。 +



演算子はConcat



コンビConcat



省略形であることを忘れないでください。 そのため、算術式（すぐに決定するaexp



で解析）の後に、「）」の横にある「（」を解析します。 aexp



呼び出すことは避けてくださいaexp



はaexp_group



呼び出すため、無限再帰が発生します。 Lazy



コンビネーターを使用します。これは、パーサーが入力に適用されるまでaexpの呼び出しを延期します。



次に、 aexp_value



とaexp_group



をaexp_term



とaexp_term



ます。 式aexp_term



は、他の式との関係で演算子の優先順位を気にする必要のない単純な独立した式です。 



 def aexp_term(): return aexp_value() | aexp_group()


今、私たちはトリッキーな部分、オペレーターと年功序列に近づいています。 aexp



別のパーサーを定義し、 aexp



する方が簡単aexp_term



。 これにより、式が生成されます。 

 1 + 2 * 3


そのような誤った分析へ： 

 (1 + 2) * 3


パーサーは演算子の優先順位を認識している必要があり、優先順位が高い他の演算子とグループ化する必要があります。



この作業を実行するために、いくつかのヘルパー関数を定義します。 



 def process_binop(op): return lambda l, r: BinopAexp(op, l, r)


process_binop



関数は、 BinopAexp



オブジェクトを作成するものです。 この関数は任意の算術演算子を取り、この演算子を使用して式のペアを結合する関数を返します...



process_binop



関数は、 Exp



コンビネータ（ *



演算子）と共に使用する必要があります。 Exp



コンビネータは、式の各ペアの間に区切り文字がある式のリストを解析します。 左の演算子Exp



は、リストの個々の要素（この場合は算術式）に一致するパーサーです。 正しい演算子は、セパレーター（演算子）に一致するパーサーです。 一致するセパレータに関係なく、右側のパーサーは、演算子の対応が与えられると、ユニオン関数を返す関数を返します。 ユニオン関数は、解析された式をセパレータの左右に取り、単一の結合された式を返します。 まだ混乱していない？ Exp



をすぐに使用します。 process_binop



関数は、正しいパーサーが返すものです。

次に、年功序列レベルとそれらに対処するためのコンビネーターを決定します。 

 def any_operator_in_list(ops): op_parsers = [keyword(op) for op in ops] parser = reduce(lambda l, r: l | r, op_parsers) return parser aexp_precedence_levels = [ ['*', '/'], ['+', '-'], ]


any_operator_in_list



関数は、キーワード文字列のリストを受け取り、対応するパーサーを返します。 各優先レベル（より高いレベルから開始）の演算子のリストを含むaexp_precedence_levels



を定義します。 



 def precedence(value_parser, precedence_levels, combine): def op_parser(precedence_level): return any_operator_in_list(precedence_level) ^ combine parser = value_parser * op_parser(precedence_levels[0]) for precedence_level in precedence_levels[1:]: parser = parser * op_parser(precedence_level) return parser


precedence



は、操作の実際の内容です。 最初の引数value_parser



は、式の単純な部分（数値、変数、グループ）を読み取ることができるパーサーです。 aexp_term



になります。 precedence_levels



リストには、レベルごとに1つのリストの演算子のリストが含まれています。 これを行うには、 aexp_precedence_levels



使用しaexp_precedence_levels



。 combine



は、演算子によって渡される関数を取り、2つの小さな式から1つの大きな式を作成する関数を返します。 これはprocess_binop



なります



precedence



内で、まずop_parser



を定義します。これは、指定された年功レベルに​​対して、同じレベルの演算子のみを読み取り、2つの式を結合する関数を返します。 op_parser



はExp



の正しい引数として使用できます。 これらの操作は最初にグループ化する必要があるため、 op_parser



を使用してExp



を最高レベルの優先度で呼び出すことから始めます。 次に、結果のパーサーを次のレベルのパーサーの要素（左引数Exp



）として使用します。 ループの終了後、結果のパーサーは算術式を正しく解析できます。



実際にはどのように機能しますか？ 見てみましょう。 

 E<sub>0</sub> = value_parser E<sub>1</sub> = E<sub>0</sub> * op_parser(precedence_levels[0]) E<sub>2</sub> = E<sub>1</sub> * op_parser(precedence_levels[1])


E 0



はvalue_parser



と同じvalue_parser



。 数値、変数、およびグループを解析できますが、演算子は解析できません。 E 1



、 E 0



と一致する可能性のあるすべてのものを含む式を解析でき、年配の第1レベルから演算子で区切られます。 したがって、 E 1



はa * b / c



と一致a * b / c



ますが、 +



演算子に遭遇するとすぐにエラーが発生します。 E 2



は、次の優先レベルの演算子で区切られた式と一致できます。 年功序列のレベルは2つしかないため、 E 2



は、サポートする任意の算術式と一致できます。



例を実行してみましょう。 複雑な算術式を取り、徐々に各部分をその比較に置き換えます。 



 4 * a + b / 2 - (6 + c) E<sub>0(4)</sub> * E<sub>0</sub>(a) + E<sub>0</sub>(b) / E<sub>0</sub>(2) - E<sub>0</sub>(6+c) E<sub>1</sub>(4*a) + E<sub>1</sub>(b/2) - E<sub>1</sub>(6+c) E<sub>2</sub>((4*a)+(b/2)-(6+c))


優先順位を直接使用してaexp



を決定しaexp



。 



 def aexp(): return precedence(aexp_term(), aexp_precedence_levels, process_binop)


おそらく、より抽象的に優先度を定義することはできませんが、このアプローチの利点は、演算子の優先度の問題があるあらゆる状況に適用できることです。 論理式を解析するために再利用します。

論理式の解析



すでに算術式から論理式に移行できます。 通常、論理式は算術よりも単純なので、それらを解析するための新しいツールは必要ありません。 最も単純な論理式から始めましょう。 

 def process_relop(parsed): ((left, op), right) = parsed return RelopBexp(op, left, right) def bexp_relop(): relops = ['<', '<=', '>', '>=', '=', '!='] return aexp() + any_operator_in_list(relops) + aexp() ^ process_relop


Process



コンビprocess_relop



関数を使用します。 接続された3つの値をRelopBexp



、それらからRelopBexp



を作成します。 bexp_relop



、関係演算子で区切られた2つの算術式（ aexp



）を解析します。 そして、私たちは老人any_operator_in_list



関数を使用するため、各演算子のケースを書く必要はありません。 また、関係式は他の言語で行われているようにIMPで相互に接続できないため、 Exp



やprecedence



ようなコンビネータを使用する必要はありません。



次に、式not



定義します。 式not



は、優先順位の高い単項演算子です。 これにより、 and



and or



式よりも解析が容易になります。 

 def bexp_not(): return keyword('not') + Lazy(bexp_term) ^ (lambda parsed: NotBexp(parsed[1]))


ここでは、 not



キーワードを論理式の名前（後で定義します）と組み合わせました。 bexp_not



を使用してbexp_term



を定義するため、 Lazy



コンビbexp_term



を使用して無限再帰を回避する必要があります。 



 def bexp_group(): return keyword('(') + Lazy(bexp) + keyword(')') ^ process_group def bexp_term(): return bexp_not() | \ bexp_relop() | \ bexp_group()


bexp_group



とbexp_term



は、同等の算術演算と同じ方法で定義します。 これは新しいことではありません。

次に、 and



およびor



演算子を含む式を定義する必要があります。 これらの演算子は、実際には算術演算子のように機能します。 どちらも左から右に実行され、最高レベルの年功序列and



持っています。 

 bexp_precedence_levels = [ ['and'], ['or'], ] def process_logic(op): if op == 'and': return lambda l, r: AndBexp(l, r) elif op == 'or': return lambda l, r: OrBexp(l, r) else: raise RuntimeError('unknown logic operator: ' + op) def bexp(): return precedence(bexp_term(), bexp_precedence_levels, process_logic)


process_binop



と同様に、 process_logic



Exp



コンビExp



で使用するためのものです。 演算子を受け取り、この演算子を使用して2つの部分式を1つの式に結合する関数を返します。 aexp



と同じ方法で、優先順位に従ってこれを置き換えます。 式を処理する複雑なコード式を繰り返す必要がないため、ここで一般的なコードを書くことは有益です。



申し立ての解析



aexp



とbexp



により、IMPステートメントの解析を開始できます。 控えめな代入文から始めましょう。 

 def assign_stmt(): def process(parsed): ((name, _), exp) = parsed return AssignStatement(name, exp) return id + keyword(':=') + aexp() ^ process




本当に面白いものはありません。 次に、 stmt_list



を確認しstmt_list



。 セミコロンで区切られた一連のステートメントを解析します。 

 def stmt_list(): separator = keyword(';') ^ (lambda x: lambda l, r: CompoundStatement(l, r)) return Exp(stmt(), separator)




左側の再帰を避けるために、 stmt() + keyword(';') + stmt()



のような単純なものの代わりに、ここでEXP



コンビネータを使用する必要があることを忘れないでください。

次に、 if



ます。 

 def if_stmt(): def process(parsed): (((((_, condition), _), true_stmt), false_parsed), _) = parsed if false_parsed: (_, false_stmt) = false_parsed else: false_stmt = None return IfStatement(condition, true_stmt, false_stmt) return keyword('if') + bexp() + \ keyword('then') + Lazy(stmt_list) + \ Opt(keyword('else') + Lazy(stmt_list)) + \ keyword('end') ^ process


ここでの唯一の難点は、 else



節がオプションであることです。 これにより、関数の実行が少し複雑になります。

最後に、 while



がwhile



。 

 def while_stmt(): def process(parsed): ((((_, condition), _), body), _) = parsed return WhileStatement(condition, body) return keyword('while') + bexp() + \ keyword('do') + Lazy(stmt_list) + \ keyword('end') ^ process


これをstmt



ラップします。 

 def stmt(): return assign_stmt() | \ if_stmt() | \ while_stmt()


if



とwhile



if



両方で、本文でstmt_list



を使用する方がstmt



よりも優れていることに気付くかもしれません。 stmt_list



は、実際には最上位の定義です。 stmt_list



に直接依存するstmt



を持つことはできません。これstmt_list



、左側のパーサーの再帰が発生します。また、 if



およびwhile



ボディにオプションのステートメントが必要なため、 stmt_list



を直接使用しstmt_list



。

すべてをまとめる



これで、言語のすべての部分のパーサーができました。 いくつかの高レベルの定義を作成するだけです。 



 def parser(): return Phrase(stmt_list())


parser



はプログラム全体を解析します。 プログラムはステートメントのリストにすぎませんが、 Phrase



コンビネータは、最後にジャンク（無効な）トークンがあるため、終了前にファイル内のすべてのトークンを使用するようにします。 



 def imp_parse(tokens): ast = parser()(tokens, 0) return ast


クライアントはimp_parse



関数を呼び出してプログラムを解析します。 トークンのリスト全体を取得し、パーサーを呼び出し、最初のトークンから開始して、結果の抽象構文ツリー（AST）を返します。



パーサーをチェックするための簡単な制御プログラムを次に示します（ユニットに加えて）。 

 import sys from imp_parser import * if __name__ == '__main__': if len(sys.argv) != 3: sys.stderr.write('usage: %s filename parsername' % sys.argv[0]) sys.exit(1) filename = sys.argv[1] file = open(filename) characters = file.read() file.close() tokens = imp_lex(characters) parser = globals()[sys.argv[2]]() result = parser(tokens, 0) print result


このプログラムは、ファイル（最初の引数）を読み取り、 imp_parse.py （2番目の引数）のパーサーで解析します。 例： 



 $ echo '1 + 2 * 3' >foo.imp $ python imp_parser_driver.py foo.imp aexp Result(BinopAexp(+, IntAexp(1), BinopAexp(*, IntAexp(2), IntAexp(3))), 5)


これにより、実験に適したサンドボックスが提供されます。

おわりに



この記事では、コンビネーター・ライブラリーをゼロから作成し、それを使用してIMPのパーサーを作成しました。 このシリーズの次と最後の記事では、構文解析された抽象構文ツリー（ AST ）のパフォーマー（ 注 transl .:単語evaluatorの最適な翻訳が見つかりませんでした ）を作成します。



オリジナル記事の著者-Jay Conrod



PS Subタグに問題があります。 初心者がこのようなタグを使用するには早すぎるという仮定があります。 それを交換する方法-私は知りません。 私は解決策が明らかになるまで去ります。



More articles:


All Articles