Карпов - Основы построения трансляторов (2005), страница 34

Операция с1ояге добавляет ситуации к множеству таких ситуаций, у которых точка стоит непосредственно слева перед некоторым нетерминалом Х. Добавляе- гго Глава б мые ситуации получаются из всех продукций грамматики, в левой части ко- торых находится этот нетерминал Х. с1овцге (М) с1о йод (для каждой ситуации <А-кхеХР> из М) ( Йог (для каждого правила грамматики Х вЂ >у) М = М~4<Х-+ау> 1; // Добавляем ситуацию <Х-+ау> к множеству М иЫ.1е (М изменилось); ге~ыгп М; Вторая операция до~о переносит точку после символа Л.

Эта операция соот- ветствует переходу синтаксического анализатора из одного состояния (си- туационного множества) в другое как только анализатор встречает на входе очередной символ Х анализируемой сентенциальной формы. до~о (М, Х) м1=0; /* вначале М1 — пустое множество */ йод (для каждой ситуации <А — кхеХР> из М) М1 = М1~ХА — нхХе~3>; ге~цгп с1ояцге (М1); Полный ЬК(0)-анализатор для грамматики б~,з представлен на рис. 6.4 в виде конечного автомата. Наличие единственной ситуации <А — «ае> в ситуационном множестве позволяет принять однозначное решение по выполнению редукции А с:= а, поскольку ситуация <А — «а>е свидетельствует о том, что конец соответствующей связки в анализируемой сентенциальной форме достигнут.

Очевидно, что построение ЬК(0)-анализатора требует формирования и анализа ситуационных множеств. Однако, после построения ЬК(0)-анализатора, Автомат в виде ситуационных множеств рис. б.4, а имеет три заключительных состояния (прямоугольники с двойной границей) по числу продукций грамматики: целью анализатора как раз и является определение того, в соответствии с какой из продукций выполнить очередную редукцию.

В этих заключительных состояниях ситуационное множество состоит только из одной ситуации вида <А — «ае>. Такие ситуации называются терминальными. Они и определяют нужную редукцию. Восходящие алгоритмы синтаксического анализа при выполнении им распознавания входных цепочек, ситуационные множества, которые составляют его состояния, уже не имеют никакого значения, важно только, в какие состояния при чтении промежуточной цепочки вывода символ за символом переходит анализатор. Конечный автомат, представляющий П(О)-анализатор для грамматики ббпр без указания ситуаций, составляющих состояния, показан на рис.

6.4, 6. а) б) Рис. 6.4. Ы(О)-анализатор для грамматики 8~ з. а) в виде ситуационных множеств и б) в виде конечного автомата ЕК(0)-автомат рис. 6.4 принимает на вход любую сентенциальную форму, выводимую в грамматике 66з. Попадание в заключительное состояние с терминальной продукцией свидетельствует о том, что при движении по сентенциальной форме мы достигли конца связки, и необходимо выполнить редукцию: последние символы сентенциальной формы (которые, конечно, совпадают с правой частью продукции) следует заменить на нетерминал, стоящий в левой части этой продукции.

При трансляции стоит задача восстановления последовательности сентенциальных форм от терминальной строки, подаваемой на вход распознавателя, 222 Глава 6 до начального символа. Очевидно, что это можно сделать, используя построенный нами автомат-распознаватель многократно.

Рассмотрим, как будет анализироваться распознавателем (см. рис. 6.4, о) терминальная цепочка ФааоссФ: 1. По входной цепочке ФааЬссд распозаватель остановится после символа Ь, в состоянии а4, указав, что символ о является связкой, и что он должен быть свернут к нетерминалу Я по правилу Ь' с== о. Полученная после свертки цепочка ФааЛссд — это в точности предпоследняя цепочка искомого вывода Я' ==> Ф,Я =~ ЯаЯсй ==> ЫааЯссЯ ==> Мааоссй. 2. Применим анализатор к новой сентенциальной форме ФааЯссФ. По ней автомат разбора (см. рис.

6.4, б), начав работу с начального состояния аО, остановится после первого символа 'с' в заключительном состоянии а7, требуя выполнить свертку' связки асс к нетерминалу Я по правилу Я с:= асс. В результате мы получаем Фа5сд — очередную промежуточную цепочку вывода нашей терминальной строки. 3.

Входная цепочка Фа5сФ приведет автомат из начального состояния аО снова в состояние а7; мы снова найдем подстроку асс как очередную связку — правую часть правила Я ==> асс, и должны свернуть ее к нетерминалу 5 по правилу 5 с== иаэс. В результате мы получим ФЯ вЂ” очередную промежуточную цепочку вывода нашей терминальной строки. 4. Эта новая промежуточная строка вывода переведет автомат (см. рис. 6.2, о) из начального состояния в заключительное состояние дЗ, которое потребует свертки всей цепочки 454 к начальному символу грамматики 5'. Теперь распознавание цепочки ФааоссФ закончено: мы нашли последовательно все промежуточные цепочки правого канонического вывода этой терминальной цепочки языка из начального символа У.

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

