Задача формалізації мов та перекладу

1. МОВИ ТА ГРАМАТИКИ

§ 1. Задача формалізації
мов та перекладу

2.

Сучасні ЕОМ – складні комплекси пристроїв,
що працюють завдяки системам
математичного забезпечення.
До них належать мови програмування,
транслятори з цих мов, операційні системи,
диспетчери, монітори (програми)
обслуговуючі програми, стандартні і типові
підпрограми.
Усі ці засоби реалізуються або програмним
або схемним способом. Певною МОВОЮ.

3.

Оскільки різні програми використовують різні
мови, то існую ВАЖЛИВА задача (проблема)
перекладу із однієї мови на іншу.
ЗАДАЧУ сформулюємо так:
Існують дві алгоритмічні мови і деякий
алгоритм, реалізований на одній з них.
Необхідно знайти оптимальну (за деякими
параметрами) реалізацію цього алгоритму на
іншій мові.

4.

5.

6.

7.

Зазвичай, в програмування одна з мов – мова
програмування, інша (друга) внутрішня мова
машини.
Отже, при перекладі йдеться про переклад з
мови програмування з одночасною
оптимізацією вихідної програми.
Але не лише в цьому випадку. На практиці, як
правило, розв’язання таких задача
поділяється на проміжні етапи, на кожному з
яких проводиться оптимізація і переклад на
свою мову.

8.

Такі задачі розв’язуються при проектуванні
трансляторів, компіляторів і при створенні
оптимальної схеми, що реалізує алгоритм
роботи деякого пристрою чи його частини.
Важливо, на кожному етапі існує своя МОВА.
Задання мови необхідне як для самого
процесу перекладу так і для визначення
коректності і припустимості записів.
Мова складається з рядків символів, а отже
весь обчислювальний процес – перетворення
однієї множини рядків на іншу множину.

9.

• § 2. Перетворення рядків символів
Буквою (символом) називатимемо простий
неподільний символ.
Множину всіх символів називатимемо
алфавітом.
Зауважимо, що, позаяк, алфавіт – множина, то
до нього можна застосовувати всі множинні
операції.
Алфавіти будемо позначати великими
латинськими, а їх символи – малими буквами,
з індексами чи без.

10.

Якщо