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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: курсовая работа. Добавлен: 29.05.13. Сдан: 2013. Страниц: 26. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Оглавление.

 

Введение. 2

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

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

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

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

Классификация распознавателей по виду их компонентов. 12

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

Теоретическая справка. 17

Составление формальной грамматики. 18

Построение  конечного распознавателя. 19

Программное моделирование работы конечного  распознавателя 20

Реализация  алгоритма средствами ООП. 23

Список используемой литературы 38

 

 

 

Введение.

Язык формирует наш  способ мышления и определяет то, о  чем мы можем мыслить. Б. Л. Ворф

Прогресс компьютерных технологий определил процесс появления  новых разнообразных знаковых систем для записи алгоритмов – языков программирования. Смысл появления  такого языка – оснащенный набор  вычислительных формул дополнительной информации, превращает данный набор  в алгоритм. Язык программирования служит двум связанным между собой  целям: он дает программисту аппарат  для задания действий, которые  должны быть выполнены, и формирует  концепции, которыми пользуется программист, размышляя о том, что делать. Первой цели идеально отвечает язык, который  настолько "близок к машине", что  всеми основными машинными аспектами  можно легко и просто оперировать  достаточно очевидным для программиста образом. Второй цели идеально отвечает язык, который настолько "близок к решаемой задаче", чтобы концепции  ее решения можно было выражать прямо  и коротко. Связь между языком, на котором мы думаем программируем, и задачами и решениями, которые мы можем представлять в своем воображении, очень близка. По этой причине ограничивать свойства языка только целями исключения ошибок программиста в лучшем случае опасно. Как и в случае с естественными языками, есть огромная польза быть, по крайней мере, двуязычным. Язык предоставляет программисту набор концептуальных инструментов, если они не отвечают задаче, то их просто игнорируют. Например, серьезные ограничения концепции указателя заставляют, программиста применять вектора и целую арифметику, чтобы реализовать структуры, указатели и т.п. Хорошее проектирование и отсутствие ошибок не может гарантироваться чисто за счет языковых средств. Может показаться удивительным, но конкретный компьютер способен работать с программами, написанными на его родном машинном языке. Существует почти столько же разных машинных языков, сколько и компьютеров, но все они суть разновидности одной идей простые операции производятся со скоростью молнии на двоичных числах. Персональные компьютеры IBM используют машинный язык микропроцессоров семейства 8086, т.к. их аппаратная часть основывается именно на данных микропроцессорах. Можно писать программы непосредственно на машинном языке, хотя это и сложно. На заре компьютеризации(в начале 1950-х г.г.), машинный язык был единственным языком, большего человек к тому времени не придумал. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (т.е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят "исходный код" (гибрид английских слов и математических выражений, который считывает машина), и в конечном итоге заставляет компьютер выполнять соответствующие команды, которые даются на машинном языке. Существует два основных вида трансляторов интерпретаторы, которые сканируют и проверяют исходный код в один шаг, и компиляторы, которые сканируют исходный код для производства текста программы на машинном языке, которая затем выполняется отдельно.

 

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

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

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

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

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

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

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

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

Любой разработчик программ, так или иначе, использует первый подход – это комментарии в программе, построение ее блок-схемы, разработка документации или любое другое описание алгоритма. Все эти способы ориентированы на человека, но универсального способа проверить, насколько описание в действительности соответствует программе, пока не существует. Для изложения программы на языке, понятном машине – в машинных командах – существуют трансляторы. Второй подход используется при отладке программы; оценку результатов выполнения программы при отладке осуществляет человек. Разработчикам компиляторов так или иначе приходится решать вопрос о смысле программ. Во-первых, компилятору для преобразования исходной программы в последовательность машинных команд необходимо иметь представление о том, какая последовательность команд должна соответствовать той или иной части программы. Обычно такие последовательности сопоставляют базовым конструкциям входного языка – используется первый подход к изложению смысла программы. Во-вторых, многие современные компиляторы позволяют выявить сомнительные с точки зрения смысла места в исходной программе – например, недостижимые операторы, неиспользуемые переменные, неопределенные результаты функций и т.п. Обычно компилятор указывает такие места в виде предупреждений, на которые разработчик может обращать или не обращать внимание. Для этого компилятор должен иметь представление о том, как программа будет выполняться, т.е. используется второй подход. Но в любом случае осмысление исходной программы закладывает в компилятор его создатель, который руководствуется неформальными методами – как правило, описанием входного языка. В теории формальных языков вопрос о смысле программ не решается. Итак, возможности трансляторов по проверке осмысленности исходной программы практически равны нулю, поэтому семантические ошибки остаются на совести авторов программ. Выше, когда шла речь о различных способах задания языков, мы выделили как наиболее реальные второй и третий способ, а именно: задание языка с помощью генераторов и распознавателей. В качестве генераторов в общем случае могут использоваться грамматики, а для более узкого класса языков – регулярные выражения. В качестве распознавателей, как правило, применяются автоматы различных типов (в зависимости от класса языка). Рассмотрим способ задания языков с помощью грамматик.

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

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

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

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

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

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

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

P – Множество правил вида a®b, где aIV+, bIV*;

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

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

Во множестве правил грамматики может быть несколько правил, имеющих  одинаковые левые части, например: a®b1, a®b2, …, a®bn. Тогда эти правила записываются в одну строку: a®b1?b2?…?bn.

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

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

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

P:

<число>®<чс>?+<чс>?–<чс>

<чс>®<цифра>?<чс><цифра>

<цифра>® 0?1?2?3?4?5?6?7?8?9

 

В данной грамматике множество  нетерминальных символов содержит 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®F?TF

F® 0?1?2?3?4?5?6?7?8?9.

 

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

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

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

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

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

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

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

Конфигурация распознавателя определяется следующими параметрами:

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

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

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

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

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

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

 

Классификация распознавателей  по виду их компонентов.

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

По видам считывающего устройства распознаватели могут быть двусторонние и односторонние.

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

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

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

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

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

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

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

У распознавателей без  внешней памяти эта память полностью  отсутствует. В процессе их работы используется только конечная память устройства управления, доступ к внешней памяти не выполняется. Для распознавателей с ограниченной внешней памятью размер внешней  памяти ограничен в зависимости от длины исходной цепочки символов. Эти ограничения могут налагаться некоторой зависимостью объема памяти от длины цепочки. Кроме того, для таких распознавателей может быть указан способ организации внешней памяти — стек, очередь, список и т. п.Распознаватели с неограниченной внешней памятью предполагают, что для их работы может потребоваться внешняя память неограниченного объема (как правило, вне зависимости от длины входной цепочки). У таких распознавателей предполагается память с произвольным методом доступа. Вместе эти три составляющих позволяют организовать общую классификацию распознавателей. Например, в этой классификации возможен такой тип: «двусторонний недетерминированный распознаватель с линейно ограниченной стековой памятью».Чем выше в классификации стоит распознаватель, тем сложнее создавать алгоритм, обеспечивающий его работу. Разрабатывать двусторонние распознаватели сложнее, чем односторонние. Можно заметить, что недетерминированные распознаватели по сложности выше детерминированных. Зависимость затрат на создание алгоритма от типа внешней памяти также очевидна. Классификация распознавателей по типам распознаваемых языков Классификация распознавателей (вид входящих в состав распознавателя компонентов) определяет сложность алгоритма работы распознавателя. Но сложность распознавателя также напрямую связана с типом языка, входные цепочки которого может принимать (допускать) распознаватель. Для языков с фразовой структурой (тип 0) необходим распознаватель, равномощный машине Тьюринга — недетерминированный двусторонний автомат, имеющий неограниченную внешнюю память. Поэтому для языков данного типа нельзя гарантировать, что за ограниченное время на ограниченных вычислительных ресурсах распознаватель завершит работу и примет решение о том, принадлежит или не принадлежит входная цепочка заданному языку. Практическая реализация таких распознавателей чрезвычайно сложна. Для контекстно-зависимых языков (тип 1) распознавателями являются двусторонние недетерминированные автоматы с линейно ограниченной внешней памятью. Автоматы данного типа имеют экспоненциальную сложность: время, необходимое на разбор входной цепочки, экспоненциально зависит от длины входной цепочки символов. Такой алгоритм распознавателя может быть реализован в программном обеспечении компьютера — зная длину входной цепочки, всегда можно сказать, за какое максимально возможное время будет принято решение о принадлежности цепочки данному языку и какие вычислительные ресурсы для этого потребуются. Как правило, такие распознаватели применяются для автоматизированного перевода и анализа текстов на естественных языках, когда временные ограничения на разбор текста несущественны. После обработки естественно языковых текстов часто требуется ручное постредактирование.

Для контекстно-свободных  языков (тип 2) распознавателями являются односторонние детерминированные / недетерминированные автоматы с  магазинной (стековой) внешней памятью  — МП-автоматы. В общем случае, автоматы данного типа имеют экспоненциальную сложность, однако алгоритм можно усовершенствовать  так, чтобы его сложность стала  полиномиальной (кубической). Среди  всех КС-языков можно выделить класс  детерминированных КС-языков, распознавателями для которых являются детерминированные  автоматы с магазинной (стековой) внешней  памятью — ДМП-автоматы. Эти языки обладают свойством однозначности (доказано, что для любого детерминированного КС-языка всегда можно построить однозначную грамматику). Кроме того, для таких языков существует алгоритм работы распознавателя с квадратичной сложностью. Более того, среди детерминированных КС-языков существуют такие классы языков, для которых возможно построить линейный распознаватель (где время принятия решения о принадлежности цепочки языку имеет линейную зависимость от длины цепочки).

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

 

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

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

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

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

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

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

Теоретическая справка.

Недетерминированный конечный автомат (НКА) - это пятерка M = (Q, T, D, q0, F), где

  • Q - конечное множество состояний;
  • T - конечное множество допустимых входных символов (входной алфавит);
  • D - функция переходов (отображающая множество Q?(T {e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;
  • q0 Q - начальное состояние управляющего устройства;
  • F Q - множество заключительных состояний.

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

 

 

 
 


 

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

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

Конечный автомат – это модель устройства с конечным числом состояний, которое отличает правильно образованные, или «допустимые» цепочки, от «недопустимых».

 

Составление формальной грамматики.

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

R0: <предложение> ::==< фраза>#

R1: <фраза> ::==< фраза>/< составное имя> | <идентификатор>

R2: <составное имя> ::==<составное имя>.<идентификатор>|<идентификатор>

R3: <идентификатор>::==<идентификатор><допустимый символ>|<начальный символ>

R4: <начальный символ>::==<буква>|<знак подчёркивания>

R5: <допустимый символ> :=:=<буква>|<цифра>|<знак подчёркивания>

R6:<буква>::==a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|

R7: <цифра>::==0|1|2|3|4|5|6|7|8|9|

R8:<знак подчёркивания>::==_

 

Таким образом, требуемую  грамматику можно описать следующей  структурой:

  • Множество терминальных символов: 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g,h,I,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,_, .,/,#
  • Множество нетерминальных символов: <фраза>, < составное имя>, <идентификатор>, <допустимый символ>, <начальный символ>, <буква>, <цифра>,  <знак подчёркивания>.
  • Множество правил вывода R0,R1, R2, R3, R4, R5, R6, R7, R8.

 

Построение конечного  распознавателя.

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

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

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

#include "iostream.h"

#include "stdio.h"

#include "conio.h"

int main()

{  int i,j,kol,tsost,slsost,tsymb;

int tabl[9][40]={

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//da     {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//net     {1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,1,1,1},//sost imya     {7,7,7,7,7,7,7,7,7,7,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,2,1},//ident     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,1},//nach sim     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,1,1},//dop sim     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,0},//bykva     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,0},//cifra     {7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,5,2,0}//znak

};printf("matrica\n");

for (i=0;i<9;i++) {for (j=0;j<40;j++) printf("%4d",tabl[i][j]); printf("\n");};

  char   ch, inpstr[80] ;

  printf("\n ENTER STRING  ");

  i=0;

 while ((ch=getch()) !=13 && i<80)

{putch(ch);

inpstr[i++]=ch;}

 inpstr[i]='\0';

 kol=i-1;

 printf("\n input string:");

 printf(inpstr);

 printf("\n");

     tsost=2;

     for (i=0;i<=kol;i=i+1)

     {   tsymb=inpstr[i];

     switch (tsymb)

 { case '0':  slsost=tabl[tsost][0]; break;

   case '1':  slsost=tabl[tsost][1]; break;

   case '2':  slsost=tabl[tsost][2]; break;

   case '3':  slsost=tabl[tsost][3]; break;

       case '4':  slsost=tabl[tsost][4]; break;


и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.