Кс языки и грамматики


Содержание

Кс – грамматики

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

Контекстно-свободной грамматика называется потому, что символ А можно заменить цепочкой , не обращая внимание на контекст, в котором он встретился.

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

Пример 1. Грамматика списка операторов .

Переход от синтаксической диаграммы к БНФ.

При переходе от синтаксической диаграммы к БНФ необходимо учитывать, что все разделители и ключевые слова языка – это множество Т-символов; все обобщающие понятия, обозначенные на синтаксических диаграммах прямоугольниками – это множество НТ- символов.

Обозначим список операторов (ведь их может быть множество ) как SОP, а один оператор — ОP. Тогда грамматика выглядит следующим образом.

Рис. 1 Синтаксическая диаграмма списка операторов

или SОP  ОP | ОP ; SОP

или SОP  ОP | SОP ; ОP

Пример 2. Грамматика множителя в арифметическом выражении.

Переход от грамматики к БНФ.

Рассмотрим синтаксическую диаграмму множителя ( рис 2.)

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

Рис. 2 Синтаксическая диаграмма множителя

Тогда грамматика множителя в БНФ будет выглядеть следующим образом:

Построение выводов

Каждая грамматика позволяет решать две задачи:

Вывести правильные ( допустимые ) предложения языка .

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

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

число => чс => чс цифра => цифра цифра => 2 цифра => 22 .

Символ => отделяет цепочку до подстановки от цепочки, получающейся после подстановки. Длина вывода в данном случае равна 5.

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

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

-левый вывод (L-вывод), когда на каждом шаге вывода заменяется самый левый НТ-символ промежуточной формы,

-правый вывод (R-вывод), когда заменяется самый правый НТ-символ.

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

у него имеется одна вершина, в которую не входит не одна дуга; эта вершина называется корнем дерева;

2) в каждую из его остальных вершин входит лишь одна дуга;

3) он не содержит контуров.

Нетрудно видеть, что из корня дерева в любую его вершину ведет ровно один путь.

Пусть задано некоторое дерево (Х,U), где Х- множество его вершин, а U — частичное отображение Х в Х, определяющее дуги дерева. Изображение дерева, удовлетворяющее следующим условиям:

все его вершины одного уровня расположены на одной прямой;

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

дуги дерева не пересекаются;

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

Построим дерево вывода из предыдущей грамматики:

Рис. 3 Синтаксическое дерево вывода

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

Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме , страница 2

3.1.2 Свойства КС-языков

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

Класс КС-языков замкнут относительно операций объединения, конкатенации, итерации, изменения имен символов.

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

Пусть есть два языка L1=0, i>0> и L2=0, i>0>. Оба эти языка являются КС, но, если взять их пересечение, то получим язык L=L1ÇL2=0>, который уже не является КС-языком.

Для КС-языков разрешимы проблемы пустоты языка и принадлежности заданной цепочки языку – для их решения достаточно построить МПА, распознающий данный язык. Но проблема эквивалентности двух произвольных грамматик является неразрешимой. Неразрешима и более узкая проблема – эквивалентности заданной произвольной КС-грамматики и произвольной регулярной грамматики. Тем не менее, для некоторых КС-грамматик можно построить эквивалентную им однозначную грамматику.

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

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

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

Лемма о разрастании КС-языков:

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

Формальная запись: Если L – это КС-язык, то $ k>0, kÎN ½если ½a½³ k и aÎL, то a=bdgjm, где dj¹l, ½dgj½£ k и bd i gj i mÎL » i ³0.

Проверим, является ли язык L=0> КС-языком. Пусть это так, тогда для него должна выполняться лемма о разрастании КС-языков. Значит, существует некоторая константа k, о которой идет речь в этой лемме. Возьмем цепочку этого языка a=a k b k c k , ½a½> k. Если её записать в виде a=bdgjm, то по условиям леммы ½dgj½£ k , следовательно, цепочка dgj не может содержать вхождения всех трех символов ‘a’, ‘b’, ‘c’, т.е. в ней нет или ‘a’, или ‘c’. Рассмотрим цепочку bd 0 gj 0 m=bgm. По условиям леммы, она должна принадлежать языку L, но она содержит либо k символов ‘a’, либо k символов ‘c’. Но ½bgm½ k 1 n ½ k ³ n > 0>; б) <0 k 1 n ½ 0 * и количество символов ’а’ ’b’ одинаково>; г) <0 n 1 0 k>; д) * и количество символов ’а’ и ’b’ четно>.

11. Как можно установить, относится ли язык к контекстно-свободному типу?

12. В чём отличие леммы о разрастании КС-языков от соответствующей леммы для регулярных языков?

3.2 Преобразование КС-грамматик

3.2.1 Цели преобразований грамматик

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

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

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

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

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

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

2. изменение вида и состава правил грамматики. При этом могут появиться новые правила и нетерминальные символы (упрощений правил нет).

