最近真面目にやりだした、アルゴリズムについて。
BNFと構文解析。四則演算の例。
2021/2/4 追記：
@shiracamus さんから
このエントリ(別の人のエントリです)に関係する話を伺いコードを一部書き換えました
TL;DR
構文解析とは文章構造の解析、パースのことです。
今回のゴールは、構文解析に欠かせないBNF記号を説明し、四則演算のBNFを示します。
その後四則演算を解析し、計算結果を表示するpythonコードを書くことにします。
記事の流れとしては、
・プログラミング言語の仕様などによく使われるBNF記法の簡単な説明
・BNF記法の例をいくつか説明
・四則演算のBNF(そこまで厳密でない)をもとにpythonで構文解析を実行
となっています。
BNFとは
基本的な記法
記号 ::= 記号の列
記号の種類
| 記号の名前 | 実際の表記法 | 簡単な説明 |
|---|---|---|
| 定義記号 | '::=' | 左側(左辺)の記号を右側(右辺)で定義するための記号 |
| 論理和 | '｜' | aまたはbと言ったように'または'を意味する |
| 非終端記号 | '<記号>' | < >で囲まれた記号。終端記号で置換可能 |
| 終端記号 | 記号 | < >で囲まれていない記号。置換不可能な最小の単位 |
※非終端記号は左辺にも右辺にも登場できるが、終端記号は右辺にしか登場できない
BNFの例
例1) 二進数のBNF記法
<bin_num> := <bin_seq>
<bin_seq> := <bin_digit> | <bin_digit> <bin_seq>
<bin_digit> := 0 | 1
これは
<bin_num> -> <bin_seq> -> <bin_digit> -> 0 | 1
<bin_num> -> <bin_seq> -> <bin_digit> <bin_seq> -> 0 | 1 | <bin_seq>
<bin_num> -> <bin_seq> -> <bin_digit> <bin_seq> -> 0 | 1 | 0 | 1
<bin_num> -> <bin_seq> -> <bin_digit> <bin_seq> -> 0 | 1 | 0 | 1 <bin_seq>
<bin_num> -> <bin_seq> -> <bin_digit> <bin_seq> -> 0 | 1 | 0 | 1..... 0 | 1
このように、永遠と続く 0と1を表記できます。
ここでは0と1が終端記号です
例2) 10進整数
<integer> ::= <digit> | <non_zero_digit> <integer>
<digit> ::= 0 | <non_zero_digit>
<non_zero_digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
これは
<integer> -> <digit> -> 0
<integer> -> <digit> -> <non_zero_digit> -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer> -> <non_zero_digit> <integer> -> <non_zero_digit> <digit> | <non_zero_digit> <integer> -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ...... 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
このように、最初だけ非ゼロの値を取って、その後は0〜9が延々と繰り返されます。これにより、どんな10進整数でも表記可能です。
例3) 基本情報技術者平成23年秋期 午前問4
<form> ::= <var> | (<form> + <form>) | <form> * <form>
<var> ::= A | B | C | D
これは選択肢から正解を導く問題でした。
具体的な解答例はこちらです。
次の説明のために簡単に書いておくと、 (A+B)(C+D)は正解で、(AB)+(C*D)は不正解です。
+の記号が入っている場合は、必ず+の左右の記号を( )で括らなければいけないと言うのがその理由です。
さて、ここまで書いてきたところで、四則演算のBNFです
<expr> ::= <term> [ ('+'|'-') <term> ]*
<term> ::= <factor> [ ('*'|'/') <factor> ]*
<factor> ::= <number> | '(' <expr> ')'
<number> :== １つ以上の数字
四則演算のBNFはいろいろありますがここではこのサイトに習って上記の記法で行きます。
pythonによる四則演算構文解析の実装(パーツ)
まずはパーツ毎に実装していきます。
実装に際しては、計算も同時にやってしまうのが慣例のようなので、
それに習っています。
expr記号
<expr> ::= <term> [ ('+'|'-') <term> ]*
expr と言う記号は term と言う記号の加減の繰り返しで表せます。
ここで出てくる記号 "[ ]*" は、中のものが0回以上繰り返される事を表す記号です。
def expr(s):
global i
val = int(term(s))
while i < len(s) and (s[i] == '+' or s[i] == '-'):
op = s[i]
i += 1
val2 = int(term(s))
if op == '+':
val += val2
else:
val -= val2
return val
term
<term> ::= <factor> [ ('*'|'/') <factor> ]*
term は factor の積と除の繰り返しで表されます。
先程のexprと組み合わせると、加減算より先に積と除が行われる事がわかります。
def term(s):
global i
val = int(factor(s))
while i < len(s) and (s[i] == '*' or s[i] == '/'):
op = s[i]
i +=1
val2 = int(factor(s))
if op == '*':
val *= val2
else:
val /= val2
return val
factor
<factor> ::= <number> | '(' <expr> ')'
factorと言う記号はnumber、または(expr)で表現されます。
def factor(s):
global i
if s[i].isdigit():
return number(s)
i += 1
ret = int(expr(s))
i += 1
return ret
number
<number> :== １つ以上の数字
number と言う非終端記号は 1つ以上の数字という終端記号に置き換えられます。
(正規表現で書くと[0-9]+ですかね)
def number(s):
global i
n = ""
while i < len(s) and s[i].isdigit():
n += s[i]
i += 1
return n
いかがでしょうか？１つのBFNに対して１つの関数が対応しているのがわかるでしょうか？
コード(全体)
これらをつなぎ合わせるだけで、四則演算のパーサーは完成です。
#-*- encodint:utf-8 -*-
def expr(s):
global i
val = int(term(s))
while i < len(s) and (s[i] == '+' or s[i] == '-'):
op = s[i]
i += 1
val2 = int(term(s))
if op == '+':
val += val2
else:
val -= val2
return val
def term(s):
global i
val = int(factor(s))
while i < len(s) and (s[i] == '*' or s[i] == '/'):
op = s[i]
i +=1
val2 = int(factor(s))
if op == '*':
val *= val2
else:
val /= val2
return val
def factor(s):
global i
if s[i].isdigit():
return number(s)
i += 1
ret = int(expr(s))
i += 1
return ret
def number(s):
global i
n = ""
while i < len(s) and s[i].isdigit():
n += s[i]
i += 1
return n
if __name__=="__main__":
s = '32*1/(10-2)+(2*2+2)'
i = 0
print(expr(s))
興味がある方はsの値をいろいろ変えてみてください。
バグ等を発見された方はコメント欄にご一報いただけると幸いです。
参考サイト
【例題あり】BNF記法を丁寧に解説【わかりやすい】
構文解析
１０進整数のBNFによる定義
Grammars(二進数の定義)
基本情報技術者平成23年秋期 午前問4
Qiita:pythonで数式の構文解析をしてみた