Page 12 - 4761

Приклад 1.3
Написати граматику для визначення поняття «ідентифікатор»
G({{AL},0,1,2,3,4,5,6,7,8,9}, {ідентифікатор,буква,цифра},P, <ідентифікатор>)
Р:
<iдентифікатор> <буква>| <ідентифікатор> <буква>| <ідентифікатор> <цифра>
<буква>| a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<цифра>0|1|2|3|4|5|6|7|8|9

1.6 Вивід. Ланцюг виводу

Виводом називається процес породження речень мови на основі правил, які
визначають мову граматики. Вивід називається закінченим, якщо на базі ланцюга β,
отриманого в результаті виводу, не можна зробити більше ні одного кроку виводу.
Ланцюг β, отриманий в результаті закінченого виводу називається кінцевим.
Вивід називається лівостороннім, якщо в ньому на кожному кроці виводу правило
граматики застосовується завжди до крайнього лівого нетермінального символу в
ланцюгу (правосторонній – навпаки).
Ланцюг β можна безпосередньо вивести з ланцюга α, якщо виконується одна з двох
умов:
- β безпосередньо виводиться з α (   );
-  γ такий, що: γ, який можна вивести з α і β , що безпосередньо виводять з γ
(  * і    ).
Якщо ланцюг виводу з α до β містить один або більше проміжних ланцюгів, то
позначається    . Якщо відомо кількість кроків виводу, то їх можна вказати

безпосередньо біля знаку виводу ланцюга, наприклад,   4  означає , що ланцюг β
можна вивести з ланцюга α за 4 кроки.
Як приклад, розглянемо граматику для отримання цілих десяткових чисел зі знаком.
G({0,1,2,3,4,5,6,7,8,9,+,-}, {S,T,F},P, S):
P:
S  T | +T | -T
T  F | TF
F  0 | 1 |2| 3 | 4 |5 | 6 |7 | 8 | 9

Побудуємо в ній декілька довільних ланцюгів виводу:
T
1.S     TF   TFF   FFF   4FF   47F   479
2. S  T  TF  T 8  F 8  18
3. T  TF  T 0  TF 0  T 50  F 50  350
4
4. TFT  TFFT  TFFF  FFFF  1FFF  1FF  10 4F  1004
5. F 
5
Отримали наступні виводи:
7
1. S  * - 479 або S  – 479
5
2. S  *18 або S  18
6
3. T  * 350 або T  350
7
4. TFT  *1004 або TFT  1004
1
5. F  *5 або F  5 (твердження F +5 невірне!).

10