パーサーは、テキストの処理を支援するプログラムです。コンパイラーとインタープリターは、パーサーを使用してプログラムをさらに処理する前に分析し、JSON や YAML などの形式のパーサーは、テキストをプログラミング言語のネイティブ データ構造に処理します。
この記事では、「再帰降下パーサー」を構築する方法を見ていきます。再帰降下パーサーは、パーサーを構築するための単純ですが強力な方法です。処理するテキスト内の「エンティティ」ごとに、関数を定義します。
最初に、構文解析の基礎となる理論のいくつかを見ていきます。次に、Python を使用して、電卓と、コメント、末尾のコンマ、および引用符で囲まれていない文字列をサポートする JSON パーサーを作成します。最後に、前述の例とは異なる動作をする他の種類の言語用のパーサーを構築する方法について説明します。
すでに理論に精通している場合は、パーサーを構築する部分に直接スキップできます。
目次
- 1 解析はどのように機能しますか?
- 2 プロダクション ルールの記述
- パーサーを構築する際の 3 つの考慮事項
- 3.1 文法における優先順位の処理
- 3.2 左再帰の回避
- 3.3 バックトラッキングの回避
- 4 Python で再帰降下パーサーのベースを構築する
- 4.1 例外クラス
- 4.2 基本パーサー クラス
- 4.3 文字範囲の処理
- 4.4 テキストから文字を抽出する
- 4.5 キーワードと記号の抽出
- 4.6 複数のプロダクションを照合するためのヘルパー
- 4.7 今後の予定 – ヘルパー関数
- 5 パーサーの最初の例:電卓
- 5.1 電卓文法の生成規則
- 5.2 パーサーの実装
- 5.3 数字の認識
- 5.4 パーサーのインターフェース
- 6 2 番目のパーサーの例:「拡張された」JSON パーサー
- 6.1 JSON 文法の生成規則
- 6.2 パーサーの実装とコメントの処理
- 6.3 リストとマップの解析
- 6.4 null と boolean の認識
- 6.5 引用符で囲まれていない文字列と数字の認識
- 6.6 引用符付き文字列の認識
- 6.7 JSON パーサーのインターフェース
- 7 他の種類のパーサーの構築
- 7.1 空白に敏感な言語
- 7.2 空白ベースのインデント
解析はどのように機能しますか?
テキストを処理するために、プログラムは 3 つのタスクを実行します。 「字句解析」または「トークン化」と呼ばれるプロセスで、プログラムはテキスト内の文字を調べ、「トークン」と呼ばれる論理グループを抽出します。たとえば、「3 + 5 – 10」などの式では、算術式を処理するプログラムは次のトークンを抽出できます。
[{ "Type": "Number" , "Text": "3" },
{ "Type": "Operator", "Text": "+" },
{ "Type": "Number" , "Text": "5" },
{ "Type": "Operator", "Text": "-" },
{ "Type": "Number" , "Text": "10" }] 次に、プログラムはルールを使用して意味のあるトークンのシーケンスを識別します。これを「解析」と呼びます。これを実現するために使用されるルールは「文法」と呼ばれます。これは、英語のような自然言語の単語が英語の文法を使用して意味のあるシーケンスにつなぎ合わされるのとほぼ同じ方法です。文法の個々のルールは「プロダクション」と呼ばれます。
数式を処理するプログラムを作成していて、足し算と引き算だけに関心があると想像してください。式には数字 (「3」など) が必要で、その後に任意の数の演算子と数字 (「+ 5」など) が続きます。解析ルールは次のように視覚化できます:
は、グループが任意の回数 (ゼロを含む) 繰り返される可能性があることを示します。
最後に、プログラムは文法規則に対して一連のアクションを実行します。たとえば、解析後、数学プログラムは式の値を計算する必要があります。
これらを個別のステップとして説明しましたが、プログラムはこれらすべてを一度に実行できます。すべての手順を一度に実行すると、いくつかの利点が得られます。これが、この記事で採用するアプローチです。
制作規則の作成
この記事の残りの部分では、プロダクション ルールを使用して文法を視覚化します。そのため、この記事全体でプロダクション ルールの記述方法を説明しました。以前に構文解析に関する教科書を読んだことがある場合、ここで使用した表記法は少し異なります。
前に、単純なプロダクションの例を見てきました。文法規則にトークンの名前が含まれていて、トークンがかなり単純な場合、トークンのテキストを文法に書き込むのが一般的です。前の例を考えると、 + が得られます または - 、したがって、次のようにルールを書き直すことができます:
また、何かが何度でも繰り返されることを示すために を使用する方法も見てきました。同様に、a は何かが繰り返されることを示しますが、少なくとも 1 回は発生する必要があります。 A はオプションであることを示します。
例として、「x> 10 and y> 30」のような条件のリストを処理するパーサーを構築しているとします。 and と仮定します はオプションなので、この条件を「x> 10 y> 30」と書き換えることができます。上記の文法を次のように設計できます:
複数の選択肢がある場合は、選択肢の順序が重要です。のようなルールの場合、最初に「+」、次に「-」の一致を試みる必要があります。この些細な例では、順序は重要ではないように見えるかもしれませんが、順序が重要になる例を後で見ていきます。
最後に、プロダクション ルールはトークンとその他の文法記号のみに焦点を当て、空白とコメントを無視します。
パーサーを構築する際の考慮事項
前に、いくつかの単純な文法を見てきました。ただし、より複雑なものを解析しようとすると、多くの問題が発生する可能性があります。ここでそれらについて説明します。
文法における優先順位の処理
前に、足し算と引き算で構成される数式を処理できる文法を見てきました。残念ながら、同じ文法を乗算 (および除算) に拡張することはできません。これらの演算は、加算 (および減算) よりも優先されるためです。
このシナリオを処理するには、パーサーが加算を延期し、遭遇するとすぐに乗算を実行するように文法を設計する必要があります。これを実現するために、以下に示すように、文法を 2 つの個別のルールに分割します。
これが実際に機能することを確認するために、式 (「3 + 2 * 5」など) を使用してみましょう。パーサーが文法規則の照合を完了すると、式が自動的に計算されると仮定します。また、パーサーが探しているものを示すために、下線付きのテキストを使用します。さらに、わかりやすくするために引用符も省略しています。
2 * 5のとき が解析されると、パーサーはすぐに 10 の結果を返します。この結果はステップで受け取られ、最後に加算が実行され、結果として 13 が得られます。
要約すると、優先順位が最も低い演算子が一番上に、優先順位が最も高い演算子が一番下になるように、ルールを配置する必要があります。
左再帰の回避
前に、再帰降下パーサーがテキスト内の「エンティティ」を処理する関数で構成されていることを述べました。トークンとプロダクション ルールについて理解したところで、これをもう少し形式的に再定義しましょう。パーサーの各関数はトークンを抽出するか、プロダクション ルールのロジックを実装します。
これが実際に何を意味するのかを確認するために、簡単な文法を見てみましょう。この文法の疑似コードを書くと、次のようになります:
def expression():
first_number = number()
read('+')
second_number = number()
# process these two numbers, e.g. adding them
次に、コンマで区切られた数字のリストを解析する文法を考えてみましょう。通常は次のように記述します:
さて、何らかの理由で、ワイルドカードを避けて次のように書き直したいと想像してください:
この文法は理論的には正しいです。テキストから 1 つの数字を選択するか、末尾に数字を含むリストに展開します。 2 番目のリストは、パーサーがテキスト全体を終了するまで、別の数値またはリストに展開できます。
ただし、このアプローチには問題があります — 無限再帰に入ってしまいます! list() を呼び出してみると 一度関数を呼び出すと、再び呼び出すことになります。文法を のように書き直すと役立つかもしれないと思うかもしれません。ただし、関数を作成しようとすると、単一の数値を読み取って解析を終了します。読み取った数字は「2、4、6」などのリストの一部である可能性があり、他の数字を読み取ることはできません。
構文解析を扱う場合、これは左再帰と呼ばれます。上記のケースには「直接左再帰」が含まれますが、A が B を呼び出し、B が A を呼び出すなどの「間接左再帰」もあります。いずれの場合も、この問題を回避するために文法を別の方法で書き直す必要があります。
後戻りを避ける
たとえば、「2 + 4」などの 2 つの数値の演算を解析するパーサーを構築しようとしていて、次のように文法を記述したとします。
この文法は正しく、期待どおりに動作し、正しい結果を生成します。ただし、この文法は使用したくないものです。
この理由を理解するために、入力文字列「5 – 2」を考えてみましょう。最初に足し算のルールを使用して、数値を解析します。次に、「+」を期待しますが、文字列を読み取ると「-」が返されます。これは、バックトラックして減算規則を適用する必要があることを意味します。そうすることで、数値の解析に時間と CPU サイクルを浪費し、それを破棄して減算規則の一部として再度解析するだけです。
さらに、ネットワーク ソケットのように、データ ストリームから直接動作するパーサーを構築する場合、ストリームの巻き戻しは多くの場合オプションではありません。この記事では、すべてのテキストをメモリに保持するパーサーのみを扱います。それにもかかわらず、後戻りを避けることは良い習慣であり、そうするために、左から共通部分を除外する必要があります.因数分解後のルールは次のようになります。
ファクタリングのステップが完了し、後戻りが回避されます。ただし、美的な理由から、次のように記述します:
Python で再帰降下パーサーのベースを構築する
解析に関するさまざまな考慮事項について説明したので、計算機と JSON パーサーを作成します。ただし、その前に、文字の認識やエラーの処理など、一般的な機能のためのいくつかのメソッドを持つ基本「パーサー」クラスを作成します。
このセクションは少し長すぎるように思えるかもしれませんが、忍耐する価値は十分にあります。このセクションを完了すると、トークンを認識してプロダクション ルールを実装するために必要なコードがほとんどなく、複雑なパーサーを構築するためのすべてのツールが手に入ります。
例外クラス
これは最も簡単なタスクなので、最初にこれに取り組みます。 ParseError という名前の独自の例外クラスを定義します そのように:
class ParseError(Exception):
def __init__(self, pos, msg, *args):
self.pos = pos
self.msg = msg
self.args = args
def __str__(self):
return '%s at position %s' % (self.msg % self.args, self.pos)
このクラスは、エラーが発生したテキスト位置、エラー メッセージ (書式文字列として)、および書式文字列への引数を受け入れます。この例外タイプの使用方法を見てみましょう:
e = ParseError(13, 'Expected "{" but found "%s"', "[") 例外を印刷しようとすると、次のようなフォーマットのメッセージが表示されます:
Expected "{" but found "[" at position 13
% を使用していないことに注意してください 書式文字列とその引数内の記号 ('"Expected "{" but found "%s"' % "[" など) ）。これは __str__ で処理されます self.msg をフォーマットしたクラスのメソッド self.pos の要素を使用 .
さて、なぜ __str__ でフォーマットする必要があるのか と尋ねるかもしれません % で記述する代わりに、メソッド ? % を使用していることがわかりました 文字列をフォーマットする演算子は、かなりの時間を要します。文字列を解析するとき、パーサーがさまざまなルールを適用しようとするため、多くの例外が発生します。そのため、文字列の書式設定は本当に必要になるまで延期しました。
パーサーの基本クラス
エラークラスが用意できたので、次のステップはパーサークラスを書くことです。次のように定義します:
class Parser:
def __init__(self):
self.cache = {}
def parse(self, text):
self.text = text
self.pos = -1
self.len = len(text) - 1
rv = self.start()
self.assert_end()
return rv
ここで、cache に気付くでしょう。 __init__ のメンバー メソッド — 文字の認識について説明するときに、なぜこれが必要なのかについて説明します。
parse メソッドは非常に単純です。まず、文字列を格納します。文字列のどの部分もまだスキャンしていないので、位置を -1 に設定します。また、文字列の最大インデックスを self.len に格納します . (最大インデックスは、常に文字列の長さより 1 少ない値です。)
次に、文字列の解析を開始し、文字列の末尾に到達したかどうかを確認します。これは、パーサーが最後に何も残さずにテキスト全体を処理できるようにするためです。この後、結果を返します。
assert_end メソッドは簡単です。現在の位置が最大インデックスより小さいかどうかを確認します。簡単にするためにインデントを省略しましたが、これらのメソッドはクラス内にあることに注意してください。
def assert_end(self):
if self.pos < self.len:
raise ParseError(
self.pos + 1,
'Expected end of string but got %s',
self.text[self.pos + 1]
)
パーサー全体を通して、現在のインデックス (self.pos) よりも 1 つ多い文字を確認します。 ）。この理由を理解するために、self.pos = -1 から始めることを考えてみてください。 ですので、インデックス 0 を見ていることになります。文字を正しく認識したら、self.pos 0 になると、インデックス 1 の文字が表示されます。これが、エラーが self.pos + 1 を使用する理由です .
ほとんどの言語では、トークン間の空白は安全に破棄できます。したがって、次の文字が空白文字かどうかをチェックし、そうであれば、次の位置に進むことによってそれを「破棄」するメソッドを含めることは理にかなっています。
def eat_whitespace(self):
while self.pos < self.len and self.text[self.pos + 1] in " fvrtn":
self.pos += 1
文字範囲の処理
次に、テキスト内の文字を認識するのに役立つ関数を作成します。ただし、その前に、ユーザーの観点から関数を検討します — テキストから一致する一連の文字を関数に与えます。たとえば、アルファベットやアンダースコアを認識したい場合は、次のように記述します:
self.char('A-Za-z_')
char を指定します 文字または範囲のリストを含むメソッド (A-Z など) 上記の例では）。範囲は - で区切られた 2 文字で表されます .最初の文字は、右側の文字より数値的に小さい値を持っています.
self.text[self.pos + 1] の文字が self.char の引数の何かに一致します 、私たちはそれを返します。そうでない場合は、例外が発生します。
内部的には、文字列を処理しやすいものに処理します — ['A-Z', 'a-z', '_'] のような個別の文字または範囲を持つリストです。 .そこで、範囲を分割する関数を書きます:
def split_char_ranges(self, chars):
try:
return self.cache[chars]
except KeyError:
pass
rv = []
index = 0
length = len(chars)
while index < length:
if index + 2 < length and chars[index + 1] == '-':
if chars[index] >= chars[index + 2]:
raise ValueError('Bad character range')
rv.append(chars[index:index + 3])
index += 3
else:
rv.append(chars[index])
index += 1
self.cache[chars] = rv
return rv
ここでは、chars をループします。 文字列、- を探します 続いて別のキャラクター。この条件に一致し、最初の文字が最後の文字よりも小さい場合は、範囲全体を追加します (A-Z など)。 ) リスト rv に .それ以外の場合は、chars[index] に文字を追加します rv へ .
次に、リストを rv に追加します それをキャッシュに。この文字列を 2 回目にすると、try ... except KeyError: ... を使用してキャッシュから返します。
確かに、['A-Z', 'a-z', '_'] のようなリストを提供することもできました。 char に 方法。ただし、私たちの意見では、この方法で行うと char() が呼び出されます 少しきれいに見えます。
テキストからの文字の抽出
範囲と文字を含むリストを提供するメソッドができたので、テキストから文字を抽出する関数を記述できます。 char のコードは次のとおりです。 メソッド:
def char(self, chars=None):
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
'character' if chars is None else '[%s]' % chars
)
next_char = self.text[self.pos + 1]
if chars == None:
self.pos += 1
return next_char
for char_range in self.split_char_ranges(chars):
if len(char_range) == 1:
if next_char == char_range:
self.pos += 1
return next_char
elif char_range[0] <= next_char <= char_range[2]:
self.pos += 1
return next_char
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
'character' if chars is None else '[%s]' % chars,
next_char
)
まず引数 chars=None に注目しましょう .これにより、self.char() を呼び出すことができます 文字のセットを指定せずに。これは、文字を特定のセットに限定せずに単純に抽出したい場合に便利です。それ以外の場合は、前のセクションで見たように、さまざまな文字で呼び出すことができます。
この関数は非常に簡単です。まず、テキストが不足しているかどうかを確認します。次に、次の文字を選択し、chars が None かどうかを確認します この場合、位置をインクリメントして文字をすぐに返すことができます。
ただし、chars に文字列がある場合 、['A-Z', 'a-z', '_'] などの個々の文字と範囲のリストに分割します .このリストでは、長さ 1 の文字列は文字であり、それ以外はすべて範囲です。次の文字が文字または範囲に一致するかどうかをチェックし、一致する場合はそれを返します。何に対しても一致しなかった場合、ParseError を発生させるループを終了します。 、予期した文字を取得できなかったと述べています。
'character' if chars is None else '[%s]' % chars より読みやすい例外を提供する方法にすぎません。 chars の場合 None です の場合、例外のメッセージは Expected character but got ... となります 、しかし char の場合 A-Za-z_ のような値に設定されていました 、 Expected [A-Za-z_] but got ... を取得します .
後で、この関数を使用してトークンを認識する方法について説明します。
キーワードと記号の抽出
個々の文字の抽出とは別に、キーワードの認識は、パーサーを構築する際の一般的なタスクです。 「キーワード」を使用して、「独自のエンティティ」である連続した文字列を大まかに参照し、その前後に空白を含めることができます。たとえば、JSON { では キーワードの可能性があり、プログラミング言語では if 、 else キーワードなどです。
これは、キーワードを認識するためのコードです:
def keyword(self, *keywords):
self.eat_whitespace()
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
','.join(keywords)
)
for keyword in keywords:
low = self.pos + 1
high = low + len(keyword)
if self.text[low:high] == keyword:
self.pos += len(keyword)
self.eat_whitespace()
return keyword
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
','.join(keywords),
self.text[self.pos + 1],
)
このメソッドは self.keyword('if', 'and', 'or') などのキーワードを取ります .このメソッドは空白を取り除き、解析するテキストが不足しているかどうかをチェックします。次に、各キーワードを繰り返し処理し、キーワードがテキストに存在するかどうかを確認します。何かが見つかった場合は、キーワードに続く空白を取り除き、キーワードを返します。
ただし、何かが見つからない場合は、ParseError を発生させるループを終了します。 、キーワードが見つからなかったことを示しています。
複数の作品を照合するためのヘルパー
前のセクションで、例外を使用してエラーを報告していることに気づきました。また、再帰降下パーサーを作成するには、トークンまたはプロダクション ルールを認識する関数を作成することもわかっています。ここで、数値または単語を期待する単純なテキストを解析したいと想像してください。生産ルールは次のようになります:
また、テキストに単語が含まれていると仮定します。パーサーが数字を探そうとしたとき (おそらく char() を使用して) )、見つからないため、例外が発生します。さらに、プロダクション ルールに一致する前後に空白を削除する必要があります。したがって、item() のコードは 次のようになります:
def item(self): self.eat_whitespace() try: rv = self.number() except ParseError: rv = self.word() self.eat_whitespace() return rv
これは単純なルールを実装するだけでも大変なことのように見えます!複雑なルールを実装するとどうなるか想像してみてください — try...except を使用する必要があります
match() と書きます。 空白を取り除き、複数のルールに一致させようとする関数。機能は次のとおりです。
def match(self, *rules):
self.eat_whitespace()
last_error_pos = -1
last_exception = None
last_error_rules = []
for rule in rules:
initial_pos = self.pos
try:
rv = getattr(self, rule)()
self.eat_whitespace()
return rv
except ParseError as e:
self.pos = initial_pos
if e.pos > last_error_pos:
last_exception = e
last_error_pos = e.pos
last_error_rules.clear()
last_error_rules.append(rule)
elif e.pos == last_error_pos:
last_error_rules.append(rule)
if len(last_error_rules) == 1:
raise last_exception
else:
raise ParseError(
last_error_pos,
'Expected %s but got %s',
','.join(last_error_rules),
self.text[last_error_pos]
)
どのように機能するかを説明する前に、前の例を match() を使用して簡単に書き直すことができるか見てみましょう。 :
def item(self):
return self.match('number', 'word')
それで、それはどのように機能しますか？ match() 実行するメソッド名を取ります (number など) または word 上記の例では）。まず、先頭の空白を取り除きます。次に、すべてのメソッド名を反復処理し、getattr() 経由でその名前を使用して各メソッドを取得します .次に、メソッドの呼び出しを試み、すべてがうまくいけば、テキストの後の空白も削除します。最後に、メソッドを呼び出して受け取った値を返します
ただし、エラーが発生した場合は self.pos をリセットします ルールに一致させる前に存在していた値に。次に、次のルールを使用して適切なエラー メッセージを選択しようとします。
- 複数のルールに一致する場合、それらの多くでエラーが発生する可能性があります。ほとんどのテキストを解析した後に生成されたエラーは、おそらく必要なエラー メッセージです。
この理由を理解するために、文字列「abc1」について考えてみましょう。 number() に電話しようとしています word() は位置 0 で失敗しますが、 位置 2 で失敗します。文字列を見ると、ユーザーが単語を入力したかったのにタイプミスをした可能性が非常に高いです。
- 2 つ以上のエラー ルールが「引き分け」になった場合、失敗したすべてのルールについてユーザーに通知することをお勧めします。
last_error_pos と last_exception 最後のエラーの位置と例外をそれぞれ追跡します。さらに、リスト last_error_rules を維持しています 同点の場合に、一致させようとしたすべてのルールをユーザーに伝えることができるようにします。
except ParseError で ブロックで、最後のエラーの位置と現在のエラーを比較します。現在のエラーが等しい場合、同点と見なし、リストに追加します。それ以外の場合は、エラーの位置、例外、およびエラーが発生したルールのリストを更新します。
最後に、失敗したルールの数を確認します。 1 つしかない場合は last_exception 最適なエラー メッセージが表示されます。それ以外の場合は引き分けであり、Expected number,word but found ... のようなメッセージでユーザーに通知します .
今後の予定 - ヘルパー関数
この時点で、パーサーに必要なものがすべて揃っており、すべての失敗で例外がスローされます。ただし、文字、キーワード、またはルールが存在する場合にのみ一致させたい場合があり、例外を処理する不便さはありません。
それを行うための 3 つの小さなヘルパーを紹介します。ものを探すときに例外が発生した場合、これらは None を返します :
def maybe_char(self, chars=None):
try:
return self.char(chars)
except ParseError:
return None
def maybe_match(self, *rules):
try:
return self.match(*rules)
except ParseError:
return None
def maybe_keyword(self, *keywords):
try:
return self.keyword(*keywords)
except ParseError:
return None
これらの機能を使用するのは簡単です。使用方法は次のとおりです:
operator = self.maybe_keyword('+', '-'):
if operator == '+':
# add two numbers
elif operator == '-':
# subtract two numbers
else: # operator is None
# do something else
最初のパーサーの例:電卓
パーサーを書くための基礎を構築したので、最初のパーサーを構築します。足し算、引き算、掛け算、割り算を含む数式を解析し、「(2 + 3) * 5」のような括弧付きの式も処理できます。
まず、文法をプロダクション ルールの形で視覚化します。
電卓文法の生成規則
以前に、括弧で囲まれた式を除くすべてを処理する文法を見てきました:
では、括弧で囲まれた式がこの文法にどのように適合するかを考えてみましょう。 「(2 + 3) * 5」を評価するときは、「(2 + 3)」を計算して数に減らす必要があります。つまり、上記の文法では、「数値」という用語は、括弧で囲まれた式、または「5」のような実際の数値のいずれかを指すことができます.
そのため、両方に対応するようにルールを微調整します。 「Term」のルールでは、「Number」を「Factor」などのより適切な用語に置き換えます。 「Factor」は、括弧で囲まれた式または「Number」のいずれかを参照できます。変更された文法は次のようになります:
それでは、本番ルールを実装しましょう!
パーサーの実装
基本の Parser クラスを拡張して、Calculator パーサーを実装します。次のようにクラスの定義を開始します。
class CalcParser(Parser):
def start(self):
return self.expression()
以前は、基本パーサー クラスを実装するときに start() がありました。 解析を開始するメソッド。 expression() を呼び出すだけです 以下のように定義します:
def expression(self):
rv = self.match('term')
while True:
op = self.maybe_keyword('+', '-')
if op is None:
break
term = self.match('term')
if op == '+':
rv += term
else:
rv -= term
return rv
の文法規則。そのため、テキストから用語を読み取ることから始めます。次に、無限ループを設定し、「+」または「-」を探します。どちらも見つからない場合は、 で指定された追加用語のリストを読み終えたことを意味するため、ループから抜け出すことができます。
それ以外の場合は、テキストから別の用語を読み取ります。次に、演算子に応じて、初期値に加算または減算します。 「+」または「-」を取得できなくなるまでこのプロセスを続け、最後に値を返します。
term() を実装します 同様に:
def term(self):
rv = self.match('factor')
while True:
op = self.maybe_keyword('*', '/')
if op is None:
break
term = self.match('factor')
if op == '*':
rv *= term
else:
rv /= term
return rv 次に「Factor」を実装します。最初に左括弧を読み取ろうとします。これは、括弧で囲まれた式があることを意味します。括弧が見つかった場合は、式と閉じ括弧を読み取り、式の値を返します。それ以外の場合は、数値を読み取って返すだけです。
def factor(self):
if self.maybe_keyword('('):
rv = self.match('expression')
self.keyword(')')
return rv
return self.match('number')
次のセクションでは、パーサーに数値を認識させます。
数字の認識
数字を認識するためには、テキストの個々の文字を見る必要があります。数値は 1 つ以上の数字で構成され、オプションで小数点以下が続きます。小数部分にはピリオド (.) があり、その後に少なくとも 1 つの数字が続きます。さらに、「-124.33」のように、数字の前に「+」や「-」などの符号が付く場合があります。
number() を実装します 次のような方法:
def number(self):
chars = []
sign = self.maybe_keyword('+', '-')
if sign is not None:
chars.append(sign)
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
if self.maybe_char('.'):
chars.append('.')
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
rv = float(''.join(chars))
return rv
関数は長いですが、かなり単純です。 chars があります 数字の文字を入れるリスト。まず、数字の前に存在する可能性のある「+」または「-」記号を調べます。存在する場合は、リストに追加します。次に、番号の最初の必須桁を探し、maybe_char() を使用してさらに桁を探し続けます。 方法。 None を取得したら maybe_char まで 、一連の数字を超えていることがわかり、ループを終了します。
同様に、小数部分とその桁を探します。最後に、すべての文字を文字列に変換し、それを浮動小数点数に変換します。
パーサーのインターフェース
パーサーの構築が完了しました。最後のステップとして、式を入力して結果を表示できるようにするコードをグローバル スコープに少し追加します。
if __name__ == '__main__':
parser = CalcParser()
while True:
try:
print(parser.parse(input('> ')))
except KeyboardInterrupt:
print()
except (EOFError, SystemExit):
print()
break
except (ParseError, ZeroDivisionError) as e:
print('Error: %s' % e)
ここまでフォローしてくださった方、おめでとうございます!これで、最初の再帰降下パーサーが作成されました!
ローカル IDE を使用している場合は、この時点でコードを実行できます。または、以下のプレイグラウンドを使用してパーサーを実行することもできます。下の「入力」タブから式を入力できます。
完全なコードもここにあります。
2 番目のパーサーの例:「拡張」JSON パーサー
JSON は、数値、文字列、リストなどの基本的なデータ構造をサポートするデータ交換形式です。これは非常に広く使用されている形式ですが、単純であるということは、コメントなどの要素が欠けていたり、受け入れる内容が厳密であったりすることを意味します。たとえば、リストの末尾にカンマを付けたり、符号を示すために数字の前に明示的な「+」を付けたりすることはできません。
Python には既に JSON モジュールがあるため、もう少し上位を目指して、コメント、末尾のコンマ、および引用符で囲まれていない文字列をサポートする JSON パーサーを構築します。
このパーサーを実装すると、コメントの処理方法がわかります。また、使いやすい言語を作成すると解析が複雑になることや、そのような状況に対処する方法についても説明します。
文法を実装する前に、拡張された JSON 形式の感触をつかみましょう。
{
# Comments begin with a '#' and continue till the end of line.
# You can skip quotes on strings if they don't have hashes,
# brackets or commas.
Size: 1.5x,
# Trailing commas are allowed on lists and maps.
Things to buy: {
Eggs : 6,
Bread: 4,
Meat : 2,
},
# And of course, plain JSON stuff is supported too!
"Names": ["John", "Mary"],
"Is the sky blue?": true
} JSON 文法の生成規則
拡張された JSON は、JSON がサポートするのと同じデータ型に固執します。 JSON には、null、ブール値、数値、文字列の 4 つのプリミティブ データ型と、リスト (または配列) とマップ (ハッシュまたは辞書とも呼ばれる) の 2 つの複雑なデータ型があります。リストとハッシュは、Python での方法と似ています。
JSON データはこれらのタイプのいずれかで構成されるため、プロダクション ルールは次のように記述できます。
次に、これら 2 つの型を JSON の型に分割できます。
この文法は、通常の JSON を解析するには問題ありませんが、今回のケースでは少し調整が必要です。引用符なしの文字列をサポートするので、「1.5」(引用符なし) は数値ですが、「1.5x」(引用符なし) は文字列です。現在の文法では、「1.5x」から「1.5」を読み取り、数字の後に「x」が必要ではないため、エラーが発生します。
これは、最初に、引用符で囲まれていない文字の完全なセットを取得する必要があることを意味します。次に、文字を分析して、それが数値か文字列かを判断します。そのため、数字と引用符のない文字列を「引用符なし」という 1 つのカテゴリにまとめます。引用符で囲まれた文字列は問題ないので、別のカテゴリ「QuotedString」に分けます。 「PrimitiveType」の変更されたプロダクション ルールは次のようになります。
さらに、ルールの順序も重要です。引用符で囲まれていないキーがあるため、最初にテキストを null またはブール値として解析する必要があります。そうしないと、「null」または「true」を引用符で囲まれていない文字列として認識してしまう可能性があります。
パーサーの実装とコメントの処理
JSON パーサーを実装するには、基本パーサー クラスを次のように拡張することから始めます。
class JSONParser(Parser): # ...
最初に、コメントを処理する問題に取り組みます。考えてみれば、コメントは空白と本当に似ています — コメントは空白が発生する可能性のある場所で発生し、空白と同じように破棄できます。 eat_whitespace() を再実装します。 コメントを処理するには、次のようにします:
def eat_whitespace(self):
is_processing_comment = False
while self.pos < self.len:
char = self.text[self.pos + 1]
if is_processing_comment:
if char == 'n':
is_processing_comment = False
else:
if char == '#':
is_processing_comment = True
elif char not in ' fvrtn':
break
self.pos += 1
ここでは、空白とコメントのどちらを処理しているかを追跡する必要があります。テキストを 1 文字ずつループし、空白や # があるかどうかをチェックします。 . # がある場合 、 is_processing_comment を更新します Trueまで そして while の次の繰り返しで ループして、行末に到達するまですべての文字を安全に破棄できます。ただし、空白文字を処理する場合、空白以外の文字が表示されたら停止する必要があります。
次に、プロダクション ルールと start() を実装します。 方法。入力テキストには JSON 型が含まれているため、単純に any_type() を呼び出します。 start() で メソッド:
def start(self):
return self.match('any_type')
def any_type(self):
return self.match('complex_type', 'primitive_type')
def primitive_type(self):
return self.match('null', 'boolean', 'quoted_string', 'unquoted')
def complex_type(self):
return self.match('list', 'map')
リストとマップの解析
以前、カンマ区切りのリストを解析する方法を見てきました。 JSON のリストは、カンマで区切られたリストに角かっこが追加されたものであり、リストには 0 個以上の要素が含まれる場合があります。リストの解析を実装する方法を見てみましょう:
def list(self):
rv = []
self.keyword('[')
while True:
item = self.maybe_match('any_type')
if item is None:
break
rv.append(item)
if not self.maybe_keyword(','):
break
self.keyword(']')
return rv
self.maybe_match('any_type') を使用して、最初の角括弧を読み取り、その後にリストから項目を読み取ります。 .アイテムの取得に失敗した場合、これはおそらくすべてのアイテムの処理が完了していることを示しているため、ループから抜け出します。それ以外の場合は、アイテムをリストに追加します。次に、リストからコンマを読み取ろうとします。コンマがないことは、リストの処理が完了していることも示しています。
同様に、マップは中括弧付きの「ペア」のカンマ区切りのリストです。ペアは、文字列キーの後にコロン (:) と値が続きます。 Python の dict とは異なり キーとして任意の「ハッシュ可能な」タイプを持つことができる s (これには int が含まれます) s と tuple s)、JSON は文字列キーのみをサポートします。
これは、マップとペアのルールを実装する方法です:
def map(self):
rv = {}
self.keyword('{')
while True:
item = self.maybe_match('pair')
if item is None:
break
rv[item[0]] = item[1]
if not self.maybe_keyword(','):
break
self.keyword('}')
return rv
def pair(self):
key = self.match('quoted_string', 'unquoted')
if type(key) is not str:
raise ParseError(
self.pos + 1,
'Expected string but got number',
self.text[self.pos + 1]
)
self.keyword(':')
value = self.match('any_type')
return key, value
pair() で 、キーの「QuotedString」または「Unquoted」を読み取ろうとします。前に述べたように、「引用符なし」は数値または文字列を返すことができるため、読み取ったキーが文字列かどうかを明示的に確認します。 pair() 次に、キーと値を含むタプルと map() を返します pair() を呼び出します これらを Python dict に追加します。
null とブール値の認識
Now that the main parts of our parser are implemented, let us begin by recognizing simple tokens such as null and booleans:
def null(self):
self.keyword('null')
return None
def boolean(self):
boolean = self.keyword('true', 'false')
return boolean[0] == 't'
Python’s None is the closest analogue to JSON’s null . In the case of booleans, the first characters is sufficient to tell whether it’s true or false , and we return the result of the comparison.
Recognizing unquoted strings and numbers
Before moving on to recognize unquoted strings, let us first define the set of acceptable characters. We’ll leave out anything that’s considered special in such as braces, quotes, colons, hashes (since they are used in comments) and backslashes (because they’re used for escape sequences). We’ll also include spaces and tabs in the acceptable set of characters so that you can write strings like “Things to buy” without using quotes.
So, what are the characters that we want to accept? We can use Python to figure this out:
>>> import string
>>> ''.join(sorted(set(string.printable) - set('{}[]:#"'fvrn')))
't !$%&()*+,-./0123456789;<=>[email protected]^_`abcdefghijklmnopqrstuvwxyz|~'
The next question is, how do you figure out if the text you read is a number or a string? The answer is — we cheat! Since Python’s int() and float() can take a string and return a number, we’ll use them and if those result in a ValueError , we’ll return a string. As for when to use int() or float() , we’ll use a simple rule. If the text contains “E”, “e” or “.”, (for example, “12.3” or “2e10”), we’ll call float(); otherwise, we’ll use int() .
Here’s the code:
def unquoted(self):
acceptable_chars = '0-9A-Za-z t!$%&()*+./;<=>?^_`|~-'
number_type = int
chars = [self.char(acceptable_chars)]
while True:
char = self.maybe_char(acceptable_chars)
if char is None:
break
if char in 'Ee.':
number_type = float
chars.append(char)
rv = ''.join(chars).rstrip(' t')
try:
return number_type(rv)
except ValueError:
return rv
Since matching rules are handled by match() , this takes care of stripping any initial whitespace before unquoted() 実行できます。 In this way, we can be sure that unquoted() won’t return a string consisting of only whitespaces. Any whitespace at the end is stripped off before we parse it as a number or return the string itself.
Recognizing quoted strings
Quoted strings are fairly simple to implement. Most programming languages (including Python) have single and double quotes that behave in the same way, and we’ll implement both of them.
We’ll support the following escape sequences — b (backspace), f (line feed), n (newline), r (carriage return), t (tab) and u(four hexadecimal digits) where those digits are used to represent an Unicode “code point”. For anything else that has a backslash followed by a character, we’ll ignore the backslash. This handles cases like using the backslash to escape itself ( ) or escaping quotes (" ).
Here’s the code for it:
def quoted_string(self):
quote = self.char('"'')
chars = []
escape_sequences = {
'b': 'b',
'f': 'f',
'n': 'n',
'r': 'r',
't': 't'
}
while True:
char = self.char()
if char == quote:
break
elif char == '':
escape = self.char()
if escape == 'u':
code_point = []
for i in range(4):
code_point.append(self.char('0-9a-fA-F'))
chars.append(chr(int(''.join(code_point), 16)))
else:
chars.append(escape_sequences.get(char, char))
else:
chars.append(char)
return ''.join(chars)
We first read a quote and then read additional characters in a loop. If this character is the same type of quote as the first character we read, we can stop reading further and return a string by joining the elements of chars .
Otherwise, we check if it’s an escape sequence and handle it in the aforementioned way, and add it to chars . Finally, if it matches neither of them, we treat it as a regular character and add it to our list of characters.
An interface for our JSON parser
To make sure we can interact with our parser, we’ll add a few lines of code that accepts input and parses it as JSON. Again, this code will be in global scope:
if __name__ == '__main__':
import sys
from pprint import pprint
parser = JSONParser()
try:
pprint(parser.parse(sys.stdin.read()))
except ParseError as e:
print('Error: '+ str(e))
To ensure we can read multiple lines, we have used sys.stdin.read() . If you’re going to run this locally, you can enter text and use Ctrl+D to stop the program from asking for more input. Otherwise, you can use this runnable snippet:
You can find the complete code here.
Building other kinds of parsers
Now that we’ve gone through building two parsers, you might have a fairly good idea of how to roll your own for the task at hand. While every language is unique (and therefore, their parsers), there are some common situations that we haven’t covered. For the sake of brevity, we won’t cover any code in these sections.
Whitespace sensitive languages
Before we begin, let us clarify that we’re not referring to languages that use whitespace-based indentation — we’ll cover them in the next section. Here, we’ll discuss languages where the meaning of things change based on the whitespace you put between elements.
An example of such a language would be where “a=10” is different than “a =10”. With bash and some other shells, “a=10” sets an environment variable, whereas “a =10” runs the program “a” with “=” and “10” as command-line arguments. You can even combine the two! Consider this:
a=10 b=20 c = 30
This sets the environment variables “a” and “b” only for the program “c”. The only way to parse such a language is to handle the whitespaces manually, and you’d have to remove all the eat_whitespace() calls in keyword() and match() . This is how you might write the production rules:
Whitespace based indentation
Languages like C and Javascript use curly braces to indicate the body of loops and if-statements. However, Python uses indentation for the same purpose, which makes parsing tricky.
One of the methods to handle this is to introduce a term such as “INDENT” to keep track of indented statements. To see how this would work, consider the following production rule:
After matching a condition, our parser would look for INDENT. Since this is the first time it’s trying to match INDENT, it takes whatever whitespace (except for newlines) that appears along with a non-whitespace character (since that would be part of a statement).
In subsequent iterations, it looks for the same whitespace in the text. If it encounters a different whitespace, it can raise an error. However, if there’s no whitespace at all, it indicates that the “while” loop is finished.
For nested indentations, you’d need to maintain a list of all indentations that you’re currently handling. When the parser handles a new indented block, it should add the new indentation string on the list. You can tell if you’re done parsing the block, by checking that you were able to retrieve less whitespace than you did previously. At this point, you should pop off the last indentation off the list.