Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 10

PDF-файл Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 10 Конструирование компиляторов (52981): Другое - 7 семестрCooper_Engineering_a_Compiler(Second Edition) (Rice) - PDF, страница 10 (52981) - СтудИзба2019-09-18СтудИзба
Rice1874

Описание файла

Файл "Cooper_Engineering_a_Compiler(Second Edition)" внутри архива находится в следующих папках: Rice, Купер и Торчсон - перевод. PDF-файл из архива "Rice", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 10 страницы из PDF

Thecompiler writer can insert a third phase between the front end and the backend. This middle section, or optimizer, takes an ir program as its input andproduces a semantically equivalent ir program as its output. By using the iras an interface, the compiler writer can insert this third phase with minimaldisruption to the front end and back end. This leads to the following compilerstructure, termed a three-phase compiler.SourceProgramFront EndIROptimizerIRBack EndTargetProgramCompilerThe optimizer is an ir-to-ir transformer that tries to improve the ir programin some way. (Notice that these transformers are, themselves, compilersaccording to our definition in Section 1.1.) The optimizer can make one ormore passes over the ir, analyze the ir, and rewrite the ir. The optimizermay rewrite the ir in a way that is likely to produce a faster target programfrom the back end or a smaller target program from the back end. It mayhave other objectives, such as a program that produces fewer page faults oruses less energy.Conceptually, the three-phase structure represents the classic optimizingcompiler.

In practice, each phase is divided internally into a series of passes.The front end consists of two or three passes that handle the details ofrecognizing valid source-language programs and producing the initial irform of the program. The middle section contains passes that perform different optimizations. The number and purpose of these passes vary fromcompiler to compiler.

The back end consists of a series of passes, each ofwhich takes the ir program one step closer to the target machine’s instruction set. The three phases and their individual passes share a commoninfrastructure. This structure is shown in Figure 1.1.In practice, the conceptual division of a compiler into three phases, a frontend, a middle section or optimizer, and a back end, is useful. The problemsaddressed by these phases are different. The front end is concerned withunderstanding the source program and recording the results of its analysis into ir form.

The optimizer section focuses on improving the ir form.1.3 Overview of Translation 9--Reg Allocation-Inst Scheduling...Inst Selection-Optimization n-Optimization 2-Optimization 1 Optimizer Back End Elaboration-Parser-ScannerFront End- 666666666?????????Infrastructuren FIGURE 1.1 Structure of a Typical Compiler.The back end must map the transformed ir program onto the boundedresources of the target machine in a way that leads to efficient use of thoseresources.Of these three phases, the optimizer has the murkiest description. The termoptimization implies that the compiler discovers an optimal solution to someproblem. The issues and problems that arise in optimization are so complex and so interrelated that they cannot, in practice, be solved optimally.Furthermore, the actual behavior of the compiled code depends on interactions among all of the techniques applied in the optimizer and the back end.Thus, even if a single technique can be proved optimal, its interactions withother techniques may produce less than optimal results.

As a result, a goodoptimizing compiler can improve the quality of the code, relative to an unoptimized version. However, an optimizing compiler will almost always fail toproduce optimal code.The middle section can be a single monolithic pass that applies one or moreoptimizations to improve the code, or it can be structured as a series ofsmaller passes with each pass reading and writing ir. The monolithic structure may be more efficient. The multipass structure may lend itself to a lesscomplex implementation and a simpler approach to debugging the compiler.It also creates the flexibility to employ different sets of optimization in different situations. The choice between these two approaches depends on theconstraints under which the compiler is built and operates.1.3 OVERVIEW OF TRANSLATIONTo translate code written in a programming language into code suitable forexecution on some target machine, a compiler runs through many steps.10 CHAPTER 1 Overview of CompilationNOTATIONCompiler books are, in essence, about notation.

After all, a compiler translates a program written in one notation into an equivalent program writtenin another notation. A number of notational issues will arise in yourreading of this book. In some cases, these issues will directly affect yourunderstanding of the material.Expressing Algorithms We have tried to keep the algorithms concise.Algorithms are written at a relatively high level, assuming that the readercan supply implementation details. They are written in a slanted, sansserif font. Indentation is both deliberate and significant; it matters mostin an if-then-else construct. Indented code after a then or an elseforms a block. In the following code fragmentif Action [s,word] = ‘‘shift si ’’ thenpush wordpush siword ← NextWord()else if · · ·all the statements between the then and the else are part of the thenclause of the if-then-else construct.

When a clause in an if-thenelse construct contains just one statement, we write the keyword thenor else on the same line as the statement.Writing Code In some examples, we show actual program text written insome language chosen to demonstrate a particular point.

