обов'язково, що S j i (Тому знаки передування іноді позначають спеціальною точкою: = Г—, <Г— , Г—>)
Метод передування заснований на тому факті, що відносини передування між двома сусідніми символами розпізнаваної рядка відповідають трьом наступними варіантами:
В· S i i +1 , якщо символ S i +1 - крайній лівий символ деякої основи;
В· S i > S i +1 , Якщо символ S i - крайній правий символ деякої основи;
В· S i = S i +1 , Якщо символи S i і S i +1 належать одній основі. p> Виходячи з цих співвідношень виконується розбір рядка для граматики передування.
На підставі відносин передування будують матрицю передування граматики. Рядки матриці передування позначаються першими символами, стовпці - другими символами відносин передування, а в клітини матриці на перетині відповідних стовпчика і рядка поміщаються знаки відносин. При цьому порожні клітини матриці говорять про те, що між даними символами немає жодного відносини передування.
Матрицю передування граматики можна побудувати, спираючись безпосередньо на визначення відносин передування, але зручніше скористатися двома додатковими множинами - множиною крайніх лівих і безліччю крайніх правих символів щодо нетерміналов граматики. Ці безлічі визначаються таким чином:
В· L (U) = {T | $ UГћ * Tz}, U, TГЋ V , zГЋ V * - безліч крайніх лівих символів щодо нетермінального символу U (ланцюжок z може бути і порожньою ланцюжком);
В· R (U) = {T | $ UГћ * zT}, U, TГЋ V , zГЋ V * - безліч крайніх правих символів щодо нетермінального символу U. p> Тоді відносини передування можна визначити так:
В· S i = S j ("S i , S j ГЋ V ), якщо $ правило U В® xS i S j y ГЋ P , де UГЋ VN , x, yГЋ V * ;
В· S i j ("S i , S j ГЋ V ), якщо $ правило U В® xS i Dy ГЋ P і S j ГЋ L (D), де U, DГЋ VN , x, yГЋ V * ;
В· S i > S j ("S i , S j ГЋ V ), якщо $ правило U В® xCS j y ГЋ P і S i ГЋ R (C) або $ правило U В® xCDy ГЋ P і S i ГЋ R (C), S j ГЋ < b> L (D), де U, C, DГЋ VN , x, yГЋ V * . p> Таке визначення відносин зручніше на практиці, так як не вимагає побудови висновків, а безлічі L (U) і R (U) можуть бути побудовані для кожного нетермінального символу UГЋ ...
