出版の明確化ユーザー@duseは以前に2つの以前の記事の翻訳を投稿しており、シリーズ全体を翻訳することを明確に意図しています。 このトピックは私にとって非常に興味がありますが、新しい翻訳はないので、元のソースに戻りました。 彼は英語にあまり強くないので、本質を失わないように、彼はロシア語に翻訳し始めました。 そして、この翻訳が生まれました。 もう少し苦労した場合は、@ duseに謝罪します。 しかし、いずれにしてもコミュニティにとっては利益になるはずです。
そこで、インタプリタ用のレクサーパーサコンビネータライブラリを作成しました。 このパートでは、抽象構文ツリー（AST）の構造データを作成し、レクサーによって返されたトークンのリストを抽象構文ツリー（AST）に変換するコンビネーターのライブラリを使用してパーサーを記述します。 ASTを解析したら、プログラムの開始は非常に簡単です。
ASTを決定する
パーサーの作成を開始する前に、パーサーが返すデータ構造を定義する必要があります。 クラスを使用してそれらを定義します。 各IMP構文要素には、対応するクラスがあります。 このクラスのオブジェクトは、ASTにノードを表示します。
IMPには、算術式（数値の計算に使用）、論理式（ifおよびwhileステートメントの条件の計算に使用）、および状態の3つの構造しかありません。 残りの2つはそれに依存しているため、算術式から始めましょう。
算術式は、次の3つの形式のいずれかを取ることができます。
42などの英数字定数xような変数x + 42ようなバイナリ演算。 他の算術式から形成されます。
式を角かっこでグループ化することもできます（
(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つのタイプがあります。
- 関係式（
x < 10 ） - 式（
x < 10 and y > 20 ） Or式- 表現で
Not
関係式の左側と右側は算術式です。
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 ConrodPS Subタグに問題があります。 初心者がこのようなタグを使用するには早すぎるという仮定があります。 それを交換する方法-私は知りません。 私は解決策が明らかになるまで去ります。