Cтраница 3
Это определение представляется более узким, чем предыдущее, хотя не известно, приводят ли указанные два определения NP-полных языков к разным классам. Определение, основанное на сводимости, означает, что если М0 - детерминированная машина Тьюринга, распознающая NP-полный язык L0 за время Т ( п), то всякий язык из ЖЗ можно распознать за время Т ( р ( п)), где р - некоторый полином, с помощью детерминированной машины Тьюринга, которая обращается к Мй как к подпрограмме нуль или более раз. [31]
Многие проблемы, касающиеся реализаций языков программирования, Возникают из-за того, что некоторые семантические особенности не являются полностью специфицированными в определениях языков Одним простым примером, типичным для императивных языков, является то, что переменные могут иметь или не иметь предварительно присвоенные значения при своем первом использовании. Вторым примером является то, что доступ к массиву со значением индекса, лежащим вне допустимых пределов, может не быть обнаружен во время выполнения, что дает непредсказуемые результаты, возможно включающие разрушение самой скомпилированной программы. Подобным образом мы были не в состоянии достичь строгого вычисления, используя интерпретатор, написанный на ленивом функциональном языке, поскольку мы определяли семантику нашего исходного языка в терминах другого функционального языка Хотя интерпретатор, очевидно, дает точное определение семантики языка, это определение зависит также от семантики второго языка, используемого для реализации. [32]
Подводя итог, можно сказать, что для языка, подобного Алголу, символ связывается с некоторым множеством операций сложения во время определения языка, операции сложения определяются во время реализации языка, каждое употребление в программе символа связывается с операцией сложения во время трансляции, и конкретное значение каждой операции сложения определяется только во время выполнения программы. Подобная система связываний характерна для многих языков программирования. Отметим, однако, что возможны также многие другие связывания и времена связываний. [33]
Таким образом, если реализация языка программирования допускает внутренний недетерминизм процессов, обеспечивая их однозначность и непрерывность, то денотационная семантика, являющаяся частью определения языка, точно специфицирует, что является результатом вычисления. [34]
Пользователь современной ЭВМ сталкивается в большим количеством языков, в числе которых машинные языки, языки высокого уровня, которые должны транслироваться, языки для выражения процесса трансляции, а также языки для определения языков. Все эти языки искусственные, они ограничены формами высказывания, изобретенными кем-то. Возникает вопрос: для чего нужно было создавать так много искусственных языков, если существуют общеупотребительные естественные языки. Почему пользователям ЭВМ необходима следующая запись. [35]
Определим язык как множество. Это определение языка может показаться необычным, однако оно полезно, потому что для языков, определенных как множества, действителен ряд отношений и операций и этот фактор имеет решающее значение. [36]
Функции гэгут давать побочные эффекты, влияющие на результат вычисления выражения. В определении языка Фортран явно указывается, что подобного рода побочные эффекты не допускаются и что в любой реализации языка разрешается в целях оптимизации изменять порядок вычисления выражения при условии, конечно, что его древовидная структура, определяемая правилами приоритета и скобками, не будет нарушена. К сожалению, нет способов предусмотреть побочные эффекты, которые могут возникнуть во время вычисления, поскольку внешние функции компилируются отдельно. Ошибки, которые могут возникнуть из-за побочных эффектов, придется искать самому программисту. [37]
Однако, как мы видели, не вполне ясно, как определить язык для моделей параллельных вычислений. Исследования в области определения языков сетей Петри привели к по меньшей мере 12 различным определениям языков, большинство из них, очевидно, различны. Различия в этих языках могут привести к различиям в соотношениях эквивалентности и включения между моделями. С другой стороны, если различия между моделями действительно существенны, то они могут быть не чувствительны к ( незначительным) изменениям в определениях эквивалентности исключения. Таким образом, подоб-ность результатов, полученных [5] - и [240], весьма важна из-за того, что в этих работах использовались различные определения эквивалентности и включения. [38]
Мы будем полагать, что каждый конкретный язык логики предикатов содержит все логические символы. Таким образом, для определения языка достаточно описать его специальные символы. [39]
На основе введенных выше определений языков разного типа для сетей Петри и помеченных сетей можно образовать различные классы языков сетей Петри, из которых выделим следующие. [40]
Части компилятора анализируют исходную программу литера за литерой для нахождения синтаксических классов, соответствую-цих элементам исходных предложений, и распознают затем основные синтаксические конструкции, выполняя эти действия с помощью строгих правил. Эти правила лежат в основе определения языка программирования, на котором написана программа. Поэтому прежг де чем перейти к описанию частей компиляторов, реализующих лексический и синтаксический анализ, мы рассмотрим схему классификации различных языков. [41]
В некотором смысле Модула-2 является не просто набором языковых правил, а расширяемым множеством языковых средств. Например, хотя ввод-вывод не является частью определения языка, для выполнения этой существенной функции используются библиотечные функции, такие как WriteString на распечатке 1.1. В настоящей книге приводится как официальный язык Вирта, так и его окружение. Мы будем отмечать, что хотя язык будет оставаться одним и тем же, те, кто реализует Модулу-2, могут по-разному реализовать это окружение. [42]
Два из этих случаев относительно просты. Смысл литералов и символов примитивных операций обычно фиксируется при определении Языка. Таким образом, обозначает ли сложение и что обозначает 10: десять ( в десятичной записи), восемь ( в восьмеричной записи) или два ( в двоичной записи) - всем этим программист не управляет. Встречаются и исключения, например функция OPSYN в языке Снобол 4 позволяет программисту переопределять символы примитивных операций. Однако эти случаи сравнительно редки, и они добавляют сравнительно мало новых понятий. Главный интерес для нас представляют оставшиеся случаи простых переменных, имен структур данных, имен подпрограмм, меток инструкций и формальных параметров. Синтаксис таких имен различен в разных языках и в разных классах одного языка. Мы будем употреблять здесь общий термин идентификатор для простого имени любого из этих типов. [43]
Третьим классом языков сетей Петри является класс языков сетей Петри Г - типа. Эти языки определяются множеством заключительных состояний, используемым в определении языков L-типа, и множеством ( не обязательно конечным) терминальных состояний. Таким образом, класс языков сетей Петри Г - типа задается следующим образом. [44]
Структуры, управляющие последовательностью действий, могут быть как неявными, так и явными. Неявными ( подразумеваемыми по умолчанию) называются структуры, которые по определению языка, действуют во всех случаях, когда программист не изменяет их посредством какой-нибудь явной структуры. Например, в большинстве языков определяется, что физическая последовательность инструкций в программе управляет последовательностью выполнения инструкций, если она не изменяется с помощью инструкций явного управления последовательностью действий. Обычно языки определяют также иерархию операций внутри выражения, которая управляет последовательностью выполнения операций в случае отсутствия скобок. Явные структуры управления последовательностью действий - это те структуры, которые программист может использовать по своему желанию для изменения подразумеваемой последовательности операций, определяемой языком. К ним относятся, например, скобки в выражениях а также инструкции перехода ( goto) и метки. [45]