Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 86
Текст из файла (страница 86)
Множество Я является также магазинным алфавитом распознавателя Ма. Конфигурация распознавателя Мо имеет вид (г), гпь, у8), где гоЕХе, уб 14*, $(ХО 6. Далее в пунктах (!), (2) п (3) определяется один такт работы синхронного распознавателя. Эти пункты аналогичны соответственно пунктам (а), (б) и (в, г) в определении КС-диаграммера. Однако существенное различие состоит в том, что, во-первых, состояниями здесь служат множества вершин, во-вторых, даже из одной вершины возможен одновременный переход за один такт по нескольким дугам и, в-третьих, синхронный распознаватель сразу определяется как детерминированный автомат, тогда как диаграммер становится детерминированным, вообще говоря, при дополнительных условиях (например, если выполнено условие разделенности).
Пусть дана конфигурация (д, агв3, уб), где а Е Х, либо а =. гв =. е. (1) Если множество а содержит вершину, из которой выходит дуга, помеченная паХ, то (д, агв$, уЦ) — (д', гп$', уй) где д' — — ((а, 1)~ дуга, выходящая из (д, 1)Ед и помеченная а, ведет в (41, 1)). г) ь-диаграымер, упоминаемый и упр. 18, тоже может следить аа ие сколькими аынолами а подходящей Ьй-граыматике, по делает ато ме меиее „прямым" способом. 41а ДОПОЛНЕНИЕ (2) Если условие в (1) не выполнено, но а содержит вершину, нз которой выходит дуга, помеченная нетерминалом, то (а, агв$, уй)'„— (а', агой, а"уй) где ~!'=((г(л, 1)) из (г(, 1) Ед выходит дуга, помеченная А) н 4' = ((с(, 1) ( из (г(, 1) Р д выходит дуга, помеченная нетерминалом). (3) Если не выполнены условия ни в (!), ни в (2), ио д содержит заключительную верп1ину или вершину, из которой выходит дуга, помеченная е (обозначим через а множество этих вершин), то (Ч ать, 73) ~ — (9', ать, у'3) где у=ч 7 и Ч =((г(, !) ~ из (с( г) Еа" в ф, /) ведет дуга, по- меченная А и д содержит вершину диаграммы г(„), языком, распознаваемым синхронным распознавателем МО, назовем множество (-(Мо)=(гвЕХ'3(((г(в 1)) гмЭ $)) — *(((дз, й)), Э, Э)) где (г(в, й) — заключительная вершина начальной диаграммы с(в.
Пример 8. Рассмотрим синхронный распознаватель Мо„со- ответствующий КС-грамматике 6а с правилами 5 А)В А — аАЬ)е  — аВс!в Его КС-диаграммы изображены на рис. Д.З. Для входной це- почки аЬ3 распознаватель Мв, сделает такую последовательность тактов: (((г(в 1И, аьь, Э) ) ((Фл, 1), (г(в, 1)) аЬЭ, 5) ) — (((г(л, 2), (г(в, 2Н, ЬЭ, ((г(в, 1)) й ) — (((с(л, 1), (г(з, 1) ), Ьб, ((г(л, 2), (г(з,2)) ((г(в, 1))$) ) — (((г(л, 3), (г(а, 3)), Ь5, (((в, 1))Э) )-(((длг 4)), 8, ((д„)))8) ~ (((г(~ 2)) $ 5) Нетрудно убедиться, что С(Мп,) =В(6,) =(ааЬи(а~0) () (а"с" ) и О). Распознаватель М назовем адекватным (грамматике 6), если ь(М ) =В(6). Упр. 19. Покажите, что если синхронный распознаватель Мо адекватен грамматике 6, не содержащей бесполезных нетер- мииалов, то 6 не леворекурсивна. 14а 419 Гл а. ОднопРОходныи синтаксический АнАлиз Бвз ВОВВРАтОВ -, з двтермнниновлнныя восходящни сннтдксическнп дндлнз Упр.
20. Покажите, что если 6 — псевдоразделенная грамма тика, то соответствующие простой МП-распознаватель А(о и сии хронный распознаватель А4о эквивалентны (и, значит, если 0 слаборазделениая грамматика, то Мо адекватен 6). Из упр. 20 и 3 следует, что проблема распознавания адекватности синхронного распознавателя неразрешима, Заметим еще, г на и в 8 Рнс. Д.з. КР-днагразсмы синхронного распознавателя. что переход от синхронного распознавателя к соответствующему анализатору нетривиален: для получения разбора может понадобиться еще один проход (об этом см. в (Алгол 681).
5.2. ДЕТЕРМИНИРОВАННЫЙ ВОСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ В предыдущем разделе мы рассмотрели класс грамматик, для которых возможен детерминированный нисходящий синтаксический анализ с чтением входной цепочки слева направо. Существует аналогичный класс грамматик, для которых тоже возможен детерминированный анализ с чтением цепочки слева направо, но анализ восходящий.
Они называются 1К-грамматиками и их изложение будет во многом параллельно изложению 1г.-грамматик предыдущего раздела. 5.2.1. Разбор с помон(ыо детерминированного алгоритма типа вперенос — свертка» В гл, 4 было показано, что восходящий разбор можно провести, чередуя свертки и переносы, с помощью двух магазинов Разбор типа „перенос — свертка" состоит в переносе входных символов в магазин, пока в его верхней части не окажется основа.
В этот момент делается свертка основы. Если не попадается ошибок, то процесс повторяется до тех пор, пока вся входная цепочка не будет прочитана, а в магазине останется один начальный символ грамматики. В гл. 4 мы изложи,ти Ра ботающий именно таким образом алгоритм с возвратами, кото рый мог вначале неправильно выбирать свертки для некотор то ых 420 основ, но в конце концов делал правильные выборы. В этом разделе будет изучен больпюй класс грамматик, для которых ~~егда возможен детерминированный безвозвратный анализ такого типа.
Это 1.К(/г)-грамматики, образующие наиболее широкий класс грамматик, анализируемых естественным образом ~низу вверх с помощью детерминированного преобразователя с магазинной памятью. Буква з в названии БК(й)-грамматик указывает на то, что входная цепочка читается слева (!еН) направо, К вЂ” на то, что выдается правый (г(ЕЫ) разбор, а й— число входных символов, на которые алгоритм „заглядывает вперед". В дальнейшем мы исследуем разные подклассы 1К(к)-грамматик, в том числе грамматики предшествования и грамматики ограниченного правого контекста. Пусть ах — правовыводимая цепочка какой-то грамматики„ причем а — либо пустая цепочка, либо оканчивается нетерминальным символом.
Тогда а называется открытой частью цепочки ах, а х — замкнутой частью. Границу между а и х назовем рубежохг. Зги определения замкнутой и открытой части правовыводнмой цепочки не следует путать с аналогичными определениями законченной и незаконченной части левовыводимой цепочки. Алгоритм разбора типа „перенос †сверт" можно рассматривать как программу расширенного детерминированного МП- преобразователя, который проводит разбор снизу вверх. Для данной входной цепочки го МП-преобразователь моделирует в обратном порядке ее правый вывод. Допустим, что В=а, О,а,~,...=р,а„— --гэ — правый вывод цепочки пг.
Каждая правовыводимая цепочка аг распределяется в памяти ДМП-преобразователя так, что ее открытая часть хранится в магазине, а замкнутая — на входной ленте справа от головки. Например, если а,=аАх, то аА будет в магазине (причем А — верхнии символ), а х — зто еще не прочитанная часть первоначальной входной цепочки. ДопУстим, что аг а = УВЗ и на шаге а,;О,а; пРименено правило В - ру, причем ур = аА и уг =-х. Имея в магазине цепочку аА, МП-преобразователь перенесет несколько (возможно, ни одного) символов с левого конца цепочки х в магазин, пока не обнаружит правый конец основы цепочки а;.
К этому моменту в магазин будет перенесена цепочка у. Затем МП-преобразователь должен локализовать левый конец основы, Как только он это сделает, он заменит основу (здесь ею будет цепочка ру), занимающую верхнюю часть магазина, подходящим нетерминалом (здесь иетерминалом В) и выдаст номер правила  — ()у. Теперь в магазине окажется уВ, 421 ГЛ. З.
ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ а г образует непрочитаииую часть входа. Зти цепочки явля1отся соответственно открытой и замкнутой частями правовыводимой цепочки я;,. Заметим, что основа цепочки яАх никогда не может лежать целиком внутри я, хотя оиа может быть полиостыо внутри х, т. е. я,, может иметь вид яАх,Вх, и к ией можно применить правило вида  — Ч, где х,их, =- х, чтобы получить я,.
Так как цепочка х, может быть очень длинной, то может потребоваться много операций переноса, прежде чем я; будет сведена к я,, Итак, в ходе разбора алгоритм типа „перепое †сверт" должен принимать репзеиия трех типов. Во-первых, перед каждым шагом надо определить, переиести ли в магазин входиой символ или делать свертку. Это решение фактически состоит в выяснении того, где в правовыводимой цепочке находится правый коиеп основы. Второе и третье решения надо принять после того, как локализован правый конец основы. Как только становится известиым, что в верхней части магазина образовалась основа, нужно локализовать в магазине ее левый коиец.
Затем, когда основа уже выделена, падо найти подходящий иетермииал, которым следует ее заменить. Грамматика, В которой никакие два различные правила ие имеют одинаковых правых частей, называется детерминированна (или однозначно) обратимой или просто обратимой. Иетрудпо показать, что каждый коитекстно-свободиый язык порождается по крайней мере одной обратимой КС-грамматикой. Если грамматика обратимая, то выделенную в правовыводимой цепочке основу можно заменить в точности одним иетермииалом. Однако многие полезные грамматики ие обратимы, так что в общем случае пам нужен какой-то механизм для определеиия того, каким иетермииалом заменить осиову. Пример $.21.
Рассмотрим грамматику 6 с правилами (1) 5 — Ба5Ь (2) Б — е и правый вывод 5 ~ Ба5Ь ~ Ба5аБЬЬ .=Р БПЯаЬЬ ~ Баа66 =; ааЬЬ Разберем цепочку ааЬЬ, используя магазин и применяя операции переноса и свертки. Символ $ будет служить концевым марке" ром входной цепочки и диа магазина. Работу алгоритма разбора типа „перенос †сверт" опишем в терминах конфигураций, представляющих собой тройки вида (яХ, х, и), где з з детеРИИНИРОВАИИЫЙ ВОСХОдящип синтАКсичРСКНЙ АНАЧИЗ (1) яХ вЂ” содержимое магазина, причем Х вЂ” верхний символ; (2) х †непрочитанн часть входной цепочки; (3) и †вых к дапиому моменту.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
