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

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

2 голосов
/ 13 марта 2011

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

1 Ответ

2 голосов
/ 19 марта 2011

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

Теперь вы спрашиваете, как отобразить действительные элементы грамматики 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/ - это место, где вы найдете исходный код бизона, но это генератор парсера LALR, и яне думайте, что он реализует LR (0).

...