今回やる事
競技プログラミングをやっていたら、再帰下降構文解析を応用したようなアルゴリズムの問題がけっこう出て解けなかったので、まずは基本から理解しようと思い、自分なりにまとめてみました。
※間違っていたらご指摘いただけると喜びます。
環境
python 3.8.5
jupyter notebook 6.2.0
構文解析とは
文字列を解析して、その文字の構成要素の意味を解析する事。
自然言語における解析と、コンパイラやプログラムなどでの使用を目的とした解析では手法が異なる。
今回は、競技プログラミングなどのプログラムおける使用を前提としているので、後者の方を追っていきます。
再帰下降構文解析とは
再帰により構文を小さな単位に分割し、解析するもので、比較的簡単に実装出来て性能はそこそこいいため競技プログラミングなどに頻出する。
処理の流れ的には、入力文字列を__左から構文解析__していって__末尾から値を確定__させていく。
Wikipediaより引用
再帰下降構文解析は__相互再帰型__(※1)の手続き（あるいは再帰型でない同等の手続き）で構成されるような__LL法のトップダウン構文解析__(※2)であり、各プロシージャが文法の各生成規則を実装する事が多い。従って、生成されるプログラムの構造はほぼ正確にその文法を反映したものとなる。そのような実装の構文解析器を再帰下降パーサと呼ぶ。
1. 相互再帰型
再帰の種類の1つで、それ自身をループさせるのではなく、複数の関数の間で相互に再帰になっているもの。
2. LL法のトップダウン構文解析
構文解析のアルゴリズムを大きく分けると、
-
トップダウン型（下降型解析）
- LL法
- 再帰下降構文解析
- 末尾再帰構文解析
- パックラット構文解析
- アップダウン型（上昇型解析）
- LR法
- SLR法
- LALR法
- CLR法
- GLR法
- アーリー法
- CYK法
などがあり、LL法というのは、トップダウン型の構文解析のアルゴリズムの1つ。
__文脈自由文法__というものの一種で、文字列を左（Left）から解析していき、左端導出（Leftmost Derivation）という左から非終端記号（他と置換が出来るもの）を終端記号（置換が出来ないもの）に置き換えていく手法を取る。
また、左から解析していき、右端導出を行うものはLR法という。
文脈自由文法については、こちらのサイトが分かりやすくまとめてありました。
うさぎでもわかるオートマトンと言語理論 第07羽 文脈自由文法
つまり、再帰下降構文解析も文脈自由文法に対する構文解析手法の一種みたいです。
どんな事が出来るのか？
四則演算や、何らかの規則によって成り立っている文字列の構造を解析出来たりする。
このアルゴリズムの例として、四則演算がよく挙げられているが、競技プログラミングとかでは四則演算のような仕組みを応用し、生成した文字列を解析する問題がけっこう存在する。
四則演算で理解する
例として、2(2+3*(6+1)+5)といった簡単な四則演算を実装する事を考えます。
ここで重要になるのは、計算の優先順位の実装をする事で
①. 【括弧の中】
②. 【 * 】 or 【 / 】 or 【 ( 】※
③. 【 + 】 or 【 - 】
の順で計算させる事です。
括弧の中に括弧があったら一番内側を優先して計算させる必要もあります。
※*が省略されている場合は【（ 】の次に数字が来る。
上記の実装はEBNFで表すとこうなります。
expr = term, {("+", term) | ("-", term)}
term = factor, {("*", factor) | ("/", factor) | ("(", factor)}
factor = ("(", expr, ")") | number
number = 1つ以上の数字
EBNFはBNFの拡張版で、構文定義を書いたりするメタ言語です。ここではプログラムの仕様を定義します。
EBNFでは左辺が非終端記号、右辺が終端記号になっており、左辺を右辺に置き換えて構文を解析していきます。
つまり、exprで言うとexprはterm（項）と、+か-だったらterm（項）に置き換えられるという事みたいです。
2(3+4)+5という式を例にして大まかに考え方を見る
①. exprは項（+か-だったら、さらに項）に置き換えられる。
まず先頭から探索し、2をtermとして置き換える。
②. termはfactor（* か / か ( だったら更にfactor）に置き換えられる
2をfactorとして置き換える。
③. factorはexprかnumberに置き換えられる
2は括弧始まりではないため、number（1つ以上の数字）に置き換えられる。
このようなexpr→term→factorという再帰を繰り返していき計算を進めていきます。
EBNFを元に実装してみる
def countup():
global i
i += 1
# number = 1つ以上の数字
def number(s):
global i
res = ''
while i < len(s) and s[i].isdigit():
res += s[i]
countup()
return int(res)
# expr = term, {("+", term) | ("-", term)}
def expr(s):
global i
res = term(s)
while i < len(s):
if s[i] == '+':
countup()
res += term(s)
continue
elif s[i] == '-':
countup()
res -= term(s)
continue
return res
return res
# term = factor, {("*", factor) | ("/", factor) | ("(", factor)}
def term(s):
global i
res = factor(s)
while i < len(s):
if s[i] == '*':
countup()
res *= factor(s)
continue
elif s[i] == '/':
countup()
res /= factor(s)
continue
elif s[i] == '(' and str(res).isdigit():
res *= factor(s)
continue
else:
break
return res
# factor = ("(", expr, ")") | number
def factor(s):
global i
if s[i] == '(':
countup()
res = expr(s)
if s[i] == ')':
countup()
return res
return number(s)
i = 0
s = '2(3+4)+5'
print(expr(s))
19
処理の流れを見る。
実装内容
- expr
- termを呼び結果を取得。
-
- or - だったらtermを呼ぶ。
- term
- factorを呼び結果を取得。
-
- or / or ( の次数字 だったらfactorを呼ぶ。
- factor
- ( だったらexprを呼び結果を取得。
- ( じゃなかったらnumberを呼ぶ。
処理の流れ
①. expr
まずtermを呼ぶ。
②. term
factorを呼ぶ。
③. factor
括弧始まりじゃないためnumberを呼ぶ。
④. number
先頭から数字じゃなくなるまで検索し、2を返す。
※これから検索した位置は保持しておく。
⑤. term
factorから2が返り、先を検索すると(でその次が数字のためfactorを呼ぶ。
⑥. factor
(は括弧始まりのため次に進めexprを呼び結果を取得。
※括弧が終わるまで再帰的に探索される。
⑦. expr
termを呼ぶ。
⑧. term
factorを呼ぶ。
⑨. factor
3なのでnumberによって3が返される。
⑩. term
factorから3が返されるが *, /, ( ではないので3を返す。
⑪. expr
次は+なので次に進めtermを呼ぶ。
⑫. term
factorを呼ぶ。
⑬. factor
4を返す。
⑭. expr
3+4が処理され、次に進む。
⑮. factor
⑥の結果が返り、括弧が終わると、⑤に結果が返り2*7が処理される。
その後再度exprが呼ばれる。
⑯. expr
+のため、次に進みtermを呼ぶ。
⑰. term
factorを呼ぶ。
⑱. factor
5のためnumberを返す。
⑲. expr
numberから返った5と14が足し合わされ、末尾まで検索したため結果が返る。
感想
構文解析系のアルゴリズムは全く触れたことが無かったので、すごい勉強になりますね。
そもそもの基礎的な知識が全く足りてない事に気づいたのでそちらも勉強していきたいと思いました。
簡単な四則演算だけじゃなく、文字列が入った計算とかも実装してみます。