В таком случае входная цепочка является допущенной.

(q_0, α, Z₀) ˫* ( q_f, λ, Z_f)

q₀ – начальное состояние УУ

α - цепочка символов

Z₀ – начальная внешняя память

q_f - заключительное состояние

λ – пустое значение, значит УУ прочитал полностью всю цепочку

Если это получится, то цепочка будет считаться распознанной

Язык, определяемый распознавателем – это множество всех цепочек, которые допускает этот распознаватель.

2.6 Задание языка регулярным выражением V+ α β → ∈ λ Ɐ

Регулярные выражений используют для порождения бесконечных цепочек языка.

Регулярное множество и регулярное выражение для некоторого алфавита V определяется рекурсивно следующим образом:

0 – регулярное выражение, обозначает пустое регулярное множество;

λ – регулярное выражение, обозначает регулярное множество { λ };

Ɐ a ∈ V a – регулярное выражение, обозначает регулярное множество {a};

если p и q – произвольные регулярные выражения, обозначающие

регулярные множества P и Q, то p+q, pq, p* – регулярные выражения, обозначающие соответственно регулярные множества P∪Q, PQ, P*;  ничто другое регулярным выражением и регулярным множеством не является.

Иными словами, регулярные множества – это цепочки символов над заданным алфавитом, построенные с использованием операций объединения, конкатенации и замыкания.

При записи регулярных выражений используются круглые скобки, как для обычных арифметических выражений. При отсутствии скобок операции выполняются слева направо с учетом приоритета. Наивысшим приоритетом обладает операция итерации ( обозначается как * - действия повторяются многократно) , затем конкатенации ( «знак умножения» - объединение множест), потом + (выбор «или»).

Все регулярные языки представляют собой регулярные множества. Два регулярных выражения α и β эквивалентны: α = β, если они обозначают одно и то же множество.

Например, α1 = (0+1)*, α2 = (0*1*)*. α1 = α2

П. (0+1)*

L = { λ, 0, 1, 00, 01, 10, 11…..}

G ( {0,1}, {S}, P, S )

S → 0S | 1S | λ

2.7 Построение КА для языка, заданного регулярным выражением.

Конечный автомат – это простейший распознаватель без вспомогательной памяти. Он является эффективным способом определения регулярных языков.

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

Работа автомата представляет собой последовательность тактов (или шагов). На каждом шаге работы автомат может остаться в том же состоянии или перейти в другое. Поведение автомата на каждом такте определяется функцией переходов, которая зависит от текущего состояния и входного символа. Если функция переходов допускает несколько переходов в следующее состояние, то КА может перейти в любое из них, и такой КА является недетерминированным (НКА).

В начале работы автомат находится в начальном состоянии q0. Работа

автомата продолжается до тех пор, пока на его вход поступают символы

---

входной цепочки. V+ α β → ∈ λ Ɐ

Мгновенным описанием (МО), или конфигурацией автомата M называется пара (q, w), где q ∈ Q – состояние УУ, w ∈ V* – неиспользованная часть входной цепочки (т.е. символ, обозреваемый считывающей головкой и все символы справа от него). Тогда пара (q0, w) называется начальной конфигурацией для цепочки w, а конфигурация (q, λ) является заключительной, или допускающей,

если q ∈ F (т.е. q – одно из заключительных состояний автомата).

Цепочка w допускается автоматом M, если (q0,w)├─*(q, λ) для некоторого q ∈ F, т.е. получив на вход эту цепочку, автомат из начальной конфигурации может перейти в заключительную.

δ (q,a) = {p} Вариант 1

	V	a
Q
q		p

Вариант 2

Пример.

M ( {q₀}, {0,1}, δ, q₀, {q₀} )

S → 0S | 1S | λ

Например, цепочку из двух символов (q₀, 10)├ (q₀, 0)├ (q₀, λ) . Конфигурация является заключительной, цепочка прочитана. КА её допустит

(q₀, 20)├ stop, КА символа (2) такого не знает, перехода не совершит, цепочку не прочитает

10 ∈ L (m)

20 ∉ L (m), L(m) – язык задаваемого автомата

2.8 Преобразование грамматик и цель преобразований.