3.2.2 Приведённые грамматики

  • АлтГТУ 419
  • АлтГУ 113
  • АмПГУ 296
  • АГТУ 266
  • БИТТУ 794
  • БГТУ «Военмех» 1191
  • БГМУ 172
  • БГТУ 602
  • БГУ 153
  • БГУИР 391
  • БелГУТ 4908
  • БГЭУ 962
  • БНТУ 1070
  • БТЭУ ПК 689
  • БрГУ 179
  • ВНТУ 119
  • ВГУЭС 426
  • ВлГУ 645
  • ВМедА 611
  • ВолгГТУ 235
  • ВНУ им. Даля 166
  • ВЗФЭИ 245
  • ВятГСХА 101
  • ВятГГУ 139
  • ВятГУ 559
  • ГГДСК 171
  • ГомГМК 501
  • ГГМУ 1967
  • ГГТУ им. Сухого 4467
  • ГГУ им. Скорины 1590
  • ГМА им. Макарова 300
  • ДГПУ 159
  • ДальГАУ 279
  • ДВГГУ 134
  • ДВГМУ 409
  • ДВГТУ 936
  • ДВГУПС 305
  • ДВФУ 949
  • ДонГТУ 497
  • ДИТМ МНТУ 109
  • ИвГМА 488
  • ИГХТУ 130
  • ИжГТУ 143
  • КемГППК 171
  • КемГУ 507
  • КГМТУ 269
  • КировАТ 147
  • КГКСЭП 407
  • КГТА им. Дегтярева 174
  • КнАГТУ 2909
  • КрасГАУ 370
  • КрасГМУ 630
  • КГПУ им. Астафьева 133
  • КГТУ (СФУ) 567

  • КГТЭИ (СФУ) 112
  • КПК №2 177
  • КубГТУ 139
  • КубГУ 107
  • КузГПА 182
  • КузГТУ 789
  • МГТУ им. Носова 367
  • МГЭУ им. Сахарова 232
  • МГЭК 249
  • МГПУ 165
  • МАИ 144
  • МАДИ 151
  • МГИУ 1179
  • МГОУ 121
  • МГСУ 330
  • МГУ 273
  • МГУКИ 101
  • МГУПИ 225
  • МГУПС (МИИТ) 636
  • МГУТУ 122
  • МТУСИ 179
  • ХАИ 656
  • ТПУ 454
  • НИУ МЭИ 641
  • НМСУ «Горный» 1701
  • ХПИ 1534
  • НТУУ «КПИ» 212
  • НУК им. Макарова 542
  • НВ 777
  • НГАВТ 362
  • НГАУ 411
  • НГАСУ 817
  • НГМУ 665
  • НГПУ 214
  • НГТУ 4610
  • НГУ 1992
  • НГУЭУ 499
  • НИИ 201
  • ОмГТУ 301
  • ОмГУПС 230
  • СПбПК №4 115
  • ПГУПС 2489
  • ПГПУ им. Короленко 296
  • ПНТУ им. Кондратюка 119
  • РАНХиГС 186
  • РОАТ МИИТ 608
  • РТА 243
  • РГГМУ 118
  • РГПУ им. Герцена 124
  • РГППУ 142
  • РГСУ 162
  • «МАТИ» — РГТУ 121
  • РГУНиГ 260
  • РЭУ им. Плеханова 122
  • РГАТУ им. Соловьёва 219
  • РязГМУ 125
  • РГРТУ 666
  • СамГТУ 130
  • СПбГАСУ 318
  • ИНЖЭКОН 328
  • СПбГИПСР 136
  • СПбГЛТУ им. Кирова 227
  • СПбГМТУ 143
  • СПбГПМУ 147
  • СПбГПУ 1598
  • СПбГТИ (ТУ) 292
  • СПбГТУРП 235
  • СПбГУ 582
  • ГУАП 524
  • СПбГУНиПТ 291
  • СПбГУПТД 438
  • СПбГУСЭ 226
  • СПбГУТ 193
  • СПГУТД 151
  • СПбГУЭФ 145
  • СПбГЭТУ «ЛЭТИ» 380
  • ПИМаш 247
  • НИУ ИТМО 531
  • СГТУ им. Гагарина 114
  • СахГУ 278
  • СЗТУ 484
  • СибАГС 249
  • СибГАУ 462
  • СибГИУ 1655
  • СибГТУ 946
  • СГУПС 1513
  • СибГУТИ 2083
  • СибУПК 377
  • СФУ 2423
  • СНАУ 567
  • СумГУ 768
  • ТРТУ 149
  • ТОГУ 551
  • ТГЭУ 325
  • ТГУ (Томск) 276
  • ТГПУ 181
  • ТулГУ 553
  • УкрГАЖТ 234
  • УлГТУ 536
  • УИПКПРО 123
  • УрГПУ 195
  • УГТУ-УПИ 758
  • УГНТУ 570
  • УГТУ 134
  • ХГАЭП 138
  • ХГАФК 110
  • ХНАГХ 407
  • ХНУВД 512
  • ХНУ им. Каразина 305
  • ХНУРЭ 324
  • ХНЭУ 495
  • ЦПУ 157
  • ЧитГУ 220
  • ЮУрГУ 306

Полный список ВУЗов

Чтобы распечатать файл, скачайте его (в формате Word).

Кс языки и грамматики

КС-грамматики находят большое применение в информатике. Ими задаётся грамматическая структура большинства языков программирования, структурированных данных и т.д. (см. грамматический анализ)

Типы КС грамматик


  • LL-грамматика
  • LALR-грамматика
  • LR-грамматика
  • SLR-грамматика

Примеры

Примеры КС-грамматик и соответствующих им КС-языков:

Вложенные скобки

  • Терминалы: ‘(‘ и ‘)’;
  • нетерминал: S;
  • продукции: S→(S), S→ε;
  • начальный нетерминал — S.

Этой грамматикой задаётся язык вложенных скобок < ( n ) n | n≥0 >.

Язык Дика

Целые числа

  • Терминалы: ‘+’, ‘-‘, ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’;
  • нетерминалы: , , , , ;
  • продукции:
  • начальный нетерминал: .

Этой грамматикой задаётся язык целых чисел.

Арифметическое выражение

  • Терминалы: ‘+’, ‘-‘, ‘*’, ‘/’, ‘(‘, ‘)’, ‘x’
  • нетерминалы: , ,
  • продукции:
  • начальный нетерминал: .

Этой грамматикой задаётся арифметическое выражение, содержащее простейшие арифметические действие над переменной x. Если заменить терминал ‘x’ на нетерминал из предыдущего примера, то получится грамматика, задающая арифметическое выражение, состоящее из операций сложения, вычитания, умножение и деления над целыми числами.

Ограничения возможностей КС грамматик

Не все языки могут быть заданы КС-грамматикой. Так, язык < a n b n c n | n≥1 > не является контекстно-свободным.

Литература

  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1

Wikimedia Foundation . 2010 .

Смотреть что такое «КС-грамматика» в других словарях:

Грамматика (наука) — Грамматика (от греч. γράμμα «запись»), как наука, есть раздел языкознания, изучающий грамматический строй языка, закономерности построения правильных осмысленных речевых отрезков на этом языке (словоформ, синтагм, предложений, текстов). Эти … Википедия

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

ГРАММАТИКА БЕСКОНТЕКСТНАЯ — грамматика контекстно свободная, КС грамматика, грамматика составляющих, все правила к рой имеют вид где А вспомогательный символ и непустая цепочка (так наз. бесконтекстные правила). Языки, порождаемые такими грамматиками, наз. бесконтекстными… … Математическая энциклопедия

Грамматика (система) — Грамматика (от греч. grammatikáos относящийся к буквам от gr2amma буква), грамматический строй (грамматическая система) совокупность закономерностей какого либо языка, регулирующих правильность построения значимых речевых отрезков (слов,… … Википедия

Грамматика (как система) — Грамматика (от греч. grammatikáos относящийся к буквам от gr2amma буква), грамматический строй (грамматическая система) совокупность закономерностей какого либо языка, регулирующих правильность построения значимых речевых отрезков (слов,… … Википедия

Грамматика — (от греческого grammata «письмена», «писания»). В первоначальном понимании слова Г. совпадает с наукой о языковых формах вообще, включая и изучение элементов звуковой формы звуков или, как выражаются вплоть до начала XIX в., «букв»; это включение … Литературная энциклопедия

ГРАММАТИКА — (греч. grammatike, от grammata письмена, происш. от graphein писать). 1) собрание законов и правил употребления устного и письменного языка. 2) учебная книга, содержащая в себе грамматику известного языка. Словарь иностранных слов, вошедших в… … Словарь иностранных слов русского языка

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

