Виды распознавателей для КС-языков

Существуют несложные преобразования КС-грамматик, выполнение которых гарантирует, что построенный на основе преобразованной грамматики МП-автомат можно будет промоделировать за конечное время на основе конечных вычислительных ресурсов. Описание сути и алгоритмов этих преобразований можно найти в [1, 3, 7]. Эти преобразования позволяют строить два основных типа простейших распознавателей:

• распознаватель с подбором альтернатив;
• распознаватель на основе алгоритма «сдвиг-свертка».

Работу распознавателя с подбором альтернатив можно неформально описать следующим образом: если на верхушке стека МП-автомата находится нетерминальный символ A, то его можно заменить на цепочку символов ? при условии, что в грамматике языка есть правило A ? ?, не сдвигая при этом считывающую головку автомата (этот шаг работы называется «подбор альтернативы»); если же на верхушке стека находится терминальный символ a, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передвинуть считывающую головку на одну позицию вправо (этот шаг работы называется «выброс»). Данный МП-автомат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида A ->?, тогда функция ?(q,?,A) будет содержать более одного следующего состояния — у МП-автомата будет несколько альтернатив.

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

Распознаватель с подбором альтернатив является нисходящим распознавателем: он читает входную цепочку символов слева направо и строит левосторонний вывод. Название «нисходящий» дано ему потому, что дерево вывода в этом случае следует строить сверху вниз, от корня к концевым вершинам («листьям»)1.

Принцип работы распознавателей с возвратом: нисходящий и распознаватель «сдвиг-свертка».

Работу распознавателя на основе алгоритма «сдвиг-свертка» можно описать так: если на верхушке стека МП-автомата находится цепочка символов ?, то ее можно заменить на нетерминальный символ A при условии, что в грамматике языка существует правило вида A ? ?, не сдвигая при этом считывающую головку автомата (этот шаг работы называется «свертка»); с другой стороны, если считывающая головка автомата обозревает некоторый символ входной цепочки a, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо (этот шаг работы называется «сдвиг» или «перенос»).

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

• что необходимо выполнять: сдвиг или свертку;
• если выполнять свертку, то какую цепочку ? выбрать для поиска правил (цепочка ? должна встречаться в правой части правил грамматики);
• какое правило выбрать для свертки, если окажется, что существует несколько правил вида A ? ? (несколько правил с одинаковой правой частью).

Для моделирования работы этого расширенного МП-автомата надо на каждом шаге запоминать все предпринятые действия, чтобы иметь возможность вернуться к уже сделанному шагу и выполнить эти же действия по-другому. Этот процесс должен повторяться до тех пор, пока не будут перебраны все возможные варианты.

Алгоритм рекурсивного спуска.

Алгоритм рекурсивного спуска -- это простейший способ разбора текста. При помощи него можно, особо не задумываясь, разобрать, например, арифметическое выражение. Основная идея заключается в том, чтобы разнести разбор разных операций (с разным приоритетом) по разным взаимно-рекурсивным функциям. Тогда, с точки зрения каждой из них, выражение представляет собой набор каких-то левых кусков текста, скреплённых знаками. Содержимое этих кусков функцию не волнует, так как его она разбирать не должна - этим займутся другие, более высокоприоритетные функции. Например, с точки зрения функции, разбирающей операции сложения и вычитания (очевидно, что они имеют равный приоритет), выражение выглядит так:

Это самое простое определение, которое, тем не менее, обладает одним существенным недостатком. Оно неверное. Причина проста: оно утверждает, что операции ( + ) и ( - ) правоассоциативны, однако это верно только по отношению к сложению. Совершенно очевидно, что вычитание следует рассматривать как левоассоциативную операцию. Любой нормальный человек скажет, что

Однако, следуя данному выше определению, получаем, что

Понятие транслятора, компилятора и интерпретатора.

Трансля́тор — программа или техническое средство, выполняющее трансляцию программы.

Трансляторы подразделяют

· Диалоговый. Обеспечивает использование языка программирования в режиме разделения времени (англ.).

· Синтаксически-ориентированный (синтаксически-управляемый). Получает на вход описание синтаксиса и семантики языка и текст на описанном языке, который и транслируется в соответствии с заданным описанием.

· Однопроходной. Формирует объектный модуль за один последовательный просмотр исходной программы.

· Многопроходной. Формирует объектный модуль за несколько просмотров исходной программы.

· Оптимизирующий. Выполняет оптимизацию кода в создаваемом объектном модуле.

· Тестовый. Набор макрокоманд языка ассемблера, позволяющих задавать различные отладочные процедуры в программах, составленных на языке ассемблера.

· Обратный. Для программы в машинном коде выдаёт эквивалентную программу на каком-либо языке программирования

Компиля́тор — программа или техническое средство, выполняющее компиляцию.^[1][2][3]

Компиляция — трансляция программы, составленной на исходном языке высокого уровня, в эквивалентную программу на низкоуровневом языке, близком машинному коду(абсолютный код, объектный модуль, иногда на язык ассемблера).^[2][3][4] Входной информацией для компилятора (исходный код) является описание алгоритма или программа напроблемно-ориентированном языке, а на выходе компилятора — эквивалентное описание алгоритма на машинно-ориентированном языке (объектный код).^[5]

Компилировать — проводить трансляцию машинной программы с проблемно-ориентированного языка на машинно-ориентированный язык.

Виды компиляции

· Пакетная. Компиляция нескольких исходных модулей в одном пункте задания.

· Построчная. То же, что и интерпретация.

· Условная. Компиляция, при которой транслируемый текст зависит от условий, заданных в исходной программе директивами компилятора. Так, в зависимости от значения некоторой константы, можно включать или выключать трансляцию части текста программы.

Интерпрета́тор — программа (разновидность транслятора) или аппаратное средство, выполняющее интерпретацию.^[1]

Интерпрета́ция — пооператорный (покомандный, построчный) анализ, обработка и тут же выполнение исходной программы или запроса (в отличие от компиляции, при которой программа транслируется без её выполнения)

Алгоритм работы простого интерпретатора

1. прочитать инструкцию;

2. проанализировать инструкцию и определить соответствующие действия;

3. выполнить соответствующие действия;

4. если не достигнуто условие завершения программы, прочитать следующую инструкцию и перейти к пункту 2.

Достоинства

· Бо́льшая переносимость интерпретируемых программ — программа будет работать на любой платформе, на которой есть соответствующий интерпретатор.

· Как правило, более совершенные и наглядные средства диагностики ошибок в исходных кодах.

· Упрощение отладки исходных кодов программ^{[источник не указан 573 дня]}.

· Меньшие размеры кода по сравнению с машинным кодом, полученным после обычных компиляторов.

Недостатки

· Интерпретируемая программа не может выполняться отдельно без программы-интерпретатора. Сам интерпретатор при этом может быть очень компактным.

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

· Практически отсутствует оптимизация кода, что приводит к дополнительным потерям в скорости работы интерпретируемых программ.

Не нашли, что искали? Воспользуйтесь поиском по сайту: