Cтраница 2
В реализации Снобола 4, описанной в этой главе, цепочки вносятся в центральную таблицу в момент их создания. Цепочки без ассоциаций могли бы храниться во временной памяти лишь до тех пор, пока они не станут мусором и их можно будет уничтожить, Укажите достоинства и недостатки этого метода. [16]
Неоднородные массивы Снобола 4 создаются динамически примитивной операцией ( функцией) ARRAY, которую можно вызвать в любой момент выполнения программы. Типы элементов массива могут меняться в ходе работы с ним, но размер массива не может быть изменен после его создания. Фиксированный размер допускает представление массива в виде последовательного блока памяти с присоединенным к нему дескриптором. Каждый элемент этого блока содержит указатель на значение элемента массива, за исключением тех случаев, когда значением является число, которое обычно записывается прямо в элемент блока. Массивы в языке Снобол 4 не имеют имени; вместо этого массив изображается указателем на блок памяти, содержащий дескриптор и значения. [17]
Выражения в Сноболе 4 порождают значения, которые яв-ляются либо цепочками литер, либо числами, либо образцами. Для построения выражений используется смесь бинарных инфиксных операций, польских префиксных операций и обычных математических префиксных операций. [18]
Полное описание языка Снобол 4 можно найти в учебнике Грисволда и др. [1971] 1) - Упрощенный курс Грисволда и Грис-волд [1973] дает более элементарное представление о языке. [19]
Другой язык - снобол - применяется в основном для машинного анализа текстов, написанных на естественных языках. В нем основным понятием является строка - произвольная последовательность букв, цифр и других знаков. Главная операция - это поиск в строке части строки, построенной по заданному образу, и замена этой части другой строкой. Как образ, так и заменяющие его строки составляются из отдельных элементов простого вида. Исход поиска определяет последовательность дальнейших действий. Язык снобол очень прост для изучения. [20]
Другой язык - снобол - применяется в основном для машинного анализа текстов, написанных на естественных языках. В нем основным понятием, является строка - произвольная последовательность букв, цифр и других знаков. [21]
Другой язык - Снобол - применяется в основном для машинного анализа текстов, написанных на естественных языках. В нем основным понятием является строка - произвольная последовательность букв, цифр и других знаков. [22]
Таблицы в языке Снобол 4 - это неоднородные линейные массивы переменного размера, для доступа к которым в качестве индексов могут использоваться не только целые числа, но и произвольные цепочки. Таким образом, таблицы представляют собой некую разновидность списка свойств. Каждый элемент таблицы состоит из индекса, являющегося указателем на цепочку в центральной таблице цепочек, и значения, которое является числом или указателем на цепочку, массив или иной элемент данных. Для создания таблиц используется примитивная функция TABLE, аргументы которой определяют начальный размер таблицы и величину приращения. [23]
В обычной реализации Снобола 4 программы транслируются в выполняемую форму, которая декодируется и выполняется программой-интерпретатором. Синтаксическая структура программ на языке Снобол 4 делает эту трансляцию относительно простой. Поскольку в языке отсутствуют ограни чители подпрограмм, декларации и структурные инструкции, каждая инструкция программы может быть странслирована без учета контекста, в котором она встречается. Поэтому можно транслировать строки программы последовательно и независимо одна от другой. Относительно позднее время связывания большинства элементов инструкций Снобола также упрощает трансляцию, поскольку во время трансляции очень мало известно об интерпретации инструкции. Таким образом, процесс трансляции сводится к выполнению простых синтаксических проверок и преобразованию каждой инструкции в блок выполняемых кодов, который в значительной степени представляет собой результат простой перекодировки исходной программы в форму, несколько более удобную для выполнения. В обычной реализации Снобола 4 эти блоки кодов имеют вид последовательности префиксных инструкций, каждая из которых состоит из символа операции и списка операндов. Операнды сами могут быть префиксными ин - j струкциями, подлежащими вычислению, так что вся программа напоминает древовидную Структуру ИЗ операций й операндов. [24]
Динамическая структура реализации Снобола 4 усложняется тем, что язык допускает сильную динамическую изменчивость. Необходим большой объем программного моделирования независимо от того, что взято за основу реализации - программный интерпретатор с простым транслятором или аппаратный интерпретатор с компилятором. Система, основанная на интерпретации, наиболее проста, и поэтому именно она рассматривается в настоящей главе. [25]
Обычно все операции Снобола 4 должны моделироваться программно. Даже арифметические операции, например сложение, нельзя прямо транслировать в эквивалентные машинные команды, поскольку при выполнении программы, прежде чем выполнить собственно сложение числовых операндов, необходимо проверить типы их дескрипторов. Поэтому, хотя в конечном счете оператор сложения в Сноболе 4 и использует аппаратную команду сложения двух чисел, существенную роль в его выполнении играет программное моделирование. Многие примитивные операции, такие, например, как конкатенация и сопоставление с образцом, настолько отличаются от обычных аппаратных операций, что трансляция их в эквивалентные последовательности машинных команд повлекла бы за собой сотни или даже тысячи команд. Именно в таких случаях целесообразно применять программное моделирование. [26]
Различие между реализацией Снобола 4, основанной почти полностью на программном моделировании, и реализацией Фортрана, базирующейся на прямое использование аппаратуры, очевидно. [27]
В большинстве реализаций Снобола 4 множество цепочек литер, существующих в любой момент выполнения программы, хранится в центральной таблице цепочек. Эта таблица организована как хеш-таблица, в которой каждая позиция является указателем на связанный список группы. Чтобы проверить, принадлежит ли множеству данная цепочка X, применяется схема двойного хеширования, X хешируется дважды: для получения хеш-адреса, используемого как индекс в центральной таблице, задающий указатель на соответствующую группу, и для получения порядкового номера в группе. Каждый элемент в списке группы состоит из порядкового номера в группе и указателя на цепочку. Элементы данной группы упорядочены по порядковому номеру. Для того, чтобы определить, хранится ли X в группе, определяемой хеш-адресом X, порядковый номер X последовательно сравнивается с номерами в списке группы до тех пор, пока не произойдет совпадение или пока не будет обнаружен порядковый номер, больший чем у X В последнем случае X немедленно включается в список, в первом требуется политерное сравнение X со всеми цепочками в группе, имеющими тот же самый порядковый номер. Запрограммируйте эту схему двойного хеширования в предположении, что цепочки хранятся в последовательных блоках и имеют дескрипторы, определяющие их длину. Желательно, чтобы в запрограммированной функции в качестве входной информации использовался указатель на некоторую цепочку и чтобы функция, проверяя наличие цепочки в таблице, включала цепочку в таблицу, если ее там не оказалось, возвращала адрес прежней позиции, если цепочка уже была в таблице, или адрес новой позиции, если ее там до этого не было. [28]
Главной примитивной операцией Снобола 4 является операция сопоставления с образцом. Есть много примитивов для создания образцов. Имеются также основные арифметические, логические примитивы и примитивы отношений. Операции создания структур данных исключительно гибки. [29]
Наиболее известная реализация Снобола 4 ( макрореализация, описанная Грисволдом [1972]) основана на моделировании виртуальной Снобол-машины полностью программными средствами. Снобол-программы транслируются только во внутреннюю выполняемую цепочку команд в префиксной польской записи, которая декодируется и выполняется программой-интерпретатором. Организация памяти во время выполнения базируется на центральной таблице цепочек литер, которая в любой момент содержит по одному элементу для каждой существующей цепочки, включая имена переменных, метки инструкций и другие идентификаторы наряду с цепочками, используемыми в качестве значений переменных и элементов массивов. Когда во время выполнения создается цепочка литер, она заносится в эту таблицу, если такой цепочки еще не существует. [30]