1

これは、コンパイラー内でFIRST＆FOLLOWセットをエンコードする方法について尋ねた前の質問のフォローアップですが、これは私のプログラムの設計に関するものです。

再帰下降パーサーを作成して、コンパイラーの構文解析フェーズを実装しています。ソースプログラムの構文のエラーをより効率的に処理できるように、FIRSTセットとFOLLOWセットを利用できる必要があります。すべての非終端記号のFIRSTとFOLLOWをすでに計算しましたが、プログラムのどこに論理的に配置するか、そしてそれを行うのに最適なデータ構造を決定するのに苦労しています。

注：すべてのコードは擬似コードになります

オプション1）マップを使用し、名前ですべての非終端記号を、FIRSTセットとFOLLOWセットを含む2つのセットにマップします。

class ParseConstants
    Map firstAndFollowMap = #create a map .....
    firstAndFollowMap.put("<program>", FIRST_SET, FOLLOW_SET)
end

これは実行可能なオプションのように見えますが、パーサーの内部では、FIRSTとFOLLOWを取得してエラー関数に渡すために、次のような醜いコードが必要になります。

#processes the <program> non-terminal
def program
    List list    = firstAndFollowMap.get("<program>")
    Set FIRST    = list.get(0)
    Set FOLLOW   = list.get(1)  

   error(current_symbol, FOLLOW)
end

オプション2）非終端記号ごとにクラスを作成し、FIRSTプロパティとFOLLOWプロパティを設定します。

class Program
    FIRST    = .....
    FOLLOW = .... 
end

これにより、コードが少し見栄えが良くなります。

#processes the <program> non-terminal
def program
   error(current_symbol, Program.FOLLOW)
end

これらは私が考えた2つのオプションです。これらの2つのセットをエンコードする方法について他の提案を聞きたいです。また、私が投稿した2つの方法に対する批評や追加も役に立ちます。ありがとう

私もここにこの質問を投稿しました：http：//www.coderanch.com/t/570697/java/java/Encode-FIRST-FOLLOW-sets-recursive

4

1 に答える 1

2

FIRST および FOLLOW セットは実際には必要ありません。解析テーブルを取得するには、それらを計算する必要があります。これは、{<non-terminal, token> -> <action, rule>}if LL(k) の表 (つまりnon-terminal、スタック内とtoken入力内の a を見て、どちらactionを取得し、適用する場合は適用ruleするか)、または{<state, token> -> <action, state>}if (C|LA|)LR(k)の表 (どちらを適用するか) です。はstate、スタックとtoken入力で指定され、どちらactionを取得してどちらに移動するかを意味しstateます。

このテーブルを取得したら、FIRST と FOLLOWS はもう必要ありません。

セマンティック アナライザーを作成している場合は、パーサーが正しく動作していると想定する必要があります。フレーズ レベルのエラー処理 (解析エラーの処理を意味します) は、セマンティック分析とは完全に直交しています。

これは、解析エラーの場合、フレーズ レベル エラー ハンドラ (PLEH) がエラーを修正しようとすることを意味します。できなかった場合、解析は停止します。可能であれば、セマンティック アナライザーは、修正されたエラーがあったのか、それともエラーがまったくなかったのかを認識できません。

例については、私のコンパイラ ライブラリをご覧ください。

フレーズ レベルのエラー処理についても、FIRST と FOLLOW は必要ありません。とりあえず LL(k) について話しましょう (単に LR(k) についてはまだあまり考えていないからです)。文法テーブルを作成した後、次のように述べたように、多くのエントリがあります。

<non-terminal, token> -> <action, rule>

さて、解析するときは、スタックにあるものをすべて取得します。それが端末の場合は、それを入力と一致させる必要があります。一致しなかった場合は、フレーズ レベルのエラー ハンドラが開始されます。

役割 1: 不足している端末を処理する - レクサーで必要なタイプの偽の端末を生成し、パーサーに再試行させるだけです。他のこともできます（たとえば、入力を事前にチェックし、必要なトークンがある場合は、レクサーから1つのトークンをドロップします）

取得したものがスタックからの非終端 ( T) である場合は、レクサーを調べて、 を取得lookaheadし、テーブルを確認する必要があります。エントリ<T, lookahead>が存在する場合は、問題ありません。アクションに従って、スタックにプッシュ/スタックからポップします。ただし、そのようなエントリが存在しない場合は、再びフレーズ レベルのエラー ハンドラが起動します。

役割 2: 予期しないターミナルを処理する- これを通過するために多くのことができます。あなたが何をするかTはlookahead、あなたの文法の専門知識と何であるかによって異なります。

できることの例は次のとおりです。

  • 失敗！あなたは何もできません
  • この端末は無視してください。これは、lookahead(再度プッシュバックした後に) スタックにプッシュしT、パーサーを続行させることを意味します。パーサーは最初に にマッチlookaheadし、それを破棄して続行します。例: 次のような式がある場合: *1+2/0.5、この方法で予期しないものを削除できます*。
  • lookahead受け入れ可能なものに変更し、押し戻しTて再試行してください。たとえば、次のような式は5id = 10;不正である可能性があります。数字で始まる ID は受け入れられないためです。_5idたとえば、次のように置き換えて続行できます
于 2012-03-18T19:20:01.760 に答える