Cоздание формальной грамматики и построение выводов

Цель работы – изучение структуры языка программирования и запись ее в формальном виде; построение выводов на основе полученной грамматики для проверки ее правильности.

Содержание

• Создание грамматики языка
• Формы Бэкуса-Науэра (БНФ)
• Пример формальной грамматики, записанной в формах Бэкуса-Науэра
• Классификация Хомского
• КС – грамматики
• Построение выводов
• ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
• ИСПОЛЬЗОВАНИЕ "УЧЕБНОГО КОМПИЛЯТОРА” В ВЫПОЛНЕНИИ Л/Р №1
• ПОРЯДОК РАБОТЫ В "УЧЕБНОМ КОМПИЛЯТОРЕ”
• СОДЕРЖАНИЕ ОТЧЕТА
• КОНТРОЛЬНЫЕ ВОПРОСЫ
• Литоература

Фрагменты из методички

Основные сведения

Создание грамматики языка

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

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

Подводя итог вышесказанному, можно сделать следующий вывод. Для создания языка программирования необходим такой математиче-ский и теоретический аппарат, который бы формально мог описать структуру любого языка, с одной стороны, а с другой – по возможности бы учел машинные требования к создаваемому языку.
Основным определением такого аппарата является определение формального языка. Всякий язык программирования можно определить как множество предложений – некоторое множество цепочек или конечных последовательностей элементарных единиц из некоторого непустого конечного множества символов, называемого словарем или алфавитом. При таком рассмотрении языка программирования задается только множество символов, которые можно использовать для записи программы, а также класс допустимых или синтаксически правильных программ и при этом не затрагивается вопрос зада¬ния смысла каждой правильной программы. Чтобы отличать употребление слова «язык» в значении точно определенного множества цепочек от употребления этого слова в повседневной речи, множество цепочек иногда называют формальным языком.

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

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

Формальная грамматика есть четверка  G = { Vt, Vnt, P , S }, где

• Vt - алфавит терминальных символов, т.е. символов, которые могут входить в левые части правил ( соответствует набору слов и знаков языка);
• Vnt -алфавит нетерминальных символов (соответствует набору обобщающих понятий языка).