これは以下のページの一部を翻訳したものです。
https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing
precedence climbingを理解するために、式解析の他のアルゴリズムを熟知している必要はありません。
実は、この中で最もシンプルなのが「precedence climbing」だと考えています。
それを説明するために、まず、このアルゴリズムが何を目指しているのかを紹介したいと思います。
この後、どのようにこれを行うかを説明し、最後にPythonで完全に機能する実装を紹介します。
このアルゴリズムの基本的な目的は、式をネストされた部分式(nested sub-expressions)の束として扱い、 それぞれの部分式(sub-expression)は、それが含む演算子の中で最も低い優先度を共通して持つようにすることです。
ここで簡単な例を挙げてみましょう。
2 + 3 * 4 * 5 - 6
仮に + (と -) の優先度を 1、* (と /) の優先度を2とすると、次のようになります。
2 + 3 * 4 * 5 - 6
|---------------| : 優先度 1
|-------| : 優先度 2
3つの数を掛け合わせた部分式の優先度は最小で2、元の式全体にまたがる部分式の優先度は最小で1です。
ここでは、より複雑な例として、優先度3のべき乗演算子^を追加しています。
2 + 3 ^ 2 * 3 + 4
|---------------| : 優先度 1
|-------| : 優先度 2
|---| : 優先度 3
二項演算子には、優先度のほかに、結合性の概念があります。 簡単に言うと、左結合の演算子は右より左に強く結合します。右結合の演算子はその逆です。
いくつか例を挙げます。 加算は左結合なので、
2 + 3 + 4
は
(2 + 3) + 4
と等価です。
一方で、べき乗（指数）は右結合であるため、
2 ^ 3 ^ 4
は
2 ^ (3 ^ 4)
と等価です。
precedence climbingアルゴリズムでは、結合性についても正しく処理する必要があります。
最後に、括弧は演算子の優先度を上書きし、部分式を明示的にグループ化するために使われることはご存知の通りです。
したがって、次の式は乗算の前に加算を計算します。
2 * (3 + 5) * 7
後から分かりますが、このアルゴリズムにはネストされた部分式を巧みに処理するための特別な規定があります。
まず、いくつかの用語を定義します。
- アトムは数字か括弧で囲まれた式です。
- 式は二項演算子によって接続されたアトムから構成されます[1]。
この2つの用語は相互に依存していることに注意してください。 これは、文法やパーサーの世界では当たり前のことです。
このアルゴリズムは演算子誘導型です。その基本的なステップは、次のアトムを消費しそれに続く演算子を見ることです。 演算子の優先度が現在のステップで許容される最低のものよりも低ければ、アルゴリズムはreturnします。 そうでなければ、ループの中で自分自身を呼び出して部分式を処理します。
擬似コードでは、次のようになります[2]。
compute_expr(min_prec):
result = compute_atom()
while curトークン(優先度を持つ二項演算子) >= min_prec:
prec, assoc = 現在のトークンの優先度と結合性
if assocが左結合:
next_min_prec = prec + 1
else:
next_min_prec = prec
rhs = compute_expr(next_min_prec)
result = 演算子を計算する(result, rhs)
return result
ここでの各再帰的呼び出しは、同じ最小優先度を共有する演算子で接続されたアトムのシーケンスを扱います。
アルゴリズムの仕組みを知るために、まずは例題を挙げてみましょう。
2 + 3 ^ 2 * 3 + 4
この式によるアルゴリズムの実行を、紙面で追ってみることをお勧めします。
計算の開始は compute_expr(1) です。なぜなら、1 は定義したすべての演算子の中で最小優先度の演算子だからです。
以下は、この式に対してアルゴリズムが生成する「呼び出しツリー」です。
* compute_expr(1) # 式全体の最初の呼び出し
* compute_atom() --> 2
* compute_expr(2) # 演算子'+'でループに入る
* compute_atom() --> 3
* compute_expr(3)
* compute_atom() --> 2
* result --> 2 # '*'でループに入らない (prec < '^')
* result = 3 ^ 2 --> 9
* compute_expr(3)
* compute_atom() --> 3
* result --> 3 # '+'でループに入らない (prec < '*')
* result = 9 * 3 --> 27
* result = 2 + 27 --> 29
* compute_expr(2) # 演算子'+'でループに入る
* compute_atom() --> 4
* result --> 4 # ループに入らない - end of expression
* result = 29 + 4 --> 33
このアルゴリズムでは、二項演算子ごとに1回の再帰的呼び出しを行うことに注意してください。
これらの呼び出しの中には短命なものもあります。
アトムを消費してそれを返すだけで、whileループに入らないからです（これは上の式の例の2番目と3番目で起こります）。
一方、長寿命のものもあります。compute_exprの最初の呼び出しは式全体を計算します。
while ループはここで重要な役割を果たします。
これは、現在の compute_expr の呼び出しが、終了する前に、与えられた最小限の優先度を持つ連続した演算子をすべて処理することを確認するものです。
私が思うに、このアルゴリズムの最もクールな点の1つは、結合性を処理するシンプルでエレガントな方法です。 それは、次の呼び出しの最小優先度を現在のものにするか、現在のものに1を足したものにするかの、その条件の中にあります。
その仕組みはこうです。この部分式がどこかにあると仮定します。
8 * 9 * 10
^
|
矢印は while ループに入った compute_expr の呼び出しの位置を示しています。prec は 2 です。
* の結合性は左結合なので、next_min_prec には 3 がセットされます。
compute_expr(3) の再帰的な呼び出しは、アトムを消費した後、次の *トークンを見ます:
8 * 9 * 10
^
|
min_prec の優先度が 3 であるのに対して * の優先度は2なので、while ループは実行されず、呼び出しはreturnされます。
つまり、2回目の乗算は内部の呼び出しではなく、元の compute_expr が処理するようになるわけです。
本質的には、これは式が次のようにグループ化されることを意味します:
(8 * 9) * 10
これこそ、私たちが左結合に求めているものです。
これに対し、以下の式では、
8 ^ 9 ^ 10
右結合なので、再帰呼び出しの min_prec は 3 のままです。
これは、再帰的な呼び出しが、元の compute_expr に戻る前に次の ^ 演算子を消費し、式を次のようにグループ化することを意味します。
8 ^ (9 ^ 10)
上に示したアルゴリズムの擬似コードでは、括弧でくくられた部分式がどのように処理されるのかが説明されていません。
この式を考えてみましょう。
2000 * (4 - 3) / 100
whileループがどのように処理できるかは不明です。その答えは、compute_atomです。
左辺を見ると、その後に部分式が続くことがわかるので、その部分式に対してcompute_exprを呼び出し（これはマッチする右辺まで続く）、
その結果をアトムの結果として返します。
つまり、compute_exprは部分式の存在に気づかないのです。
最後に、擬似コードは短くするために、いくつかの興味深い詳細を省いています。
以下は、そのギャップを補うアルゴリズムの完全な実装です。
ここでは、Precedence climbingによる式解析のPython実装を紹介します。簡単のために短くしてありますが、
より現実的な式の言語をカバーするために簡単に拡張することができます。
以下のセクションでは、コードを少しずつ紹介しています。全コードは[ここから入手可能です]。
まずは、テキストをトークンに分割して状態を保持する小さなトークナイザーのクラスから始めようと思います。
文法は非常にシンプルで、数値式、基本的な算術演算子+, -, *, /, ^、括弧 - (, ) があります。
Tok = namedtuple('Tok', 'name value')
class Tokenizer(object):
""" Simple tokenizer object. The cur_token attribute holds the current
token (Tok). Call get_next_token() to advance to the
next token. cur_token is None before the first token is
taken and after the source ends.
"""
TOKPATTERN = re.compile("\s*(?:(\d+)|(.))")
def __init__(self, source):
self._tokgen = self._gen_tokens(source)
self.cur_token = None
def get_next_token(self):
""" Advance to the next token, and return it.
"""
try:
self.cur_token = self._tokgen.next()
except StopIteration:
self.cur_token = None
return self.cur_token
def _gen_tokens(self, source):
for number, operator in self.TOKPATTERN.findall(source):
if number:
yield Tok('NUMBER', number)
elif operator == '(':
yield Tok('LEFTPAREN', '(')
elif operator == ')':
yield Tok('RIGHTPAREN', ')')
else:
yield Tok('BINOP', operator)次は、compute_atomです:
def compute_atom(tokenizer):
tok = tokenizer.cur_token
if tok.name == 'LEFTPAREN':
tokenizer.get_next_token()
val = compute_expr(tokenizer, 1)
if tokenizer.cur_token.name != 'RIGHTPAREN':
parse_error('unmatched "("')
tokenizer.get_next_token()
return val
elif tok is None:
parse_error('source ended unexpectedly')
elif tok.name == 'BINOP':
parse_error('expected an atom, not an operator "%s"' % tok.value)
else:
assert tok.name == 'NUMBER'
tokenizer.get_next_token()
return int(tok.value)本当のアトム（ここでは数値）と、括弧付きの部分式を扱っています。
以下にcompute_expr自身を示しますが、これは上に示した擬似コードに非常に近いものです。
# For each operator, a (precedence, associativity) pair.
OpInfo = namedtuple('OpInfo', 'prec assoc')
OPINFO_MAP = {
'+': OpInfo(1, 'LEFT'),
'-': OpInfo(1, 'LEFT'),
'*': OpInfo(2, 'LEFT'),
'/': OpInfo(2, 'LEFT'),
'^': OpInfo(3, 'RIGHT'),
}
def compute_expr(tokenizer, min_prec):
atom_lhs = compute_atom(tokenizer)
while True:
cur = tokenizer.cur_token
if (cur is None or cur.name != 'BINOP'
or OPINFO_MAP[cur.value].prec < min_prec):
break
# Inside this loop the current token is a binary operator
assert cur.name == 'BINOP'
# Get the operator's precedence and associativity, and compute a
# minimal precedence for the recursive call
op = cur.value
prec, assoc = OPINFO_MAP[op]
next_min_prec = prec + 1 if assoc == 'LEFT' else prec
# Consume the current token and prepare the next one for the
# recursive call
tokenizer.get_next_token()
atom_rhs = compute_expr(tokenizer, next_min_prec)
# Update lhs with the new value
atom_lhs = compute_op(op, atom_lhs, atom_rhs)
return atom_lhs唯一の違いは、このコードではトークンの扱いをより明確にしていることです。
基本的には普通の「再帰的降下プロトコル」に従っています。
各再帰呼び出しでは、現在のトークンを tokenizer.cur_tok に格納し、
(tokenizer.get_next_token() を呼び出して) 扱ったすべてのトークンを消費するようにしています。
さらに1つの小さなピースが欠けています。
compute_opは単にサポートされている二項演算子の算術計算を実行します。
def compute_op(op, lhs, rhs):
lhs = int(lhs); rhs = int(rhs)
if op == '+': return lhs + rhs
elif op == '-': return lhs - rhs
elif op == '*': return lhs * rhs
elif op == '/': return lhs / rhs
elif op == '^': return lhs ** rhs
else:
parse_error('unknown operator "%s"' % op)Precedence climbingは、実際のツールでも使われています。
その一例が、C/C++/ObjCのフロントエンドであるClangです。
Clangのパーサーは手書きの再帰的降下法で、式の効率的なパースのためにprecedence climbingを使っています。
もし興味があれば、lib/Parse/ParseExpr.cppのParser::ParseExpression [3]のコードをご覧ください。
このメソッドはcompute_exprの役割を担っています。
compute_atomの役割はParser::ParseCastExpressionが担っています。