2

コンパイラ設計で SLR 解析で有効な LR(0) 項目を表示する C++ プログラムを作成する必要があります。これまで、文法をユーザーからの入力として受け取り、そのクロージャーを見つけることができました。しかし、SLR での goto 実装をさらに進めることができません。文法の有効な LR(0) 項目を表示する方法について、リンクまたはコードを教えてください。
-前もって感謝します

4

1 に答える 1

2

あなたは文法の閉鎖をとることができますか？技術的には、クロージャ機能はアイテムのセット（各プロダクションに関連付けられた位置を持つプロダクションのセット）で定義されます。

ここで、文法の有効なLR（0）項目を表示する方法を尋ねます。上記の段落で定義されているように、すべてのアイテムを表示するか、LR（0）オートマトンのすべての状態を表示することを意味します。1つ目は、考えられるすべての項目が有効であるため、些細なことです。したがって、すべての状態が必要だと思います。これはあなたがすることです（ドラゴンブックからまっすぐに）。

SetOfItems getValidStates(Grammar G) {
    // S' -> S is the "first" production of G (which must be augmented)
    SetOfItems C = {[S' -> *S]};
    do {
      bool added = false;
      for (Item I : C) {
        for (Symbol X : G) {
          L = GOTO(I, X);
          if (L.size() > 0 && !C.contains(L)) {
            added = true;
            C.add(L);
          }
        }
      }
    } while (added);
    return C;
}

唯一の問題は、GOTO（SetOfItems、Symbol）を実装する方法です。

それで、 

SetOfItems GOTO(SetOfItems S, Symbol X) {
  SetOfItems ret = {}
  for (Item I : S)
    if (I.nextSymbol().equals(X))
      ret.add(I.moveDotByOne())
  return closure(ret);
}

セット内の各アイテムの形式は[A->a* Yb]です。ここで、Aはプロダクションのヘッド、aXbはプロダクションの本体です（aとbは単なる文法記号の文字列、Yは単一の記号です）。 ）。'*'は、私が言及した位置です。文法には含まれていません。[A-> a * Yb] .nextSymbol（）はYです。基本的に、Item.nextSymbol（）は、ドット。[A-> a * Yb] .moveDotByOne（）は[A-> aY*b]を返します。

さて、コンパイラブックの構文解析の章を終えたところですが、理解に完全に満足しているわけではないので、書いた内容に注意してください。

実際のコードへのリンクについては、http：//ftp.gnu.org/gnu/bison/にbisonのソースがありますが、これはLALRパーサージェネレーターであり、LR（0）を実装しているとは思いません。 。

于 2011-03-19T15:13:47.400 に答える