Елементи синтаксичного аналізу, Детальна інформація

тобто правий ланцюжок є довільною послідовністю терміналів і нетерміналів, а лівий містить принаймні один нетермінал.

S – початковий нетермінал із множини N, або позначення головного поняття, яким позначаються слова мови.

Нетермінали записуються словами в дужках <> або великими латинськими буквами. Термінали за необхідності часом беруться в апострофи. Як і в мові БНФ, замість продукцій вигляду v\xF0AE w1ww2 і v\xF0AE w1w2 записується продукція v\xF0AE w1[w]w2, а замість продукцій v\xF0AE w1u1w2 і v\xF0AE w1u2w2 – продукція v1\xF0AE w1(u1|u2)w2 .

Приклад 21.3. Множину продукцій граматики

G1 =({ a, 1, 2 },

{ A, B, C, D },

{ A \xF0AE BC, A \xF0AE BD, A \xF0AE B, B \xF0AE a, C \xF0AE 1, D \xF0AE 2 },

A )

можна переписати у вигляді

{ A \xF0AE B [ C | D ], B \xF0AE a, C \xF0AE 1, D \xF0AE 2 }.

Як бачимо, продукції граматики дуже схожі на БНФ як за формою, так і за змістом – лише замість знака "::=" вживається "\xF0AE ". Проте в лівій частині їх продукцій може бути не поодинокий нетермінал, а цілий ланцюжок, у якому обов'язково є нетермінал. За рахунок такого узагальнення граматики виявляються більш потужним засобом задання мов, ніж системи БНФ, тобто існують мови, які задаються граматиками, але не задаються БНФ. Тепер опишемо спосіб, у який граматика G = (X, N, P, S) задає мову.

1. На множині слів об'єднаного алфавіту (X\xF0C8 N)* означається відношення безпосередньої виводимості, позначене знаком \xF0DE G (або \xF0DE , коли відомо, якою саме є G):

v \xF0DE G w, якщо v = x1 u x2 , w = x1 y x2 , u \xF0AE y \xF0CE P.

При цьому кажуть, що w безпосередньо виводиться з v застосуванням продукції u\xF0AE y. Наприклад, у граматиці G1 із прикладу 21.3 BC\xF0DE aC застосуванням продукції B\xF0AE a, aC\xF0DE a1застосуванням C\xF0AE 1.

2. На множині (X\xF0C8 N)* означається відношення виводимості, позначене \xF0DE *G (або \xF0DE *, коли відомо, якою саме є G): v\xF0DE *w, якщо v=w або існує послідовність w1, w2, … , wn слів, де n\xF0B3 1, така, що v\xF0DE w1, w1\xF0DE w2, … , wn-1\xF0DE wn, wn=w. Так, у граматиці G1 BC\xF0DE *a1, оскільки BC\xF0DE aC, aC\xF0DE a1. Послідовність v\xF0DE w1\xF0DE w2\xF0DE …\xF0DE wn називається виведенням wn із v, а n – довжиною виведення. Інколи довжину записують замість '*' таким чином: v\xF0DE nw, наприклад, BC \xF0DE 2a1.

3. Якщо S\xF0DE G*w, то послідовність S\xF0DE …\xF0DE w називається виведенням слова w у граматиці G, а слово w – вивідним. Так, слова A, BC, aC, a1 вивідні в граматиці G1.

4. Вивідні слова в алфавіті X називаються породжуваними, а множина їх усіх – мовою, що задається (породжується) граматикою G: L(G) = {w | w\xF0CE X* та S \xF0DE * w }.

Приклади

4. Граматика G1 із прикладу 21.3 задає мову { a, a1, a2 }.

5. Граматика

G2 = ( { a, …, z, 0, …, 9 }, { I, L, D },

{ I \xF0AE L | IL | ID, L \xF0AE a | … | z, D \xF0AE 0 | ... | 9 },

I )

породжує множину ідентифікаторів.

6. Граматика G3 = ( { (, ) }, { S }, { S \xF0AE \xF065 | ( S ) }, S ) задає множину "вкладених дужок" { (n)n | n \xF0B3 0 }.\xF0E7

21.7. Граматика

G4 = ( { a, b, c }, { S, A, B, C},

{ S \xF0AE aSBC | abC, CB \xF0AE BC, bB \xF0AE bb, bC \xF0AE bc, cC \xF0AE cc },

S )

визначає мову { anbncn | n \xF0B3 1 }.\xF0E7