Теория синтаксического анализа, перевода и компиляции - Том 1 (Теория синтаксического анализа, перевода и компиляции)

ЛЕРйЕ0 г'. ЛНО Веи Те!ер!гопе ЕаЬогагог!еа, $пс. Мпггау Н!!!, й.,!, УЕРРЕЕУ О. !!ЕЕМЛН Перевод с английского В. Н . Агафонова Под редакцией В. М, Курочкина Ргеп11се-НЕИ, !пс. Епй!евой СИНЬ, Х.,1. 1972 ТНЕ ТНЕОКУ ОГ РАКЯХО, ТРА%Я.А'ПОДАЧ А1ЧВ СОМРП.1%О уо1ипге 1: РАК8!Р!О Оераг!п|еп! о', Е!есеиса! Епд!пееипЕ Рг!псе!оп !!и!гега!гу А.

АХО, ДЖ. УЛЬМАН ТЕОРИЯ СИНТАКСИЧЕСКОГО АНАЛИЗА, ПЕРЕВОДА И КОМПИЛЯЦИИ ~ОМ 1 Синтаксический анализ НЗДА ТЕЛ Ь СТВО «М Н Р> МОСКВА 1978 УДК 619.662Л+68К!42,2 Первый том фундаментальной монографии известных амери. капских ученых содержит основной мзтемзтический аппарат (в чзстиостн, теорию грзммзтнк и звтомзтов), краткий обзо п оляции, начала теории снитзксическн управляемого перевода и обстоятельное азложение методов синтаксического злго итмы а б анализа. Рассмотрены н снстемзтизированы почти все из звестиые и ко р р зборз.

Для некоторых из вих впервые деется полно б . е ность и оцев рректное описание. для большинства доказывается евивзется сложность. Прнвелеио большое иолнчесгво корректупражнений. Особен ность книги в том, что оиз трактует теоретические вопросы в связи с потребностямв реализации языков программирования, и этим онз отличается от книг по системному программированию. Книга предназначена тем, кто работает в области системного и теоретического прагрзммировзиия, преподает или изучает зти дисциплины,з также математикам, интересующимся приложениями теории грамматик и автоматов. Рей ейакция литерагпуры ло маткиатичеасим наукам ии — ! и|(рч и ю — ~В ОПР Ру ~г, к Р', ийи ОТ РЕДАКТОРА ПЕРЕВОДА Перед читателями — перевод фундаментального труда американских ученых А. Ахо и Дж. Ульмана, трактующего широкий круг проблем, связанных с языками программирования и методами их реализации на вычислительных машинах.

Основой для него до известной степени послужила большая серия статей по теории языков и перевода, опубликованная авторами в различных нау~ных журнанах в течение 4 — 5 предшествующих лет. Первый том посвящен теории языков, общим вопросам теории перевода и (главным образом) методам синтаксического анализа контекстно-свободных языков, Во втором томе рассматриваются вопросы, более тесно связанные с реализацией языков, в частности вопросы оптимизации анализаторов и объектного када. На русском языке уже имеется ряд изданий, касающихся этих тем или даже целиком посвященных им, но книга А. Ахо и Дж. Ульмана сравнительно мало пересекается с ними.

Причин этому две. Во-первых, здесь собран и систематизирован очень большой по объему материал — по широте охвата вопросов синтаксического анализа контекстно-свободных языков книга, повидимому, не имеет себе равных ни в нашей, ни в зарубежной литературе. Во-вторых, авторы сосредоточили основное внимание лишь на тех вопросах, которые уже нашли или могут найти приложения на практике при создании компиляторов и других связанных с языками частей математического обеспечения. Приятен стиль авторов, значительно облегчающии чтение книги. Введение новых более или менее сложных понятий и концепций начинается, как правило, с неформального их изложения и примеров, При этом делаются намеки, которые позволяют лучше понять следующее затем строгое, аккуратное и формальное построение, Описание многочисленных алгоритмов построено по аналогичной схеме: сначала дается неформальное разъяснение сути их работы, зателт четкая формулировка алгоритма, иллюстрируемая часто на примере, и, наконец, доказач низ Ди~гка.

К ~6 Р ° ОТ РЕДАКТОРА ПЕРЕВОДА солидным списком задач различной трудности † чисто технических н учебных упражнений до нерешенных научных проблем. Благодаря такому характеру изложения эту книгу, содержащую большой н трудный материал, легко читать на любом уровне: поверхностного чтения (только по неформальным и общим описаниям), знакомства с фактическим материалом (определения, теоремы, алгоритмы), глубокого изучения (разбор или воспроизведение доказательств, решение трудных задач). Для свободного владения излагаемым материалом полезен разбор примеров н решение большинства приводимых задач, В целом книга будет интересной для широкого круга читателей: от студентов, изучающих основы теории языков программирования, до специалистов — разработчикон систем математического обеспечения н научных работников.

Вместе с авторами можно надеяться, „что алгоритмы и понятия, изложенные в этой книге, переживут следующее поколение вычислительных машин и языков программирования н что хотя бы некоторые из них найдут применение ие только при построении компиляторов, но и в других областях". В. М, Курочкин Посеян(ается Адриенне и Холли ПРЕДИСЛОВИЕ Эта книга задумана как пособие для одно- или двухсеместрового курса лекций по теории компиляции для студентов старших курсов.

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

(2) Прогресс в построении компиляторов достиг того этапа, когда компилнтор можно расчленить на много составных частей и каждую часть подвергнуть запланированной оптимизации. Поэтому важно снабдить людей, предпринимающих попытки такой оптимизации, подходящими математическими средствами. (3) Для полного понимания некоторых из самых полезных и самых эффективных алгоритмов компиляции (например, алгоритма ).К (я)-анализа) требуется основательная математическая подготовка. Мы полагаем, что хорошая теоретическая подготовка становится все более существенной для тех, кто строит компиляторы. Включая в книгу трудные теоремы, имеющие отношение к компиляции, мы старались сделать изложение как можно более доступным.