Грамматика Николая Греча — Пространная русская грамматика была опубликована в 1827 году с посвящением Николаю I. Свет увидел только первый том. Грамматику предваряет предисловие Ф.В. Булгарина, который счел необходимым заменить авторское предисловие, поскольку оно было… … Википедия

ГРАММАТИКА СОСТАВЛЯЮЩИХ — грамматика непосредственно составляющих, НС грамматика, грамматика контекстная, частный случай грамматики порождающей, когда каждое ее правило имеет вид , где цепочки в алфавите и 0 непуста. Каждый шаг вывода в Г. с. состоит в замене одного… … Математическая энциклопедия

ГРАММАТИКА ПОРОЖДАЮЩАЯ — грамматика Хомского, один из видов формальной грамматики;представляет собой, по существу, частный случай исчисления Поста (см. Поста каноническая система). Систематич. изучение Г. п. было начато в 50 х гг. 20 в. Н. Хомскнм (N. Chomsky), к рый… … Математическая энциклопедия

Свойства КС-языков и грамматик

Язык, определяемый детерминированным МП-автоматом, называется детерминированным КС-языком.

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

Илон Маск рекомендует:  Что такое код imageline

Так, МП-преобразователь из примера 3.7, переводящий арифметические выражения из префиксной формы в постфиксную — детерминированный. Анализаторы М и Мг из примеров 3.11 и 3.12 — недетерминированные, так как возможны несколько траекторий, при построении траектории, приводящей к заключительной конфигурации (показанной в примерах), необходимы возвраты к уже прочитанной части цепочки. Отсюда происходят и названия разных классов методов синтаксического анализа или синтаксически управляемой трансляции: однопроходные, безвозвратные, детерминированные, с возвратами, с ограниченными возвратами и др.

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

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

Пример 5.1. Рассмотрим грамматику G с правилами

и арифметическое выражение а+а*а, порождаемое грамматикой G. Это выражение может иметь два левых вывода:

Рис. 5.1. Синтаксическое дерево для примера 5.1

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

Определение (неоднозначность/однозначность КС-языков): КС- язык называется неоднозначным, если не существует ни одной однозначной КС-грамматики, порождающей этот язык.

Введенное понятие неоднозначности — это свойство грамматики, а не языка. Для многих неоднозначных грамматик можно получить эквивалентные им однозначные грамматики. Все используемые языки программирования однозначны. С точки зрения их разработки важнее всего то, что каждый детерминированный КС-язык определяется однозначной КС-грамматикой [1].

Определение (рекурсивность КС-грамматики):

  • а) нетерминал А КС-грамматики G = (N, 2, Р, S) называется рекурсивным, еслнА=> + сЩ) для некоторых а, (Зе (MjI) *. Если а = е, то А называется леворекурсивным, если р = е, то праворекурсивным’,
  • б) грамматика, в которой все нетерминалы рекурсивные, называется рекурсивной (исключение составляет начальный символ S, который может быть или не быть рекурсивным);
  • в) грамматика, имеющая хотя бы один леворекурсивный нетерминал, называется леворекурсивной. Аналогично определяется праворекурсивная грамматика.

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

Определение. Символ Te(iVuI) называется бесполезным в КС- грамматике G = (N, 2, Р, S), если в ней нет вывода вида 5=>*(оЛ/у=>*ому, где со, х, ye2*.

Определение. Символ Хе (Mj2) называется недостижимым в КС- грамматике G = (N, 2, Р, S), если X не появляется ни в одной выводимой цепочке.

Определение. КС-грамматика G = (N, 2, Р, S) называется грамматикой без е-правил (неукорачивающей грамматикой), если:

  • — либо Р не содержит е-правил;
  • — либо есть точно одно е-правило 5->е и 5 не встречаются в правых частях остальных правил из Р.

Определение. Правило А-^В, где A, BeN, называется цепным.

Определение. КС-грамматика G = (N, 2, Р, S) называется грамматикой без циклов, если в ней нет выводов/4=> + /1 для Л е TV.

Определение. КС-грамматика G = (N, 2, Р, S) называется приведенной, если она без циклов, без е-правил и без бесполезных символов.

Пример 5.2. Рассмотрим грамматики G и G2 с правилами Р и Ру.

Грамматика G порождает только одну терминальную цепочку — L(GX) = <а>и правила 2, 3, 4 не играют никакой роли в определении языка L(G <),следовательно, нетерминалы А и В и терминал b бесполезны. В грамматике G2 нетерминал А недостижим, так как не может появиться в выводах.

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

Нормальные формы КС-грамматик. В ряде случаев бывает необходимо, чтобы все правила КС-грамматики имели определенную «стандартную» форму. В качестве таких стандартов используются нормальные формы Хомского и Грейбах.

Определение. КС-грамматика G = (N., 2, Р, S) называется грамматикой в нормальной форме Хомского (или в бинарной нормальной форме), если каждое правило из Р имеет один из следующих видов:

  • 1) А-^ВС, гдеХ, В, C&N;
  • 2) А->а, где яе2;
  • 3) S->e, если eeL(G), причем Sне встречается в правых частях правил.

Определение. КС-грамматика G = (N, 2, Р, S) называется грамматикой в нормалной форме Грейбах, если в ней нет е-правил и каждое правило из Р, отличное от имеет вид А^аа, где яе2 и asN» (другими словами, все правые части правил начинаются с терминалов).

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

Регулярные языки и КС-грамматики Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Мартыненко Борис Константинович

Существует множество технологических средств построения анализаторов формальных языков, используемых при создании разного вида трансляторов языков программирования. Все они, в конечном счёте, основываются на КС-грамматиках с теми или иными ограничениями, частным случаем которых являются регулярные (автоматные) грамматики. Как правило, эти технологические средства обеспечивают лишь проверку соответствующих требований, предъявляемых к грамматике, и выдачу диагностических сообщений об их нарушениях, тогда как существует множество способов эквивалентных преобразований КС-грамматик , которые могут быть выполнены автоматически и дать грамматики, удовлетворяющие требованиям метода анализа. Цель этой статьи – описать способ исключения несамовставленных нетерминалов из КС-грамматик за счёт введения регулярных выражений в правые части правил грамматики. В предельном случае такая преобразованная грамматика включает единственное правило для начального нетерминала.There is a variety of parser generators for formal languages being used during designing compilers for programming languages of different types. All of them are based on the use of context-free grammars with various restrictions, regular grammars being a special case. As a rule, they only check the requirements imposed on grammar, and issue diagnostic messages in case of their violation. The purpose of this article is to describe the way of eliminating all nonterminals from the non-self-embedding grammar that gives the equivalent regular expression as result.

