アーリーパーサー

アーリーパーサー

クラス	文脈に依存しない文法の解析
データ構造	弦
最悪の場合の パフォーマンス	${\displaystyle O(n^{3})}$
最高の パフォーマンス	${\displaystyle \オメガ (n)}$すべての決定論的文脈自由文法について ${\displaystyle \オメガ (n^{2})}$明確な文法のため
平均的 なパフォーマンス	${\displaystyle \Theta (n^{3})}$

コンピュータサイエンスにおいて、アーリーパーサは、特定の文脈自由言語に属する文字列を解析するアルゴリズムであるが、（その変種によっては）特定のヌル許容文法で問題が発生することがある。^[1]発明者のジェイ・アーリーにちなんで名付けられたこのアルゴリズムは、動的プログラミングを使用するチャートパーサであり、主に計算言語学の解析に使用されている。1968年にアーリーの博士論文^[2]で初めて紹介された（その後、より読みやすい短縮形で雑誌^[3]に掲載された）。

Earley パーサは、 LR パーサやLL パーサとは異なり、すべての文脈自由言語を解析できるため魅力的です。LRパーサや LL パーサは、コンパイラでより一般的に使用されますが、限られた言語クラスしか処理できません。Earley パーサは、一般的なケースでは 3 乗時間 ( nは解析された文字列の長さ)、一義的な文法では 2 乗時間、^{[4] 、すべての}決定論的文脈自由文法では線形時間で実行されます。ルールが左再帰的に記述されている場合に特に優れたパフォーマンスを発揮します。 ${\displaystyle {O}(n^{3})}$ ${\displaystyle {O}(n^{2})}$

次のアルゴリズムは、Earley 認識器について説明しています。認識器は、認識時に解析ツリーを作成するように変更することができ、そのようにしてパーサーに変換できます。

以下の説明では、α、β、γ は任意の終端記号/非終端記号の文字列(空文字列を含む) を表し、X と Y は単一の非終端記号を表し、a は終端記号を表します。

Earley のアルゴリズムは、トップダウンの動的プログラミングアルゴリズムです。以下では、Earley のドット表記を使用します。生成規則X → αβ が与えられた場合、表記 X → α • β は、α がすでに解析されており、β が期待される条件を表します。

入力位置0は入力前の位置です。入力位置nはn番目のトークンを受け入れた後の位置です。（非公式には、入力位置はトークン境界の位置と考えることができます。）入力位置ごとに、パーサは状態セットを生成します。各状態はタプル（X → α • β, i）であり、次のもので構成されています。

• 現在マッチングされている生産量（X → α β）
• その作品の現在の位置（視覚的にはドット・で表されます）
• この生成規則のマッチングが開始された入力の位置i :原点位置

(Earley の元のアルゴリズムには、状態の先読みが含まれていましたが、その後の研究では、これが解析効率にほとんど影響を与えないことが判明し、その後、ほとんどの実装から削除されました。)

状態は、その現在の位置が生成の右側の最後の位置である場合、つまり、状態の視覚的表現でドット • の右側にシンボルがない場合に終了します。

入力位置kの状態セットはS( k )と呼ばれます。パーサーには最上位ルールのみで構成されるS(0)がシードされます。パーサーは 予測、スキャン、完了の3つの操作を繰り返し実行します。

• 予測: S( k )内の(X → α • Y β, j )( jは上記のように原点位置)の形式をとるすべての状態について、左側にYがある文法内のすべての生成規則(Y → γ)に対して、 (Y → • γ, k )をS( k )に追加します。
• スキャン:入力ストリーム内の次のシンボルがaである場合、(X → α • a β, j )の形式のS( k )内のすべての状態に対して、(X → α a • β, j )をS( k +1)に追加します。
• 完了: (Y → γ •, j )の形式のS( k )のすべての状態について、 (X → α • Y β, i )の形式のS( j )のすべての状態を見つけ、(X → α Y • β, i )をS( k )に追加します。

重複した状態は状態セットに追加されず、新しい状態のみが追加されます。これらの 3 つの操作は、セットに新しい状態を追加できなくなるまで繰り返されます。セットは通常、処理する状態のキューとして実装され、実行される操作は状態の種類によって異なります。

このアルゴリズムは、(X → γ •, 0) が S( n )に含まれる場合に受け入れます。ここで、(X → γ) はトップレベルのルールで、n は入力の長さです。それ以外の場合は拒否します。

ダニエル・ジュラフスキーとジェームズ・H・マーティン の音声言語処理^{[5]から引用。}

配列Sを宣言します。  

関数INIT (単語) S ← CREATE_ARRAY ( LENGTH (単語) + 1 ) k ← 0からLENGTH (単語)までS [ k ] ← EMPTY_ORDERED_SETを実行します 
        
           
          

function EARLEY_PARSE ( words , grammar ) INIT ( words ) ADD_TO_SET (( γ → • S , 0 ) , S [ 0 ]) for k ← from 0 to LENGTH ( words ) do for each state in S [ k ] do // S[k] はこのループ中に拡張できますif not FINISHED ( state ) then if NEXT_ELEMENT_OF ( state )が非終端記号then PREDICTOR ( state , k , grammar ) // non_terminal else do SCANNER ( state , k , words ) // terminator else do COMPLETER ( state , k ) end end return chart  
    
        
           
               
               
                     
                               
                 
                                   
             
                 
        
    
     

手順PREDICTOR (( A → α• B β , j ) , k ,文法)それぞれの( B → γ )に対してGRAMMAR_RULES_FOR ( B ,文法)を実行し、 ADD_TO_SET (( B → •γ , k ) , S [ k ])を実行します。終了      
            
            
    

手順SCANNER (( A → α• a β , j ) , k , words )もしj < LENGTH ( words )かつa ⊂ PARTS_OF_SPEECH ( words [ k ] )ならばADD_TO_SET (( A → α a •β , j ) , S [ k + 1 ] )終了      
            
            
    

手順COMPLETER (( B → γ• , x ) , k ) S [ x ]内の各( A → α• B β , j )に対してADD_TO_SET (( A → α B •β , j ) , S [ k ]) を実行するend     
            
            
    

算術式の次の簡単な文法を考えてみましょう。

<P> ::= <S> # 開始ルール
<S> ::= <S> "+" <M> | <M>
<M> ::= <M> "*" <T> | <T>
<T> ::= "1" | "2" | "3" | "4"

入力内容:

2 + 3 * 4

状態セットのシーケンスは次のとおりです。

状態(P → S •, 0)は完了した構文解析を表す。この状態は完全な文であるS(3)とS(1)にも現れる。

Earleyの博士論文^[6]では、Earley項目内の各非終端記号から、その項目が認識される原因となった項目へのポインタのセットを追加することで、構文木を構築するアルゴリズムについて簡単に説明しています。しかし、Tomitaは^[7] 、これが記号間の関係を考慮していないことに気付きました。そのため、文法S → SS | bと文字列bbbを考えると、各Sが1つまたは2つのbに一致する可能性があることのみが示され、bbbの2つの正しい導出だけでなく、bbとbbbbの誤った導出も生成されます。

別の方法^[8]は、構文解析フォレストを構築しながら、各 Earley 項目に、(s, i, j) の 3 つのラベルが付いた共有パック構文解析フォレスト (SPPF) ノードへのポインターを追加します。ここで、s はシンボルまたは LR(0) 項目 (ドット付きの生成規則) であり、i と j は、このノードによって導出された入力文字列のセクションを示します。ノードの内容は、1 つの導出を与える子ポインターのペア、またはポインターのペアを含み 1 つの導出を表す「パックされた」ノードのリストのいずれかです。SPPF ノードは一意 (特定のラベルを持つノードは 1 つだけ) ですが、あいまいな構文解析に対して複数の導出を含む場合があります。そのため、操作によって Earley 項目が追加されない場合でも (すでに存在するため)、項目の構文解析フォレストに導出が追加されることがあります。

• 予測された項目には null SPPF ポインターがあります。
• スキャナーは、スキャンしている非端末を表す SPPF ノードを作成します。
• 次に、スキャナーまたはコンプリーターが項目を進めるときに、ドットが進められた項目のノードと、進められた新しいシンボル (非終端項目または完了項目) のノードを子とする派生を追加します。

SPPF ノードは、完了した LR(0) 項目でラベル付けされることはありません。代わりに、どの代替生成からの派生であるかに関係なく、すべての派生が 1 つのノードの下に結合されるように生成されたシンボルでラベル付けされます。

Philippe McLean と R. Nigel Horspool は、論文「より高速な Earley パーサー」で、Earley 解析と LR 解析を組み合わせて、桁違いの改善を実現しました。

• CYKアルゴリズム
• 文脈自由文法
• 解析アルゴリズム

• Aycock, John; Horspool, R. Nigel (2002). 「Practical Earley Parsing」. The Computer Journal . 45 (6): 620–630. CiteSeerX  10.1.1.12.4254 . doi :10.1093/comjnl/45.6.620.
• Leo, Joop MIM (1991)、「先読みを使用せずにすべてのLR( k )文法で線形時間で実行される一般的な文脈自由構文解析アルゴリズム」、理論計算機科学、82 (1): 165–176、doi : 10.1016/0304-3975(91)90180-A、MR  1112117

• 富田 勝 (1984) 「自然言語のための LR パーサー」(PDF) COLING第10 回国際計算言語学会議 pp. 354–357。