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

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья не цитировать любой источники. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. Найдите источники: «Отношение приоритета Вирта – Вебера» – Новости · газеты · книги · ученый · JSTOR (Декабрь 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом. Пожалуйста помоги улучшить статью к обеспечение большего контекста для читателя. (Октябрь 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к сделать понятным для неспециалистов, не снимая технических деталей. (Июль 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

${ Displaystyle { begin {выровнен} X doteq Y & iff { begin {case} 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 {case}} X lessdot Y & iff { begin {case} A to alpha XB beta in P B Rightarrow ^ {+} Y gamma A, B in V_ {n} alpha, beta, gamma в (V_ {n} cup V_ {t}) ^ {*} X, Y in (V_ {n} cup V_ {t}) end {ases}} 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 {case}} end {align}}}$

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

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

${ displaystyle { begin {align} mathrm {Head} ^ {+} (X) & = {Y mid X Rightarrow ^ {+} Y alpha } mathrm {Tail} ^ {+ } (X) & = {Y mid X Rightarrow ^ {+} alpha Y } mathrm {Head} ^ {*} (X) & = ( mathrm {Head} ^ {+} ( X) чашка {X }) cap V_ {t} end {align}}}$

Голова^*(Икс) является Икс если Икс является терминалом, а если Икс нетерминальный, 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 {Хвост} ^ {+} (X) gtrdot mathrm {Head} ^ {*} (Y)}$)
• добавить (RelationTable, ${ displaystyle $ lessdot mathrm {Head} ^ {+} (S)}$) куда S - начальный нетерминал грамматики, а $ - маркер предела
• добавить (RelationTable, ${ Displaystyle mathrm {Хвост} ^ {+} (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 а 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 {Голова} ^ {+} (S)}$
      • ${ displaystyle S lessdot a}$
      • ${ Displaystyle S lessdot c}$
    • ${ Displaystyle mathrm {Хвост} ^ {+} (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 {Хвост} ^ {+} (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 .; Ульман, Джеффри Д., Теория синтаксического анализа, перевода и компиляции