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

前の3つのパートでは、トイ言語IMPのレクサー、パーサー、およびASTを作成しました。 パーサーコンビネータの独自のライブラリも作成しました。 この最後の記事では、インタプリタの最後のコンポーネントであるパフォーマーを作成します。





プログラムの通常の実行方法について考えてみましょう。 どの時点でも、プログラムが次に実行する式を示す「コントロールポイント」がいくつかあります。 次の式が実行されると、「制御点」を改善し、変数の値を変更することにより、プログラムの状態が変更されます。



IMPプログラムを実行するには、次の3つが必要です。

1. 制御点-実行のために次の式を知る必要があります。
2. 環境-「プログラムの状態の変化」をシミュレートする必要があります。
3. 実行関数-式ごとに状態と制御点を変更する方法を知る必要があります。

少なくともIMPの場合、最も単純なのはコントロールポイントです。 中間表現をツリー構造の形式で配置しました。 式の最上位レベルの評価関数を呼び出すだけで、内部の式の実行関数を再帰的に呼び出します。 本質的には、Pythonコントロールポイントを独自のものとして使用します。 関数や例外など、より複雑な制御構造を持つ言語ではそれほど単純ではありませんが、IMPでは単純に保つことができます。



環境もシンプルです。 IMPにはグローバル変数のみがあるため、標準のPython辞書を使用して環境をシミュレートできます。 値が変更されたら、辞書の変数の値を更新します。



実行関数は、私たちが考える必要がある唯一のものです。 式の各タイプには独自の実行関数があり、現在の環境を使用して値を返します。 算術式は整数で返され、ブール式はtrueまたはfalseを返します 。 式には副作用がないため、環境は変更されません。 式の各タイプには、実行機能もあります。 クレームは、結果を返さないように環境を変更することによって機能します。

実行関数を定義する

これらをASTクラスのメソッドとして定義します。 これにより、実行する構造体への各機能への直接アクセスが提供されます。 算術関数は次のとおりです。

class IntAexp(Aexp): ... def eval(self, env): return self.i class VarAexp(Aexp): ... def eval(self, env): if self.name in env: return env[self.name] else: return 0 class BinopAexp(Aexp): ... def eval(self, env): left_value = self.left.eval(env) right_value = self.right.eval(env) if self.op == '+': value = left_value + right_value elif self.op == '-': value = left_value - right_value elif self.op == '*': value = left_value * right_value elif self.op == '/': value = left_value / right_value else: raise RuntimeError('unknown operator: ' + self.op) return value
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、プログラマーが以前に定義されていない変数（環境ディクショナリーで定義されていない変数）を使用する場合の少し余分なロジックを見ることができます。 簡単にするため、およびエラーをキャッチするシステムを作成しないようにするために、すべての未定義変数0を指定します。



BinopAexpでは 、 RuntimeErrorをスローすることで「不明な演算子」のケースを処理します。 パーサーは未知の演算子からASTを作成できないため、簡単になります。 ただし、誰かが独自のASTを作成する場合は、そこで検討する必要があります。



ブール演算の機能は次のとおりです。

 class RelopBexp(Bexp): ... def eval(self, env): left_value = self.left.eval(env) right_value = self.right.eval(env) if self.op == '<': value = left_value < right_value elif self.op == '<=': value = left_value <= right_value elif self.op == '>': value = left_value > right_value elif self.op == '>=': value = left_value >= right_value elif self.op == '=': value = left_value == right_value elif self.op == '!=': value = left_value != right_value else: raise RuntimeError('unknown operator: ' + self.op) return value class AndBexp(Bexp): ... def eval(self, env): left_value = self.left.eval(env) right_value = self.right.eval(env) return left_value and right_value class OrBexp(Bexp): ... def eval(self, env): left_value = self.left.eval(env) right_value = self.right.eval(env) return left_value or right_value class NotBexp(Bexp): ... def eval(self, env): value = self.exp.eval(env) return not value
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

とても簡単です。 私たちは、ピットニーのリレーショナルおよび論理演算子を使用します。



次に、各タイプの式の実行関数を示します。

 class AssignStatement(Statement): ... def eval(self, env): value = self.aexp.eval(env) env[self.name] = value class CompoundStatement(Statement): ... def eval(self, env): self.first.eval(env) self.second.eval(env) class IfStatement(Statement): ... def eval(self, env): condition_value = self.condition.eval(env) if condition_value: self.true_stmt.eval(env) else: if self.false_stmt: self.false_stmt.eval(env) class WhileStatement(Statement): ... def eval(self, env): condition_value = self.condition.eval(env) while condition_value: self.body.eval(env) condition_value = self.condition.eval(env)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

AssignStatement：右側で算術式を実行し、結果の値で環境を更新します。 プログラマーは、既に定義されている変数を再定義することに制限されていません。



CompoundStatement：各式を次々に実行します。 式が許可されている場所であればどこでもCompoundStatementが許可されるため、式の長いチェーンはネストされたものとしてデコードされます。



IfStatement：最初に、式のブール条件を実行します。 trueの場合、true式を実行します。 falseおよびfalse式が定義されている場合、false式を実行します。



WhileStatement：ループの本体を1回実行するかどうかを確認する条件を満たします。 条件は、ループの反復ごとに実行され、条件を確認します。

すべてをまとめる

さて、私たちはインタプリタの主要なコンポーネントを作成しましたが、今では統合プログラムを書くだけです：

 #!/usr/bin/env python import sys from imp_parser import * from imp_lexer import * def usage(): sys.stderr.write('Usage: imp filename\n') sys.exit(1) if __name__ == '__main__': if len(sys.argv) != 2: usage() filename = sys.argv[1] text = open(filename).read() tokens = imp_lex(text) parse_result = imp_parse(tokens) if not parse_result: sys.stderr.write('Parse error!\n') sys.exit(1) ast = parse_result.value env = {} ast.eval(env) sys.stdout.write('Final variable values:\n') for name in env: sys.stdout.write('%s: %s\n' % (name, env[name]))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

1つの引数のみがプログラムに提供されます-解釈される名前。 彼女はファイルを読み取り、レクサーとパーサーに送信し、エラー（ある場合）を報告します。 次に、パーサーの結果からASTを抽出し、空の環境を使用して実行します。 IMPには出力がないため、単に環境全体を端末に出力します。



階乗を計算する標準的な例：

 n := 5; p := 1; while n > 0 do p := p * n; n := n - 1 end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実行自体：

 $ ./imp.py hello.imp Final variable values: p: 120 n: 0
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

おわりに

前回の記事では、単純な言語のインタープリターをゼロから作成しました。 言語自体はほとんど使用されませんが、インタープリターは非常に拡張可能であり、その主要コンポーネントは他の何かで使用できます。



この資料が、人々に言語設計の実験をする良い出発点となることを願っています。 いくつかのアイデア：

• 変数を名前空間にローカルにします。
• forループを追加します。
• I / O（入力/出力）の式を追加します。
• 機能を追加します。