Правила грамматики регулярного числового арифметического выражения. Лабораторная работа №3

1.

ПРАВИЛА ГРАММАТИКИ РЕГУЛЯРНОГО ЧИСЛОВОГО
АРИФМЕТИЧЕСКОГО ВЫРАЖЕНИЯ (ЛАБОРАТОРНАЯ РАБОТА № 3)
Правила грамматики
Семантика нетерминальных символов
1. S→B
2-3. B→A | B,A
S – начальный нетерминальный символ
B – последовательность арифметических выражений, разделенных запятыми
4-6. A→T | ZT | AZT
7-8. T→U | TMU
A – арифметическое выражение
T – алгебраическое слагаемое (терм) в арифметическом выражении, перед первым
термом может стоять знак + или -, между термами один из этих знаков обязателен
9-10. U→H | U^H
U – множитель в терме, между множителями должен стоять знак * или /
11-14. H→F | V | R| (A)
H – первичное арифметическое выражение в множителе, между H ставится знак
операции возведения в степень, H представляется одним из четырех видов: функция,
идентификатор, вещественное число или арифметическое выражение в скобках
F – функция, представлена идентификатором, за которым в скобках находится
последовательность арифметических выражений
15. F→V(B)
16-18. V→L | VL | VD
V – идентификатор – последовательность строчных латинских букв и цифр,
начинающаяся со строчной буквы
19-22. R→I | I. | .I | I.I
R – вещественное число, представленное последовательностью цифр, в которой в
любом месте может находится десятичная точка
23-24. I→D | ID
I – целое число – последовательность цифр
25-26. Z→+\27-28. M→* | /
29-54. L→λ
55-64. D→δ
Z – знак операции сложения или вычитания
M – знак операции умножения или деления
L– любая строчная латинская буква
D – любая десятичная цифра

2.

ОБРАТИТЕ ВНИМАНИЕ :
1. Неограниченное число повторений достигается
леворекурсивными правилами, что соответствует порядку
выполнения действий в арифметическом выражении слева
направо.
2. Приоритет выполнения операций в арифметическом
выражении отражается последовательностью использования
нетерминальных символов в правилах: сначала определяется
терм, т.е. сложение и вычитание будут выполняться в
последнюю очередь, затем – множитель и в последнюю
очередь определяется первичное арифметическое выражение.
Таким образом, высший приоритет имеет вычисление функции,
затем возведение в степень, после чего выполняются операции
умножения и деления и, наконец, сложение и вычитание.

3.

РЕКОМЕНДУЕМАЯ МЕТОДИКА СОЗДАНИЯ
ГРАММАТИКИ В ЛАБОРАТОРНОЙ РАБОТЕ № 4
Так как язык в задании лабораторной работы № 4
представляет собой подмножество языка из
лабораторной работы № 3, то удобно создавать
порождающую грамматику удалением из общей
грамматики ненужных правил и нетерминальных
символов.
Рассмотрим, например, следующее задание:
Язык представляет собой множество
арифметических выражений со скобочной
структурой, операнды которого – целые числа
(неограниченной длины), а операции –
сложение и умножение.

4.

Так как цепочка заданного языка – одно
арифметическое выражение, то удаляем из
грамматики, порождающей последовательность
выражений, символ B.
В результате вместо правил:
1. S→B
2-3. B→A | B,A
получаем следующее правило:
1. S→A

5.

В заданном языке отсутствуют операции вычитания
и унарный плюс, следовательно, вместо правил:
4-6. A→T | ZT | AZT
получаем правила:
2-3. A→T | A+T
Становятся ненужными символ Z и правила:
25-26. Z→+\-

6.

В заданном языке отсутствует операция деления.
В результате вместо правил:
7-8. T→U | TMU
получаем правила:
4-5. T→U | T*U
В заданном языке отсутствует операция возведения в
степень, следовательно, не нужны символы M и H и
правила:
9-10. U→H | U^H
27-28. M→* | /
Множитель U одновременно является и первичным
арифметическим выражением.

7.

По условию операндами арифметического выражения
могут быть целые числа и арифметические выражения в
скобках.
Значит, не нужны правила 15, 16-18, 19-22 и 29-54:
15. F→V(B)
16-18. V→L | VL | VD
19-22. R→I | I. | .I | I.I
29-54. L→λ
Соответственно не нужны символы F, V, R и L.
Вместо правил:
11-14. H→F | V | R| (A)
получаем правила:
6-7. U→I | (A)

8.

Итак, получаем следующий набор правил искомой
грамматики:
1. S→A
2-3. A→T | A+T
4-5. T→U | T*U
6-7. U→I | (A)
8-9. I→D | ID
10-19. D→δ