Похожие темы научных работ по математике , автор научной работы — Мартыненко Борис Константинович,

Текст научной работы на тему «Регулярные языки и КС-грамматики»

УДК 519.682.1 +681.142.2

Мартыненко Борис Константинович

РЕГУЛЯРНЫЕ ЯЗЫКИ И КС-ГРАММАТИКИ

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

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

Ключевые слова: КС-грамматика, регулярное выражение, эквивалентное преобразование грамматики.

Впервые КС-грамматики были использованы для описания синтаксиса алгоритмических языков в [1]. Формализм металингвистических формул, названный позднее БМР-формой, в [2] был дополнен возможностью использовать регулярные выражения над терминалами, нетерминалами в правых частях правил и получил ещё одну букву в обозначении класса грамматик ЯБМР.

В 1970-х годах ЯБМР-грамматики были использованы в проекте реализации языка программирования Алгол 68 [3]. Несколько позже [4] в эту модель описания языков было введено понятие операционной среды, а в правила грамматики — контекстные символы (семантики и резольверы) с их интерпре-

© Мартыненко Б.К., 2012

тацией в виде семантических процедур и предикатных функций. Это нововведение дало возможность использовать RBNF-грамматики в качестве средства описания трансляций, учитывающего контекст конструкций входного языжа трансляции. Эта модель описания и реализации трансляций использовалась при реализации ряда нетривиальных языков программирования, таких как Алгол 68 и Ада. Несколько позже она быша воплощена в технологическом комплексе SYNTAX, который в течение ряда лет использовался в семинарских занятиях по технологии трансляции на математико-механическом факультете Санкт-Петербургского университета.

ТК SYNTAX включает средства эквивалентных преобразований на уровне граф-схем за счёт перевода несамовставленных нетерминалов в разряд вспомогательных понятий, определения которыгх подставляются вместо

примененных вхождении таких символов в правые части правил (метаподстановки). В остальном, ТК SYNTAX требует грамматик, уже приведенных к нужному виду, так же как большинство известных технологических систем генерации анализаторов.

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

2. НЕКОТОРЫЕ ПРЕДВАРИТЕЛЬНЫЕ ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КС-ГРАММАТИК

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

Пусть G = (VN,VT,P,S) — КС-грамматика, где VN — конечное множество нетерминалов, VT — конечное множество терминалов (VN n VT = 0), P — конечное множество правил вида A ® a, A е VN, ae V *. Здесь V * — бесконечное множество всех цепочек над алфавитом V = VN u VT, включая и пустую цепочку, обозначаемую символом е.

Пусть x = yxAyv где g1, g2 е V*, и A ® ae P. Считается, что из цепочки x непосредственно выводится цепочка y посредством указанного правила x ^ y, если У = TiaYT

Будем использовать обозначение x y для вывода цепочки y из цепочки x за счет использования нескольких правил грамматики, при этом считается, что любая цепочка x выводима сама из себя, и для этого не требуются никакие правила.

порождаемый грамматикой G.

Далее рассматриваются все эквивалентные преобразования КС-грамматик регулярного языка, предшествующие получению

регулярного выражения, его представляющего.

I) ПРОДУКТИВНОСТЬ НЕТЕРМИНАЛОВ

Пусть G = (Уы, Ут, Р, Б) — произвольная КС-грамматика. Нетерминал А е Уы называется продуктивным, если существует вывод вида А == м, где м е УТ*.

Известно, что любой КС-языгк может быгтъ порождён КС-грамматикой, каждыгй нетерминал которой продуктивен.

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

Алгоритм 1. Проверка пустоты языка

Вход: G = (Ум,Ут,Р,Б) — КС-грамматика.


Шаг 1. Начать построение коллекции деревьев вывода с единственного дерева, представленного только корнем — узлом с меткой

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

Шаг 3. Если в построенной коллекции есть хотя бы одно дерево, представляющее вывод терминальной цепочки, то язык Ц(в) не пуст. Иначе — язык Ц(в) пуст.

Алгоритм 2. Исключение непродуктивных нетерминалов

Вход: G = (У^,УТ, Р, Б) — КС-грамматика.

Выгход: G1 = (Ум 1, Ут, Р1, Б), причём Ь^) = ЦО).

Метод: Для каждого нетерминала А е Ук рассмотрим грамматику вА = (У№ Ут, Р, А).

Если язык Ц(СА) пуст, то мы удалим А из множества У№ а также все правила, использующие А в правой или левой части.

После удаления из в всех таких нетерминалов и правил мы получим новую грамматику в1 = (У^, Ут, Р1, 5), где У^ и Р1 — оставшиеся нетерминалы и правила.

II) ДОСТИЖИМОСТЬ НЕТЕРМИНАЛОВ

Говорят, что нетерминал А gFn достижим, если существует вывод вида S ajAa2 для некоторых цепочек

Известно, что любой КС-языгк может быгтъ порождён КС-грамматикой, каждыгй нетерминал которой достижим. Для получения такой грамматики можно использовать следующий алгоритм.

Алгоритм 3. Исключение недостижимых нетерминалов

Вход: Gj = (VN VT,Pj,S) — КС-грамматика, все нетерминалы которой продуктивны.

Выгход: G2 = (VN2,VT,P2,S) — эквивалентная КС-грамматика, все нетерминалы которой используются в выводах цепочек языка.

Метод: Мы можем эффективно построить множество VN всех нетерминалов A, таких что существует вывод вида S а1Аа2, где aj ,а2 е V*.

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

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

Положим G2 = (VN2,Vt,P2,S), где P2 -множество правил, оставшихся после исключения всех правил из P1, которые используют символы из VNi \ VN2 в левых или

правых частях правил. Известно, что ОД) = ОД).

Грамматики, в которых все нетерминалы продуктивные и достижимые, называются приведёнными. Они хороши тем, что не содержат нетерминалов и правил, не участвующих в порождении данного языка.

III) ЦЕПНЫЕ ПРАВИЛА

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

жащей цепныгх правил, то естъ правил вида A ® B, где A и B — нетерминалыi.

Алгоритм 4. Исключение цепных правил

Вход: G2 = (VN ,VT,P2, S) — приведённая КС-грамматика.

Выход: G3 = (VN,VT,P3,S) — КС-грамматика без цепных правил, эквивалентная исходной.

Метод: Мы построим новое множество правил P3, прежде всего включив в него все нецепные правила из P2. Затем из каждого цепного правила вида A ® B е P2 образуем множество новых нецепных правил вида A ® а, если существует нецепное правило B ® ае P2, и пополним множество P3 новыми нецепными правилами, полученными таким путём.

Вывод одной и той же цепочки в грамматике P3 короче вывода в грамматике P2 на число применённых цепных правил из P2.

