Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 22
Текст из файла (страница 22)
е. левую часть этого правила, в качестве своей подцепочки, то можно образовать новую цепочку ()„заменив одно вхождение АВ в а на СВЕ. Тогда говорят, что р выводима (или выводится) в данной грамматике. Например, если цепочка РСАВН выводима, то РОСОЕВ тоже выводима. Язык, определяемый грамматикой,— это множество цепочек, которые состоят только из терминалов и выводятся, начиная с одной особой цепочки, состоящей из одного выделенного символа, обычно обозначаемого В, Соглашение.
Правило (ех, ()) будем записывать в виде а— Дадим теперь формальное определение грамматики, Определение. Граммшпикоа называется четверка б =(Х, Г, Р, В), где (1) 1ч' — конечное множество неперминальиых сииаолов, или нетармииалав (иногда называемых вспомогательными символами, синтаксическими переменными или понятиями); х) В соответствии с нашим соглашением об обозначеннях алфавитов этот символ является пропнсной греческой буквой „ню", хотя читателю, вероятно, захочется пронзпоснть его как „эн".
205 ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ (2) Х вЂ” не пересекающееся с 1ч' конечное множество терминальных символов, или терминалов; (3) Р— конечное подмножество множества ()ч! Ц ~)' г ! ( ч () ~)* Х (1ч! О Х)* (элемент (а, (!) множества Р называется правилом (или продукцией) и записывается в виде гх — ()); (4) 5 — выделенный символ из )ч(, называемый нгггальным (или исходным) символом. Пример 2.1. Примером грамматики служит четверка 6;= =((Л, 5), (О, 1), Р, Я), где Р состоит из правил 5 — + ОА! ОА ООА1 А — е Нетермниальными символами являются А и 5, а терминальны- ми — 0 и 1.
к г. оп<козы оп~еделения языков которых ге=а„сгг г=!гсгг при 1 =г(й и аь=(). Эта последовательность цепочек называется выводом длины к цепочки () из цепочки а в грамматике 6. Отметим, что а=о*р тогда и только тогда, когда и=хгг() для некоторого г)0, и гг=>+(з тогда и только тогда, когда а=агр для некоторого г') 1, Пример 2.2. Рассмотрим грамматику 6; из примера 2.! и вывод 5=-.:>ОА1=чгООА!1=Ф0011. На первом шаге этого вывода 5 заменяется на ОА1 в соответствии с правялом 5 — ОА!.
На втором шаге ОА заменяется на ООА1, и иа третьем шаге А заменяется на е. Можно сказать, что 5=!ь'0011, 5=„-' '0011, Я=о" 0011, и что 0011 принадлежит языку Т.(6г). Можно показать, что В(6,) = (О" 1" ( п~ 1) Доказательство оставляем в качестве упражнения. (') Соглашение, Для обозначения и правил а а- Грамматика определяет язык рекурсивным образом. Рекурсивность проявляется в задании особого рода цепочек, называемых выводимыми г!епогками грамматики 6 — -(!ч', Х, Р, 5): (1) Я вЂ” выводимая цепочка.
(2) Если сгру — выводимая ггепочка и !3 — б содержится в Р, то абу — тоже выводимая цепочка. Выводимая цепочка грамматики 6, не содержащая нетерминальных символов, называется терминальной цепочкой, порождаемой ераммаогнкой 6. Язык, порождаемый ераммитикой 6 (обозначается ь'(6)),— это множество терминальных цепочек, порождаемых грамматикой 6. Теперь введем терминологию, которая окажется далее полезной. Пусть 6 = (Х, Х, Р, 5) †граммати.
Определим отношение ~о на множестве (Х () Х)" (Ч =>оф читается ф непосредственно выводима из гр) следующим образом: если а(!! — цепочка из ()ч((1Х)' и () — б — правило из Р, то гхру=>оабу. Транзитивное замыкание отношения =>о обозначим через =>о (гр ~' ф читается: гр выводима из гр нетривиальным образом), а его рефлексивное и транзитивное замыкание — через =>о (гр =О" р читается: ф выводима из Вг).
В тех случаях, когда из контекста ясно, о какой грамматике идет речь, нижний индекс 6 будем опускать. Таким образом, С (6) =(ш(го~ Х*, 5=>*го). Через =>' будем обозначать !г-ю степень отношения =>. Иначе говоря, сг =>" (), если существует последовательность а„а„..., сг„, состоящая из й+1 цепочек (не обязательно различных), для !об а удобно пользоваться сокращенной записью а рч((),!...(р„ Примем еще следующие соглашения относительно различных символов и цепочек, связанных с грамматикои: (1) а, о, с, й и цифры О, 1, ..., 9 обозначают терминалы; (2) А, В, С, О, 5 обозначают нетермииалы; 5 — начальный символ; (3) У, У,..., е обозначают либо нетерминалы, либо терминалы; (4) сг, й, ...
обозначают цепочки, которые могут содержать как терминалы, так и нетерминалы; (б) и, о, ..., з обозначают цепочки, состоящие только из терминалов. Эти соглашения распространяются также и на буквы с нижними и верхними индексами. Мы не будем напоминать об этих соглашениях, когда рассматриваемые символы им удовлетворяют. Таким образом, грамматику, все терминалы и нетерминалы которой подчиняются соглашениям (1) и (2), можно определить, просто выписав все ее правила.
Например, грамматику 6, можно задать списком правил 5 — ОА1 ОЛ вЂ” ООА 1 А — е гот ГЛ. В. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Р ! СПОСОБЫ ОПРЕДЕЛЕНИЯ ЯЗЫКОВ В грамматике 6 Эта грамматика ' 10В Теперь нет необходимости говорить о множествах терминалов и нетерминалов или о начальном символе. Приведем еще примеры грамматик. Пример 2.3. Пусть 6=((<цифра>), (О, 1, .;., 9), (<цифра>- О)! )...(9), <цифра>). Здесь <цифра> рассматривается как единственный нетермннальиый символ. Е(6) — это, очевидно, множество, состоящее из десяти цифр.
Заметим, что Е(6) — конечное множество. Д Пример 2.4. Пусть 6,=((Е, Т, Р), (а, +, «, (, )), Р, Е), где Р†состо нз правил Е- Е+Т) Т Т- Т»Р(Р Р- (Е) )а Вот пример вывода в этой грамматике Е=ОЕ+Т ~Т+Т =>Р+Т ==.'«а+ Т =Ф а+Т»Р =>а+лР~а+а»Р =>а+а»а Язык Е(6,) представляет собой множество арифметических выражении, построенных из символов а, +, «, ( и ). Д Грамматика из примера 2.4 пе раз встретится нам в этой книге; мы всегда будем обозначать ее 6,, Пример 2.5. Пусть 6 определяется правилами 5 — аВВС ) аЬС СВ- ВС Ь — ЬЬ ЬС-Ьс СС вЂ” сс возможен вывод В =э аЗВС =.«ааЬСВС => ааЬВСС =:> ааЬЬСС =:ь ааЬЬсС =э ааЬЬсс порождает язык (а"Ь"с" ) п ~!).
(:) Пример 2.6. Пусть 6 — грамматика с правилами 5- С0 АЬ вЂ” ЬА С аСА Ва- ПВ С вЂ” ЬСВ ВЬ - ЬВ А0 а0 С вЂ” с В0 30 0 — е Аа аА Пример вывода в грамматике 6: В=РС0 =,"> аСА0 ~ аЬСВА0 -"Ф аЬВА0 ~ аЬВП0 =:;Р аЬаВ0 =~ ПЬаЬ0 =~ аЬаЬ Покажем, что Е(6)=(вю)вЕ(а, Ь)'), т. е. Е(6) состоит Яз цепочек четной длипы, составленных из букв а и Ь, причем первая половина каждой цепочки совпадает со второй половиной. Так как Е(6) — множество„то самый легкий способ показать, что Е(6) = (ияс ~ в ~ (а, Ь)'), состоит в том, чтобы показать, что (ияс ) ж Е (а, Ь)') ~ Е (6) и Е (6) ~ (и«с ) и Е (а, Ь)*). Чтобы показать, что (юю/гав(а, Ь)') с:-Е(6), надо показать, что каждую цепочку вида ии можно вывести из 8.
Простой индукцней можно доказать, что в 6 возможны такие выводы: (1) В=~СО. (2) Для и) О С ~" с,с,... с„СХ„Х„т... Х; — с„Х„Х„,... Х„ где для всех 1~(<п с;=а тогда н только тогда, когда х,=А, и с;=Ь тогда и только тогда, когда Х;=-В. (3) Х„... Х»Х,0 =~ Х„... Х,с,0 ~" «сгХ„...Х,0 с,с,...с„тХ„0 =О с,с,... с„,с„0 =Ф С«С«... С««С» Летали доказательства мы опускаем, так как они проверя ются непосредственно. 109 гл.
г. элементы теогии языков З.!. СПОСОБЫ ОПРЕДЕЛЕНИЯ ЯЗЫКОВ Ь(А)=А, Ь(В)=В б можно показать индукцией по то я можно представить в виде й (а) =Ь(Ь) =е, Для нашей грамматики т) 1, что если 5=>" а, с,с,...с„У'р$', где (1) с; для всех !=1, 2, (2) У вЂ” либо С, либо е; (3) р — такая цепочка из й(()) = с,с,...с,, н — либо а, либо Ь; языка (а, Ь, А, В»", что й(()) =-х„х„,...х,„ Х =А, если с;=а, н Х =В, если с =-Ь (! <)~н); (4) к' — либо В, либо е.
Детали индукции опускаем. Заметим, что все выводимые цепочки грамматики 6, состоящие лишь из терминальных символов, имеют вид с,с,... с„с,с,...с„, где с!Е(а, Ь» для всех !=1...,, н. Таким образом, Е(б) ~ ( (!Б Е (а, Ь»*». Наконец, заключаем, что Т.(б)=(ихв»и!Е(а, Ь»'», Е] !!о В выводе (2) из С выводится цепочка, составленная из букв а и Ь, за которой следует ее зеркальное отражение, составленное соответственно из букв А и В. В выводе (3) нетерминалы А и В перемещаются к правому концу цепочки, где А становится терминалом а, а В становится терминалом Ь, вступая в контакт с нетерминалом О, который действует как правый концевой маркер. Нетерминалы А и В могут превратиться в терминалы единственным способом- только передвинувшись к правому концу цепочки. При этом цепочка, составленная из букв А и В, будет обращена и совпадет, таким образом, с цепочкой букв а и Ь, выведенной из С в выводе (2).
Комбинируя выводы (1) — (3), получаем для и) О 5 =О' с,с,... с„с,с, с„ где с! 6 (а, Ь» для 1 ( !' = и. Итак, (и!ш ~ и! а (а, Ь»'» с=. ~ (6), Теперь покажем, что Л(6) ~ (иш~!БЕ(а, Ь»'». Для этого надо показать, что из 5 выводятся только те терминальные цепочки, которые имеют вид иге. Вообще говоря, показать, что грамматика порождает цепочки только данного вида (т. е. что она не может породить других цепочек), гораздо труднее, чем показать, что она может породить все цепочки данного вида. Здесь удобно задать два гомоморфизма д и 1!, удовлетворяющие условиям д(а) =-а, й(Ь) =Ь, д(Л) =д(В) =е 2Л.З. Грамматики с Ограничениями на правила Грамматики можно классифицировать по виду их правил.
Пусть 6 ††(Х, 1, Р, 5) †граммати, Определение. Грамматика б называется (1) криволинейной, если каждое правило из Р имеет вид А хВ или А х, где А, ВЕН, хЕ2*; (2) контекстно-свободной (или бесконтекс!иной), если каждое правило из Р имеет вид А — а, где А бМ, аЕ(Ь(1)Х)"; (3) контекстно-зависимой (или неукорачивающей), если каждое правило из Р имеет вид а — (), где )а»:.»(11. Грамматика, не удовлетворяющая ни одному из указанных ограничений, называется грамматикой общего вида (или без ограничений). Грамматика примера 2.3 праволинейная. Другой пример праволинейной грамматики — грамматика с правилачи 5 — 05»15»е Эта грамматика порождает язык (О, 1»'.
Важным примером контекстно-свободной грамматики служит грамматика примера 2.4. Заметим, что, согласно нашему определению, каждая праволинейная грамматика контекстно-свободная. В примере 2.5 грамматика, очевидно, контекстно-зависимая. Следует подчеркнугь, что определение контекстно-зависимой грамматики не допускает правил вида А — е, обычно называемых е-иравилал!и. Таким образом, контекстно-свободная грамматика, содержащая е-правила, не является контекстно-зависимой. Запрещение е-правил в контекстно-зависимой грамматике вызвано желанием гарантировать рекурсивность порождаемого ею языка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
