Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 45
Текст из файла (страница 45)
Следовательно, над алгебраической системой (Уе, О, !) мы можем свести зти продукции к матричной схеме Х ХА!В в М(п, (Уе, О, !)), или, ааписывая альтернативный оператор ! как +, к схе- ме Х ХА+В в М'!и, (У*, О, +)). По аналогии с простым (нематрнчным) случаем, о кото- 293 ром будет более подробпо сказано в гл. 9, скажем, что Х ВУ, где У -АЪ'+1, а 1 определяется на (Уэ, ОЭ, +) как Х. Х, ЛМ ! Х, А„. ! Х, АМ! В1 хв= хв= хв= 0 -«Рх Е -«вва Р -«вэр Ед ! Рз Рэ Ед ! Рг ! вв, Итак, Хэ — ~~Э ~ВэУэь Поэтому э «Х ~эУж = ~эУю = во~ зв — «юУзз Р «юУэз Уе = Х.4вэ~ ы + 1вв', следователыщ.
Уп- хуп!аую!РУз~!Л, Ум - хум ! а1 м ! РУэз, 1 13 в" х 1 !э ! а 1 23 ! Р 1 зэ~ Узв руп ! ЧУзн Узэ «УУ!2 ! ЯУ32 ! Лв Узз уувз ! ЧУзз, Узв- зум ! сУю ! гуэп Уэз - з Угз ! сузз ! г1'зю Уэз - з Увэ ! сузз ! гУэз ! Л. В етом примере преобразования проивзодят ненужные нетерминалы; удаляя их, получаем Р- эсУэвв 294 ((Л), если ! = у, 1" —.— ! И, если Пример 4.4.
Предположим, что 8=11 и С имеет следующие продукции: П Пх! Еу(Рз, Е- Па!Рс, Р - Рр ! Ед ! Рг ! лв. Таким образом, используя общую схему, получаем уз< - зу«! сум ! гГз<, Уп - хуп ! а Уа< ! р Ум ! Л, Уа< Ууп ! Ч»а! ° Изменяя соответствующим образом выела, получаем Р .<сУ, з зК!сЬ(гУ, К - хК ! а<. ! Р1 ! Л, Р=уК! уУ. <1тобы нагляднее показать степень трансформации, приведем здесь дерево грамматического разбора строки в<ссдзауха для первоначальной грамматики (рис.
8АО,а) и модифицированной (рис, 8АО, Ь) грамматик. Л . ВАО Удаление левых рекурсий обеспечивает, если это возмол<но, вывод строки, начинающейсн с требуемого терминального символа; однако это не гарантирует, что мы получим только одну такую строку, и, следовательно, мон<ет случиться, что ыы пойдем неправильным путем. Пытаясь избел<ать неправильных последовательностей грамматического разбора, мы моя<ем явно использовать манипуляции, у>не встречавшиеся при предыдущих преобразованиях.
Этот процесс казывают левой факторизацией. Процесс требует, чтобы были проведены продукции, включающие в левую часть данный нетермпнал. Затем расширвют все правые части и те, которые начинаются с общей подстроки над Т, собирают вместе. П р и м е р 4.5. А - хуВ ! хуВС ! уР<) ! ухУ ю~А хуВ(Л ! С) ! у(РЯ ! ху) А хуВ.!< ! уАа, 29з где А ~ - Л! С, обычно записываемое как С ! Л, и Аз-РО) Г У' Заметим, что мы вновь можем ввести Л-продукции. Однако если в настоящий момент нет Л-продукций, то в заключительных левофакторизованных продукциях п грамматике не будет левых рекурсий. В атом случае следующий символ входной строки можно использовать для того, чтобы непосредственно определить, какие альтернативы надо использовать для расширения нетерминалов в сенгенциальяую форму.
Если Л-продукции встречаются в явном виде, то это вызывает затруднения. В силу того что Л является ведущей подстрокой каждой строки над произвольным алфавитом, оиа всегда совпадает с началом строки задавая, и, следовательно, никакие последующие альтернативы никогда ие будут рассматриваться. Здесь иет возможности входить в полный анализ проблемы, однако заметим, что если С (1г', Т, Р, 5) и мы определяем а) Г1КЯТ(а) = (х: а =;-хр, хек Т, раиУз~ б) ГОП.О% (и) = (х: Б =:.
Тихб, з а= Т, уб еи У*1, и если для каждой продукции Х- п~! аз! ... ! а„ а) Г)КЯТ(а,) П Г1КБТ(и ) = О, (зь1 б) Х=~.Л, то Г1ИЗТ(Х) () ГО1Д 0%(Х) Э. В атом случае С можно использовать для предсказывающего анализа (см. рис. 8.9, б). В таком аналиае можно проверять альтернативы в произвольиом порядке, ие применяя Л-выводов, пока все другие возможности ие исчезли.
Следующий пример иллюстрирует этот процесс. Пример 4.6. Предположим, что единственной продукцией в грамматике является С- эСх) Л. Попытаемся провести грамматический разбор строки «ххю Строка отбрасывается, хотя она и законна, потому что мы вынуждены применить первую продукцию дваж- 296 ды, порождая таким обрааом неправильное продвижение, поскольку ха Г!ВЭТ(С)д ГОгЛОЮ(6) и С-+ Л, Это графически изображено па ряс. 8 тт. Использование грамматики С- ххС! Л (рис.
8А2) не вызывает никаких трудностей в грамматическом разборе, потому что сейчас хФгО(ЛО%(С). Х С //~ С 1 Ф и Я Ркс. 8А2 Рвс. 88$ а) А=~ АуА; б) А=~аА~А(); в) Ас аА(аАРА; г) Ас А при (ш(УЦ Т)е и а, р ш(У 9 Т)+. 297 Перед тем как завершить параграф, упомянем другой основной метод грамматического разбора — снизу вверх, в котором продукции применяют назад, пытаясь свести строку задания к Я (см. ркс, 8.9, с).
Этот метод применяют более широно по сравнению с методом сверху вниз; используя некоторые модификации этого метода, можно повысить эффективность грамматического разбора. Упражнение 8А. 1. Модифицировать грамматику, продукции которой даны ниже, таким образом, чтобы она не была леворекурсивной: А - Вх 1 Сг! ш, В- АЬ! Вс, С- Ах! Ву! Ср, 2. Пусть 6 (У, Т, Р, Я) является КСГ и символ А шУ не является бесполезным символом б. Показать, что существование одного из следующих выводов в 6 влечет за собой неоднозначность 6: 3. Определить Л-свободную КСГ, вквивалентпую КСГ и определенную как С =((Я, (о, Ь), Р, Я), где Р М- аВЬЯ! ЬВаЯ(Л).
4, Пусть б .((А, В, С, Э, Е, В), (а, Ь, с), Р, Б), где Р (Я А~ВА С!ЭВ 6!ВС- Я!а!Л, Р- Я!Ь,В- Я!с!Л), Найти приведенпую грамматику, эквивалентную б, б 5. Грамматики операторного предшествования Важное подмножество КСГ содержит к себе так называемые операторные ерамжатили. Это грамкаткки, в которых все продукции такие, что никакие два нетермннала не являютсл смел~ными в любой правой части, п, следовательно, лежащий между ними терминал можно представить как оператор (хотя не обязательно в арифметическом смысле), Попытаемся определить отношения предшествовання на множестве Т0(~-, -(), где )- и -( суть поные символы, которых пет в «' и которые ограничивают «предложение», Правила определим следующим образом: 1. а-Ь, если А - аа~Ь1ыР; вкось и, т««г'«и б«в ш ДГ Ц (Л), 2. а( Ь,если А - ааВЬ««Р; вдесьВ=ьубб, у~Л'0(Л) и а, б, бы г'«.
3. а >Ь, если А ~ аВЬбы Р; здесьВ~ уаб, бывай 0 (Л) и а, р, 1 ю г'«, 4, (- < а, если Я~аар, а~и У () (Л), реиЛ*, 5. а )-(, если Я~аар, реп Л' () (Л), авиа*. Символы °, ' и > обозпачают отношения предшествования (читается как «виеет меньшее старшинство, чем«, «имеет такое же стар~опнство, как«, «виеет большее старшинство, чем«); при условии что ие более од- ели ного такого отношения справедливо между двумя произвольными операторами из Т () ()-, -(), соответствующую операторную грамматику называют грамматикой операторного предшествованнл. Хотя она и является гораздо более сложной, чем другие виды грамматик, встречавшихся до сит пор, понятие предшествования может быть введено так, что будет совпадать с обычным старшинством арифметических операторов и будет расширено до операторов, действия которых важны с точки зрения вычислений, однако обычно считаются само собой разумеющимися при вычпслеппях «на бумаге».
Пример 5.1, Е- Е+Т(Т, Т- Т«Р!Р, Р- (Е)!х. Для втой грамматики отношения предшествовапня приведены в виде таблпцы на рпс. 8.13. е Рве. 8.13 Для того чтобы увидеть, что происходит в действительности, рассмотрим этап внутри вывода предложения (- х«(х+ г) — о Из правила 2 определений предшествования видно, что для символов «и ( имеем + Т-«Т*Р, Р=» (Е). Таким образом, выполняется отношение «( (, и поэтому поддерево Р должно быть вычислено перед вычислением Т «Р; следовательно, действие, связанное с «(», которым является удаление этой и парной к пеп закрывающая скобки, выполняется перед действием, обозначенным «»».
(Графнчесшт ситуацию»«он«но представить так, как зто сделано па ркс. 8.14, Здесь для правила 2 имеемА Та Та «,Е Р,р=Л,( Л,Ь (и б Е. Отсюда видно, что основная структура граммэтпк 299 операторного иредшествования является простой и естественной, однако выглядит сложной при записи пз-за общности правил.) Заменяя х целыми числами 2, 3 и 4, '' У1~ ! ь ю 1 Е 1 с Сиктакеи«ескак стссетура с Ойиеая срсСка яра Сирс Л а Аритиетикескае структура Рнс. В,14 получаем )- 2и(3+ 4)). Записывая отношения предшествования под этим выражением, видим, как определяется порядок вычислений 2 < >: а) выберем члсло 2 н сохраним его в стеке: а ( 3 +, « < >1 б) аналогично удалим 3 пз выражения и поместим в стек: а ( + 4 ), « « >; в) с 4 поступим подобным образом: )- * ( + ) « < >; д) отбросим скобка: -Ь < ° >; г) выполним сложение двух верхних элементов в стеке и результат оставим там же; удавим символ +1 ( ) « е) произведем умножение двух верхних элементов стека, оставляя результат в стеке; удалим символ е: ж) останов нз-за отсутствия отношений предшествования; ответ находится в стеке.
Конечно, вместо выполнения арифметических операпий мы могли бы породить код и после этого вычислить выражение — это как раэ то, что сделал бы компилятор. У п р а ж н е н и е 8.5. $. В проведенном ранее обсуждении привлекаемая семантика принималась само собой разумеющейся, однако она была тесно переплетена с грамматической структурой. Показать, что каждая нэ следующих грамматик является грамматикой операторного предшествования, и исследовать, как ее внутренняя семантика отличается от обычных соглашений: Р~ !Е- Е>Т!Т,Т- Т+Р)Р,Р (Е)!з), Рз ° (Е- Т+Е! Т вЂ” Е! Т, Т- Т ° Р ! Р, Р- (Е)! л). гллвл в КОНЕЧНЫЕ АВТОМАТЫ Автоматом является устройство, управляющее и контролирующее само себя.
Обычный компьютер с программой способен прв достаточпом запасе зпвргии контролировать сам себя и, следовательно, является автоматом. Как таковые, компьютеры изучались много лет, однако более естественно рассматривать программу и машину, в которой ока содержится, как отдельпые комвопекты. Копечпо, для выполпепия вычислений нам яунзва пе только программа, но и машина, па которой вти вычислепия могут выполняться. Однако здесь мы пе стремимся приступать к детальпому изччекию теории вычислений, поэтому, за исключением тех случаев, где зто необходимо дчя полноты, мы ограничим наше зикмапие математическим описанием некоторых конечных машин.
Несмотря па зги аамечапия, мы начнем (в $ $) с общего введения, которое показывает границы того, что машины могут выполнять. Далее ($ 2) мы изучим математические модели устройств (обычпо их малые фрагмепты), а затем (в ~ 3) сзязалпу|о с зтвм алгебру. $ 3. Общие понятия Все используемые ка практике компьютерпые устройства ограничены (некоторым образом) количеством ипформации, которую опи могут храппть,-опи кокечпы. Цель данного параграфа — показать, как можно делать утверждеппл о программах без утомительпого рассмотрения сиптакспческпх деталей; затем мы продемонстрируем, что даже при отсутствии ограпичепил па размеры памяти существуют задачи, которые кельвя решить. 1.г.
Упиверсалькая машипа. Несмотря па испольво вапие мпогочислепвых различпых типов даппых и мвожеств символов нпутрп реальных программ, для теоретического изучеппя достаточно ограппчизьсл рассмотропием программ, которые действуют на и~он<естве р Хй 0 (0), Вто разносил з по пэучеппю программ, вычисляю. 302 щих теоретико-числовые функции, которые будут введены в з 2; паша непосредственная задача — описать идеализированный компьютер, позволяющий запоминать элементы р, с которыми можно осуществлять преобразования, п дать детальное описание гого, как могут гз быть представлопы программы для гь машины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