IV) СВОЙСТВО САМОВСТАВЛЕННОСТИ

Пусть G = (VN,VT,P,S) — КС-грамматика. Символ А е VN называется самовстав-ленныгм, если существует вывод вида А ajA а2, где aj Ф в и а2 Ф в в предположении, что в грамматике не существует e-правил, и, кроме того, если в е L(G), то S не должен встречаться в правой части никакого правила, и пустое предложение порождается единственным правилом вида S ® в.

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

Алгоритм 5. Исключение начального нетерминала S из правых частей правил

Вход: G = (VN,VT,P,S) — КС-грамматика.

Выгход: G’ = (VN, VT, P’, S’) — КС-грамматика, эквивалентная исходной.

Метод: Пусть S’ — символ, не принадлежащий ни алфавиту нетерминалов, ни алфавиту терминалов.

Положим G’ = (VN и , VT, P’, S’), где P ‘= P/ и .

3. ПОЛУЧЕНИЕ РЕГУЛЯРНОГО ВЫРАЖЕНИЯ ПО КС-ГРАММАТИКЕ

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

По следствию из теоремы С.К. Клини [5], если язык регулярный, то он может быть представлен регулярным выражением, то есть конечной формулой с терминальными цепочками в качестве операндов и операциями конкатенации, объединения и замыкания, называемых регулярными. Наша задача — описать способ его получения, исходя из КС-грамматики, полученной с помощью предварительных преобразований (см. раздел 2).

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

Алгоритм 6. Исключение несамовстав-ленных нетерминалов

Вход: G = (VN,VT,P,S) — приведённая КС-грамматика без самовставлений.

Выход: регулярное выражение, представляющее язык L(G).

Метод: Введём отношение зависимости нетерминалов, определяемое правилами КС-грамматики следующим образом.

Пусть A ® a1Ba2, где A, B е VN, a1, a2е V*, есть правило грамматики. Будем считать, что нетерминал A зависит от нетерминала B.

Шаг 1. Построим граф зависимостей нетерминалов. В нём будет столько вершин, сколько нетерминалов в грамматике, по одной на каждый нетерминал. Вершины свя-

зываются ориентированными дугами от вершины А к вершине В в соответствии с отношением зависимости, определённым выше.

Шаг 2. С помощью топологической сортировки [6] распределим вершины графа зависимостей по уровням. В результате вершина 5 окажется на самом высоком уровне, а вершины, не зависящие от других, — на самом низком уровне (см. рис. 1).

Шаг 3. Выполним подстановки значений нетерминалов в виде регулярных выражений в правые части правил исходной КС-грамматики в порядке от минимального уровня (0) к максимальному (8) вдоль дуг в противоположном направлении.

Илон Маск рекомендует:  Что такое код bdosptr

При этом прежде чем выполняется упомянутая выше подстановка, леворекурсивное правило, то есть правило вида

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

а праворекурсивное правило, то есть правило вида

преобразуется к виду

Шаг 4. Алгоритм завершается, когда образуется регулярное выражение для начального нетерминала грамматики 5. Именно оно и является выходом данного алгоритма.

Замечание 1. Ясно, что шаг 2 алгоритма 6 выполним, только если в исходном графе зависимостей нетерминалов не существует циклов (см. [6]). Однако, петли допустимы.

Замечание 2. На графе зависимостей нетерминалов КС-грамматики (см. рис. 1) лево-сторонняя рекурсия отражается в виде петли.

Замечание 3. На рис. 1 против нетерминалов показаны правые части соответствующих правил исходной грамматики и/или результаты вышеупомянутых подстановок с учётом исключения левосторонней рекурсии, если таковая встречается, и других очевидных регулярных тождеств [4: гл. 5], однако без объяснения, как выбирать и применять регулярные тождества.

Покажем на следующем примере (рис. 1) как преобразовать КС-грамматику чисел языка программирования Алгол 68 [3] к регулярному выражению. Ради краткости,

понятия языка Алгол 68 (они указаны в фигурных скобках) обозначены нетерминальными символами А1-А15. В результате топологической сортировки нетерминалы распо-

Пример 1. Грамматика чисел в языке Алгол 68. Дана КС-грамматика G = (VN,VT,P,S), где V =

КомбинАторный Синтаксический анализ — II

2. Контекстно-свободные языки и грамматики

Это тоже просто (точнее, это просто на том уровне, на котором я это знаю и излагаю, хотите сложно — читайте Ахоульмана. Я его начинал, но пока не осилил).

2.1. Введение в проблематику

Сначала несколько тупых определений.

Алфавит — набор символов (конечное множество, если вам так проще).

Например:

  • <0, 1>алфавит из двух символов: 0 и 1
  • <'(', ')'>алфавит из правой и левой скобки
  • алфавит, состоящий из букв английского алфавита
  • <'(', ')', '+', '*', '-', '/', 0, 1, .. 9>алфавит, состоящий из скобок, арифметических операторов и цифр

Цепочка — конечная (возможно, пустая) последовательность символов некоторого алфавита (не уверен, что конечность обязательна). Примеры как-нибудь сами придумаете :) Пустая цепочка обычно обозначается буквой эпсилон. Я буду обозначать её как ».

Язык — множество «правильных» цепочек. Как именно задаётся правильность — да как угодно. Говорят, что язык определён над алфавитом. Т.е. типа: «.. пусть задан язык L над алфавитом Z. » (только по традиции, вместо Z должна быть заглавная сигма..).

Например:

  • <'0', '1'>язык из двух цепочек: ‘0’ и ‘1’
  • <'0', '1', ''>язык из трёх цепочек: ‘0’, ‘1’ и пустая цепочка
  • язык, которому принадлежат все возможные цепочки из символов 0 и 1
  • язык, над алфавитом <0, 1>, которому принадлежат все цепочки из 0 и 1, содержащие простое число (все помнят, кто такие простые числа?) единичек
  • язык над «арифметическим» алфавитом, содержащий все цепочки, являющиеся корректными арифметическими выражениями. Корректные с точки зрения синтаксиса, т.е. чтобы все скобки закрыты, а знаки с числами некоторым образом чередуются (например, не встречается подряд два знака умножения)
  • такой же как в предыдущем пункте. Но чтобы все выражения были вычислимы :) Т.е. чтобы нигде не получалось деления на 0.

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

2.2. Формальное определение и пара слов

КС-грамматика состоит из четырёх частей:

  • Множество терминальных символов T (алфавит языка)
  • Множество нетерминальных символов N (узнаете..)
  • Начальный символ S, принадлежащий N
  • Множество правил.

Правила имеют вид:

Где:

  • X принадлежит N
  • yi принадлежит либо N, либо T
  • n >= 0

