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

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

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

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

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

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

Thissection details the impact of the problems that we have seen in the precedingexamples.Handling Nonlocal InformationSome problems map cleanly onto the attribute-grammar paradigm, particularly those problems in which all information flows in the same direction.However, problems with a complex pattern of information flow can bedifficult to express as attribute grammars. An attribution rule can name only4.3 The Attribute-Grammar Framework 195values associated with a grammar symbol that appears in the same production; this constrains the rule to using only nearby, or local, information.

If thecomputation requires a nonlocal value, the attribute grammar must includecopy rules to move those values to the points where they are used.Copy rules can swell the size of an attribute grammar; compare Figures 4.8,4.9, and 4.10. The implementor must write each of those rules. In the evaluator, each of the rules must be executed, creating new attributes and additionalwork.

When information is aggregated, as in the declare-before-use rule orthe framework for estimating execution times, a new copy of the information must be made each time a rule changes an aggregate’s value. Thesecopy rules add another layer of work to the tasks of writing and evaluatingan attribute grammar.Storage ManagementFor realistic examples, evaluation produces large numbers of attributes. Theuse of copy rules to move information around the parse tree can multiplythe number of attribute instances that evaluation creates. If the grammaraggregates information into complex structures—to pass declaration information around the parse tree, for example—the individual attributes can belarge.

The evaluator must manage storage for attributes; a poor storagemanagement scheme can have a disproportionately large negative impacton the resource requirements of the evaluator.If the evaluator can determine which attribute values can be used after evaluation, it may be able to reuse some of the attribute storage by reclaimingspace for values that can never again be used. For example, an attributegrammar that evaluated an expression tree to a single value might returnthat value to the process that invoked it.

In this scenario, the intermediatevalues calculated at interior nodes might be dead—never used again—and,thus, candidates for reclamation. On the other hand, if the tree resulting fromattribution is persistent and subject to later inspection—as might be the casein an attribute grammar for type inference—then the evaluator must assumethat a later phase of the compiler can traverse the tree and inspect arbitraryattributes. In this case, the evaluator cannot reclaim the storage for any ofthe attribute instances.This problem reflects a fundamental clash between the functional nature ofthe attribute-grammar paradigm and the imperative use to which it mightbe put in the compiler. The possible uses of an attribute in later phasesof the compiler have the effect of adding dependences from that attributeto uses not specified in the attribute grammar.

This bends the functionalparadigm and removes one of its strengths: the ability to automaticallymanage attribute storage.196 CHAPTER 4 Context-Sensitive AnalysisInstantiating the Parse TreeAn attribute grammar specifies a computation relative to the parse tree for avalid sentence in the underlying grammar. The paradigm relies, inherently,on the availability of the parse tree. The evaluator might simulate the parsetree, but it must behave as if the parse tree exists. While the parse tree isuseful for discussions of parsing, few compilers actually build a parse tree.Some compilers use an abstract syntax tree (ast) to represent the programbeing compiled.

The ast has the essential structure of the parse tree buteliminates many of the internal nodes that represent nonterminal symbolsin the grammar (see the description starting on page 226 of Section 5.2.1).If the compiler builds an ast, it could use an attribute grammar tied to agrammar for the ast. However, if the compiler has no other use for the ast,then the programming effort and compile-time cost associated with buildingand maintaining the ast must be weighed against the benefits of using theattribute-grammar formalism.Locating the AnswersOne final problem with attribute-grammar schemes for context-sensitiveanalysis is more subtle.

The result of attribute evaluation is an attributedtree. The results of the analysis are distributed over that tree, in the formof attribute values. To use these results in later passes, the compiler musttraverse the tree to locate the desired information.The compiler can use carefully constructed traversals to locate a particular node, which requires walking from the root of the parse tree down tothe appropriate location—on each access.

This makes the code both slowerand harder to write, because the compiler must execute each of these traversals and the compiler writer must construct each of them. The alternative isto copy the important answers to a point in the tree where they are easilyfound, typically the root. This introduces more copy rules, exacerbating thatproblem.Breakdown of the Functional ParadigmOne way to address all of these problems is to add a central repository forattributes.

In this scenario, an attribute rule can record information directlyinto a global table, where other rules can read the information. This hybridapproach can eliminate many of the problems that arise from nonlocal information. Since the table can be accessed from any attribution rule, it has theeffect of providing local access to any information already derived.Adding a central repository for facts complicates matters in another way.If two rules communicate through a mechanism other than an attribution4.3 The Attribute-Grammar Framework 197rule, the implicit dependence between them is removed from the attributedependence graph.

The missing dependence should constrain the evaluator to ensure that the two rules are processed in the correct order; withoutit, the evaluator may be able to construct an order that, while correct forthe grammar, has unintended behavior because of the removed constraint.For example, passing information between the declaration syntax and anexecutable expression through a table might allow the evaluator to processdeclarations after some or all of the expressions that use the declared variables.

If the grammar uses copy rules to propagate that same information,those rules constrain the evaluator to orders that respect the dependencesembodied by those copy rules.SECTION REVIEWAttribute grammars provide a functional specification that canbe used to solve a variety of problems, including many of theproblems that arise in performing context-sensitive analysis. Inthe attribute-grammar approach, the compiler writer producessuccinct rules to describe the computation; the attribute-grammarevaluator then provides the mechanisms to perform the actualcomputation.

A high-quality attribute-grammar system wouldsimplify the construction of the semantic elaboration section of acompiler.The attribute-grammar approach has never achieved widespreadpopularity for a number of mundane reasons. Large problems, suchas the difficulty of performing nonlocal computation and the need totraverse the parse tree to discover answers to simple questions, havediscouraged the adoption of these ideas. Small problems, such as spacemanagement for short-lived attributes, evaluator efficiency, and the lackof widely-available, open-source attribute-grammar evaluators have alsomade these tools and techniques less attractive.Review Questions1. From the “four function calculator” grammar given in the margin,construct an attribute-grammar scheme that attributes each Calcnode with the specified computation, displaying the answer on eachreduction to Expr.2.

The “define-before-use” rule specifies that each variable used in a procedure must be declared before it appears in the text. Sketch anattribute-grammar scheme for checking that a procedure conformswith this rule. Is the problem easier if the language requires that alldeclarations precede any executable statement?Calc → ExprExpr → Expr + Term| Expr − Term| TermTerm → Term × num| Term ÷ num| numFour Function Calculator198 CHAPTER 4 Context-Sensitive Analysis4.4 AD HOC SYNTAX-DIRECTED TRANSLATIONThe rule-based evaluators for attribute grammars introduce a powerful ideathat serves as the basis for the ad hoc techniques used for context-sensitiveanalysis in many compilers. In the rule-based evaluators, the compiler writerspecifies a sequence of actions that are associated with productions in thegrammar.

The underlying observation, that the actions required for contextsensitive analysis can be organized around the structure of the grammar,leads to a powerful, albeit ad hoc, approach to incorporating this kind ofanalysis into the process of parsing a context-free grammar. We refer to thisapproach as ad hoc syntax-directed translation.In this scheme, the compiler writer provides snippets of code that executeat parse time. Each snippet, or action, is directly tied to a production in thegrammar. Each time the parser recognizes that it is at a particular place in thegrammar, the corresponding action is invoked to perform its task. To implement this in a top-down, recursive-descent parser, the compiler writer simplyadds the appropriate code to the parsing routines.

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