Распознаватель

Cтраница 1

Распознаватель решает задачу разбора. В процессе синтаксического анализа распознаватель использует матрицу предшествования ( или функции предшествования) и таблицу порождающих правил грамматики входного языка. Каждая запись этой таблицы содержит одно из порождающих правил и ( для некоторых правил) имя семантической подпрограммы, которую нужно выполнить, когда это правило применяется для редукции. [1]

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

Распознаватель состоит из двух блоков. [3]

Формат правил подстановки Флойда. [4]

Распознаватель использует таблицу правил подстановки, записанных в формате рис. 5.27, и стек, содержащий уже рассмотренную и быть может частично редуцированную часть приводимой строки. Как и все ранее рассмотренные распознаватели, распознаватель работает слева направо. При несовпадении хотя бы одного символа применяется следующее по порядку правило. [5]

Распознаватель, описанный правилами подстановки, нетрудно переписать а виде набора синтаксических подпрограмм. Например, алгоритм распознавателя ( транслятора для перевода в обратную польскую запись), заданный таблицей 5.26, можно записать в виде пяти подпрограмм с именами ПО, ВО-МО-ТО, Ml, Т1 и В1, в которые включены соответствующие семантические подпрограммы ОШИБКА 1, СП1, СП2, СПЗ и ВЫХОД. [6]

Распознаватели на этом рисунке изображены в виде кружков, а операторы - в виде прямоугольников. Оператор ху - - означает подстановку вместо первого вхождения слова ху пустого слова. [7]

Граф переходов машины Тьюринга. [8]

Распознаватели служат для распознавания наличия тех или иных свойств перерабатываемой информации и для изменения, в зависимости от результатов распознавания, последовательности выполнения операторов. Для указания набора операторов и порядка их следования будем использовать блок-схемы, представляющие собой конечное множество соединенных между собой стрелками прямоугольников ( или других геометрических фигур), называемых узлами блок-схемы. Каждому узлу, кроме двух особых узлов, назьшаемых входным и выходным, поставлен в. Из каждого операторного узла, а также из входного узла выходит точно по одной стрелке; из каждого распознавательного - точно по две стрелки; из выходного узла не выходит ни одной стрелки. Число стрелок, входящих в узел, может быть любым. [9]

Распознаватель ПСС проверяет правила в установленном порядке. Если соответствие найдено, то для того, чтобы отличить это правило от последующих, следует проверить только достаточное количество контекста. Количество требуемого контекста определяется посредством проверки всех пар внутри группы. Для каждой пары: а) правые части равны; б) правая часть второго компонента пары является собственно хвостом правой части первого компонента или в) правая часть второго компонента не является хвостом правой части первого компонента. [10]

Очень простой распознаватель разработал Лидин в Гарвардском университете в 1967 г.; написанный первоначально для ЭВМ DEC PDP-1, позднее он был реализован на ЭВМ ТХ-2 [ 60 и на ЭВМ PDP-10. Лидин использует тот же метод выделения признаков, что и Тейтелмен, но у него словарь организован гораздо компактнее. Признаки каждого штриха упакованы в шестнадцати разрядах данных. [11]

Распознаватель символов Лидина производит обработку штрихов, вычерченных пользователем на кодирующем планшете графического ввода, и решает, какой символ изображают эти штрихи. Соответствие между символами и совокупностями штрихов устанавливается в процессе обучения: пользователь чертит штрихи, изображающие символ, и имеет возможность сообщить распознавателю, какой символ представлен этими штрихами. По новой информации распознаватель уточняет хранящуюся в памяти информацию для данной совокупности штрихов. [12]

Описанный левосторонний распознаватель неприменим, если грамматика леворекурсивна. [13]

Распознавателям соответствуют команды условного перехода, в которых указывается условие и адрес перехода. Если полученный в результате выполнения предыдущих команд результат удовлетворяет заданным в команде условного перехода условиям, то выполняется переход по заданному в команде адресу. [14]

Некоторые распознаватели снабжаются для этой цели стандартным набором выводимых символов. [15]

Страницы: 1 2 3 4