ГРАММАТИКА

Грамматика:

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>), Сдвиг