Теория языков программирования и методы трансляции

КУРСОВАЯ РАБОТА

Тема: «Формальные языки и грамматики»

Дисциплина: «Теория языков программирования и методы трансляции»

Введение

Глава 1. Формальные языки и грамматики

1.1 Языки и цепочки символов

1.1.1 Цепочки символов и операции над ними

1.1.2 Понятие языка. Способы задания языков

1.1.3 Особенности языков программирования

1.2 Определение грамматики

1.2.1 Понятие грамматики и формальное определение. Форма Бэкуса-Наура

1.2.2 Другие способы задания грамматик

1.3 Классификация языков и грамматик

1.3.1 Классификация грамматик по Хомскому

1.3.2 Классификация языков

1.4 Вывод и выводимость

1.4.1 Цепочки вывода. Сентенциальная форма

1.4.2 Дерево вывода

1.5 Распознаватели. Задача разбора

1.5.1 Общая схема распознавателя

1.5.2 Виды распознавателей и их классификация

1.5.3 Задача разбора Глава 2. Регулярные языки

2.1 Регулярные множества и регулярные выражения

2.1.1 Определение и свойства регулярных выражений

2.1.2 Уравнения с регулярными коэффициентами

2.2 Конечные автоматы и грамматики

2.2.1 Автоматные грамматики

2.2.2 Определение конечного автомата

2.3 Особенности регулярных языков

2.3.1 Способы задания регулярных языков

2.3.2 Свойства регулярных языков Глава 3. Описание программы Заключение Список используемой литературы

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

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

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

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

Глава 1. Формальные языки и грамматики

1.1 Языки и цепочки символов

1.1.1 Цепочки символов и операции над ними

Сначала дадим все необходимые определения и введем некоторые понятия.

Под алфавитом будем понимать непустое конечное множество символов.

Цепочка, или строка — это последовательность символов некоторого алфавита, при этом символы в строке могут повторяться. Для цепочки важен ее состав, порядок символов и их количество.

Длиной цепочки является количество символов в ней. Например, цепочка x = 'abcab' имеет длину |x| = 5.

Две цепочки и совпадают (равны): =, если они имеют один и тот же состав и порядок символов и их количество.

Цепочка, не содержащая символов, называется пустой цепочкой, обозначается через или .

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

Над цепочками можно выделить следующие операции:

Конкатенацией, или сцеплением (сложением) цепочек, называется строка, полученная их объединением, например: x = 'abcab', y = 'cde', тогда конкатенация цепочек x и y будет иметь вид z = x· y = 'abcabcde'. Свойства: Так как в цепочке важен порядок символов, очевидно, что операция сложения не коммутативна, т. е. в общем случае ,. Конкатенация ассоциативна, т. е., () = ().

Обращение цепочки x — это запись ее символов в обратном порядке, обозначается x^R. Например, для цепочки x = 'abcab' ее обращение x^R = 'bacba'. Свойство операции обращения:, ()^R= ^RR.

Итерация цепочки n раз — это ее сцепление (повторение) n раз, обозначается ⁿ.

Для пустой цепочки справедливы следующие равенства:

|| = 0;

: = = ;

^R = ;

n0: ⁿ = ;

: ⁰ = .

1.1.2 Понятие языка. Способы задания языков

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

Цепочка символов является цепочкой над алфавитом У: (У), если в нее входят только символы этого алфавита.

Если — некоторый алфавит, то:

⁺ — множество всех цепочек над алфавитом без .

* - множество всех цепочек над алфавитом, включая .

Языком L над алфавитом У: L (У) — называют некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над этим алфавитом. Множество цепочек языка не обязано быть конечным и каждая цепочка может иметь сколь угодно большую длину.

Для любого языка L (У) справедливо L (У) У*.

Язык L (У) включает в себя язык L (У): L (У) L (У), если L (У) L (У).

Два языка совпадают (эквивалентны): L (У) = L (У), если L (У) L (У) и L (У) L (У).

Конкатенацией (объединением) языков L₁ и L₂ называют язык L, состоящий из всевозможных сцеплений цепочек языков L₁ и L₂: L = L₁· L₂ = x· y .

Замыкание Клини, или итерация языка L, обозначается L* и определяется рекурсивно: 1) L⁰ = {л}, 2) Lⁿ = L· L^n-1 для n > 0, 3) L* = Lⁿ для всех n 0.

