21

LR（1）アイテムの先読みを計算する方法を理解するのに問題があります。

私がこの文法を持っているとしましょう：

S -> AB
A -> aAb | a
B -> d

LR（1）アイテムは、先読みのあるLR（0）アイテムです。したがって、状態0の次のLR（0）アイテムを取得します。

S -> .AB , {lookahead} 
A -> .aAb,  {lookahead} 
A -> .a,  {lookahead}

状態：1

A ->  a.Ab, {lookahead} 
A ->  a. ,{lookahead} 
A -> .aAb ,{lookahead} 
A ->.a ,{lookahead}

誰かが先読みを計算する方法を説明できますか？一般的なアプローチは何ですか？

前もって感謝します

4

4 に答える 4

35

LR（1）パーサーで使用される先読みは、次のように計算されます。まず、開始状態には次の形式のアイテムがあります

S -> .w  ($)

すべてのプロダクションS->wに対して、ここでSは開始記号です。ここで、$マーカーは入力の終わりを示します。

次に、A-> x.By（t）の形式のアイテムを含む状態の場合、xは終端記号と非終端記号の任意の文字列であり、Bは非終端記号であり、B->.wの形式のアイテムを追加します。 （s）すべてのプロダクションB-> wおよびセットFIRST（yt）内のすべての端末。（ここで、FIRSTとは、LLパーサーについて話すときに通常紹介されるFIRSTセットを指します。これまでに見たことがない場合は、これらの講義ノートを確認するのに数分かかります）。

これを文法で試してみましょう。まず、以下を含むアイテムセットを作成します。

S -> .AB ($)

次に、2番目のルールを使用して、Aのすべてのプロダクションに対して、そのプロダクションに対応し、FIRST（B $）のすべての端末の先読みを使用して新しいアイテムを追加します。Bは常に文字列dを生成するため、FIRST（B $）= dであるため、ここで紹介するすべての生成には先読みdがあります。これは与える

S -> .AB ($)
A -> .aAb (d)
A -> .a (d)

それでは、この初期状態での「a」の表示に対応する状態を構築しましょう。まず、以下で始まるプロダクションごとに1つのステップにドットを移動します。

A -> a.Ab (d)
A -> a. (d)

ここで、最初のアイテムには非終端記号の前にドットがあるため、ルールを使用して、Aの生成ごとに1つのアイテムを追加し、それらのアイテムに先読みFIRST（bd）=bを与えます。これは与える

A -> a.Ab (d)
A -> a. (d)
A -> .aAb (b)
A -> .a (b)

このプロセスを続行すると、最終的に、このLR（1）パーサーのすべてのLR（1）状態が構築されます。これはここに示されています：

[0]
S -> .AB  ($)
A -> .aAb (d)
A -> .a   (d)

[1]
A -> a.Ab (d)
A -> a.   (d)
A -> .aAb (b)
A -> .a   (b)

[2]
A -> a.Ab (b)
A -> a.   (b)
A -> .aAb (b)
A -> .a   (b)

[3]
A -> aA.b (d)

[4]
A -> aAb. (d)

[5]
S -> A.B  ($)
B -> .d   ($)

[6]
B -> d.   ($)

[7]
S -> AB.  ($)

[8]
A -> aA.b (b)

[9]
A -> aAb. (b)

それが役立つ場合に備えて、私は昨年の夏にコンパイラコースを教え、すべての講義スライドをオンラインで利用できるようにしました。ボトムアップ解析のスライドは、LR解析と解析テーブルの構築の詳細をすべて網羅しているはずです。これらがお役に立てば幸いです。

お役に立てれば！

于 2013-01-02T18:35:35.163 に答える
4

これが文法のLR（1）オートマトンです。以下は上記で行われたためです。オートマトンを描画しようとすることを理解する方が良いと思います。フローにより、先読みの概念がより明確になります。

これが文法のオートマトンです

于 2015-03-14T06:55:52.080 に答える
0

作成したLR（1）アイテムセットには、さらに2つのアイテムが必要です。

I8 A-> aA.b、b from I2

I9A->aAb。、BからI8

于 2013-04-03T06:39:30.287 に答える
0

また、8つではなく11の状態を取得します。

State 0
        S: .A B ["$"]
        A: .a A b ["d"]
        A: .a ["d"]
    Transitions
        S -> 1
        A -> 2
        a -> 5
    Reductions
        none
State 1
        S_Prime: S .$ ["$"]
    Transitions
        none
    Reductions
        none
State 2
        S: A .B ["$"]
        B: .d ["$"]
    Transitions
        B -> 3
        d -> 4
    Reductions
        none
State 3
        S: A B .["$"]
    Transitions
        none
    Reductions
        $ => S: A B .
State 4
        B: d .["$"]
    Transitions
        none
    Reductions
        $ => B: d .
State 5
        A: a .A b ["d"]
        A: .a A b ["b"]
        A: .a ["b"]
        A: a .["d"]
    Transitions
        A -> 6
        a -> 8
    Reductions
        d => A: a .
State 6
        A: a A .b ["d"]
    Transitions
        b -> 7
    Reductions
        none
State 7
        A: a A b .["d"]
    Transitions
        none
    Reductions
        d => A: a A b .
State 8
        A: a .A b ["b"]
        A: .a A b ["b"]
        A: .a ["b"]
        A: a .["b"]
    Transitions
        A -> 9
        a -> 8
    Reductions
        b => A: a .
State 9
        A: a A .b ["b"]
    Transitions
        b -> 10
    Reductions
        none
State 10
        A: a A b .["b"]
    Transitions
        none
    Reductions
        b => A: a A b .
于 2015-10-29T07:33:02.817 に答える