Как это всё работает проще объяснять в сторону генерации. Тогда правила это просто подстановки. Алгоритм действий:

  1. Берём начальный символ S. Это наша исходная цепочка.
  2. Просматриваем текущую цепочку, находим в ней нетерминальный символ X (не обязательно первый по очереди, можно любой).
  3. Находим правила, содержащие этот символ слева. Т.е правила вида X = . выбираем одно из них. Если нет нет ни одного, то этой генерации каюк, цепочку нам уже не закончить. Если не закончить ни одну цепочку, то грамматика задаёт пустой язык.
  4. Подставляем вместо X в соответствующую позицию цепочки правую часть правила.
  5. Если в цепочке ещё есть нетерминальные символы, goto 2
  6. Конец.

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

2.3. Примеры

2.3.1 Первый

1. Берём S
2. Применяем первое правило. S -> aSb
3. Находим нетерминал.. Опять S! Применяем первое правило aSb -> aaSbb
4. Находим нетерминал.. Опять S! Применяем второе правило aaSbb -> aabb
5. Нет нетерминалов, конец.

Ну, в общем, понятно, что получается? », ‘ab’, ‘aabb’, ‘aaabbb’, . a n b n , ..

2.3.2. Второй

Правила:
S = E
E = M
E = E ‘+’ E
M = a
M = b
M = M ‘*’ M
M = ‘(‘ E ‘)’

Если я нигде не ошибся, должно получаться множество арифметических выражений со знаками + и * над буквами a и b. E от слова expression, M от multiplication. По классике вместо M пишут T, от слова term, но к сожалению T уже занята.

2.4. Деревья

Казалось бы, причём тут деревья? А оказывается, что очень даже причём. Процесс генерации цепочки аналогичен построению следующего дерева (все знают, кто такие деревья?):

  • Корень — S
  • При применении правила, заменяющего нетерминал X на цепочку y1y2. yn, в дерево добавляются узлы y1y2. yn, они становятся детьми узла, содержащего X.

В результате:

  • Крона (узлы, не имеющие детей) дерева — текущее состояние цепочки
  • К концу генерации в листьях находятся только нетерминалы и символы «пустая строка»
  • По дереву невозможно восстановить последовательность применения правил в разных ветках. Впрочем, этот порядок ни на что и не влияет.
  • Но вот каждую ветку можно восстановить точно

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

В качестве примечания: соответствие дерево цепочка всегда однозначно, дерево точно определяет цепочку. А вот соответствие цепочка дерево — не всегда. Например, в приведённой выше грамматике цепочку a+b+a можно получить двумя способами:
Отличия кажутся незначительными.. До тех пор, пока ‘+’ обозначает ассоциативную операцию, т.е. пока (a+b)+a = a+(b+a) В некоторых случаях это не верно даже для обычного плюса. Ещё смешнее получается если заменить ‘+’ на ‘-‘.

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

кс-языки — КС-грамматика

Нужно построить КС-грамматику, которая бы описывала язык, алфавит которого есть $%\<0,1\>$%, причем в каждом слове количество нулей больше количества единиц.

задан 15 Май ’16 19:24

Я, видимо, чего-то жутко не понимаю. Любой такой язык, в котором каждое выводимое слово содержит больше нуликов, чем единиц? Тогда почему не работает такая грамматика, например? «S ::= 100». Грамматика выводит одно-единственное слово. Оно удовлетворяет условию. Грамматика контекстно-свободная, то есть раскрытие нетерминала (аксиомы) не зависит от контекста…

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

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

1 ответ

Если в слове нулей больше, чем единиц, то слово или состоит из одних нулей, будучи непустым, или в нём есть одно из подслов 01, 10. Вычёркивая такое подслово, мы получим слово, в котором нулей по-прежнему больше, и так делаем до тех пор, пока не останутся только нули.

Следующая КС-грамматика будет порождать данный язык: $%S\to T0T$%; $%T\to\varepsilon$%; $%T\to T0T$%; $%T\to T0T1T$%; $%T\to T1T0T$%. Здесь мы стартуем от слова 0, и далее в любое место вписываем либо 0, либо 01, либо 10. Символ $%T$% обозначает место потенциального вписывания таких подслов. Ввиду того, что после вычёркиваний подслов вида 01, 10 получается слово из одних нулей, мы этим процессом охватываем все слова языка. То, что у всех порождаемых слов количество нулей больше количества единиц, очевидно.

Классификация формальных языков и грамматик по Хомскому

Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил.
Определение 1.9. Формальной грамматикой называется четверка вида:

где VN— конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);
VT — множество терминальных символов грамматики (обычно строчные латинские буквы, цифры и т.п.),VT ÇVN =Æ;
Р — множество правил вывода грамматики, являющееся конечным подмножеством множества (VT ÈVN)+ ´(VT ÈVN)*; элемент (a, b) множества Р называется правилом вывода и записывается в виде a®b(читается: «из цепочки a выводится цепочка b»);
S — начальный символ грамматики, S принадлежащий N.

Классификация грамматик в иерархии американского математика Хомского осуществляется по структуре правил вывода. В расширенной иерархии Хомского выделяется четыре типа грамматик.

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

Тип 1. Грамматика называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид a®b, где aÎ (VT È VN)+, b Î (VT È VN)* и |a| £ |b|. Расширение допускает не более одного e-правила, т.е. правила вида А®e, АÎVN.
Тип 2. Грамматика называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: , где и
Тип 3. Грамматика называется регулярной грамматикой (Р-грамматикой), выровненной вправо, если ее правила вывода имеют вид , где .
Грамматика называется регулярной грамматикой (Р-грамматикой), выровненной влево, если ее правила вывода имеют вид , где .

Расширение допускает единственное e-правило вида S®e, но в этом случае начальный символ грамматики S не должен встречаться в правых частях правил.

Определение 1.15. Язык L(G) называется языком типа k, если его можно описать грамматикой типа k, где k – максимально возможный номер типа грамматики.
Пример 1.7. Язык вида L=<0n1n | n>0> порождается КЗ-грамматикой (тип 1) G1 (пример 1.4) и КС-грамматикой (тип 2) G2= (<0, 1>, <S>, P2, S), где
множество правил вывода P2 содержит правила вида S® 0S1|01.
Так как не существует регулярной грамматики (тип 3), порождающей данный язык, то язык L является языком типа 2 или КС-языком.
Соотношение типов грамматик и языков представлено на рисунке 1.1.

Р – регулярная грамматика;КС – контекстно-свободная грамматика;

КЗ – контекстно-зависимая грамматика;
Тип 0 – грамматика типа 0.

Рисунок 1.1 – Соотношение типов формальных языков и грамматик

Пример 1.8. Примеры различных типов формальных языков и грамматик по классификации Хомского. Терминалы будем обозначать строчными символами, нетерминалы – прописными буквами, начальный символ грамматики – S.

