Читать онлайн «Методические указания к лабораторным работам по курсу ''Теория вычислительных процессов и структур''»

Министерство образования Российской Федерации ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра программного обеспечения и автоматизированных систем Д. Л. Домашова В. А. Стенюшкина МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторным работам по курсу “Теория вычислительных процессов и структур” Оренбург 2000 4  К 32. 973- 0181Я7 91 УДК 681. 3(07) Meтодические указания для выполнения лабораторных работ по курсу «Теория вычислительных процессов и структур» для студентов 3-го курса специальности 220400 Введение Перевод программы, написанной на языке программирования, на машинный язык осуществляется программой, которая называется транслятором. В методических указаниях рассматриваются общие подходы к построению компиляторов и интерпретаторов, дано описание модельного языка MPL и построены лексический, синтаксический и семантический анализаторы для языка MPL. Далее рассмотрены перевод программы в польскую инверсионную запись (ПОЛИЗ) и построение интерпретатора ПОЛИЗа для модельных языков MPL и SOL. Приведены примерные варианты заданий для курсовых работ по построению транслятора для модельного языка MPL, а также интерп- ретаторов ПОЛИЗа и модельного языка SOL. 5  1 Основы теории 1. 1 Нормальные формы Бэкуса Нормальные формы Бекуса, или металингвистические формулы, являются наиболее распространенным метасинтаксическим языком, используемым для описания многих языков программирования. Каждая металингвистическая формула описывает правила построения некоторой конструкции языка и состоит из двух частей: в левой части находится металингвистическая переменная, обозначающая соответствующую конструкцию; далее следует металингвистическая связка ": : = " ,имеющая смысл "по определению равно"; в правой части указывается один или несколько вариантов построения конструкции, обозначенной в левой части. Для того, чтобы построить определяемую формулой конструкцию, нужно выбрать некоторый вариант построения правой части формулы и подставить вместо каждой металингвистической переменной соответствующие цепочки основных символов. Варианты правой части формулы разделяются металингвистической связкой "|". , имеющей значение "или". Металингвистическая переменная обозначается словами языка разработчика, заключенными в угловые скобки. БНФ используются для описания формальных языков. Пример : <имя>::=<буква>|<имя><буква>|<имя><цифра> И::=Б|ИБ|ИЦ И,Б,Ц – метапеременные или нетерминальные символы (нетерминалы) Терминальные символы (терминалы) – символы из алфавита языка. Цепочка (строка)- любая последовательность из терминальных и нетерминальных символов. Терминальная цепочка – цепочка из терминальных символов Формальный язык – некоторое множество из терминальных цепочек. 1. 1. 1 Описание модельного языка MPL P::=program Д';Д.