VN за дуже простим алгоритмом:
Крок 1. Для кожного нетермінального символу U шукаємо всі правила, що містять U в лівій частини. В безліч L (U) включаємо самий лівий символ з правої частини правил, а в безліч R (U) - самий крайній символ правої частини. Переходь до кроку 2. p> Крок 2. Для кожного нетермінального символу U: якщо безліч L (U) містить нетермінальні символи граматики U ', U ", ..., то його треба доповнити символами, входять у відповідні безлічі L (U '), L (U "), ... і не входять до L (U). Ту ж операцію треба виконати для R (U). p> Крок 3. Якщо на попередньому кроці хоча б одне безліч L (U) або R (U) для деякого символу граматики змінилося, то треба повернутися до кроку 2, інакше побудова закінчено.
Після побудови множин L (U) і R (U) за правилам граматики створюється матриця передування. Матрицю передування доповнюють символами ^ н і ^ до (початок і кінець ланцюжка). Для них визначено такі відносини передування:
^ н V , якщо $ SГћ * xa, де SГЋ VN , xГЋ V * або (з іншого боку) якщо aГЋ R (S) .
3.2 Граматики операторного передування
Граматикою операторного передування називається наведена КС-граматика без l-правил (E-правил), в якій праві частини продукцій не містять суміжних нетермінальних символів. Для граматики операторного передування відносини передування можна задати на безлічі термінальних символів (включаючи символи ^ н і ^ до ).
Відносини передування для граматики операторного передування G ( VN , VT , P , S) задаються наступним чином:
В· a = b, якщо і тільки якщо існує правило U В® xaby ГЋ P або правило U В® xaCby, де a, bГЋ VT , U, CГЋ VN , x, yГЋ V * ;
В· a P і висновок CГћ * bz або висновок CГћ * Dbz, де a, bГЋ VT , U, C, DГЋ VN , x, y, zГЋ V * ;
В· a> b, якщо і тільки якщо існує правило U В® xCby ГЋ P і висновок CГћ * za або висновок CГћ * ZaD, де a, bГЋ VT , U, C, DГЋ VN , x, y, zГЋ V * . p> У граматиці операторного передування різні породжують правила мають різні праві частини. Для граматики операторного передування теж будується матриця передування, але вона містить тільки термінальні символи граматики.
Для побудови цієї матриці зручно ввести безлічі крайніх лівих і крайніх правих термінальних символів щодо нетермінального символу U - L t (U) або R t
