2

私はレモンパーサーのPHPポーションを読んでいます:

for ($i = 0; $i < $this->nstate; $i++) {   /* Loop over all states */
    $stp = $this->sorted[$i]->data;
    for ($cfp = $stp->cfp; $cfp; $cfp = $cfp->next) {
        /* Loop over all configurations */
        if ($cfp->rp->nrhs == $cfp->dot) {        /* Is dot at extreme right? */
            for ($j = 0; $j < $this->nterminal; $j++) {
                if (isset($cfp->fws[$j])) {
                    /* Add a reduce action to the state "stp" which will reduce by the
                    ** rule "cfp->rp" if the lookahead symbol is "$this->symbols[j]" */
                    PHP_ParserGenerator_Action::Action_add($stp->ap, PHP_ParserGenerator_Action::REDUCE,
                                            $this->symbols[$j], $cfp->rp);
                }
            }
        }
    }
}

アクションテーブルの計算方法によると、パーサーはSLR（1）パーサーのように見えますが、@レモンのホームページでは、LALR（1）パーサーとしての役割を果たしています。

http://www.hwaci.com/sw/lemon/

それは SLR(1) または LALR(1) ですか?

4

1 に答える 1

2

純粋な SLR の場合、リダクションを制御するために使用される先読みシンボル ($this->symbol[$j]) はありません。したがって、LALR(1) であると結論付けます。

編集: yoyo は正しいです SLR( 1 ) は次の入力シンボルを使用してリダクションを制御します (質問を [LALR(1) vs] SLR(0) と読み間違えましたが、これは単に気にしません); 私は訂正します。チェックでは、SLR(1) は (プロダクション ルール コンテキストフリー) FOLLOW セットを使用してリダクションを制御します。LALR(1) は (左コンテキストに依存する) LOOKAHEAD セットを使用します。そのため、どちらも削減ごとに「先読み」が設定されています。つまり、このコード フラグメントからは、それがどの種類のものであるかを判断することはできません。せいぜい、コーダーが実際に「a」先読みセットを計算していることを願っています。それがどのようなものかを知るには、残りのコードを確認する必要があります。

実際問題として、ボトムアップ パーサー ジェネレーターを構築する場合は、SLR(0) [私がかつて行ったことがあり、それが私の脳が質問を読み違えた方法です]、SLR(1)、LALR を構築することを選択できます。 (1)、および LR(1) パーサー ジェネレーターは、ほぼ同じ機構を使用しています。30 年の経験から、LALR(1) がこれらの中で最も実用的であることが示されているため、デフォルトは ... LALR(1); です。SLR(x) は厳密にはサブセットなので、ほんの少し努力すれば LALR(1) が得られるのに、わざわざそんなことをする必要があるでしょうか? Lemon の実装者が伝統に従うなら、LALR(1) パーサー ジェネレーターを期待します。だから今、あなたは彼らの言葉をある程度受け入れています。

もちろん、自分自身を納得させるために簡単な実験を組み立てることもできます。SLR(1) では適切に解析できず、LALR(1) では適切に解析できない文法を構築し、それを試してみてください。または、コードを非常に注意深く読むことができます。

http://en.wikipedia.org/wiki/LALR_parserで LALR 解析を参照してください。

于 2011-02-16T10:29:59.383 に答える