L⁺ = L*{л}.

Язык L обладает суффиксным (префиксным) свойством, если никакая цепочка языка не является суффиксом (префиксом) другой цепочки.

Язык состоит из бесконечного множества цепочек символов над некоторым алфавитом, или слов. Но не любая цепочка символов над этим алфавитом принадлежит языку, т.к. существуют правила построения допустимых цепочек для каждого конкретного языка. Указать эти правила — значит задать язык. Существуют три основных способа задания языка:

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

Указание способа порождения цепочек языка (задание грамматики языка) — применение т.н. генератора.

Задание метода распознавания цепочек языка — использование распознавателя.

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

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

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

Семантика языка — это раздел, определяющий значение предложений языка. Семантика определяет «содержание языка», т. е. задает значение всех допустимых цепочек языка. Для большинства языков семантика определяется неформальными методами.

Лексика — это словарный запас языка. Лексическая единица (лексема) — конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций. Т. е. лексема может содержать в себе только элементарные символы алфавита и не может содержать других лексем. Например, лексемами русского языка являются слова, а пробелы и знаки препинания представляют собой разделители. Лексемами алгебры являются числа, знаки математических операций, обозначения функций и т. п. В языках программирования лексемы — это ключевые слова, идентификаторы, константы, метки, знаки операций.

1.1.3 Особенности языков программирования

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

Для задания языка программирования необходимо решить три основных вопроса:

определить множество допустимых символов языка;

определить множество правильных программ языка;

задать смысл каждой правильной программы.

С помощью теории формальных языков удается решить (полностью или частично) только первые два вопроса.

Первый вопрос решается легко. Алфавит языка и представляет собой множество его допустимых символов. Для языков программирования это, как правило, тот набор символов, который можно ввести с клавиатуры.

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

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

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

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

2. использовать для проверки смысла некоторую «идеальную машину», которая предназначена для проверки программ, написанных на данном языке.

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

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

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

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

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

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

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

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

1.2 Определение грамматики

1.2.1 Понятие грамматики и формальное определение. Форма Бэкуса-Наура

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

Формальное описание грамматики построено на основе системы правил, или продукций. Правило представляет собой упорядоченную пару цепочек символов (,), которую обычно записывают как и читают как «порождает «.

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

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

Формально грамматика G определяется как четверка G (VT, VN, P, S), где VT — множество терминальных символов (символы алфавита);

VN — множество нетерминальных символов (слова, понятия, конструкции языка); VTVN=; V=VTVN — полный алфавит грамматики G;

P — множество правил вида, где V⁺, V*;

SVN — начальный (целевой) символ грамматики G, с которого начинается процесс порождения цепочек языка.

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

Во множестве правил грамматики может быть несколько правил, имеющих одинаковые левые части, например: ₁, ₂, …, _n. Тогда эти правила записываются в одну строку: ₁₂…_n.

Рассмотренная форма записи правил грамматики называется формой Бэкуса-Наура. В ней, как правило, нетерминальные символы заключаются в угловые скобки <>.

Пример: грамматика порождения целых десятичных чисел со знаком.

G ({0,1,2,3,4,5,6,7,8,9,-,+}, {<�число>,<�чс>,<�цифра>}, P, <�число>).

P:

<�число> <�чс>+<�чс>-<�чс>

<�чс> <�цифра><�чс><�цифра>

<�цифра> 123 456 789

В данной грамматике множество нетерминальных символов содержит 3 элемента (символы <�число>,<�чс>,<�цифра>), множество терминальных символов — 12 элементов (10 цифр и два знака), множество P — 15 правил, записанных в три строки. Начальный символ грамматики — <�число>.

В грамматике можно изменить названия нетерминальных символов без какого-то изменения языка, заданного ею. Терминальные символы изменять нельзя! Они соответствуют алфавиту задаваемого языка.

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

G ({0,1,2,3,4,5,6,7,8,9,-,+}, {S, T, F}, P, S).

P:

S T+T-T

T FTF

F 123 456 789.

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

В грамматиках G и G явная рекурсия присутствует во второй части второго правила: <�чс> <�чс><�цифра>, T TF.

Чтобы рекурсия не была бесконечной, участвующий в ней нетерминальный символ должен обязательно присутствовать в левой части другого правила, где он определяется, минуя самого себя. В грамматиках G и G это достигается в первой части второго правила: <�чс> <�цифра>, T F.

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

