トップダウン解析言語

トップダウン構文解析言語(TDPL)は、1970 年代初頭に Alexander Birman によって開発された解析 形式文法の一種です^{[1] [2] [3]。}これは、限定的な形式のバックトラッキングをサポートする一般的なトップダウン構文解析器の動作を形式的に研究するためでした。Birman は当初、初期の構文解析器生成器TMGにちなんでこの形式論をTMG スキーマ(TS) と名付けましたが、後にAhoとUllmanの古典アンソロジー The Theory of Parsing, Translation and CompilingでTDPL という名前が付けられました^[4]。

正式には、TDPL 文法 Gは次のコンポーネントから構成される 4 つの要素です。

• 非終端記号の有限集合N。
• Nと交わらない終端記号の有限集合 Σ 。
• 生成規則の有限集合P。規則は次のいずれかの形式を持ちます。
  • A → ε、ここでAは非終端記号、ε は空文字列です。
  • A → f、ここでf は無条件の失敗を表す特別な記号です。
  • A → a、ここでa は任意の終端記号です。
  • A → BC/D、ここでB、C、およびDは非終端記号です。

TDPL 文法は、再帰下降パーサーの極めて最小限の形式表現と見なすことができます。再帰下降パーサーでは、各非終端記号が構文解析関数を図式的に表します。これらの各非終端関数は、認識される文字列を入力引数として受け取り、次の 2 つの結果のいずれかを生成します。

• 成功の場合、関数はオプションで前進するか、与えられた入力文字列の1つ以上の文字を消費するか、または
• 失敗の場合、入力は消費されません。

非終端関数は実際には入力を消費せずに成功する可能性があり、これは失敗とは異なる結果と見なされることに注意してください。

A → εの形式の規則で定義された非終端記号A は、提供された入力文字列に関係なく、入力を消費せずに常に成功します。逆に、A → fの形式の規則は、入力に関係なく常に失敗します。A → aの形式の規則は、入力文字列の次の文字が終端記号aである場合に成功します。この場合、非終端記号は成功し、その終端記号を 1 つ消費します。次の入力文字が一致しない場合 (または次の文字がない場合)、非終端記号は失敗します。

A → BC/D の形式の規則によって定義された非終端記号Aは、最初に非終端記号B を再帰的に呼び出し、Bが成功した場合は、Bによって消費されなかった入力文字列の残りの部分に対してC を呼び出します。BとC の両方が成功した場合は、Aも成功し、 BとC を合わせたのと同じ入力文字数を消費します。 ただし、 BまたはCのいずれかが失敗した場合は、A は最初に呼び出された入力文字列の元のポイントまでバックトラックし、元の入力文字列に対してD を呼び出し、 D が生成した結果を返します。

次の TDPL 文法は、任意の長さの a と b のシーケンスで構成される 正規言語を記述します。

S → AS/T

T → BS/E

あ→ あ

B → b

E → ε

次の文法は、「{}」、「{{}{{}}}」などの一致する中括弧の任意の長さの文字列で構成される 文脈自由 Dyck 言語を記述します。

S → OT/E

T → SU/F

U → CS/F

お→ {

C → }

E → ε

F → f

上記の例は、解析式の文法表記ではそれぞれ および として同等に、しかしより簡潔に表すことができます。 S ← (a/b)*S ← ({S})*

TDPL のわずかなバリエーションである一般化 TDPLまたは GTDPL は、同じミニマリスト アプローチを維持しながら (実際には同等ですが)、TDPL の表現力を大幅に向上させます。GTDPL では、TDPL の再帰ルール形式A → BC/Dの代わりに、ルール形式A → B[C,D]が使用されます。このルールは次のように解釈されます。非終端記号Aが何らかの入力文字列で呼び出されると、最初にB を再帰的に呼び出します。Bが成功した場合、A は続いてBで消費されなかった入力の残りに対してC を呼び出し、 Cの結果を元の呼び出し元に返します。一方、Bが失敗した場合、 A は元の入力文字列に対してD を呼び出し、結果を呼び出し元に返します。

このルール形式とTDPL で使用されるA → BC/Dルール形式の重要な違いは、 CとDの両方がAへの同じ呼び出しで呼び出されることはないということです。つまり、 GTDPL ルールは、 B を条件として 使用する「純粋な」 if/then/else 構造のように動作します。

GTDPL では、古典的な例 {a ⁿ b ⁿ c ⁿ } のような興味深い非文脈自由言語を簡単に表現できます。

GTDPL文法は、同じ言語を認識する同等のTDPL文法に縮小することができますが、そのプロセスは簡単ではなく、必要なルールの数が大幅に増加する可能性があります。^[5] また、TDPLとGTDPLはどちらも、同じクラスの文法を表す、非常に制限された形式の構文解析式文法と見なすことができます。^[5]

• 正式な文法
• 再帰降下パーサー
• 構文解析式の文法

• Packrat の解析と解析式文法のページ