Презентація на тему Розбір полеволінійної граматики
Подібні презентації
Презентація на тему: "Розбір по леволінійній граматиці. Угоди: - для опису лексем використовуватимемо леволінійну автоматну граматику без порожніх правих частин: G." - Транскрипт:
1 Розбір з ліволінійної граматики. Угоди: - для опису лексем використовуватимемо леволінійну автоматну граматику без порожніх правих частин: G = (T, N, P, S) леволінійна, якщо кожне правило з Р має вигляд A Bt або A t, де A N, B N, t T. - аналізований ланцюжок закінчується спеціальним символом - ознакою кінця ланцюжка. Алгоритм розбору за леволінійною граматикою: (1) перший символ вихідного ланцюжка a 1 a 2. a n замінюємо нетерміналом A, для якого в граматиці є правило виведення A a 1 (іншими словами, робимо "згортку" терміналу a 1 до нетерміналу A) (2 ) багаторазово (до тих пір, доки не рахуємо ознаку кінця ланцюжка) виконуємо наступні кроки: отриманий на попередньому кроці нетермінал A і розташований безпосередньо праворуч від нього черговий термінал a i вихідного ланцюжка замінюємо нетерміналом B, для якого в граматиці є правило виведення B Aa i ( i = 2, 3. n);
2 Діаграми станів (ДС) Діаграма станів (ДС) - невпорядкований орієнтований позначений граф, який будується наступним чином: (1) будуємо вершини графа, позначені нетерміналами граматики (для кожного нетермінала - одну вершину), і ще одну вершину, поміч від нетермінальних (наприклад, H). Ці вершини називаються станами. H – початковий стан. (2) з'єднуємо ці стани дугами за такими правилами: a) для кожного правила виду W t з'єднуємо дугоюстану H та W (від H до W) і позначаємо дугу символом t; б) для кожного правила виду W Vt з'єднуємо дугою стану V та W (від V до W) і позначаємо дугу символом t; Діаграма станів для граматики G_ex = ( < a, b, >, < L(G) = < ([ab ba]) n n >= 1 > Алгоритм аналізу за діаграмою станів: (1) оголошуємо поточним стан H; (2) багаторазово (до тих пір, доки не рахуємо ознаку кінця ланцюжка) виконуємо наступні кроки: зчитуємо черговий символ вихідного ланцюжка і переходимо з поточного стану в інший стан по дузі, позначеної цим символом. Стан, який ми при цьому потрапляємо, стає поточним. = 1 & gt; Алгоритм аналізу за діаграмою станів: (1) оголошуємо поточним стан H; (2) багаторазово (до тих пір, доки не рахуємо ознаку кінця ланцюжка) виконуємо наступні кроки: зчитуємо черговий символ вихідного ланцюжка і переходимо з поточного стану в інший стан по дузі, позначеної цим символом. Стан, в який ми потрапляємо, стає поточним.">
3 Діаграми станів для праволінійних граматик ДС з праволінійної регулярної граматики будується наступним чином: (1) будуємо вершини графа, позначені нетерміналами граматики, і ще одну вершину, позначену символом, відмінним від нетермінальних (наприклад, F). Ці вершини називаються станами. S – початковий стан. F – заключний стан. (2) з'єднуємо ці стани дугами за такими правилами: a) для кожного правила виду W t з'єднуємо дугою стану F і W (від W до F) і позначаємо дугу символом t; б) для кожного правила виду W tV з'єднуємо дугою стану V та W (від W до V) і позначаємо дугу символом t; Діаграма станів для граматики G_ex2 = ( < 0, 1, >, < S, B, C>, P, S ), де P: S 0B виглядатиме так: B 1B 1C C L(G) = < 0 1 n n >= 0 > Маючи ДС, побудовану за будь-якою регулярною граматикою, можна по ній відновити як леволінійну, так і еквівалентну їй праволінійну регулярну граматику S B C F = 0 > Маючи ДС, побудовану за будь-якою регулярною граматикою, можна по ній відновити як леволінійну, і еквівалентну їй праволінійну регулярну граматику. 0 1 1 S B C F">
4 Алгоритм побудови праволінійної граматики G right по ДС, побудованої за ліволінійною граматикою G left. Нетерміналами G right будуть усі стани з ДС, крім S. Якщо ДС є вихідні дуги з S, то вводимо в ДС новий заключний стан S, в яке з S веде дуга, позначена ознакою кінця. Кожній дузі зі стану V до заключного стану S (або S), позначеної символом t ( ) ставиться у відповідність правило V t ( V ). Кожній дузі зі стану V стан W, позначеної символом t, ставиться у відповідність правило V tW. Початковий стан H оголошується початковим символом граматики.
5 Алгоритм побудови леволінійної граматики G rleft по ДС, побудованої праволінійної граматики G right. Нетерміналами G left будуть усі стани з ДС для G right, крім S. Кожній дузі зі стану S стан W, позначеної символом t, ставиться у відповідність правило W t. Якщо ДС є вхідні дуги в S, то G left додається також і правило W St. Кожній дузі зі стану V стан W, позначеної символом t, ставиться у відповідність правило W Vt. Заключний стан F оголошується початковим символом граматики.
6 Угоди для роботи з діаграмами станів a) Якщо з одного стану в інший виходить кілька дуг, позначених різними символами, то зображується одна дуга, позначена всіма цимисимволи. b)Непомічена ніякими символами дуга відповідає переходу за будь-якого символу, крім тих, якими позначені інші дуги, що виходять із цього стану. c)Вводиться додатковий стан помилки (ER); перехід у цей стан означає, що вихідний ланцюжок мови не належить.
7 Кінцевий автомат (КА) Кінцевий автомат (КА) - це п'ятірка (K, T, δ, H, S), де K - кінцева множина станів; T - кінцева множина допустимих вхідних символів; δ - відображення (функція переходів) множини K T K, що визначає поведінку автомата; H K – початковий стан; S K - заключний стан (чи кінцеве безліч заключних станів, але граматик – одне!). δ (A, t) = B означає, що зі стану A за вхідним символом t відбувається перехід у стан B. Кінцевий автомат допускає ланцюжок a 1 a 2. a n, якщо δ(H, a 1 ) = A 1 ; δ(A 1, a 2) = A 2;. ; δ(A n-2, a n-1) = A n-1; δ(A n-1, an ) = S, де a i T, A j K, j = 1, 2. n-1; i = 1, 2. n; H - початковий стан, S - один із заключних станів. Безліч ланцюжків, що допускаються кінцевим автоматом, становить мова, яку він визначає.
> c; >state CS; // CS – поточний стан CS = H; do < gc(); switch (CS) < case H: if (c == 'a') < CS = A; else if (c == 'b') ; void gc ( ) < cin >> c; >state CS; // CS – поточний стан CS = H; do < gc(); switch (CS) < case H: if (c == 'a') < CS = A; else if (c == 'b') 8 Аналізатор для регулярної граматики G_ex. char c;bool scan_G ( ) < enum state < H, A, B, C, S, ER >; void gc ( ) < cin >> c; >state CS; // CS – поточний стан CS = H; do < gc(); switch (CS) < case H: if (c == 'a') < CS = A;>else if (c == 'b') < CS = B;>else CS = ER; break; case A: if (c == 'b') < CS =C;>інакше CS = ER; перерва; випадок B: if (c == 'a') < CS = C;>інакше CS = ER; перерва; випадок C: if (c == 'a') < CS = A;>інакше, якщо (c == 'b') < CS = B;>інакше, якщо (c == ' ') CS = S; інакше CS = ER; перерва; > > while (CS != S && CS != ER); if (CS == ER) повертає false; інакше повертає істину; > > c; >стан CS; // CS - поточний стан CS = H; зробити < gc (); перемикач (CS) < випадок H: якщо (c == 'a') < CS = A;>інакше, якщо (c == 'b') > c; >стан CS; // CS - поточний стан CS = H; зробити < gc (); перемикач (CS) < випадок H: якщо (c == 'a') < CS = A;>інакше, якщо (c == 'b') < CS = B;>інакше CS = ER; перерва; випадок A: if (c == 'b') < CS = C;>інакше CS = ER; перерва; випадок B: if (c == 'a') < CS = C;>інакше CS = ER; перерва; випадок C: if (c == 'a') < CS = A;>інакше, якщо (c == 'b') < CS = B;>інакше, якщо (c == ' ') CS = S; інакше CS = ER; перерва; > > while (CS != S && CS != ER); if (CS == ER) повертає false; інакше повертає істину; >"> > c; >state CS; // CS - поточний стан CS = H; do < gc (); switch (CS) < case H: if (c == 'a') < ; CS = A;>else if (c == 'b') ; void gc ( ) < cin >> c; >state CS; // CS - поточний стан CS = H; do < gc (); switch (CS) < case H: if (c == 'a') < CS = A;>else if (c == 'b')
9 О недетерминированном разборе При аналізі по ДС для регулярної граматики може виявитися, що з одного стану виходить кілька дуг, провідних у різних станах, але позначених одним і тим же символом. Для леволинейной граматики ця ситуація виникає, коли в правилах виведення є совпадающие праві частини. Для праволінійної граматики виникає аналогічна ситуація, коли альтернативні виведення з одного нетерміналу граматики починаються одинаковими термінальними символами. Недетермінованийкінцевий автомат (НКА) - це п'ятірка (K, T, δ, H, S), де K - кінцева множина станів; T - кінцева множина допустимих вхідних символів; δ - відображення множини K T в множину підмножин K; H K - кінцева множина початкових станів (у нас одне!); S K - кінцева множина заключних станів (у нас одне!). δ (A,t) = означає, що зі стану A за вхідним символом t можна здійснити перехід у будь-який із станів Bi, i = 1, 2. n.
10 Алгоритм побудови детермінованого КА НКА Вхід: M = (K, T, δ, H, S) - НКА. Вихід: M1 = (K1, T, δ1, H1, S1) - детермінований КА, що допускає ту ж мову, що і автомат М. Метод: 1. Будуємо відображення δ1 (K1 T K1) по δ, починаючи зі стану H. 2 δ1 для Н К1 будуємо в.о.: - якщо в НКА перехід з Н за якимось символом був детермінованим, переносимо відповідні відображення в результуючий КА. Стани, що з'являються у правій частині відображень δ1 належать К1; - якщо в НКА перехід з Н за якимось символом t був недетермінованим, то КА включаємо відображення δ1 за правилом: δ1 (H, t) = A1A2. An,де Ai К, і в НКА є F(H, t) = Ai для всіх 1
=1 > δ (A, 1) = B δ (A, 1) = S δ (B, 0) = A, Функції переходів КА, побудовані за НКА відповідно до пре " title="Приклад роботи алгоритму перетворення НКА в КА Заданий НКА M = ( < H, A, B, S >, < 0, 1 >, δ, < H >, < S >), де δ (H, 1) = BL = < 1(01) n n >=1 > δ (A, 1) = B δ (A, 1) = S δ (B, 0) = A, Функції переходів КА, побудовані за НКА відповідно до 11 Приклад роботи алгоритму перетворення НКА в КА Задано НКА M = ( < H, A, B, S >, < 0, 1 >, δ, < H >, < S >), де δ (H, 1) = BL = 1(01) n n = 1 δ (A, 1) = B δ (A, 1) = S δ (B, 0) = A, Функціїпереходів КА, побудовані за НКА відповідно до запропонованого алгоритму. δ1(Н, 1) = B δ1(B, 0) = A δ1(A, 1) = BS δ1(BS, 0) = A Заключним станом побудованого детермінованого КА є стан BS. Таким чином, M1 = (, , δ1, H, BS). =1 > δ (A, 1) = B δ (A, 1) = S δ (B, 0) = A, Функції переходів КА, побудовані за НКА відповідно до пре "> B δ (A, 1) = S δ (B, 0) = A, Функції переходів КА, побудовані за НКА відповідно до запропонованого алгоритму.δ1(Н, 1) = B δ1(B, 0) = A , 1) = BS δ1(BS, 0) = A Заключним станом побудованого детермінованого КА є стан BS. Таким чином, M1 = (, , δ1, H, BS)."> =1 > δ (A, 1) = B δ (A, 1) = S δ (B, 0) = A, Функції переходів КА, побудовані за НКА відповідно до пре " title="Приклад роботи алгоритму перетворення НКА в КА Заданий НКА M = ( < H, A, B, S >, < 0, 1 >, δ, < H >, < S >), де δ (H, 1) = BL = < 1(01) n n >=1 > δ (A, 1) = B δ (A, 1) = S δ (B, 0) = A, Функції переходів КА, побудовані за НКА відповідно до пре">
13 Лексичний аналіз мов програмування Прийнято виділяти такі типи лексем: ідентифікатори, службові слова, константи та обмежувачі. Кожній лексемі зіставляється пара: (тип_лексеми, покажчик_на_інформацію_про_ній). Таким чином, лексичний аналізатор - це транслятор, входом якого є ланцюжок символів, що представляють вихідну програму, а виходом - послідовність лексем. Лексеми наведених вище типів можна описати за допомогою регулярних граматик. Наприклад, ідентифікатор (I): I a b. z Ia Ib. Iz I0 I1. I9 ціле без знаку (N): N 0 1 . 9 N0 N1. N9
14 Опис модельної мови P program D1; B D1 var D D I : [ int bool ] B begin S < ; S >end S I :=E if E then S else S while E до S B read (I) write (E) E E1 [ = = != ] E1 E1 E1 T < [ + - or ] T &T T F < [ * / and ] F & F; z Ia Ib. Iz I0 I1. I9 N 0 1 . 9 N0 N1. N9 Примітки: запис типу < > означає ітерацію ланцюжка, тобто. в ланцюжку, що породжується, в цьому місці може знаходитися або, або, або, і т.д. запис виду [ ] означає, що у ланцюжку, що породжується, в цьому місці може знаходитися або, або. P – мета граматики; символ - маркер кінця тексту програми.
16 Подання лексем enum type_of_lex < LEX_NULL, /*0*/ LEX_AND, LEX_BEGIN, … LEX_WRITE, /*18*/ LEX_FIN, /*19*/ LEX_SEMICOLON, LEX_COMMA, … */ POLIZ_LABEL, /*38*/ POLIZ_ADDRESS, /*39*/ POLIZ_GO, /*40*/ POLIZ_FGO >; /*41*/ Змістовно внутрішнє уявлення лексем - це пара (тип_лексеми, значення_лексеми). Значення лексеми - це номер рядка у таблиці лексем відповідного класу, що містить інформацію про лексему, або безпосереднє значення, наприклад, у разі цілих чисел. Угода про таблиці лексем, що використовуються: TW - таблиця службових слів М-мови; TD - таблиця обмежувачів М-мови; TID – таблиця ідентифікаторів аналізованої програми;
19 Клас tabl_ident class tabl_ident
20 Клас Scanner class Scanner < enum state < H, IDENT, NUMB, COM, ALE, DELIM, NEQ >; static char * TW []; static type_of_lex words []; static char * TD []; static type_of_lex dlms[]; state CS; FILE * fp; char c; char buf [80]; int buf_top; void clear(); void add (); int look (const char * buf, char * * list); void gc ( ) < c = fgetc (fp); >public: Scanner (const char * program); Lex get_lex(); >;