ся процедура:
Procedure Check;
Для знаходження В«ЛівихВ» і В«правихВ» використовується процедура:
Procedure SearchLR;
Побудова матриці передування виконує процедура:
Procedure Matrix;
Побудова функції передування здійснюється процедурою:
Procedure FuncPrecede;
3. Граматики передування
КС-мови поділяються на класи у відповідності зі структурою правил їх граматик. У кожному з класів накладаються додаткові обмеження на допустимі правила граматики.
Одним з таких класів є клас граматик передування. Вони використовуються для синтаксичного розбору ланцюжків за допомогою алгоритму "зсув-згортка". Виділяють такі типи граматик передування:
В· простого передування;
В· розширеного передування;
В· слабкого передування;
В· змішаної стратегії передування;
В· операторного передування. p> Далі будуть розглянуті обмеження на структуру правил і алгоритми розбору для двох типів - граматик простого і операторного передування.
3.1 Граматики простого передування
Граматикою простого передування називають таку КС-граматику G ( VN , VT , P , S), V = VT Г€ VN в якій:
1. Для кожної впорядкованої пари термінальних і нетермінальних символів виконується не більше ніж одне з трьох відносин передування:
В· 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 і висновок DГћ * S j z, де U, DГЋ < b> VN , x, y, zГЋ V * ;
В· S i > S j ("S i , S j ГЋ V ), якщо і тільки якщо $ правило U В® xCS j y ГЋ P і висновок CГћ * zS i або $ правило U В® xCDy ГЋ P та висновки CГћ * zS i і DГћ * S j w, де U, C, DГЋ VN , x, y, z, wГЋ V * .
2. Різні породжують правила мають різні праві частини. p> Відносини =, <і> називають відносинами передування для символів. Ставлення передування єдино для кожної впорядкованої пари символів. При цьому між якими-небудь двома символами може і НЕ бути відносини передування - це означає, що вони не можуть перебувати поруч ні в одному елементі розбору синтаксично правильної ланцюжка. Відносини передування залежать від порядку, в якому стоять символи, і в цьому сенсі їх не можна плутати із знаками математичних операцій - наприклад, якщо S i > S j , то не ...
