if
新しい構文が表示され、ブロックヘッダーで変数を直接宣言できます。 これは非常に便利です。
Foo foo = make_foo(); if(foo.is_nice()) { // do work with foo } // never use foo again // foo gets deleted
非常に一般的です。 プログラマーの手の軽い動き（および標準化委員会の手の激しい動き）を伴う上記のコードは次のようになります。
if(Foo foo = make_foo(); foo.is_nice()) { // do work with foo } // foo gets deleted // never use foo again (well, you can't anyway)
それはまだ完璧に見えませんが、少し良くなりました。 Pythonにはそれさえありませんが、もしPythonコードが私と同じくらい嫌いで
if
簡単なパーサーの書き方を早く学びたいなら、catにようこそ。 この記事では、Python 2でJSON用の短くエレガントなパーサーを作成しようとします（もちろん、追加のモジュールはありません）。
構文解析とは何ですか？
解析 （ロシア語の「解析」）は、プログラミング言語、マークアップ言語、構造化照会言語、生活の主言語、宇宙など、何らかの固定言語で書かれた何かを意味のある単位に解析して変換する不滅のタスクです。 問題を解決するための典型的な一連の手順は、次のようになります。
- 言語を説明してください 。 もちろん、最初に解決するタスクを決定する必要があります。 通常、言語記述はBackus-Naur形式の別のバリエーションです 。 （たとえば、パーサーの構築に使用されるPython文法の説明です。）この場合、言語の「文章の構築」のルールと有効な単語を決定するルールの両方が設定されます。
- 入力をトークンに分割します。 入力行またはファイルをトークンのシーケンスに分割する字句アナライザー （一般的にはトークナイザー）が作成されます。つまり、言語の有効な単語（またはこれができないという痛み）です。
- 構文を確認し、構文ツリーを構築します 。 トークンのシーケンスが言語の説明と一致するかどうかを確認します。 ここでは、再帰降下法などのアルゴリズムが使用されます。 言語の有効な各文には、有効な単語または他の有効な文の有限数が含まれます。 トークンが調和のとれた画像を形成できる場合、出力で自動的にツリーを取得します。これは抽象構文ツリーと呼ばれます 。
- 最後に、仕事をします。 構文ツリーがあり、算術式の値の計算、データベース内のクエリの編成、プログラムのコンパイル、Webページの表示など、最終的に必要なことを実行できます。
一般に、この分野はこれまでに研究されてきており、驚くべき結果に満ちており、何百もの（おそらく良い）本が書かれています。 ただし、問題の理論的な解決可能性とコードの記述は同じものではありません。
モデルの問題
JSON構文解析という単純ではあるが完全に自明ではない例を使用して、パーサーを説明します。 文法は次のようになります。
root ::= value value ::= string | number | object | array | 'true' | 'false' | 'null' array ::= '[' ']' | '[' comma-separated-values ']' comma-separated-values ::= value | value ',' comma-separated-values object ::= '{' '}' | '{' comma-separated-keyvalues '}' comma-separated-keyvalues ::= keyvalue | keyvalue ',' comma-separated-keyvalues keyvalue ::= string ':' value
string
と
number
ルールはありません-それらは引用符で囲まれたすべての文字列とともにトークンになります。
Parsim JSON
本格的なトークナイザーは作成しません（これは退屈であり、記事のトピックではありません）-必要に応じて、文字列全体を処理し、トークンで打ちます。 最初の2つの関数を作成します。
import re # re.DOTALL number_regex = re.compile(r"(-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?)\s*(.*)", re.DOTALL) def parse_number(src): match = number_regex.match(src) if match is not None: number, src = match.groups() return eval(number), src # eval - , string_regex = re.compile(r"('(?:[^\\']|\\['\\/bfnrt]|\\u[0-9a-fA-F]{4})*?')\s*(.*)", re.DOTALL) def parse_string(src): match = string_regex.match(src) if match is not None: string, src = match.groups() return eval(string), src # JSON' # ,
（ifsなしで約束しましたが、これは最後のチェスロボです！）
他のすべてについて、単純なパーサー関数を生成する関数を1つ作成します。
def parse_word(word, value=None): l = len(word) def result(src): # .lower() case-insensitive ! if src.startswith(word): # if! ! return value, src[l:].lstrip() # lstrip , . result.__name__ = "parse_%s" % word # return result parse_true = parse_word("true", True) parse_false = parse_word("false", False) parse_null = parse_word("null", None)
合計、どの基礎に基づいて機能を構築するか：
- 解析する文字列を受け入れます。
- 成功した場合（つまり、行の先頭に必要な構成が見つかった場合）にペア（結果、remaining_string）を返し、失敗した場合に
None
を返します。 - トークン間のすべての空白をスペースに送ります。 （Pythonパーサーを作成している場合は、これをしないでください！）
実際、トークンに関する問題はこれら3つの関数で解決されており、興味深い部分に進むことができます。
Parsimの分岐ルール
上記の文法に対応する
parse_value
関数はどのように見えるべきですか？ 通常、次のようなものです。
def parse_value(src): # match = parse_string(src) if match is not None: # ! return match # ; match = parse_number(src) if match is not None: return match # . ... # ...
まあ、いいえ、これらが私を手に入れた
if
！
上記の3つの関数を最も予期しない方法で変更しましょう
return
を
yield
置き換え
yield
ください！ ジェネレーターを返すようになりました-解析が失敗した場合は空、成功した場合は正確に1つの要素を返します。 はい、はい、原則番号2 90度を展開しています。すべての関数をこのスタイルで記述します。
number_regex = re.compile(r"(-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?)\s*(.*)", re.DOTALL) def parse_number(src): match = number_regex.match(src) if match is not None: number, src = match.groups() yield eval(number), src # yield, . # , . string_regex = re.compile(r"('(?:[^\\']|\\['\\/bfnrt]|\\u[0-9a-fA-F]{4})*?')\s*(.*)", re.DOTALL) def parse_string(src): match = string_regex.match(src) if match is not None: string, src = match.groups() yield eval(string), src def parse_word(word, value=None): l = len(word) def result(src): if src.startswith(word): yield value, src[l:].rstrip() result.__name__ = "parse_%s" % word return result # -, yield' parse_true = parse_word("true", True) parse_false = parse_word("false", False) parse_null = parse_word("null", None)
parse_value
何になりますか？ 一見すると、次のようになります。
def parse_value(src): for match in parse_string(src): yield match return for match in parse_number(src): yield match return # ...
しかし、一見すると、各オプションは1行しか使用できないことがわかります。
# itertools.chain # , from itertools import chain def parse_value(src): for match in chain( parse_string(src), parse_number(src), parse_array(src), parse_object(src), parse_true(src), parse_false(src), parse_null(src), ): # , yield match return
同時に、効率は同じレベルにとどまります-各関数は、前の関数が結果を出さない場合にのみ実行を開始します（したがって、正規表現をチェックして作業を行います）。
return
は、リストの途中で構文解析が成功した場合に余分な作業が実行されないようにします。
Parsimシーケンス設計
プログラムの次の番号である
parse_array
関数に移りましょう。 次のようになります。
parse_left_square_bracket = parse_word("[") parse_right_square_bracket = parse_word("]") def parse_array(src): # tsrc, # "" for _, tsrc in parse_left_square_bracket(src): for _, tsrc in parse_right_square_bracket(tsrc): # , '[' ']' yield [], tsrc return # src -- for _, src in parse_left_square_bracket(src): for items, src in parse_comma_separated_values(src): for _, src in parse_right_square_bracket(src): yield items, src # yield,
約束どおり単一の
if
ではありませんが、何かがまだ間違っています...
chain
が「or」モードで接続するのと同じように、パーサー関数をシーケンスで接続するのに役立つ小さなヘルパー関数を作成しましょう。 この関数は、すべての結果を注意深く取得し、結果の最初の要素（分析結果）と最後の2番目の要素（行の残りの未分析部分）をすべて返す必要があります。 私のオプションは次のようになります。
def sequence(*funcs): if len(funcs) == 0: # , if' def result(src): yield (), src return result def result(src): for arg1, src in funcs[0](src): for others, src in sequence(*funcs[1:])(src): yield (arg1,) + others, src # return result
この強力な（恐ろしい）ツールを使用して、関数を次の形式で書き換えます。
parse_left_square_bracket = parse_word("[") parse_right_square_bracket = parse_word("]") parse_empty_array = sequence(parse_left_square_bracket, parse_right_square_bracket) def parse_array(src): for _, src in parse_empty_array(src): # , , [] yield [], src return # return , # {} {"a": 1} for (_, items, _), src in sequence( parse_left_square_bracket, parse_comma_separated_values, parse_right_square_bracket, )(src): yield items, src # yield,
さて、関数
parse_comma_separated_values
追加します-単に吐き出します：
parse_comma = parse_word(",") def parse_comma_separated_values(src): for (value, _, values), src in sequence( parse_value, parse_comma, parse_comma_separated_values # , if? )(src): yield [value] + values, src return for value, src in parse_value(src): yield [value], src
そのような解決策は無限の再帰につながりますか？ いや！
parse_comma
関数
parse_comma
次のコンマを見つけないと、実行は次の
parse_comma_separated_values
到達しません。
先に進みましょう！ 対象
parse_left_curly_bracket = parse_word("{") parse_right_curly_bracket = parse_word("}") parse_empty_object = sequence(parse_left_curly_bracket, parse_right_curly_bracket) def parse_object(src): for _, src in parse_empty_object(src): yield {}, src return for (_, items, _), src in sequence( parse_left_curly_bracket, parse_comma_separated_keyvalues, parse_right_curly_bracket, )(src): yield items, src parse_colon = parse_word(":") def parse_keyvalue(src): for (key, _, value), src in sequence( parse_string, parse_colon, parse_value )(src): yield {key: value}, src def parse_comma_separated_keyvalues(src): for (keyvalue, _, keyvalues), src in sequence( parse_keyvalue, parse_comma, parse_comma_separated_keyvalues, # , )(src): keyvalue.update(keyvalues) yield keyvalue, src return for keyvalue, src in parse_keyvalue(src): # , yield keyvalue, src
さて、次は何ですか？
実際、それだけです！ シンプルなインターフェイス関数を追加することは残っています。
def parse(s): s = s.strip() # , match = list(parse_value(s)) if len(match) != 1: # - - . :) raise ValueError("not a valid JSON string") result, src = match[0] if src.strip(): # , - . . raise ValueError("not a valid JSON string") return result
出来上がり！
すべてのコードをまとめて
from itertools import chain import re def sequence(*funcs): if len(funcs) == 0: def result(src): yield (), src return result def result(src): for arg1, src in funcs[0](src): for others, src in sequence(*funcs[1:])(src): yield (arg1,) + others, src return result number_regex = re.compile(r"(-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?)\s*(.*)", re.DOTALL) def parse_number(src): match = number_regex.match(src) if match is not None: number, src = match.groups() yield eval(number), src string_regex = re.compile(r"('(?:[^\\']|\\['\\/bfnrt]|\\u[0-9a-fA-F]{4})*?')\s*(.*)", re.DOTALL) def parse_string(src): match = string_regex.match(src) if match is not None: string, src = match.groups() yield eval(string), src def parse_word(word, value=None): l = len(word) def result(src): if src.startswith(word): yield value, src[l:].lstrip() result.__name__ = "parse_%s" % word return result parse_true = parse_word("true", True) parse_false = parse_word("false", False) parse_null = parse_word("null", None) def parse_value(src): for match in chain( parse_string(src), parse_number(src), parse_array(src), parse_object(src), parse_true(src), parse_false(src), parse_null(src), ): yield match return parse_left_square_bracket = parse_word("[") parse_right_square_bracket = parse_word("]") parse_empty_array = sequence(parse_left_square_bracket, parse_right_square_bracket) def parse_array(src): for _, src in parse_empty_array(src): yield [], src return for (_, items, _), src in sequence( parse_left_square_bracket, parse_comma_separated_values, parse_right_square_bracket, )(src): yield items, src parse_comma = parse_word(",") def parse_comma_separated_values(src): for (value, _, values), src in sequence( parse_value, parse_comma, parse_comma_separated_values )(src): yield [value] + values, src return for value, src in parse_value(src): yield [value], src parse_left_curly_bracket = parse_word("{") parse_right_curly_bracket = parse_word("}") parse_empty_object = sequence(parse_left_curly_bracket, parse_right_curly_bracket) def parse_object(src): for _, src in parse_empty_object(src): yield {}, src return for (_, items, _), src in sequence( parse_left_curly_bracket, parse_comma_separated_keyvalues, parse_right_curly_bracket, )(src): yield items, src parse_colon = parse_word(":") def parse_keyvalue(src): for (key, _, value), src in sequence( parse_string, parse_colon, parse_value )(src): yield {key: value}, src def parse_comma_separated_keyvalues(src): for (keyvalue, _, keyvalues), src in sequence( parse_keyvalue, parse_comma, parse_comma_separated_keyvalues, )(src): keyvalue.update(keyvalues) yield keyvalue, src return for keyvalue, src in parse_keyvalue(src): yield keyvalue, src def parse(s): s = s.strip() match = list(parse_value(s)) if len(match) != 1: raise ValueError("not a valid JSON string") result, src = match[0] if src.strip(): raise ValueError("not a valid JSON string") return result
130行。 実行してみましょう：
>>> import my_json >>> my_json.parse("null") >>> my_json.parse("true") True >>> my_json.parse("false") False >>> my_json.parse("0.31415926E1") 3.1415926 >>> my_json.parse("[1, true, '1']") [1, True, '1'] >>> my_json.parse("{}") {} >>> my_json.parse("{'a': 1, 'b': null}") {'a': 1, 'b': None}
成功！
おわりに
もちろん、パーサーを作成するときに発生する可能性のあるすべての状況を考慮しませんでした。 プログラマーは、一連の
chain
および
sequence
を開始するのではなく、実行を手動で制御する必要がある場合があります。 幸いなことに、これは、考えられるアプローチほど不便ではありません。 したがって、オプションのデザインを解析し、その可用性に応じてアクションを実行する必要がある場合、次のように記述できます。
for stuff, src in parse_optional_stuff(src): # -- break # else else: # -- pass
ここでは、人気のあるPythonチップ（ループ用の
else
ブロック）を使用します。ループは、ループが中断せずに終了した場合に実行されます。 記事のコードほど魅力的には見えませんが、それほど優雅に取り除いたとしても、それは確かに悪くはありません。
プレゼンテーションが不完全でアカデミックでないという性質にもかかわらず、この記事が初心者のプログラマーに役立つこと、そしておそらく高度なプログラマーのアプローチの斬新さを驚かせることを願っています。 同時に、これは古き良き再帰降下のための単なる新しい形式であることをよく知っています。 しかし、プログラミングが芸術である場合、少なくともコンテンツに近い程度であれば、形式は重要ではありませんか？
いつものように、発見されたすべての不正確さ、つづり、文法、事実上の誤りについて個人的なメールを書くことをためらわないでください-さもなければ私は恥をかきます！