18-11-2020-Теория_формальных_грамматик_и_языков (1) (817642), страница 2
Текст из файла (страница 2)
Если при построении вывода цепочки α при каждомприменении правила заменяется самый левый нетерминальный символ, тотакой вывод называется левым или левосторонним выводом α. Если припостроении вывода α, всегда заменяется самый правый нетерминальныйсимволпромежуточнойцепочки,товыводназывается правым или правосторонним выводом α.Например, приведенный выше вывод цепочки i * i + i в грамматикеГ1.9 является левосторонним выводом. Следует отметить, что различнымвыводам цепочки i+i в грамматике Г1.9 соответствует одно и то жесинтаксическое дерево. Аналогичная ситуация имеет место и при выводецепочки i * i + i.Неоднозначные и эквивалентныеграмматикиСуществуют грамматики, в которых одна и та же цепочка может бытьполучена с помощью различных выводов.
Например, в грамматикеГ1.10 цепочка abc может быть получена с помощью двух различных выводов,и ей соответствуют два различных синтаксических дерева.Г1.10Vт = {a, b, c, d}, VА = {<I>, <A>, <B>},R = { <I><A><B>,<A>ac,<B>b,<B>cb}.Первый вывод этой цепочки имеет вид:1) <I><A><B><A>bacb,а второй можно получить так:2) <I><A><B><A>cbacbЭтим выводам соответствуют разные синтаксические деревья и разборы:Рис. 1.Следующая грамматика также допускает построение одной и той жецепочки с помощью двух выводов, имеющих разные синтаксические деревья.Г1.11:Vт = {0, +}, VА = {<I>},R = { <I>0,<I><I> + 0,<I>0 +<I> }Два вывода этой грамматики, порождающие одинаковые цепочки, имеютвид:1) <I>2) <I><I> + 00 + <I><I> + 0 + 00 + 0 +<I>0 + 0 + 0,0 + 0 + 0,а синтаксические деревья, соответствующие этим выводам, можноизобразить так:Рис.
2.Рассмотренное свойство грамматик называется неоднозначностью. Ономожет быть определено следующим образом.Определение. Цепочка языка L(Г) называется неоднозначной, еслидля её вывода существует более чем одно синтаксическое дерево. Еслиграмматика Г порождает неоднозначную цепочку, то она называетсянеоднозначной.Свойство неоднозначности является крайне нежелательным дляискусственных языков, поскольку оно не позволяет однозначным образомвосстановить дерево вывода по заданной цепочке языка.В общем случае можно сделать следующий вывод:1.
каждой цепочке, выводимой в грамматике, может соответствовать одноили несколько синтаксических деревьев,2. каждому синтаксическому дереву могут соответствовать нескольковыводов,3. каждому синтаксическому дереву соответствует единственный правыйи единственный левый выводы.Кроме того, следует подчеркнуть, что один и тот же язык может бытьполучен с помощью различных грамматикОпределение. Две грамматики Г1 и Г2 называются эквивалентными,ecли они порождают один и тот же язык, т.е.L(Г1) = L(Г2)Способы задания схем грамматик.Форма Наура-БэкусаСхема грамматики содержит правила вывода, определяющие синтаксисязыка, или, другими словами, возможные компоненты и конструкции цепочекпорождаемого языка.
Для задания правил используются различные формыописания: символическая, формаНаура-Бэкуса, итерационнаяформа и синтаксические диаграммы.В работах, связанных с рассмотрением общих свойств грамматик, обычноприменяют символическую форму задания правил. Эта форма быларассмотрена в предыдущем параграфе. Она предусматривает использованиев качестве элементов нетерминального словаря отдельных символов истрелки в качестве разделителя правой и левой частей правила.При описании синтаксиса конкретных языков программированияприходится вводить большое число нетерминальных символов, исимволическая форма записи теряет свою наглядность.
В этом случаеприменяют форму Наура-Бэкуса (ФНБ), которая предполагает использованиев качестве нетерминальных символов комбинаций слов естественного языка,заключенных в угловые скобки, а в качестве разделителя - специальногознака, состоящего из двух двоеточий и равенства. Например, если правила<L><L> и <L><E> записаны в символической форме, и символ<L> соответствует синтаксическому понятию "список", а символ <E> "элемент списка", то их можно представить в форме Наура-Бэкуса так:<список>::= <элемент списка><список>,<список>::= <элемент списка>Чтобы сократить описание схемы грамматики, в ФБН разрешаетсяобъединять правила c одинаковой левой частью в одно правило, правая частькоторого должна включать правые части объединяемых правил, разделенныевертикальной чертой. Используя объединение правил, для рассматриваемогопримера получаем:<список>::=<элемент списка><список>|<элемент списка>Итерационная формаДляполученияболеекомпактныхописанийсинтаксисаприменяют итерационную форму описания.
Такая форма предполагаетвведение специальной операции, которая называется итерацией иобозначается парой фигурных скобок со звездочкой. Итерация вида {a}*определяется как множество, включающее цепочки всевозможной длины,построенные с использованием символа a, и пустую цепочку.{a}* = {$, a, aa, aaa, aaaa,...}Иcпользуя итерацию для описания множества цепочек, задаваемыхсимволическими правилами, для списка получаем:<L><E> {<E>}*Например, описание множества цепочек, каждая из которых должнаначинаться знаком # и может состоять из произвольного числа букв x и y,может быть представлено в итерационной форме так:<I>#{x | y}*В итерационных формах описания наряду с итерационными cкобкамичасто применяют квадратные скобки для указания того, что цепочка ,заключенная в них, может быть опущена.
С помощью таких скобок правила:<A>x<A>y<B>z и <A>могут быть записаны так:<A>x[<A>y]<B>z.x<B>zСинтаксические диаграммыДля того, чтобы улучшить зрительное восприятие и облегчить пониманиесложных синтаксических описаний, применяют представление правилграмматики в виде синтаксических диаграмм.
Правила построения такихдиаграмм можно сформулировать в следующем виде:1. Каждому правилу вида <A>a1 | a2 |...| ak ставится в соответствиедиаграмма, структура которой определяется правой частью правила.2. Каждое появление терминального символа x в цепочке ai изображаетсяна диаграмме дугой, помеченной этим символом x, заключенным вкружок.Рис. 1.3. Каждому появлению нетерминального символа <A> в цепочкеai ставится в соответствие на диаграмме дуга, помеченная символом,заключённым в квадрат.Рис. 2.4. Порождающее правило, имеющее вид:<A>a1a2...anизображается на диаграмме следующим образом:Рис. 3.5.
Порождающее правило, имеющее вид:<A>a1 | a2 | ... | anизображается на диаграмме так:Рис. 4.6. Если порождающее правило задано в виде итерации:<A>{a}*,то ему соответствует диаграмма:Рис. 5.Число синтаксических диаграмм, которые можно построить для заданнойсхемы грамматики, определяется числом правил. Чтобы сократить числодиаграмм, их объединяют, заменяя нетерминальные символы, входящие вдиаграмму, построенными для них диаграммами.Правила 3-6 предусматривают, что в качестве цепочки a1 наобъединенной диаграмме могут быть использованы диаграммы построенныедля этих цепочек.
В качестве примера рассмотрим следующую грамматику сначальным символом <A>:Г1.14:Vт = { x, +, (, ) }, VA = {<A>, <B>, <C>},R = {<A>x | (<B>),<B><A><C>,<C>{+<A>}*}Рис. 6.Заменяя нетерминальные символы, соответствующими диаграммами,получаем объединенную диаграмму в виде:Рис. 7..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