2.2 Другие способы задания грамматик

Кроме формы Бэкуса-Наура, существуют и другие способы записи грамматик, а именно запись с использованием метасимволов и графическое представление.

Запись грамматик с использованием метасимволов предполагает, что в строке правила могут присутствовать особые символы — т.н. метасимволы, которые трактуются специальным образом. Обычно в этой роли используются () круглые, [] квадратные и {} фигурные скобки, а также «,» запятые и «» ««кавычки. Они имеют следующий смысл:

() — в данном месте правила может стоять только одна из всех перечисленных внутри них цепочек;

[ ] - указанная внутри них цепочка может быть в правиле грамматики один раз или ни одного раза;

{} - указанная внутри них цепочка может встречаться любое количество раз (в том числе сколь угодно много или ни одного);

 — разделяет цепочки символов внутри круглых скобок;

" «- используются в том случае, когда какой-то из метасимволов нужно включить в цепочку символов языка.

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

<�число> [(+, -)] <�цифра>{<�цифра>}

<�цифра> (0,1,2,3,4,5,6,7,8,9)

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

Грамматика стала более понятной, кроме того, удалось полностью избежать рекурсии, заменив ее символом итерации {}. Эта форма наиболее употребима для одного из типов грамматик, а именно — для регулярных грамматик, которые мы рассмотрим ниже.

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

В такой форме записи каждому нетерминальному символу соответствует диаграмма, построенная в виде направленного графа. Граф имеет следующие типы вершин:

точка входа (не обозначена — из нее начинается входная дуга графа);

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

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

узловая точка — обозначена закрашенным кружком;

точка выхода — в нее входит выходная дуга графа.

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

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

Описанная ранее грамматика G порождения целых десятичных чисел со знаком в графическом виде будет выглядеть следующим образом:

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

1.3 Классификация языков и грамматик

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

1.3.1 Классификация грамматик по Хомскому

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

Пусть грамматика обозначена как G(VT,VN,P,S), V=VTVN. В соответствии с иерархией Хомского выделяют 4 типа грамматик.

Тип 0 — грамматики с фразовой структурой, или без ограничений

На структуру их правил не накладывается никаких ограничений, т. е. правила имеют вид:, где V⁺, V*. Это самый общий тип грамматик. Грамматики, которые относятся только к этому и не могут быть отнесены ни к какому другому типу, являются самыми сложными по структуре.

Тип 1 — Контекстно-зависимые (КЗ) и неукорачивающие грамматики

К этому типу относятся два основных класса грамматик.

Контекстно-зависимые грамматики имеют правила вида ₁A_{2 12}, где ₁,₂V^*, AVN, V⁺.

Неукорачивающие грамматики имеют правила вида, где, V⁺, .

В КЗ-грамматиках при построении предложений заданного языка один и тот же нетерминальный символ может быть заменен различными терминальными цепочками в зависимости от контекста, в котором он встречается. Цепочки ₁ и ₂ в правилах обозначают контекст: ₁ — левый контекст, ₂ — правый контекст. В общем случае они могут быть пустыми.

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

Эти два класса грамматик эквивалентны.

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

Тип 2 — Контекстно-свободные (КС) грамматики

Контекстно-свободные (КС) грамматики имеют правила вида A, где AVN, V⁺. В правой части у них стоит всегда хотя бы один символ.

Такие грамматики еще называют неукорачивающими контекстно-свободными (НКС) грамматиками. Существует почти эквивалентный им класс укорачивающих контекстно-свободных (УКС) грамматик, отличие которого в том, что он допускает пустую цепочку, т. е. правила имеют вид A, где AVN, V^*. В дальнейшем, если возможность наличия в языке пустой цепочки не имеет принципиального значения, будем говорить просто о КС-грамматиках.

КС-грамматики широко используются при описании синтаксических конструкций языков программирования.

Тип 3 — Регулярные грамматики

К этому типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.

Леволинейные грамматики могут иметь правила двух видов: A B, или A, где A, BVN, VT⁺.

Праволинейные грамматики имеют правила тоже двух видов: A B, или A, где A, BVN, VT⁺.

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