а) Язык типа 0 L(G)= определяется грамматикой с правилами вывода:

б) Контекстно-зависимый язык L(G)=<anbncn | n³1> определяется грамматикой с правилами вывода:

в) Контекстно-свободный язык L(G)=<(aс)n(cb)n | n>0> определяется грамматикой с правилами вывода:

г) Регулярный язык L(G)=<w^ | wÎ<a, b>+, где нет двух рядом стоящих а> определяется грамматикой с правилами вывода:

Определение 1.16. Грамматики G1 и G2 называются эквивалентными, если они определяют один и тот же язык, т.е. .
Определение 1.17. Грамматики G1 и G2 называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов, т.е. .
Пример 1.9. Для грамматики G1 эквивалентной будет грамматика G2 = (<0, 1>, <S>, P3, S), где P2: S® 0S1|01, т.к. L(G1)=L(G2)=<0n1n | n>0> (пример 1.7).

Почти эквивалентной для грамматики G1 будет грамматика G3 = (<0, 1>, <S>, P3, S), где множество правил вывода P3 содержит правила вида S® 0S1|e, т.к. L(G3)=<0n1n | n³0>.

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

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

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

По классификации Хомского выделяют четыре типа грамматик.

Тип 0: грамматики с фразовой структурой

На правила грамматики с фразовой структурой не накладывается никаких ограничений: для грамматики вида G(VT,VN,P,S), V=VNVT правила имеют вид: ??, где ?V+, ?V*.

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

Практического применения грамматики, относящиеся только к типу 0, не имеют.

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

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

Контекстно-зависимые грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: ?1А?2?1??2, где ?1,?2V*, AVN, ?V+.

Неукорачивающие грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: ??, где . V+, |?||?|.

Структура правил КЗ-грамматик такова, что при построении предложений заданного ими языка один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Именно поэтому эти грамматики называют “контекстно-зависимыми”. Цепочки ?1и ?2в правилах грамматики обозначают контекст (?1– левый контекст, а ?2– правый контекст), в общем случае любая из них (или даже обе) может быть пустой. Говоря иными словами, значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречается.

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

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

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

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

Контекстно-свободные (КС) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: А?, где AVN, ?V+. Такие грамматики также иногда называют неукорачивающими контекстно-свободными (НКС) грамматиками (видно, что в правой части правила у них должен всегда стоять как минимум один символ).

Существует также почти эквивалентный им класс грамматик – укорачивающие контекстно-свободные (УКС) грамматики G(VT,VN,P,S), V = VNVT, правила которых могут иметь вид: А?, где AVN, ?V*.

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

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

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

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

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

Леволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: АВ? или А?, где A,BVN, ?VT*.

В свою очередь, праволинейные грамматики G(VT,VN,P,S),
V = VNVT могут иметь правила тоже двух видов: А?? или А?, где A,BVN, ?VT*.

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

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

Типы грамматик соотносятся между собой особым образом. Из определения типов 2 и 3 видно, что любая регулярная грамматика является КС-грамматикой, но не наоборот. Также очевидно, что любая грамматика может быть отнесена и к типу 0, поскольку он не накладывает никаких ограничений на правила. В то же время существуют укорачивающие КС-грамматики (тип 2), которые не являются ни контекстно-зависимыми, ни неукорачивающими (тип 1), поскольку могут содержать правила вида “А”, недопустимые в типе 1. В целом можно сказать, что сложность грамматики обратно пропорциональна тому максимально возможному номеру типа, к которому может быть отнесена грамматика. Грамматики, которые относятся только к типу 0, являются самыми сложными, а грамматики, которые можно отнести к типу 3 – самыми простыми.

Языки классифицируются в соответствии с типами грамматик, с помощью которых они заданы. Причем, поскольку один и тот же язык в общем случае может быть задан сколь угодно большим количеством грамматик, которые могут относиться к различным классификационным типам, то для классификации самого языка среди всех его грамматик всегда выбирается грамматика с максимально возможным классификационным типом. Например, если язык L может быть задан грамматиками G1и G2, относящимися к типу 1 (контекстно-зависимые), грамматикой G3, относящейся к типу 2 (контекстно-свободные), и грамматикой G4относящейся к типу 3 (регулярные), то сам язык должен быть отнесен к типу 3 и является регулярным языком.

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

Сложность языка убывает с возрастанием номера классификационного типа языка. Самыми сложными являются языки типа 0, самыми простыми – языки типа 3.

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

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

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

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

Далее языки с фразовой структурой рассматриваться не будут.

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

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

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

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

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

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

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

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

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

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

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

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

Статьи к прочтению:

Мастер класс №3Вся грамматика польского языка!

Похожие статьи:

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

Формальные грамматики и языки. Элементы теории трансляции. (издание второе, переработанное и дополненное) 1999 УДК 519.682.1+681.142.2 Приводятся…

Примеры грамматик и языков.

Замечание:если при описании грамматики указаны только правила вывода Р, то будем считать, что большие латинские буквы обозначают нетерминальные символы, S — цель грамматики, все остальные символы — терминальные.

1) Язык типа 0: L(G) = = 1>

2) Язык типа 1: L(G) = < a n b n c n , n >= 1>

4) Язык типа 3: L(G) = + , где нет двух рядом стоящих а>

Разбор цепочек

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

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

Рассмотрим основные понятия и определения, связанные с разбором по КС-грамматике.

Определение: вывод цепочки b Î (VT) * из S Î VN в КС-грамматике
G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Определение: вывод цепочки b Î (VT) * из S Î VN в КС-грамматике
G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

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

Например, для цепочки a+b+a в грамматике

можно построить выводы:

Здесь (2) — левосторонний вывод, (3) — правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.

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

Определение: дерево называется деревом вывода (или деревом разбора) в КС-грамматике G =

(1) каждая вершина дерева помечена символом из множества (VN È VT È e ) , при этом корень дерева помечен символом S; листья — символами из (VT È e);

(2) если вершина дерева помечена символом A Î VN, а ее непосредственные потомки — символами a1, a2, . , an, где каждое ai Î (VT È VN), то A ® a1a2. an — правило вывода в этой грамматике;

(3) если вершина дерева помечена символом A Î VN, а ее единственный непосредственный потомок помечен символом e, то A ® e — правило вывода в этой грамматике.

Пример дерева вывода для цепочки a+b+a в грамматике G:

Определение: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка a Î L(G), для которой может быть построено два или более различных деревьев вывода.

Это утверждение эквивалентно тому, что цепочка a имеет два или более разных левосторонних (или правосторонних) выводов.

Определение: в противном случае грамматика называется однозначной.

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

Пример неоднозначной грамматики:

