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

Содержание

Введение…………………………………………………………………….       3

1.Понятие грамматики……..………………………………………………       4

2 Классификация грамматик………………………………………………       7

3. Автоматные грамматики ………………………………………………       9

Заключение…………………………………………………………………       14

Литература………………………………………………………………….       15 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

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

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

1.Понятие грамматики и формальное определение.

Форма Бэкуса-Наура

         Любой конечный механизм задания языка называется грамматикой.

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

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

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

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

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

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

     P – множество правил вида a ® b, где aÎV⁺, bÎV*;

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

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

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

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

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

     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.

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

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

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

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

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

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

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

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

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

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

     Контекстно-зависимые  грамматики имеют правила вида a₁Aa₂ ® a₁ba₂, где a₁,a₂ÎV^*, AÎVN, bÎV⁺.

     Неукорачивающие грамматики имеют правила вида a ® b, где a,bÎV⁺, ½b½³½a½.

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