Из определения типов видно, что любая регулярная грамматика является также КС-грамматикой, или любая грамматика может быть отнесена к типу 0. В то же время существуют УКС-грамматики, которые не относятся к типу 1, поскольку могут содержать правила вида A, недопустимые в этом типе. В общем, сложность грамматики обратно пропорциональна тому максимально возможному номеру типа, к которому может быть отнесена эта грамматика. Самыми простыми являются грамматики типа 3, самыми сложными — типа 0.

1.3.2 Классификация языков

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

Тип 0 — языки с фразовой структурой

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

Практически все естественные языки относятся к этому типу. Одно и то же слово в естественном языке может иметь различный смысл в зависимости от контекста и играть различную роль в предложении. Мы такие языки далее рассматривать не будем.

Тип 1 — контекстно-зависимые (КЗ) языки

В общем случае время на распознавание языка типа 1 экспоненциально зависит от длины исходной цепочки символов.

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

Однако языки программирования имеют более простую структуру, поэтому в компиляторах КЗ-языки не применяются.

Тип 2 — контекстно-свободные (КС) языки

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

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

Тип 3 — регулярные языки

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

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

1.4 Вывод и выводимость

1.4.1 Цепочки вывода. Сентенциальная форма

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

Цепочка ₁₂ называется непосредственно выводимой из цепочки ₁₂ в грамматике G(VT,VN,P,S), V=VTVN, ₁,₂V^*, V⁺, если в грамматике G существует правило P. Непосредственная выводимость обозначается. Т. е. цепочка выводима из цепочки в том случае, если можно взять несколько символов в цепочке, заменить их на другие символы согласно правилу грамматики и получить при этом цепочку. В формальном определении любая из цепочек ₁, ₂ (или обе) может быть пустой. В пределе вся цепочка может быть заменена на цепочку, тогда в грамматике должно существовать правило P.

Цепочка называется выводимой из цепочки — обозначается *, если выполняется одно из двух следующих условий:

непосредственно выводима из: ;

такая, что: выводима из и непосредственно выводима из (* и).

Это рекурсивное определение выводимости цепочки. Т. е. выводима из цепочки, если она либо непосредственно выводима, либо можно построить последовательность непосредственно выводимых цепочек от к: _{1 2} … _{i i+1} … _n. Такая последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода, а каждый переход — шагом вывода. Если непосредственно выводима из (), то имеется всего один шаг вывода.

Если вывод содержит два или более шагов, то говорят, что нетривиально выводима из: ⁺. Если количество шагов вывода известно, его можно указать у знака выводимости цепочек: ⁴ означает, что выводима из-за 4 шага. Запись ⁰ означает, что цепочки равны.

Целесообразно при записи цепочки вывода на каждом шаге над знаком выводимости указывать номер правила, согласно которому выполнен этот шаг.

Грамматика, в которой для любой цепочки порождаемого языка существует единственная цепочка вывода, называется однозначной.

Вывод называется законченным, если из полученной цепочки нельзя сделать более ни одного шага, т. е. если полученная цепочка пустая или содержит только терминальные символы грамматики: VT^*. Цепочка, полученная в результате законченного вывода, называется конечной цепочкой вывода.

Цепочка символов V^* называется сентенциальной формой грамматики G(VT,VN,P,S), если она выводима из целевого символа грамматики S: S ^*. Если цепочка получена в результате законченного вывода, она называется конечной сентенциальной формой.

Вывод называется левосторонним, если в нем на каждом шаге вывода правило грамматики применяется к самому левому нетерминальному символу в цепочке. Аналогично определяется правосторонний вывод.

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

Рассмотрим снова пример грамматики целых десятичных чисел со знаком.

G ({0,1,2,3,4,5,6,7,8,9,-,+}, {S, T, F}, P, S).

P:

S T+T-T

T FTF

F 123 456 789.

Построим в ней несколько цепочек вывода.

ST -TFFF -1 °F -19 (левосторонний);

T TF T0 TF0 T30 F30 730; (правосторонний)

S T TF TFF T6 °F F6 °F F63 263; (-)

S T TF T3 TF3 T63 F63 263; (правосторонний);

S T TF TFF T8 °F F8 °F (не законченный);

TFT TFTF TFFF TFF0 TF10 T210 F210 1210 (правосторонний).

Здесь (1) — (4) — конечные сентенциальные формы, поскольку цепочка в (2) может быть получена из целевого символа грамматики (хотя в этом примере и получена из нетерминала T); (5) — просто сентенциальная форма (не конечная). В выводе (6) в явном виде не присутствует сентенциальная форма, хотя цепочка 1210 и является конечной сентенциальной формой. Для того, чтобы это подтвердить, достаточно построить другой вывод этой цепочки из целевого символа. А цепочка TFT не является сентенциальной формой, т.к. ее невозможно получить из целевого символа. Все выводы, за исключением (5), являются законченными. На примере (3), (4) видно, что одна и та же цепочка может быть получена посредством разных выводов. Выводы (2), (4), (6) — правосторонние, (1) — левосторонний, (3), (5) — ни то, ни другое.

1.4.2 Дерево вывода

Деревом вывода грамматики G называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

каждая вершина дерева обозначается символом грамматики AV;

корнем дерева является вершина, обозначенная целевым символом грамматики S;

листьями дерева являются вершины, обозначенные терминальными символами грамматики или символом ;

если некоторый узел обозначен символом AVN, а связанные с ним узлы — символами b₁, b₂,…, b_nn > 0, 0 < i n, b_iV{}, то в грамматике существует правило A b₁b₂…b_n P.

По структуре правил дерево вывода всегда можно построить для грамматик типа 2 и 3. Для строго формализованного построения дерева удобнее пользоваться левосторонним либо правосторонним выводом. Дерево вывода можно построить двумя способами: сверху вниз (обычно левосторонний вывод) и снизу вверх (обычно правосторонний).

Алгоритм построения дерева сверху вниз:

целевой символ грамматики помещается в вершину дерева;

в грамматике выбирается необходимое правило и целевой символ раскрывается на несколько символов первого уровня;

среди всех концевых вершин дерева выбирается крайняя (левая для левостороннего вывода, правая — для правостороннего вывода) вершина, обозначенная нетерминальным символом;

для нее выбирается нужное правило и она снова раскрывается на несколько вершин следующего уровня;

если все концевые вершины обозначены терминальными символами, процесс закончен. Иначе — возврат на шаг 3.

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

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

Пример: Рассмотрим деревья вывода для сентенциальных форм (1) и (2).

1.5 Распознаватели. Задача разбора

1.5.1 Общая схема распознавателя

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

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

Распознаватель входит в состав компилятора и является частью программного обеспечения компьютера.

Условная схема распознавателя имеет следующий вид:

Основные компоненты распознавателя:

входная лента — линейная последовательность клеток, или ячеек, каждая из которых содержит ровно один символ входного алфавита;

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

устройство управления (УУ), которое координирует работу распознавателя, имеет некоторое множество состояний и конечную память;

внешняя (рабочая) память может хранить некоторую информацию в процессе работы распознавателя и может иметь неограниченный объем.

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

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

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

Такт состоит из следующих моментов:

входная головка распознавателя сдвигается на одну ячейку вправо, влево или остается на месте;

в память помещается некоторая информация;

изменяется состояние УУ.

В процессе работы распознавателя происходит смена конфигураций. Конфигурация распознавателя (мгновенное описание) определяется следующими параметрами:

состояние УУ;

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

содержимое внешней памяти.

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

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

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

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

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

1.5.2 Виды распознавателей и их классификация

Распознаватели классифицируют в зависимости от вида составляющих их компонентов: считывающего устройства, устройства управления и внешней памяти.

По видам считывающего устройства распознаватели могут быть двусторонними и односторонними. Односторонние распознаватели допускают перемещение считывающей головки по ленте только в одном направлении, обычно слева направо (такой распознаватель называется левосторонним). Такие распознаватели не возвращаются назад к уже прочитанной части цепочки. Двусторонние распознаватели допускают перемещение считывающей головки в любом направлении.

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

По видам внешней памяти распознаватели бывают следующих типов:

распознаватели без внешней памяти;

распознаватели с ограниченной внешней памятью;

с неограниченной внешней памятью.

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

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

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

Все три рассмотренных составляющих организуют общую классификацию распознавателей. Например, в ней возможен такой тип: «односторонний детерминированный полностью определенный распознаватель с линейно ограниченной стековой памятью».

Тип распознавателя в классификации определяет его сложность в целом. Сложность распознавателя напрямую связана с типом языка, цепочки которого он должен определять.

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