В этой грамматике для цепочки if b then if b then a else a можно построить два различных дерева вывода.

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

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

В приведенном выше примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена:

S ® if b then S | if b then S’ else S | a

S’ ® if b then S’ else S’ | a

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

Однако можно указать некоторые виды правил вывода, которые приводят к неоднозначности:

(4) A ® aA | aAbA | g

Пример неоднозначного КС-языка:

Интуитивно это объясняется тем, что цепочки с i = j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j = k. Но тогда, по крайней мере, некоторые из цепочек с i = j = k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, что КС-язык L неоднозначный, приведен в [3, стр. 235-236].

Одна из грамматик, порождающих L, такова:

Очевидно, что она неоднозначна.

Дерево вывода можно строить нисходящим либо восходящим способом.

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

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

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

Преобразования грамматик

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

Определение: символ x Î (VT È VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

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

Вход: КС-грамматика G = (VT, VN, P, S)

Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

3. Если Vi ¹ Vi-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = Vi Ç VN;
VT’ = Vi Ç VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

Определение: символ A Î VN называется бесплодным в грамматике
G = (VT, VN, P, S), если множество < a Î VT * | A Þ a>пусто.

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

Вход: КС-грамматика G = (VT, VN, P, S).

Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).

Рекурсивно строим множества N, N1, .

3. Если Ni ¹ Ni-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = Ni; P’ состоит из правил множества P, содержащих только символы из VN’ È VT; G’ = (VT, VN’, P’, S).

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

Алгоритм приведения грамматики:

(1) обнаруживаются и удаляются все бесплодные нетерминалы.

(2) обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Замечание: если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

Задачи.

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

a) S ® T | T+S | T-S b) S ® aSBC | abC

T ® F | F*T CB ® BC

Цепочка a-b*a+b bC ® bc

2. Построить все сентенциальные формы для грамматики с правилами:

3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

a) S ® APA b) S ® aQb | e

c) S ® 1B d) S ® A | SA | SB

4. Построить грамматику, порождающую язык :

g) L = < w | w Î <0,1>+ и содержит равное количество 0 и 1, причем любая подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей>.

5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

a) S ® a | Ba b) S ® Ab

B ® Bb | b A ® Aa | ba

c) S ® 0A1 | 01 d) S ® AB

0A ® 00A1 AB ® BA

*e) S ® A | B *f) S ® 0A | 1S

A ® aAb | 0 A ® 0A | 1B

B ® aBbb | 1 B ® 0B | 1B | ^

*g) S ® 0S | S0 | D *h) S ® 0A | 1S | e

D ® DD | 1A | e A ® 1A | 0B

A ® 0B | e B ® 0S | 1B

*i) S ® SS | A *j) S ® AB^

A ® a | bb A ® a | cA

*k) S ® aBA | e *l) S ® Ab | c

6. Эквивалентны ли грамматики с правилами :

а) S ® AB и S ® AS | SB | AB

b) S ® aSL | aL и S ® aSBc | abc

7. Построить КС-грамматику, эквивалентную грамматике с правилами:

а) S ® aAb b) S ® AB | ABS

aA ® aaAb AB ® BA

8. Построить регулярную грамматику, эквивалентную грамматике с правилами:

а) S ® A | AS b) S ® A.A

A ® a | bb A ® B | BA

9. Доказать, что грамматика с правилами:

порождает язык L = = 1>. Для этого показать, что в данной грамматике

1) выводится любая цепочка вида a n b n c n (n >= 1) и

2) не выводятся никакие другие цепочки.

10. Дана грамматика с правилами:

a) S ® S0 | S1 | D0 | D1 b) S ® if B then S | B = E

D ® H. E ® B | B + E

H ® 0 | 1 | H0 | H1 B ® a | b

Построить восходящим и нисходящим методами дерево вывода для цепочки:

a) 10.1001 b) if a then b = a+b+b

11. Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Написать для этого языка КС-грамматику.

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

13. Написать КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc.

14. Построить грамматику, порождающую сбалансированные относительно круглых скобок цепочки в алфавите < a, ( , ), ^ >. Сбалансированную цепочку a определим рекуррентно: цепочка a сбалансирована, если

a) a не содержит скобок,

15. Написать КС-грамматику, порождающую язык L, и вывод для цепочки aacbbbcaa в этой грамматике.

16. Написать КС-грамматику, порождающую язык L, и вывод для цепочки 110000111 в этой грамматике.

17. Дана грамматика G. Определить ее тип; язык, порождаемый этой грамматикой; тип языка.

18. Дан язык L = <1 3n+2 0 n |>=0>. Определить его тип, написать грамматику, порождающую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки 1111111100.

19. Привести пример грамматики, все правила которой имеют вид
A ® Bt, либо A ® tB, либо A ® t, для которой не существует эквивалентной регулярной грамматики.

20. Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики для

Замечание:L =L1 * L2 — это конкатенация языков L1 и L2, т.е.L = < ab | a Î L1, b Î L2>; L = L1 * — это итерация языка L1, т.е. объединение È L1 È L1*L1 È L1*L1*L1 È .

21. Написать КС-грамматику для L=i 2 wi+1 R | i Î N, wi=(i)2 — двоичное представление числа i, w R — обращение цепочки w>. Написать КС-грамматику для языка L * (см. задачу 20).

22. Показать, что грамматика

E ® E+E | E*E | (E) | i

неоднозначна. Как описать этот же язык с помощью однозначной грамматики?

23. Показать, что наличие в КС-грамматике правил вида

где a, b, g Î (VTÈVN) * , A Î VN, делает ее неоднозначной. Можно ли преобразовать эти правила таким образом, чтобы полученная эквивалентная грамматика была однозначной?

*24. Показать, что грамматика G неоднозначна. Какой язык она порождает? Является ли этот язык однозначным?

25. Дана КС-грамматика G=. Предложить алгоритм построения множества

26. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли язык L(G).

27. Написать приведенную грамматику, эквивалентную данной.

a) S ® aABS | bCACd b) S ® aAB | E

A ® bAB | cSA | cCC A ® dDA | e

B ® bAB | cSB B ® bE | f

C ® cS | c C ® cAB | dSD | a

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

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

30. Доказать, что нециклическая КС-грамматика порождает конечный язык.

Замечание: Нетерминальный символ A Î VN — циклический, если в грамматике существует вывод A Þ x1Ax2. КС-грамматика называется циклической, если в ней имеется хотя бы один циклический символ.

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

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

Замечание: Циклический символ называется эффективным, если A Þ aAb, где |aAb| > 1; иначе циклический символ называется фиктивным.

Дата добавления: 2020-02-25 ; просмотров: 1393 | Нарушение авторских прав

Илон Маск рекомендует:  API для получения TimeZone временная зона часовой пояс.
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL