Отношения предшествования Вирта – Вебера

В информатике соотношение Вирта-Вебера между парой символов. $(V_{t}\cup V_{n})$ необходимо, чтобы определить, ли формальная грамматика является простой грамматикой приоритета . В таком случае простой анализатор приоритета можно использовать . Отношения названы в честь ученых-компьютерщиков Никлауса Вирта и Гельмута Вебера.

Цель состоит в том, чтобы определить, когда жизнеспособные префиксы имеют центральную точку и их необходимо сократить. А $\gtrdot$ означает, что стержень найден, $\lessdot$ означает, что потенциальный разворот начинается, и $\doteq$ означает, что отношения остаются в той же точке поворота .

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

$G=\langle V_{n},V_{t},S,P\rangle$

${\begin{aligned}X\doteq Y&\iff {\begin{cases}A\to \alpha XY\beta \in P\\A\in V_{n}\\\alpha ,\beta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\lessdot Y&\iff {\begin{cases}A\to \alpha XB\beta \in P\\B\Rightarrow ^{+}Y\gamma \\A,B\in V_{n}\\\alpha ,\beta ,\gamma \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\gtrdot Y&\iff {\begin{cases}A\to \alpha BY\beta \in P\\B\Rightarrow ^{+}\gamma X\\Y\Rightarrow ^{*}a\delta \\A,B\in V_{n}\\\alpha ,\beta ,\gamma ,\delta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\\a\in V_{t}\end{cases}}\end{aligned}}$

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

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

${\begin{aligned}\mathrm {Head} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}Y\alpha \}\\\mathrm {Tail} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}\alpha Y\}\\\mathrm {Head} ^{*}(X)&=(\mathrm {Head} ^{+}(X)\cup \{X\})\cap V_{t}\end{aligned}}$

 Голова ^* ( X ) является X , если X является терминалом, и если X является нетерминалом, Head ^* ( X ) — это множество, в котором только терминалы принадлежат Head ⁺ ( Х ). Этот набор эквивалентен первому набору или Fi( X ) описано в парсере LL .

 Голова ⁺ ( X ) и хвост ⁺ ( X ) равны ∅, если X является терминалом.

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

• Таблица отношений := ∅
• Для каждого производства $A\to \alpha \in P$
  • Для каждых двух соседних символов XY в α
    • добавить (Таблица отношений, $X\doteq Y$)
    • добавить (Таблица отношений, $X\lessdot \mathrm {Head} ^{+}(Y)$)
    • добавить (Таблица отношений, $\mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)$)
• добавить (Таблица отношений, $\$\lessdot \mathrm {Head} ^{+}(S)$), где S — начальный нетерминал грамматики, а $ — маркер предела
• добавить (Таблица отношений, $\mathrm {Tail} ^{+}(S)\gtrdot \$$), где S — начальный нетерминал грамматики, а $ — маркер предела

 $\lessdot$ и $\gtrdot$ используются с наборами вместо элементов, как они были определены, в этом случае вы должны добавить все декартово произведение между наборами/элементами.

Примеры

Пример 1

$S\to aSSb|c$

• Голова ⁺ ( а ) знак равно ∅
• Голова ⁺ ( S ) знак равно { а, с }
• Голова ⁺ ( б ) знак равно ∅
• Голова ⁺ ( с ) знак равно ∅
• Хвост ⁺ ( а ) знак равно ∅
• Хвост ⁺ ( S ) знак равно { б, с }
• Хвост ⁺ ( б ) знак равно ∅
• Хвост ⁺ ( с ) знак равно ∅
• Голова ^* ( а ) = а
• Голова ^* ( S ) знак равно { а, с }
• Голова ^* ( б ) знак равно б
• Голова ^* ( с ) знак равно с
• $S\to aSSb$
  • а рядом с S
    • $a\doteq S$
    • $a\lessdot \mathrm {Head} ^{+}(S)$
      • $a\lessdot a$
      • $a\lessdot c$
  • S Рядом с S
    • $S\doteq S$
    • $S\lessdot \mathrm {Head} ^{+}(S)$
      • $S\lessdot a$
      • $S\lessdot c$
    • $\mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(S)$
      • $b\gtrdot a$
      • $b\gtrdot c$
      • $c\gtrdot a$
      • $c\gtrdot c$
  • S Рядом с b
    • $S\doteq b$
    • $\mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(b)$
      • $b\gtrdot b$
      • $c\gtrdot b$
• $S\to c$
  • существует только один символ, поэтому никакое отношение не добавляется.

таблица приоритетов

${\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&\doteq &\lessdot &\doteq &\lessdot &\\a&\doteq &\lessdot &&\lessdot &\\b&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}$

Пример 2

$S\to a|aT|[S]$

$T\to b|bT$

• Голова ⁺ ( S ) знак равно { а, [ }
• Голова ⁺ ( а ) знак равно ∅
• Голова ⁺ ( Т ) знак равно { б }
• Голова ⁺ ( [ ) = ∅
• Голова ⁺ ( ] ) = ∅
• Голова ⁺ ( б ) знак равно ∅

• Хвост ⁺ ( S ) знак равно { а, Т, ], б }
• Хвост ⁺ ( а ) знак равно ∅
• Хвост ⁺ ( Т ) знак равно { б, Т }
• Хвост ⁺ ( [ ) = ∅
• Хвост ⁺ ( ] ) = ∅
• Хвост ⁺ ( б ) знак равно ∅

• Голова ^* ( S ) знак равно { а, [ }
• Голова ^* ( а ) = а
• Голова ^* ( Т ) знак равно { б }
• Голова ^* ( [ ) = [
• Голова ^* ( ] ) = ]
• Голова ^* ( б ) знак равно б

• $S\to aT$

• • рядом с Т
    • $a\doteq T$
    • $a\lessdot \mathrm {Head} ^{+}(T)$
      • $a\lessdot b$

• $S\to [S]$

• • [ Рядом с С
    • $[\doteq S$
    • $[\lessdot \mathrm {Head} ^{+}(S)$
      • $[\lessdot a$
      • $[\lessdot [$

• • S Рядом с ]
    • $S\doteq ]$
    • $\mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(])$
      • $a\gtrdot ]$
      • $T\gtrdot ]$
      • $]\gtrdot ]$
      • $b\gtrdot ]$

• $T\to bT$

• • б Рядом с Т
    • $b\doteq T$
    • $b\lessdot \mathrm {Head} ^{+}(T)$
      • $b\lessdot b$

таблица приоритетов

${\begin{array}{c|ccccccc}&S&T&a&b&[&]&\$\\\hline S&&&&&&\doteq &\doteq \\T&&&&&&\gtrdot &\gtrdot \\a&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\b&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\{\text{[}}&\doteq &&\lessdot &&\lessdot &&\\]&&&&&&\gtrdot &\gtrdot \\\$&\doteq &&\lessdot &&\lessdot &&\end{array}}$

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

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