Для КС-языков распознавателями являются односторонние недетерминированные автоматы с магазинной (стековой) внешней памятью. Кроме того, среди всего множества КС-языков можно выделить подкласс детерминированных языков, для которых распознавателями являются детерминированные автоматы с магазинной памятью — ДМПА. Этот класс языков наиболее интересен для построения компиляторов.

Для языков программирования более целесообразно строить компиляторы на основе КС-языков, дополняя их семантическим анализатором, чем использовать в качестве основы КЗ-языки — такая комбинация имеет более высокую скорость работы.

Для регулярных языков распознавателями являются односторонние недетерминированные распознаватели без внешней памяти — конечные автоматы (КА). Кроме того, любой недетерминированный КА всегда может быть преобразован в детерминированный (ДКА). В компиляторах распознаватели на основе регулярных языков используются для лексического анализа текста исходной программы. Регулярные языки находят применение также во многих областях, связанных с разработкой ПО вычислительных систем.

1.5.3 Задача разбора

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

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

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

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

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

Глава 2. Регулярные языки

2.1 Регулярные множества и регулярные выражения

2.1.1 Определение и свойства регулярных выражений

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

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

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

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

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

если p и q — произвольные регулярные выражения, обозначающие регулярные множества P и Q, то p+q, pq, p* - регулярные выражения, обозначающие соответственно регулярные множества PQ, PQ, P*;

ничто другое регулярным выражением и регулярным множеством не является.

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

Все регулярные языки представляют собой регулярные множества.

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

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

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

Например, язык, представляющий собой множество всех цепочек из нулей и единиц произвольной длины, может быть описан эквивалентными регулярными выражениями б₁ и б₂: б₁ = (0+1)*, б₂ = (0*1*)*.

Пусть, , — регулярные выражения. Тогда свойства регулярных выражений можно записать в виде следующих формул:

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

2.1.2 Уравнения с регулярными коэффициентами

Простейшие уравнения с регулярными коэффициентами будут выглядеть следующим образом: X=X+; X=X+, где, V^* — регулярные выражения над алфавитом V, а XV. Два вида записи уравнений (правосторонняя и левосторонняя запись) связаны с тем, что для регулярных выражений операция конкатенации не обладает свойством коммутативности. Обе записи равноправны.

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

Решением первого уравнения является регулярное множество, обозначенное ^*. Если подставить его вместо переменной X в уравнение, получим X+=(^*)+=⁶ (^*)+=¹³(^*)+=⁵(^* +)=^1* =X.

Аналогично, для второго уравнения решение будет иметь вид ^*. Подставив его в уравнение, также получим тождество.

Указанные решения уравнений не всегда являются единственными. Например, если регулярное выражение в первом уравнении обозначает множество, которое содержит пустую цепочку, то решением уравнения может быть любое множество, обозначенное выражением X=^*(+), где может обозначать произвольное множество (в том числе не регулярное). Однако указанные решения — наименьшие возможные для данных уравнений. Они называются наименьшей подвижной точкой.

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

X₁=₁₀+₁₁X₁+₁₂X₂+…+_1nX_n;

X₂=₂₀+₂₁X₁+₂₂X₂+…+_2nX_n;

…

X_i=_i0+_i1X₁+_i2X₂+…+_inX_n;

…

X_n=_n0+_n1X₁+_n2X₂+…+_nnX_n;

В данной системе все коэффициенты _ij являются регулярными выражениями над алфавитом V, а переменные не входят в этот алфавит: X_iV i.

Системы уравнений с регулярными коэффициентами решаются методом последовательных подстановок. Рассмотрим метод решения для правосторонней записи. Алгоритм решения работает с переменной номера шага i.

Алгоритм решения:

Положить i:=1.

Если i=n, то перейти к шагу 4, иначе записать i-е уравнение в виде:

X_i=_iX_i+_i, где _i=_ii, _i=_i0+_{i i+1} X_i+1+…+_{i n} X_n, решить уравнение и получить X_i=_i^*_i. Затем подставить это выражение во все уравнения для переменных X_i+1,…, X_n.

Увеличить i на единицу и вернуться к шагу 2.

После всех подстановок уравнение для X_n будет иметь вид: X_n=_nX_n+, где _n=_nn, а — регулярное выражение над алфавитом V^*, т. е. не содержит переменных X_i. Тогда можно найти решение X_n=_n^*.