3.1. Представлення оператора case за допомогою кв-граматики
Граматики можна класифікувати за виглядом їхньої продукції. Така класифікація називається ієрархією Хомського, за якою всі граматики поділяються на чотири типи.
Отже, нехай G = (N, T, P, S) — граматика.
Тип 0. Будь-яка граматика називається граматикою загального вигляду.
Тип 1. Контекстно-залежні граматики.
Тип
2. Граматика
називається контекстно-вільною
(КВ-граматика), якщо
кожна продукція з Р
має
вигляд: A
→ α,
де
A
належить
до множини
N,
.
Тип 3. Праволінійні та ліволінійні граматики.
КВ-граматика не є регулярною, вона не використовує контексту (звідки і назва).треба зазначити, що з чотирьох типів граматик ієрархії Хомського клас контекстно-вільних граматик є найбільш важливим з точки зору застосувань до мов програмування і компіляції. За допомогою саме цього типу граматик можна визначити велику частину синтаксичної структури мови програмування. Крім того, вона є основою різних схем перекладів.
Розв’язок поставленої задачі
Розглянемо стандартний вигляд заданого оператора Case:
Case i of
1: x:= х1;
5..9: x:= x2;
End;
<КС1> <ІД> <КС2>
<Ц> <CC> <ІД><СС><ІД><СС>
<Ц> <CC> <Ц> <CC> <ІД> <СС> <ІД> <СС>
<КС3> <CC>
КС - ключове слово;
ІД – ідентифікатор;
СС – службовий символ;
Б – буква;
Ц – цифра;
БЦ – Буквено-цифровий ланцюг;
<КС1> → Case
< КС2> → of
< КС3> → End
<ІД> → Б
<ІД> → БЦ
<БЦ> → <Б>
<БЦ> → <Ц>
<БЦ> → <Б>
<БЦ> → <Ц>
<Б> → <A>
<Б> → <B>
<Б> → <Y>
<Б> → <Z>
<Б> → <a>
<Б> → <b>
<Б> → <y>
<Б> → <z>
<Ц> → <1>
<Ц> → <2>
<Ц> → <3>
<Ц> → <4>
<Ц> → <5>
<Ц> → <6>
<Ц> → <7>
<Ц> → <8>
<Ц> → <9>
<Ц> → <0>
<СС> → <;>
<СС> → <:>
<СС> → <:=>
<СС> → <..>
3.2. Представлення оператора циклу Case за допомогою нормальної форми Бєкуса
Для зручності запису продукції граматик використовується нотація, що введена Бєкусом — нормальна форма Бєкуса-Наура. Ця нотація полягає в наступному:
символ «→» замінюється на символ «::=»;
в кутові дужки «< >» беруться не термінальні символи;
для скороченого запису продукції граматики використовується знак «|», що позначає «або» і об’єднує групу продукцій з однаковою лівою частиною, але різними правими.
Розв’язок поставленої задачі
Розглянемо стандартний вигляд оператора:
Case i of
1: x:= х1;
5..9: x:= x2;
End;
<КС1> <ІД> <КС2>
<Ц> <CC> <ІД><СС><ІД><СС>
<Ц> <CC> <Ц> <CC> <ІД> <СС> <ІД> <СС>
<КС3> <CC>
КС - ключове слово;
ІД – ідентифікатор;
СС – службовий символ;
Б – буква;
Ц – цифра;
БЦ – Буквено-цифровий ланцюг;
<КС1> ::= Case
< КС2> ::= of
< КС3> ::= End
<ІД> ::= Б│БЦ
<БЦ> ::= <Б>│<Ц>│…│<Б>│<Ц>
<Б> ::= <A>│<B>│…│<Y>│<Z>│<a>│<b>│…│<y>│<z>
<Ц> ::= <1>│<2>│<3>│<4>│<5>│<6>│<7>│<8>│<9>│<0>
<СС> ::= <;>│<:>│<:=>│<..>
РОЗДІЛ ІV
Розробка програми формування матриці відношень типу aRb
(R≡≤ , де а,b – цілі числа від 0 до 9) на мові Turbo Pascal
Таблиця символьних імен
|
Математична величина |
Ідентифікатор |
Тип змінної |
|
Числа стовпчика |
b |
byte |
|
Числа рядка |
a |
byte |
Текст програми
program ODM;
uses crt;
var a,b: byte;
Begin
Clrscr;
writeln ('Матрица отношений типа aRb ( R',#22,'<= )');
writeln;
for b:=0 to 10 do
begin
if b>0 then
write ((b-1):3)
else write (' ');
for a:=0 to 9 do
begin
if b=0 then
write (a:3)
else
if a<=(b-1) then
write ('1':3)
else write ('0':3);
end;
writeln; writeln;
end;
readln;
End.
Блок-схема програми
Результати роботи програми
Матриця відношень типу ( R≡<= )
0 1 2 3 4 5 6 7 8 9
0 1 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0
2 1 1 1 0 0 0 0 0 0 0
3 1 1 1 1 0 0 0 0 0 0
4 1 1 1 1 1 0 0 0 0 0
5 1 1 1 1 1 1 0 0 0 0
6 1 1 1 1 1 1 1 0 0 0
7 1 1 1 1 1 1 1 1 0 0
8 1 1 1 1 1 1 1 1 1 0
9 1 1 1 1 1 1 1 1 1 1