Теория языков программирования вопросы

Теория языков программирования и методы трансляции

Курсовая работа по информатике выполняется согласно учебному плану в седьмом семестре и имеет целью систематическое рассмотрение основ формального описания языков программирования и методов трансляции, формальных моделей, методов и алгоритмов синтаксически управляемого разбора и перевода.

Выполнение курсовой работы осуществляется самостоятельно по типовому заданию под руководством преподавателя и предусматривает постановку, алгоритмизацию, программирование поставленных задач, получение решения на персональном компьютере и оформление отчета. При этом используется весь арсенал изученных и освоенных методов программирования и приемов работы на персональном компьютере.

Оценка выполненной работы зависит от качества разработанных алгоритмов, программ, результатов тестирования, содержания и оформления отчета, а также от полноты используемых возможностей персонального компьютера при решении задач.

2. Задание на курсовую работу

2.1. Задача 1. Минимизация конечного автомата

Задача заключается в создании программы, которая способна минимизировать предлагаемый пользователем конечный автомат, а затем распознавать с помощью этого автомата цепочки, вводимые пользователем с клавиатуры.

Конечный автомат задается в виде матрицы смежности в текстовом файле. После загрузки необходимо провести удаление эквивалентных и недостижимых состояний. Удаление эквивалентных состояний производится методом разбиения на группы. Поиск недостижимых производится через поиск состояний, достижимых из начального состояния. Минимизированный автомат необходимо сохранить в текстовый файл.

С помощью минимизированного автомата программа должна позволять делать арифметические вычисления без учета приоритета операций. Возможные действия – сложение, вычитание, умножение, деление.

Например, при вводе строки 2+2*2 в результате мы получает ответ 8. При вводе ошибочного выражения получает сообщение об ошибке с позицией ошибочного символа.

2.2. Задача 2. Разработка модели интерпретатора

Данная задача заключается в создании приложения, позволяющего выполнять исходный код программы, созданный на основе определенной модели языка. Данный язык позволяет выполнять несколько видов операторов:

• Объявление переменных списком с возможностью инициализации;
• Присваивание переменной выражения;
• Ввод значения переменной с клавиатуры;
• Вывод значения переменной на экран.

Индивидуальные задания по согласованию с преподавателем могут включать:

Допускается объявление переменных трех типов:

• integer – целый;
• float – с плавающей точкой;
• string – текстовая строка.

Решение данной задачи состоит из двух частей: создание лексического и синтаксического блоков. Задача лексического блока состоит в преобразовании входного потока символов программы в поток лексем. Каждая лексема представляет собой пару (класс;значение). Где класс означает тип лексемы:

Для работы МП-автомата можно использовать следующую структуру данных:

Источник

Теория языков программирования и методы трансляции

Данный конспект представляет собой краткое изложение лекционного курса, читавшегося студентам по специальности «Программирование вычислительной техники и автоматизированных систем» в объёме 54 часа.

Введение. …………………………………………………………………….. 4 1. Языки и кризис программирования…………………………………………6

2. Математические методы описания языков. Формальные языки и

3. Основные понятия и определения…………………………………………..9

4. Этапы построения трансляторов…………………………………………….16

5. Основные методы поиска ошибок в исходных текстах программ………..18

6. Современное состояние и перспективы развития программирования

7. Лексический анализ. Интуитивный подход……………………………….21

8. Классы лексем и их особенности…………………………………………..21

9. Формирование таблиц лексем и построение дескрипторного текста

10. Синтаксический анализ. Метод рекурсивного спуска………………….26

11. Пример грамматики упрощенного языка Паскаль……………………..26

12. Пример программы на упрощенном Паскале…………………………..27

13. Алгоритм синтаксического анализа по методу рекурсивного спуска…31

14. Формализация методов построения трансляторов. Формальные

языки и грамматики. Классификация формальных языков

15. Лексический анализ, регулярные грамматики и конечные автоматы…39

16. S-грамматики и магазинные автоматы………………………………..…42

17. Грамматики типа LL(k). Алгоритмы построения магазинных

18. Детерминированный синтаксический анализ сверху вниз……………..50

19. Правила определения детерминированного МП-преобразователя

Современные специалисты в областях программирования вычислительной техники и других, использующих вычислительные машины в своей практической деятельности, так или иначе, соприкасаются с системами программирования, к которым, наряду с традиционными компиляторами и интерпретаторами можно отнести системы управления базами данных, различные информационно-поисковые, интеллектуальные, экспертные и многие другие программные системы. Но в любом случае основой вычислительной машины является двоичные элементы. Язык ЭВМ – машинный код, состоящий из нулей и единиц, нашему естественному языку полностью не соответствует, что является одной из причин возникновения психологического барьера меду человеком и ЭВМ.

