Показать действительные LR(0) позиции

Question

Мне нужно создать программу на C++, чтобы отображать действительные элементы LR(0) при разборе SLR в дизайне компилятора. До сих пор я могу принять грамматику как ввод от пользователя и найти ее закрытие. Но я не могу продолжить работу по внедрению goto в SLR. Может ли кто-нибудь предоставить мне ссылки или код относительно того, как отображать действительные элементы грамматики LR(0).
-Заранее спасибо

Answer 1

Вы в состоянии принять закрытие грамматики? Технически, функция закрытия определяется для наборов элементов (которые представляют собой наборы производств, позиция которых связана с каждым производством).

Теперь вы спрашиваете, как отобразить действительные элементы грамматики LR(0). Вы имеете в виду либо отображение всех элементов, как определено в параграфе выше, либо отображение всех состояний автомата LR(0). Первый тривиален, потому что все возможные элементы действительны, поэтому я предполагаю, что вы хотите все состояния. Это то, что вы делаете (прямо из книги дракона).

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),