Основою створення правил граматики є спосіб виділення структури заданої множини ланцюжка . Цей спосіб передбачає ділення ланцюжка на частини таким чином, щоб виявити частини, які повторюються , і які входять до усіх ланцюжків в незмінному вигляді. Множина таких визначень складає основу словаря нетермінальних символів деякої граматики.
Наступним кроком є виявлення послідовності, в якій елементи структури можуть входити до заданих ланцюжків. Такі послідовності є основою для будування правил граматики.
5.1.Опис списків
Простіша послідовність може містити 1 символ – а. Всі інші послідовності отримуються шляхом приписування до початкового елементу інших елементів. Якщо список не містить жодного елемента, додаємо правило 4.
1. H ® a R
2. R ® a R
3. R ® $
4. H ® $
5.2. Граматики, що містять розділові знаки
1. B1 ® i K
2. K ® , i K
3. K ® $
4. B1 ® $
У випадку, якщо список може бути порожнім, додаємо правило 4.
Аналізуємо структуру ланцюжка B1 ® i K. Вона складається з 2-х частин : i та K. i – це термінальный символ, K – нетермінальный символ, який далі описується граматикою
K ®, iK. Така граматика дозволяє описати, наприклад, такий ланцюжок – i,i,i.
5.3. Граматика, яка описує цілі числа без знака
A ® BC
C ® BC
C ® $
B ® 0|1|…|9
Така граматика дозволяє описати, наприклад, такий ланцюжок – 1929394.
5.4. Граматика, яка описує ідентифікатори
1. I ® CA
2. A ® CA|DA
3. A ® $
4. C ® a |b |c |…|z
5. D ® 0 |1 | ...| 9| _
Така граматика дозволяє описати, наприклад, такий ланцюжок – ad_2.
5.5. Граматика для арифметичних виразів
Приклад 1. Граматика, що описує вираз без дужок.
1. H ® i R
2. R ® W i R
3. R ® $
4. W ® * | / | + | -
Така граматика дозволяє описати, наприклад, такий ланцюжок : i+i*ii.
Приклад 2. Граматика, що описує вираз з дужками без вкладеності
1. G ® HQ
2. G ® (H)Q
3. Q ® WG
4. Q ® $
5. H ® i R
6. R ® W i R
7. R ® $
8. W ® * | / | + | -
Така граматика дозволяє описати, наприклад, такий ланцюжок : (i-i*i)i.