Языки программирования не только позволяют автоматизировать трудоёмкий процесс программирования, но и максимально приблизить алгоритмический язык к естественному для нас языку.

Актуальной проблемой программирования остаётся отладка уже написанных программ. Современные трансляторы позволяют находить все сто процентов лексических ошибок, синтаксических ошибок и семантический ошибок, что существенно ускоряет процесс программирования и повышает достоверность результатов. На совести программиста остаются ошибки в самом алгоритме вычислений и неправильное программное представление заданного алгоритма вычислений.

В ЭВМ вся информация в виде двоичного кода никак не различается внешне. Смысл двоичного кода зависит только от его места положения в памяти ЭВМ. Это требует соответствующего размещения программы в памяти и решения задач распределения памяти ЭВМ. Эта сложная задача также автоматизирована с помощью трансляторов и операционной системы ЭВМ.

Таким образом, современное программирование возможно только на алгоритмических языках, а применение их возможно только при наличии трансляторов с них.

Транслятор представляет собой достаточно сложную программу. Которая реализует несколько этапов трансляции: лексический, синтаксический, построение объектной программы и, наконец, формирование машинного кода. При программировании транслятора эти этапы могут быть реализованы на интуитивном уровне, которым должен обладать программист, или на основе формальных методов. Интуитивный подход много проще формального, но он не гарантирует стопроцентного обнаружения всех ошибок. Кроме того, для задач реальной сложности интуитивный подход просто нереализуем.

Формальные методы достаточно сложны. Требуют применения теории формальных языков и грамматик. Но формализация позволяет решать задачи практически любой сложности и гарантирует стопроцентное обнаружение всех ошибок.

В данных лекциях будут рассмотрены основные, часто применяющиеся методы, использующие как интуитивный подход, так и теорию формальных языков и грамматик, математические модели элементов транслятора.

Источник

Теория языков программирования и методы трансляции

Курсовая работа по информатике выполняется согласно учебному плану в седьмом семестре и имеет целью систематическое рассмотрение основ формального описания языков программирования и методов трансляции, формальных моделей, методов и алгоритмов синтаксически управляемого разбора и перевода.

Выполнение курсовой работы осуществляется самостоятельно по типовому заданию под руководством преподавателя и предусматривает постановку, алгоритмизацию, программирование поставленных задач, получение решения на персональном компьютере и оформление отчета. При этом используется весь арсенал изученных и освоенных методов программирования и приемов работы на персональном компьютере.

Оценка выполненной работы зависит от качества разработанных алгоритмов, программ, результатов тестирования, содержания и оформления отчета, а также от полноты используемых возможностей персонального компьютера при решении задач.

2. Задание на курсовую работу

2.1. Задача 1. Минимизация конечного автомата

Задача заключается в создании программы, которая способна минимизировать предлагаемый пользователем конечный автомат, а затем распознавать с помощью этого автомата цепочки, вводимые пользователем с клавиатуры.

Конечный автомат задается в виде матрицы смежности в текстовом файле. После загрузки необходимо провести удаление эквивалентных и недостижимых состояний. Удаление эквивалентных состояний производится методом разбиения на группы. Поиск недостижимых производится через поиск состояний, достижимых из начального состояния. Минимизированный автомат необходимо сохранить в текстовый файл.

С помощью минимизированного автомата программа должна позволять делать арифметические вычисления без учета приоритета операций. Возможные действия – сложение, вычитание, умножение, деление.

Например, при вводе строки 2+2*2 в результате мы получает ответ 8. При вводе ошибочного выражения получает сообщение об ошибке с позицией ошибочного символа.

2.2. Задача 2. Разработка модели интерпретатора

Данная задача заключается в создании приложения, позволяющего выполнять исходный код программы, созданный на основе определенной модели языка. Данный язык позволяет выполнять несколько видов операторов:

• Объявление переменных списком с возможностью инициализации;
• Присваивание переменной выражения;
• Ввод значения переменной с клавиатуры;
• Вывод значения переменной на экран.

Индивидуальные задания по согласованию с преподавателем могут включать:

Допускается объявление переменных трех типов:

• integer – целый;
• float – с плавающей точкой;
• string – текстовая строка.

Решение данной задачи состоит из двух частей: создание лексического и синтаксического блоков. Задача лексического блока состоит в преобразовании входного потока символов программы в поток лексем. Каждая лексема представляет собой пару (класс;значение). Где класс означает тип лексемы:

Для работы МП-автомата можно использовать следующую структуру данных:

Источник