В общем случае для КС-грамматик невозможно проверить их однозначность и эквивалентность. Но для конкретных случаев бывает можно и нужно привести заданную грамматику к некоторому определённому виду таким образом, чтобы получить грамматику,

эквивалентную исходной. Заранее определённый вид зачастую позволяет упростить работу с языком и построение распознавателей для него. Итак, преобразования грамматик могут преследовать две цели:

1) упрощение правил грамматики;

2) облегчение создания распознавателя языка.

В теории языков программирования основой является создание компилятора для языка,

поэтому главной становится вторая цель. Следовательно, можно пренебречь упрощением правил (и даже смириться с некоторым их усложнением), если при этом удастся упростить построение распознавателя языка.

V+ α β → ∈ λ Ɐ ∪

Приведёнными (или грамматиками в каноническом виде) называются

грамматики, которые не содержат недостижимых и бесплодных символов,

циклов и пустых правил ( λ -правил).

Рассмотрим некоторую грамматику G(VT,VN,P,S) и дадим необходимые определения.

Нетерминальный символ A∈VN называется бесплодным (или бесполезным), если из него нельзя вывести ни одной цепочки терминальных символов, т.е. { α | A →* α, α ∈ VT*} = ø

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

Символ x ∈ (VT∪VN) называется недостижимым, если он не

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

---

λ -правилами, или правилами с пустой цепочкой, называются все правила грамматики вида A→ λ, A∈VN. Грамматика G называется грамматикой без λ -правил, если в ней нет правил вида (A→ λ), A∈VN, A ≠ S, и существует только одно правило (S→ λ) ∈P, если λ ∈L(G) и при этом S не встречается в правой части ни одного правила грамматики G. Для упрощения процесса построения распознавателя цепочек языка L(G) любую грамматику целесообразно привести к виду без λ -правил.

Циклом в грамматике G называется вывод вида A→*A, A∈VN.

Очевидно, что такой вывод бесполезен, поэтому в распознавателях КС-языков рекомендуется избегать возможности появления циклов.

Таким образом, для того чтобы преобразовать произвольную КС-грамматику к каноническому виду, необходимо выполнить следующие действия (причём именно в том порядке, каком они перечислены):

• удалить все бесплодные символы;

• удалить все недостижимые символы;

• удалить λ -правила;

• удалить цепные правила.

2.9 Определение LL(k)- грамматики и принципы построения распознавателей для этой грамматики.

Одним из таких подклассов КС-грамматик являются так называемые LL(k)- грамматики. Это самый большой “естественный” класс левоанализируемых грамматик.

Грамматика обладает свойством LL(k) (называется LL(k)- грамматикой) для k>0, если на каждом шаге вывода для однозначноговыбора очередной альтернативы автомату с магазинной памятью необходимо знать один верхний символ стека и рассмотреть k символов

входной цепочки справа от положения считывающей головки.

Существуют LL(1), LL(2), LL(3), … грамматики. Все они в совокупности образуют класс LL-грамматик. В этом обозначении (LL) первая L означает, что входная цепочка считывается в направлении слева направо, а вторая L – что выполняется левосторонний разбор. Число k показывает, сколько символов справа от считывающей головки нужно

рассмотреть для однозначного выбора альтернативы.

На каждом шаге разбора правло грамматики применяется к самому левому нетерминалу цепочки. Данный процесс соответствует построению дерева разбора цепочки сверху вниз

Всякая LL(k)-грамматика для любого k>0 является однозначной.

В основе распознавателя LL(k)- грамматик лежит левосторонний разбор строки языка

Для построения распознавателей LL(k)-грамматик используются два

специальных множества, определяемых следующим образом:

Очевидно, что, если имеется цепочка терминальных символов α ∈ VT*,

то FIRST(k, α) – это первые k символов этой цепочки.

2.10-2.11 Трансляторы, компиляторы, интерпретаторы. Общие схемы и их отличия.

Транслятор (в пер. с англ. - "переводчик") – это программа, принимающая на вход программу на одном языке и преобразующая её в программу на другом языке.. Как видно из определения, в работе транслятора всегда участвуют три программы:

1. Сам транслятор является программой

