WikiDer > Отношение приоритета Вирта – Вебера

Wirth–Weber precedence relationship

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

Цель состоит в том, чтобы определить, когда жизнеспособные префиксы иметь вращаться и должен быть сокращен. А означает, что вращаться найден, означает, что потенциал вращаться начинается, и означает, что мы все еще в том же вращаться.

Формальное определение

Алгоритм вычисления отношений предшествования

Мы определим три набора для символа:

Голова*(Икс) является Икс если Икс является терминалом, а если Икс нетерминальный, Head*(Икс) - это набор, в котором только клеммы принадлежат Head+(Икс). Этот набор эквивалентен Первый сет или же Fi (Икс) описано в LL парсер.
Голова+(Икс) и хвост+(Икс) равны, если Икс это терминал.

Псевдокод для вычисления отношений:

  • RelationTable: = ∅
  • Для каждого производства
    • Для каждых двух соседних символов X Y в α
      • добавить (RelationTable, )
      • добавить (RelationTable, )
      • добавить (RelationTable, )
  • добавить (RelationTable, ) куда S - начальный нетерминал грамматики, а $ - маркер предела
  • добавить (RelationTable, ) куда S - начальный нетерминал грамматики, а $ - маркер предела
и используются с наборами вместо элементов, как они были определены, в этом случае вы должны добавить все декартово произведение между наборами / элементами.

Примеры

  • Голова+(а) = ∅
  • Голова+(S) = {а, в}
  • Голова+(б) = ∅
  • Голова+(c) = ∅
  • Хвост+(а) = ∅
  • Хвост+(S) = {до н.э}
  • Хвост+(б) = ∅
  • Хвост+(c) = ∅
  • Голова*(а) = а
  • Голова*(S) = {а, в}
  • Голова*(б) = б
  • Голова*(c) = c
    • а Следующий на S
    • S Следующий на S
    • S Следующий на б
    • есть только один символ, поэтому отношение не добавляется.
таблица приоритетов

дальнейшее чтение

  • Ахо, Альфред V .; Ульман, Джеффри Д., Теория синтаксического анализа, перевода и компиляции