Грамматика:
I. Структура
1. Описание переменных (int, string)
2. Тело программы
II. Операторы (зарезервированные слова, операции и т.д.)
1. Input [имя_переменной] // функция ввода
2. Output [имя_переменной] // функция вывода
3. Арифметические операции: только бинарные
4. Логические операции: только бинарные
§ > < <= >= <> = and or xor
5. Оператор присваивания: :=
6. Оператор цикла: while <логическое_выражение>
7. Оператор условия: if (без else)
8. Блок: { }
9. Разделитель операторов: ;
III. Синтаксис операторов
1. <описание_переменных>
(<описание_переменной>;)
2. <описание_переменной>
<имя_типа> <список_переменных>
3. <имя_типа>
int | string
4. <список_переменных>
id
5. <список_переменных>
id(,id)
6. <ввод>
input[id];
7. <вывод>
output[id];
8. <присваивание>
id:=<ариф_выражение> | <str_выражение>;
9. <ариф_выражение>
<операнд_int><знак_операции><операнд_int>;
10. <операнд_int>
id | num
11. <операция>
+ | - | * | div
12. <строка>
’<набор_символов>’
13. <набор_символов>
(a..z | A..Z | 0..9)
14. <str_выражение>
<операнд_str>+<операнд_str>
15. <блок>
{<последовательность_операторов>}
16. <последовательность_операторов>
<оператор>; <последовательность_операторов>
17. <последовательность_операторов>
ε
18. <оператор цикла>
while <логическое_выражение> <блок>;
19. <условие>
if <логическое_выражение> <блок>;
и т.д.
Пример 1:
1. <E>
<E>+<T> {a,b,(}
2. <E>
<T> {a,b,(}
3. <T>
<T>*<P> {a,b,(}
4. <T>
<P> {a,b,(}
5. <P>
(<E>) {(}
6. <P>
a {a}
7. <P>
b {b}
Шаг 1. Проверка корректности грамматик: проверка достижимости символов и продуктивности +
Шаг 2. Находим множества выбора – множества выбора пересекаются. Значит это не LL(1)-грамматика.
Грамматику разобрать нисходящими методами нельзя.
Пример 2:
1. <A>
a<B>a{y}<D> {a}
2. <A>
b {b}
3. <B>
b{x}<D> {b}
4. <B>
a<B> {a}
5. <D>
d<A> {d}
6. <D>
ε СЛЕД(<D>)={
,a}
Шаг 1. Проверка корректности грамматик: проверка достижимости символов и продуктивности +
Шаг 2. Находим множества выбора – множества выбора не пересекаются -
Значит это Q-грамматика
Входные символы: {a,b,d,
}
Магазинные символы: {<A>,<B>,<D>,{y}, }
| a
| b
| d
|
|
<A>
| #1
| #2
| Отвергнуть
| Отвергнуть
|
<B>
| #3
| #4
| Отвергнуть
| Отвергнуть
|
<D>
| #5
| Отвергнуть
| #6
| #5
|
{y}
| Выполнить(y)
| Выполнить(y)
| Выполнить(y)
| Выполнить(y)
|
a
| Вытолкнуть, Сдвиг
| Отвергнуть
| Отвергнуть
| Отвергнуть
|
| Отвергнуть
| Отвергнуть
| Отвергнуть
| Допустить
|
#1: Заменить(<D>{y}a<B>), Сдвиг
#2: Вытолкнуть, Сдвиг
#3: Заменить(<B>), Сдвиг
#4: Заменить(<D>{x}), Сдвиг
#5: Вытолкнуть, Держать
#6: Заменить(<A>), Сдвиг