2. Исходными данными для работы транслятора служит текст входной про- граммы – некоторая последовательность предложений входного языка программирования. Обычно это символьный файл, но этот файл должен содержать текст программы, удовлетворяющий синтаксическим и семантическим требованиям входного языка. Кроме того, этот файл несет в себе некоторый смысл, определяемый семантикой входного языка.

---

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

Важным требованием в определении транслятора является эквивалентность входной и выходной программ. Эквивалентность двух программ означает совпадение их смысла с точки зрения семантики входного языка (для исходной программы) и семантики выходного языка (для результирующей программы). Без выполнения этого требования сам транслятор теряет всякий практический смысл.

Если исходная программа содержит хотя бы одну ошибку, то результатом работы транслятора будет сообщение об ошибке (как правило, с дополнительными пояснениями и указанием места ошибки в исходной программе).

Компилятор – это транслятор, который осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера. Таким образом, компилятор отличается от транслятора лишь тем, что его результирующая программа всегда должна быть написана на языке машинных кодов или на языке ассемблера. Результирующая

программа транслятора же, в общем случае, может быть написана на любом языке – возможен, например, транслятор программ с языка Pascal на язык С.

Результирующая программа компилятора называется «объектной программой» или «объектным кодом». Файл, в который она записана, обычно называется «объектным файлом».

Интерпретатор – это программа, которая воспринимает входную программу на исходном языке и выполняет ее.

В отличие от трансляторов интерпретаторы не порождают результирующую программу (и вообще какого-либо результирующего кода) – и в этом принципиальная разница между ними. Интерпретатор, так же как и транслятор, анализирует текст исходной программы. Однако он не порождает результирующей программы, а сразу же выполняет исходную в соответствии с ее смыслом, заданным семантикой входного языка. И компиляторы и интерпретаторы преобразуют исходный код в машинный код, только разными путями.Интерпретатор читает исходный код программы и выполняет его. Преобразование исходного кода в бинарный и выполенение выполняется построчно.Вот схема работы интерпретаторов:
[1]исходный код программы -> [2]интерпретатор -> [3]ОС -> [4]результатКомпиляторы же, полностью переобразовывают исходный код программы в бинарный (а не построчно, как в случае с интрепретаторами), который ОС может выполнять самостоятельно. То есть, для запуска программы иметь компилятор нет необходимости.Вот схема работы компилятора:
[1]исходный код программы -> [2]компилятор -> [3]объектный код -> [4]ОС -> [5]результатКак я уже говорил ранее, при использовании программы, 1-ый и 2-ой пункт этой схемы откидывается.Откомпилированные компилятором программы работают заметно быстрее, т.к. не требуется делать повторный анализ и преобразование исходного кода в код, понятный компьютеру.

---

2.12 Понятие прохода

Как уже было сказано, процесс компиляции программ состоит из нескольких фаз. В одном

случае компилятор просматривает текст исходной программы, сразу выполняет все фазы компиляции и получает результат – объектный код. В другом варианте он выполняет над исходным текстом только некоторые из фаз компиляции и получает не конечный результат, а набор некоторых промежуточных данных. Эти данные затем снова подвергаются обработке, причем этот процесс может повторяться несколько раз.

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

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

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

Однако сократить число проходов не всегда удается. Количество необходимых проходов определяется, прежде всего, грамматикой и семантическими правилами исходного языка. Чем сложнее грамматика языка и чем больше вариантов предполагают семантические правила – тем больше проходов будет выполнять компилятор. Например, именно поэтому обычно компиляторы с

языка Pascal работают быстрее, чем компиляторы с языка С – грамматика языка Pascal более проста, а семантические правила более жесткие.

Однопроходные компиляторы – редкость, они возможны только для очень простых языков. Реальные компиляторы выполняют, как правило, от двух до пяти проходов. Таким образом, реальные компиляторы являются многопроходными. Наиболее распространены двух- и трехпроходные компиляторы, например: первый проход – лексический анализ, второй – синтаксический разбор и семантический анализ, третий – генерация и оптимизация кода (варианты

---

Смотрите также файлы

• Рабочая тетрадь по теоретической механике 3.pdf

• Информационные технологии. Лекции.docx

• Инструктаж по технике безопасности на уроках информатики.docx

• Тема 1.1 Основные понятия теории множеств.docx

• ЧМ Контрольная работа 1.docx