5

PetitParser で実装しようとしている (簡略化された) EBNF セクションは次のとおりです。

variable :: component / identifier
component :: indexed / field
indexed :: variable , $[ , blah , $]
field :: variable , $. , identifier

私がしたことは、これらすべてのプロダクション ( を除くidentifier) をサブクラスの ivar として追加PPCompositeParserし、対応するメソッドを次のように定義することでした。

variable
  ^component / self identifier

component
  ^indexed / field

identifier
  ^(#letter asParser, (#word asParser) star) flatten

indexed
  ^variable , $[ asParser, #digit asParser, $] asParser

field
  ^variable , $. asParser, self identifier

start
  ^variable

最後に、パーサーの新しいインスタンスを作成し、メッセージを送信しましたparse: 'a.b[0]'。

問題:スタック オーバーフローが発生します。

4

2 に答える 2

5

問題は、文法がrecursive のままになっていることです。PetitParser は、トップダウンの貪欲なアルゴリズムを使用して、入力文字列を解析します。start順を追ってみると、それからということがわかりますvariable -> component -> indexed -> variable。これは、入力を消費せずに無限に実行されるループになり、スタック オーバーフローの原因になります (実際には左再帰です)。

この状況を解決する秘訣は、中間ステップを追加してパーサーを書き直し、左再帰を回避することです。基本的な考え方は、書き換えられたバージョンは各サイクルで少なくとも 1 文字を消費するということです。「indexed」と「field」の非再帰部分をリファクタリングするパーサーを少し単純化し、それらを一番下に移動することから始めましょう。

variable
  ^component, self identifier

component
  ^indexed / field

indexed
  ^variable, subscript

field
  ^variable, fieldName

start
  ^variable


subscript
    ^$[ asParser, #digit asParser, $] asParser

fieldName
    ^$. asParser, self identifier

identifier
  ^(#letter asParser, (#word asParser) star) flatten

variableこれで、(ループをたどることで) 再帰が終了する場合、最初に識別子を見つける必要があることをより簡単に確認できます。それが開始する唯一の方法であり、その後、さらに入力が行われます (または終了します)。その2番目の部分を呼びましょうvariable':

variable
    ^self identifier, variable'

これで、 は実際に消費された識別子を持つものを参照し、 の左から右にvariable'再帰を安全に移動できます。indexedfieldvariable'

variable'
    component', variable' / nil asParser

component'
    ^indexed' / field'

indexed'
    ^subscript

field'
    ^fieldName

実際にコードをテストせずにこの回答を書きましたが、問題ないはずです。パーサーはさらに単純化できます。それは練習問題として残します ;)。

左再帰消去の詳細については、左再帰消去を参照してください。

于 2019-01-16T00:51:33.853 に答える