Дадим теперь определение того класса грамматик, которые допускают син- таксический анализ таким простым и эффективным методом. Определение 6.2. КС-грамматика С' является ЕК(0)-грамматикой, если не более одной ситуации вида <А — +ае> входит в каждое ситуационное множество построенного для нее 1 К(0)-анализатора. При этом условии 1.К(0)-анализатор позволяет однозначно принять решение о редукции связки в любой сентенциальной форме грамматики б, переходя 223 Восходящие алгоритмы синтаксического анализа в заключительное состояние после чтения последнего символа связки, т. е. той подцепочки, которую на данном шаге следует свернуть к нетерминалу. 6.3.2.

~.Й(К)-грамматики Построим 1.К(0)-анализатор для другой грамматики: бб 4 ° 0 ° У +ФЯ 1. Я вЂ” +аЛ'с 2. Я-+е Эта грамматика отличается от грамматики 66~ только одной продукцией— Я-+е. Начальное состояние 1.Й(0)-анализатора для б~4 не отличается от начального состояния автомата для грамматики С~бз. Соответствующее ситуационное множество [<У вЂ” +ада>1. Однако уже следующее ситуационное множество [<5' — +ФеЯ>, <Я-+вас>, <Я вЂ” +е>~ отличается качественно: среди ситуаций этого множества есть терминальная ситуация <5 — +а>.

Она говорит о том, что в данном месте промежуточной цепочки вывода возможна замена пустой цепочки на символ 5 в соответствии с продукцией 5 — и=.. Однако опа пе является единственной ситуацией в этом ситуационном множестве. Итак, здесь нельзя принять единственное решение о дальнейших действиях анализатора. Действительно, ситуация <5 — +е> говорит о том, что мы достигли конца (пустой) связки, и ее можно свернуть к Я. Однако другие ситуации говорят, что анализатор в данном состоянии анализа может также находиться в середине других связок.

Конечно, существует сентенциальная форма д 6, которая должна быть свернута к 4ЯФ. Но существуют и другие сентенциальные формы, например ФЛФ, ФаЛсФ, ФасФ и т. д., которые могут быть входными для нашего анализатора и при анализе которых мы попадем в то же состояние. Следовательно, после первого символа Ф на входе распознавателя мы не можем без дополнительного анализа однозначно принять решение о редукции — мы можем находиться не только в конце продукции Я-+е, но и в начале продукции Я-+асс или же в середине продукции У-+ФЯФ. Именно об этом и говорит ситуационное множество [<У-+ФеЯ>, <Я-+еаЛс>, 5-+е>1. Итак, грамматика 064 не является 1.К(0)-грамматикой.

Очевидно, что любая грамматика с а-продукциями не будет принадлежать классу ЬК(0). Во многих случаях для того чтобы принять решение о том„следует ли выполнить редукцию А ~ е при синтаксическом анализе таких грамматик, достаточно учесть правый контекст — следующие символы в анализируемой сентенциальной форме. Именно это и делает 1.К(1)-анализатор при 1 > О. Восходящие алгоритмы синтаксического анализа является то, что добавленный контекст очень сильно увеличивает число различных ситуационных множеств.

Однако этот контекст не всегда нужен. Фактически он нужен только для разрешения конфликтов именно в тех ситуационных множествах, которые содержат кроме терминальной ситуации вида <,4 — +ае> какие-либо другие ситуации, что не позволяет принять однозначное решение о возможности редукции в соответствии с терминальной ситуацией. Мы будем называть такую коллизию конфликтом. Встает вопрос, можно ли привлечь анализ контекста в ЬК(0)-анализаторе только в случае возникновения подобной неоднозначности и только для того ситуационного множества, в котором эта коллизия возникла'? Оказывается, это сделать можно, хотя и более грубо, чем в ЬК(1)-анализаторе.

В то жс время, для многих практических случаев даже такой грубой информации оказывается достаточно для разрешения конфликта. Именно эту идею реализуют анализаторы Я К(1с) (ялур, т. с. простой) и 1 АЬК(1с) (/огй-аЬесИ, т. е. с заглядыванием вперед). Общая идея построения этих анализаторов проста: для грамматики строится ЬК(0)-распознаватель, после чего при наличии конфликтов их пытаются разрешить непосредственно в месте их возникновения с учетом контекста, анализируя во входной цепочке следующие А: символов. Анализаторы Я.К(1) и 1 АЬК(1с) различаются только методом выявления возможности применимости редукции для терминальной ситуации в ситуационных множествах. Соответственно, Я.

К(1с)- и ЬАЬК(ф)-грамматиками называются такие грамматики, для которых соответствующие синтаксические анализаторы дают однозначное решение вопроса о выполнении редукции для каждой терминальной ситуации. Число состояний в этих двух типах анализаторов такое же. как в ЬК(О)-анализаторах, но учет контекста для разрешения конфликта позволяет расширить класс грамматик, для которых синтаксический анализ цепочек порождаемого языка проводится однозначно. Я К(1 )-анализатор для каждого ситуационного множества 1.К(0)-анализатора, содержащего конфликты, для разрешения вопроса о том, следует ли в распознавателе выполнить свертку Л с:= а по терминалыюй ситуации <А — +ае>, пытается разрешить анализом контекста — проверяет, какие терминальные цепочки длиной Й могут стоять после А во всех возможных сенте н циал ьн ых формах грам мати ки.