ub> (U):
В· L t (U) = {t | $ UГћ * tz або $ UГћ * Ctz}, де tГЋ VT , U, CГЋ VN , zГЋ V * ;
В· R t (U) = {t | $ UГћ * zt або $ UГћ * ztC}, де tГЋ VT , U, CГЋ VN , zГЋ V * . p> Тоді визначення відносин операторного передування будуть виглядати так:
В· a = b, якщо $ правило U В® xaby ГЋ P або правило U В® xaCby, де a, bГЋ VT , U, CГЋ VN , x, yГЋ V * ;
В· a P і bГЋ L t (C), де a, bГЋ < b> VT , U, CГЋ VN , x, yГЋ V * ;
В· a> b, якщо $ правило U В® xCby ГЋ P і aГЋ R t (C), де a, bГЋ < b> VT , U, CГЋ VN , x, yГЋ V * . p> У даних визначеннях ланцюжка символів x, y, z можуть бути і порожніми ланцюжками.
Для знаходження множин L t (U) і R t (U) використовується наступний алгоритм:
Крок 1. Для кожного нетермінального символу граматики U будуються безлічі L (U) і R (U).
Крок 2. Для кожного нетермінального символу граматики U шукаються правила виду U В® tz і U В® Ctz, де tГЋ VT , CГЋ VN , zГЋ V * ; термінальні символи t включаються в безліч L t (U). Аналогічно для безлічі R t (U) шукаються правила виду U В® zt і U В® ztC. p> Крок 3. Проглядається безліч L (U), в яке входять символи U ', U ", ... Безліч L t (U) доповнюється символами, що входять до L t (U '), L t (U "), ... і не входять до L t (U). Аналогічна операція виконується і для безлічі R t (U) на основі безлічі R (U).
Для практичного використання матрицю передування доповнюють символами ^ н і ^ до (початок і кінець ланцюжка). Для них визначено наступні відносини передування:
^ н VT , якщо $ SГћ * xa або $ SГћ * xaC, де S, CГЋ VN , xГЋ V * або якщо aГЋ R t (S).
3.3 Приклад побудови матриці передування
Побудуємо матрицю передування для граматики операторного передування.
Розглянемо як приклад граматику G ({S, B, T, J}, { - , & , ^ , (, ) , p }, P , S): (Термінали виділені жирним шрифтом)
P : S В® - B (Правило 1)
B В® T | B & T (правила 2 і 3)
T В® J | T ^ J (правила...