Для этого приводится много примеров, причем в каждом из них используется какая-нибудь малая грамматика, а не те большие грамматики, что встречаются на практике. Мы надеемся, что в тех случаях, когда трудно следить за теоретическими построениями, для иллюстрации основных идей этих примерон будет достаточно. ПРЕДИСЛОВИЕ ПРЕДИСЛОВИЕ О пользовании книгой Книга возникла из записей лекций, прочитанных на старших курсах Принстонского университета и Стивенсовского технологического института. По ним читались как односемсстровый курс, так и двухсеместровый.

В первом случае курсу по теории компиляции предшествовал курс теории конечных автоматов и контекстно-свободных языков, поэтому не было необходимости излагать материал гл. О, 2 и 8. Остальные же главы излагались подробно. В случае двухсеместрового курса ббльшая часть материала первого тома излагалась в первом семестре, а болыпая часть второго, исключая гл. 8,— во втором. При этом доказательствам и технике доказательств уделялось больше внимания, чем в одно- семестровом курсе. Ясно, что одни разделы кннги более важны, чем другие. Поэтому нам хочется кратко пояснить читателю, как мы оцениваем относительную важность различных частей первого тома.

Общее замечание состоит в том, что большинство доказательств, по-виднмому, можно пропустить. Мы включили доказательства всех главных результатов потому, что считаем их необходимыми для глубокого понимания предмета. Однако в курсах, посвященных компиляции, обычно предпочитают не особенно углубляться во многие вопросы, причем разумный уровень понимания достигается при довольно поверхностном знакомстве с доказательствами. В гл. О (математические основы) и 1 (обзор компиляции) почти весь материал существен, за исключением, быть может, равд. 1.3, в котором рассматриваются приложения синтаксического-анализа, не связанные с компиляцией. 'Мы считаем, что каждое понятие и теорема, введенные в гл. 2 (теорня языков), найдут применение где-нибудь в остальных девяти главах. Однако в курсе лекций по компиляторам некоторый материал следует опустить.