Actual programtext is written in a monospace font.Arithmetic Operators Finally, we have forsaken the traditional useof * for × and of / for ÷, except in actual program text. The meaningshould be clear to the reader.To make this abstract process more concrete, consider the steps needed togenerate executable code for the following expression:a ← a × 2 × b × c × dwhere a, b, c, and d are variables, ← indicates an assignment, and × is theoperator for multiplication. In the following subsections, we will trace thepath that a compiler takes to turn this simple expression into executable code.1.3.1 The Front EndBefore the compiler can translate an expression into executable targetmachine code, it must understand both its form, or syntax, and its meaning,1.3 Overview of Translation 11or semantics.

The front end determines if the input code is well formed, interms of both syntax and semantics. If it finds that the code is valid, it createsa representation of the code in the compiler’s intermediate representation; ifnot, it reports back to the user with diagnostic error messages to identify theproblems with the code.Checking SyntaxTo check the syntax of the input program, the compiler must compare theprogram’s structure against a definition for the language.

This requires anappropriate formal definition, an efficient mechanism for testing whether ornot the input meets that definition, and a plan for how to proceed on anillegal input.Mathematically, the source language is a set, usually infinite, of stringsdefined by some finite set of rules, called a grammar. Two separate passesin the front end, called the scanner and the parser, determine whether or notthe input code is, in fact, a member of the set of valid programs defined bythe grammar.Programming language grammars usually refer to words based on their partsof speech, sometimes called syntactic categories.

Basing the grammar ruleson parts of speech lets a single rule describe many sentences. For example,in English, many sentences have the formSentence → Subject verb Object endmarkwhere verb and endmark are parts of speech, and Sentence, Subject, andObject are syntactic variables. Sentence represents any string with the formdescribed by this rule.

The symbol “→” reads “derives” and means that aninstance of the right-hand side can be abstracted to the syntactic variable onthe left-hand side.Consider a sentence like “Compilers are engineered objects.” The first stepin understanding the syntax of this sentence is to identify distinct wordsin the input program and to classify each word with a part of speech. In acompiler, this task falls to a pass called the scanner. The scanner takes astream of characters and converts it to a stream of classified words—thatis, pairs of the form (p,s), where p is the word’s part of speech and s is itsspelling.

A scanner would convert the example sentence into the followingstream of classified words:(noun,“Compilers”), (verb,“are”), (adjective,“engineered”),(noun,“objects”), (endmark,“.”)Scannerthe compiler pass that converts a string ofcharacters into a stream of words12 CHAPTER 1 Overview of CompilationIn practice, the actual spelling of the words might be stored in a hash tableand represented in the pairs with an integer index to simplify equality tests.Chapter 2 explores the theory and practice of scanner construction.In the next step, the compiler tries to match the stream of categorized wordsagainst the rules that specify syntax for the input language.

For example,a working knowledge of English might include the following grammaticalrules:123456SentenceSubjectSubjectObjectObjectModifier...→→→→→→Subject verb Object endmarknounModifier nounnounModifier nounadjectiveBy inspection, we can discover the following derivation for our examplesentence:Rule—1256Prototype SentenceSentenceSubject verb Object endmarknoun verb Object endmarknoun verb Modifier noun endmarknoun verb adjective noun endmarkThe derivation starts with the syntactic variable Sentence. At each step, itrewrites one term in the prototype sentence, replacing the term with a righthand side that can be derived from that rule.

The first step uses Rule 1to replace Sentence. The second uses Rule 2 to replace Subject. The thirdreplaces Object using Rule 5, while the final step rewrites Modifier withadjective according to Rule 6. At this point, the prototype sentence generated by the derivation matches the stream of categorized words produced bythe scanner.Parserthe compiler pass that determines if the inputstream is a sentence in the source languageThe derivation proves that the sentence “Compilers are engineered objects.”belongs to the language described by Rules 1 through 6. The sentence isgrammatically correct.

The process of automatically finding derivations iscalled parsing. Chapter 3 presents the techniques that compilers use to parsethe input program.1.3 Overview of Translation 13A grammatically correct sentence can be meaningless. For example, thesentence “Rocks are green vegetables” has the same parts of speech inthe same order as “Compilers are engineered objects,” but has no rationalmeaning. To understand the difference between these two sentences requirescontextual knowledge about software systems, rocks, and vegetables.The semantic models that compilers use to reason about programming languages are simpler than the models needed to understand natural language.A compiler builds mathematical models that detect specific kinds of inconsistency in a program.

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5075
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее