Page 42 - 4761

2. Різні правила в граматиці мають різні праві частини (тобто в граматиці не має
бути двох різних правил з однією і тією ж правою частиною).
Відношення = , < ,  > називається відношеннями передування для
символів. Відношення передування є єдиним для кожної пари впорядкованих символів.
При цьому між якимось двома символами може і не бути відношення передування – це
значить, що вони не можуть знаходитись поряд ні в одному елементі розбору
синтаксичного правильного ланцюга. Відношення передування залежить від порядку, в
якому стоять символи (тому їх не можна путати зі знаками математичних операцій; вони
не мають ні властивостей комутативності, ні асоціативності).
Наприклад, якщо відомо, що B i  > B j , то не обов’язково B j < B i (тому знаки
передування деколи позначають спеціальною крапкою  = , < ,  >).
Для граматик простого передування відомі наступні властивості:
1. Всяка граматика простого передування є однозначною.
2. Легко перевірити є чи ні довільна КВ-граматика, граматикою простого
передування (для цього достатньо перевірити властивості граматики, або побудувати
матрицю передування).
Метод передування базується на тому факті, що відношення передування між
двома сусідніми символами рядка, що розпізнається відповідають трьом наступним
варіантам:
– B i < B i+1 , якщо символ B i+1 – крайній лівий символ деякої основи;
– B i  > B i+1 , якщо символ B i+1 – крайній правий символ деякої основи;
– B i = B i+1 , якщо символи B i та B i+1 – належать одній основі.
Виходячи з цих співвідношень, виконуємо розбір рядка для ГПП (рис. 3.4).

Рисунок 3.4 – Відношення між символами вхідного ланцюга
На рисунку 3.4 показано вхідний ланцюг символів α β , в ньому виконується
згортка ланцюга  . Символ а є останнім символом підланцюга £, а символ b першим
символом підланцюга β.
Якщо граматика є граматикою простого передування, то в процесі виконання
розбору по аморитму “зсув-згортка” можна виконувати зсув до тих пір, поки символом на
верхівці стеку і поточним символом вхідного ланцюга існує відношення < або = . Як
тільки між ними буде  >, то треба зразу виконувати згортку. Причому для виконання
згортки зі стеку треба вибрати всі символи, що зв’язані відношенням = .
На основі відношень передування будують матрицю передування граматики. Рядки
матриці передування помічають першими (лівими) символами, стовпці – другими
(правими) символами відношень передування. В клітинці матриці на перетині відповідних
стовпця та рядка поміщають знаки операцій. При цьому пусті клітинки матриці говорять
проте, що між даними символами немає ні одного відношення передування.
Матриця передування служить основою для роботи розпізнавача мови, заданої
граматикою простого передування.

Алгоритм “зсув-згортка” для ГПП
Операція передування служить для того, щоб визначити в процесі виконання
алгоритму, яку дію – зсув чи згортку – треба виконати на кожному кроці алгоритму, і
однозначно вибрати ланцюг для згортки.
В початковому стані автомата зчитуючи головка зчитує перший символ вхідного
ланцюга, в стеку МП-автомата знаходиться символ  n (початок ланцюга), в кінець

40