Отношение приоритета Вирта – Вебера - Wirth–Weber precedence relationship

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

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

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

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

${\displaystyle {\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 a&\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}}}$

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

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

${\displaystyle {\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}}}$

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

Голова⁺(Икс) и хвост⁺(Икс) равны, если Икс это терминал.

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

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

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

Примеры

${\displaystyle S\to aSSb|c}$

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

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

${\displaystyle {\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}}}$

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

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