Формальные грамматики и языки (1119467), страница 4
Текст из файла (страница 4)
Устранение левой рекурсии2. Левая факторизация3. Подстановка нетерминалов(терминализация)4. Преобразования,учитывающие наличиеε-альтернатив102Устранение левой рекурсии• Если в грамматике для цепочек есть нетерминальныесимволы, правила вывода которых леворекурсивны :A → Aα1 | ... | Aαn | β1 | ... | βm αi∈(T ∪ N)+ i = 1,2,...,nβj∈(T ∪ N)* j = 1,2,...,mприменять метод рекурсивного спуска нельзя• Непосредственную левую рекурсию можно заменитьA → β1A’ | ... | βmA’правой (цепочки βj {αi}):A’ → α1A’ | ... | αnA’ | ε• Если для символа есть одни лишь леворекурсивныеправила (альтернативы βj отсутствуют), то символ A' невводится, а правила для символа A становятся такими:A → α1A | ...
| αnA | ε103Устранение левой рекурсии• Левая рекурсия может не быть непосредственной:S → Aa | bA → Ac | Sd | εиз S имеется вывод S → Aa → Sda, но эта рекурсия неявляется непосредственной, поэтому удаление левойрекурсии необходимо повторить• Сначала выполняется подстановка правила для S:A → Ac | Aad | bd | ε• Далее:S → Aa | bA → bdA’ | A’A’ → cA’ | adA’ | εα1 = cβ1 = bdα2 = adβ2 = εЛевая факторизация• В грамматике есть правила, начинающиесяодинаковыми символами:A → aα1 | aα2 | ...
| aαn | β1 | ... |βmгде a ∈ (T ∪ N)+; αi, βj ∈ (T ∪ N)*, βj не начинается с ‘a’• Можно объединить правила с общими началами водно правило, введя новый символ A’:A → aA’ | β1 | ... | βmA’ → α1 | α2 | ... | αn• ГрамматикаS → if E then S | if E then S else S | aE→bпреобразуется в S → if E then S S’ | aS’ → else S | ε105E→bПодстановка нетерминалов• В грамматике есть нетерминальный символ, укоторого несколько правил вывода, и среди них естьправила, начинающиеся нетерминальнымисимволами:A → B1α1 | ...
| Bnαn | a1β1 | ... | amβmB1 → γ11 | ... | γ1k...Bn → γn1 | ... | γnpгдеBi ∈ Naj ∈ Tαi, βj ∈ (T ∪ N)*γij ∈ (T ∪ N)+• Можно заменить символы Bi их правилами:A → γ11α1 |…| γ1kα1 |…| γn1αn |…| γnpαn | a1β1 |…| amβm106ε-правила• Наличие ε-альтернатив (A → a1α1 | ... | anαn | ε) невсегда препятствует применению рекурсивного спуска• Анализатор для грамматики G1 = ({a, b, ⊥}, {S, A}, P, S)A → aA | εP1: S → bAa⊥void S () { if (c != ‘b’)ERROR ();GetL ();A ();if (c != ‘a’)ERROR ();GetL ();if (c != ‘⊥’)ERROR ();}void A () { if (c == ‘a’) { GetL (); A (); } // нет ‘else’} // здесь есть проблема с анализом цепочки ‘baaa⊥’ε-правила• Проблемы возникают, если подцепочка, следующая зацепочкой, выводимой из A, начинается таким жесимволом, как и цепочка, выводимая из А• В противном случае проблем нет:для грамматики G2 = ({a, b, с, ⊥}, {S, A}, P, S), гдеP2:S → bAс⊥A → aA | εудаётся построить анализатор, работающий методомрекурсивного спуска108ε-правила• Проблемы возникают, если подцепочка, следующая зацепочкой, выводимой из A, начинается таким жесимволом, как и цепочка, выводимая из А• В противном случае проблем нет:void S () { if (c != ‘b’)ERROR ();GetL ();A ();if (c != ‘c’)ERROR ();GetL ();if (c != ‘⊥’)ERROR ();}void A () { if (c == ‘a’) { GetL (); A (); } // нет ‘else’}109Достаточные условия применимостирекурсивного спуска для грамматик с ε-правилами• first (A) – множество терминальных символов,которыми начинаются цепочки, выводимые из А вграмматике G = (T, N, P, S):first (A) = {a ∈ T | A ⇒ aα, A ∈ (T ∪ N)+, α ∈ (T ∪ N)*}• follow (A) – множество терминальных символов,которые следуют за цепочками, выводимыми из А:follow (A) = {a ∈ T | S ⇒ αAβ, β ⇒ aγ, A ∈ Nβ ∈ (T ∪ N)+}α, γ ∈ (T ∪ N)*• Если first (A) ∩ follow (A) = ∅, метод рекурсивногоспуска применим к данной грамматике• Если first (A) ∩ follow (A) ≠ ∅, метод рекурсивногоспуска неприменим к данной грамматике110Канонический вид грамматики идостаточные условия для методарекурсивного спуска1.
либо X → α и это единственное правиловывода для X2. либо X → a1α1 | a2α2 | ... | anαn3. либо X → a1α1 | a2α2 | ... | anαn | εи first (X) ∩ follow (X) = ∅ai ∈ T для всех i = 1, 2,..., nα, αi ∈ (T ∪ N)*ai ≠ aj для i ≠ j111ε-правила• Метод неприменим для грамматикиG1 = ({a, b, ⊥}, {S, A}, P, S), гдеP1: S → bAa⊥A → aA | εfirst (A) = {a}, follow (A) = {a}first (A) ∩ follow (A)≠∅• Метод применим для грамматикиG2 = ({a, b, с, ⊥}, {S, A}, P, S), гдеP2: S → bAс⊥A → aA | εfirst (A) = {a}, follow (A) = {c}first (A) ∩ follow (A)=∅112ε-правила• Грамматику с правилом, в котором для некоторогосимвола A имеется ε-альтернатива, можнопреобразовать, введя символ A’ (A’ ≡ Aβ):A → α1A | ...
| αnA | β1 | ... | βm| εA, B ∈ Nα, β, αi, βj ∈ (T ∪ N)*B → αAβfirst (A) ∩ follow (A) ≠ ∅A → α1A | ... | αnA | β1 | ... | βm | εB → αA’A’ → α1A’ | ... | αnA’ | β1β | ... | βmβ | β• Из B выводятся цепочки вида α {αi} βj β, либо α {αi} β113ε-правила• Преобразовать грамматику G1 = ({a, b, ⊥}, {S, A}, P, S)для применения метода рекурсивного спуска:P1: S → bAa⊥A → aA | ε• Для удаления ε-правила вводится правило A’ → Aa⊥:A’ → aA’ | a⊥A → aA | εS → bA’• Правило для A удаляется (символ A бесполезен):A’ → aA’ | a⊥S → bA’• Объединяются общие начала альтернатив:A’ → aA”A” → A’ | ⊥S → bA’• Проводится терминализация правила для символа A”:A’ → aA”A” → aA” | ⊥S → bA’114ε-правила• Грамматика содержит пустые правые части вдвух правилах: S → aAA → BC | BC→b|εB→ε• Для нетерминала A из обеих альтернативвыводится пустая цепочка:BC ⇒ ε и B → ε• Для цепочки “a” строятся два различных деревавывода:S → aA → aB → aε ≡ aS → aA → aBC → aεC → aεε ≡ a115ε-правила• Грамматика содержит пустую правую часть водном правиле: S → BdB → a | cAaA → aA | εfirst (a) = {a}first (cAa) = {c}first (a) ∩ first (cAa) = ∅• Любой вывод, содержащий A, имеет вид:S → Bd → cAad → … → ca…aAad116Критерий применимости методарекурсивного спуска• Метод рекурсивного спуска применим кконтекстно-свободной грамматике G, если итолько если для любых двух её правилX → α | β выполняются условия:1.
first(α) ∩ first(β) = ∅2. Справедливо не более, чем одно из двухсоотношений: α ⇒ ε, β ⇒ ε3. Если β ⇒ ε, то first(α) ∩ follow(X) = ∅117Преобразование списков• Грамматика со списком элементов, ограниченныхсимволом, совпадающим с внутренним разделителемэлементов списка:S → LBL → a {, a}B→,bS → LBL→a|a,LB→,b• Вводится дополнительный нетерминальный символ L’:S → LBL’ → , L | εL → aL’B→,bfirst (L’) = {,}follow (L’) = follow (L) = first (B) = {,}first (L’) ∩ follow (L’) ≠ ∅118Преобразование списков• Подправляется правило для L’ (L’ → ,aL’ | ε):S → LBL” → ,aL” | εL → aL”B→,bL’ → ,aL’ | εиз исходных правил:L (B): α = a β = εL’ (A): α1 = ,a βi = εнедостижимое правило• Очередное поколение правил в точности повторяетпредыдущее, поэтому преобразования по показаннымметодикам не могут привести к получениюграмматики, которые методом рекурсивного спускасмогут обрабатывать подобные списки119Грамматики с действиями• В тела процедур вставляются вызовы дополнительных“семантических” процедур:A → a<D1>B<D1;D2> | bC<D3>A → aB | bCA, B, C ∈ N; a, b ∈ T<Di> – вызов семантической процедуры Di(), i=1,2,3• Процедура рекурсивного спуска, выполняющаясинтаксический анализ и дополнительные действия:void A () { if (c == ‘a’) { GetS (); D1 (); B (); D1 (); D2 (); }else if (c == ‘b’) { GetS ();C ();D3 (); }else ERROR ();}120Примеры грамматик• Грамматики, которые позволяют распознавать цепочки языкаL = {α ∈ (0,1)+⊥ | α содержит равное количество 0 и 1}:G1 = ({0, 1}, {A, S}, P1, S)G2 = ({0, 1}, {S}, P2, S)P2: S → 0S1 | 1S0 | 01 | 10P1: S → 0A1 | 1A00A → 00A11A → 11A0A→ε• Грамматика с действиями, дающая тот же результат:S → <k0 = 0; k1 = 0> A⊥A → 0 <k0 ++> A | 1 <k1 ++> A |0 <k0 ++; check ()> | 1 <k1 ++; check ()>void check (){ if (k0 == k1) { cout << “ХОРОШО!!!” << endl; return 0; }else{ cout << “ПЛОХО!!!” << endl; return 1; }121}Контекстные условия ввыражениях• Разбор выражения:x * y + 5 > xint * intint+ intint> intbool• Изменённая цепочка:x > 5 * yint > intbool * intошибка122Контекстные условия ввыражениях• Разбор выражения:x * y + 5 > xint * intint+ intint> intbool• Изменённая цепочка:x > 5 * yint * intint > intbool123Контекстные условия ввыражениях• Простейшая грамматика для выражений:G1: E → E + E | E * E | (E) | I• Разные деревья вывода для выражения I + I * I:+**II+IIII124Контекстные условия ввыражениях• Однозначная правоассоциативная грамматикаG2, не отражающая старшинство операций:G2: E → T + E | T * E | TT → I | (E)I+I*I• Симметричная грамматике G2 однозначнаялевоассоциативная грамматика G3:G3: E → E + T | E * T | TT → I | (E)I+I*I125Контекстные условия ввыражениях• Правоассоциативная, учитывающаястаршинство операций, грамматика G4:G4: E → T | T + ET→F|F*TF → I | (E)10 * 3 / 5 = 0• Левоассоциативная грамматика G5:G5: E → T | E + TT→F|T*FF → I | (E)рекурсивный спускнеприменим126Контекстные условия ввыражениях• Грамматика G6 (рекурсия заменена итерацией):G6: E → T { + T }T→F{*F}F → I | (E)• Семантические проверки: E → T { + T <DT>}T → F { * F <DF>}F → I <DI> | (E)• DI – проверка одиночного операнда• DT – проверка совместимости слагаемых• DF – проверка совместимости множителей127Синтаксически управляемыйперевод• Синтаксис и семантика языков взаимосвязаны• При синтаксически управляемом переводе в соответствии ссемантикой входных и выходных правил каждому правилувходного языка сопоставляются правила выходного языка• С каждой вершиной дерева синтаксического разбора Nсвязывается цепочка C (N)• Образ вершины N строится путём сцепления в определённомпорядке последовательности C (N) и последовательностейцепочек, связанных со всеми вершинами, являющимисяпрямыми потомками вершины N• Процесс перевода продолжается снизу вверх в порядке,управляемом структурой дерева• Перевод программы состоит в поиске образа корня дерева 128Формальный перевод• Формальный перевод τ – это подмножествомножества всевозможных пар цепочек (α, β) валфавитах T1 и T2: τ ⊆ (T1* × T2*)гдеα ∈ T1*, β ∈ T2*• Входной язык перевода τ:Lвх = {α | ∃ β : (α, β) ∈ τ}• Целевой (выходной) язык перевода τ:Lц = {β | ∃ α: (α, β) ∈ τ}• Перевод τ неоднозначен, если для некоторыхα ∈ T1*, β, γ ∈ T2*, β ≠ γ(α, β) ∈ τ и (α, γ ) ∈ τ129Синтаксически управляемыйперевод• С помощью грамматики с действиями выполнитьперевод цепочек языка L1 = {0n1m | n ≥ 0, m > 0} вцепочки языка L2 = {ambn | n ≥ 0, m > 0}• Определение перевода τ: для любых n ≥ 0, m > 0цепочке 0n1m ∈ L1 соответствует цепочка ambn ∈ L2,τ = { (0n1m, ambn) | n ≥ 0, m > 0 }, Lвх (τ) = L1, Lц (τ)= L2• Грамматика языка L1: S → 0S | 1AA → 1A | ε• Действия по переводу цепочек “0n1m” в цепочкиS → 0S <Put (‘b’)> | 1 <Put (‘a’)> A“ambn”:130A → 1 <Put (‘a’)> A | εСинтаксически управляемыйперевод• Перевести цепочки языка L1 = {ancmbn | n, m ≥ 0} вцепочки языка L2 = {0m1n+m | n, m ≥ 0}• Цепочку “aacccbb” (n = 2, m = 3) перевести в цепочку“00011111” (m = 3, n + m = 5)• Грамматика языка L1: S → aSb | AA → cA | ε• Вычисление множеств first(A) и follow(A):first(A) = {c}follow(A) = {b}• Действия по переводу цепочек “ancmbn” в цепочки“0m1n+m”: S → aSb <cout << ‘1’> | AA → c <cout << ‘0’> A <cout << ‘1’> | ε 131Преобразование в ПОЛИЗ• Простые выражения:E → T {+ T}T → F {* F}F → a | b | (E)• Грамматика с действиями: E → T {+ T <Put (‘+’)>}T → F {* F <Put (‘*’)>}F → a <Put (‘a’)> | b <Put (‘b’)> | (E)• Генератор, совмещённый с синтаксическим анализатором:void E () { T (); while (c == ‘+’) {void T () { F (); while (c == ‘*’) {void F () {if (c == ‘a’){else if (c == ‘b’){else if (c == ‘(’){}else Error ();GetS (); T (); Put (‘+’); } }GetS (); F (); Put (‘*’); } }GetS ();Put (‘a’); }GetS ();Put (‘b’); }GetS (); E ();if (c == ‘)’) GetS (); else Error (); }132.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
