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

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

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

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

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

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

This requires simple handshaking between the errorrecovery apparatus and the high-level driver that invokes the various partsof the compiler.3.5.2 Unary OperatorsThe classic expression grammar includes only binary operators. Algebraicnotation, however, includes unary operators, such as unary minus and absolute value. Other unary operators arise in programming languages, includingautoincrement, autodecrement, address-of, dereference, boolean complement, and typecasts. Adding such operators to the expression grammarrequires some care.Consider adding a unary absolute-value operator, k, to the classic expressiongrammar.

Absolute value should have higher precedence than either x or ÷.Goal0Goal → Expr123Expr456Term → Term x Value| Term ÷ Value| Value78Value → k Factor| Factor91011Factor → ( Expr )| num| nameExpr→ Expr + Term| Expr - Term| Term(a) The Grammar-Expr||TermTermValueValueFactorFactor<num,3><name,x>(b) Parse Tree for kx - 3n FIGURE 3.27 Adding Unary Absolute Value to the Classic Expression Grammar.3.5 Practical Issues 143However, it needs a lower precedence than Factor to force evaluation of parenthetic expressions before application of k.

One way to write this grammaris shown in Figure 3.27. With these additions, the grammar is still lr(1). Itlets the programmer form the absolute value of a number, an identifier, or aparenthesized expression.Figure 3.27b shows the parse tree for the string kx - 3. It correctly shows thatthe code must evaluate kx before performing the subtraction. The grammardoes not allow the programmer to write kkx, as that makes little mathematical sense. It does, however, allow k(kx), which makes as little senseas kkx.The inability to write kkx hardly limits the expressiveness of the language.With other unary operators, however, the issue seems more serious.

Forexample, a C programmer might need to write **p to dereference a variable declared as char **p;. We can add a dereference production for Valueas well: Value → * Value. The resulting grammar is still an lr(1) grammar,even if we replace the x operator in Term → Term x Value with *, overloading the operator “*” in the way that C does.

This same approach works forunary minus.3.5.3 Handling Context-Sensitive AmbiguityUsing one word to represent two different meanings can create a syntacticambiguity. One example of this problem arose in the definitions of severalearly programming languages, including fortran, pl/i, and Ada.

These languages used parentheses to enclose both the subscript expressions of anarray reference and the argument list of a subroutine or function. Given atextual reference, such as fee(i,j), the compiler cannot tell if fee is atwo-dimensional array or a procedure that must be invoked. Differentiatingbetween these two cases requires knowledge of fee’s declared type. Thisinformation is not syntactically obvious. The scanner undoubtedly classifies fee as a name in either case. A function call and an array reference canappear in many of the same situations.Neither of these constructs appears in the classic expression grammar.

Wecan add productions that derive them from Factor.Factor→ FunctionReference||||ArrayReference( Expr )numnameFunctionReference → name ( ArgList )ArrayReference→ name ( ArgList )144 CHAPTER 3 ParsersSince the last two productions have identical right-hand sides, this grammaris ambiguous, which creates a reduce-reduce conflict in an lr(1) tablebuilder.Resolving this ambiguity requires extra-syntactic knowledge. In a recursivedescent parser, the compiler writer can combine the code for FunctionReference and ArrayReference and add the extra code required to check thename’s declared type.

In a table-driven parser built with a parser generator,the solution must work within the framework provided by the tools.Two different approaches have been used to solve this problem. The compiler writer can rewrite the grammar to combine both the function invocationand the array reference into a single production. In this scheme, the issue isdeferred until a later step in translation, when it can be resolved with information from the declarations. The parser must construct a representation thatpreserves all the information needed by either resolution; the later step willthen rewrite the reference to its appropriate form as an array reference or asa function invocation.Alternatively, the scanner can classify identifiers based on their declaredtypes, rather than their microsyntactic properties.

This classification requiressome hand-shaking between the scanner and the parser; the coordination isnot hard to arrange as long as the language has a define-before-use rule.Since the declaration is parsed before the use occurs, the parser can makeits internal symbol table available to the scanner to resolve identifiers intodistinct classes, such as variable-name and function-name. The relevantproductions become:FunctionReference → function-name ( ArgList )ArrayReference→ variable-name ( ArgList )Rewritten in this way, the grammar is unambiguous. Since the scannerreturns a distinct syntactic category in each case, the parser can distinguishthe two cases.3.5.4 Left versus Right RecursionAs we have seen, top-down parsers need right-recursive grammars ratherthan left-recursive ones. Bottom-up parsers can accommodate either left orright recursion.

Thus, the compiler writer must choose between left and rightrecursion in writing the grammar for a bottom-up parser. Several factors playinto this decision.3.5 Practical Issues 145Stack DepthIn general, left recursion can lead to smaller stack depths. Consider two alternate grammars for a simple list construct, shown in Figures 3.28a and 3.28b.(Notice the similarity to the SheepNoise grammar.) Using these grammars toproduce a five-element list leads to the derivations shown in Figures 3.28cand 3.28d, respectively. An lr(1) parser would construct these sequences inreverse. Thus, if we read the derivation from the bottom line to the top line,we can follow the parsers’s actions with each grammar.1.

Left-recursive grammar This grammar shifts elt1 onto its stack andimmediately reduces it to List. Next, it shifts elt2 onto the stack andreduces it to List. It proceeds until it has shifted each of the five elti sonto the stack and reduced them to List. Thus, the stack reaches a2maximum depth of two and an average depth of 106 = 13.2. Right-recursive grammar This version shifts all five elti s onto itsstack. Next, it reduces elt5 to List using rule two, and the remainingList → List elt| eltList → elt List| elt(a) Left-Recursive Grammar(b) Right-Recursive GrammarListListelt1 ListList elt5elt1 elt2 ListList elt4 elt5elt1 elt2 elt3 ListList elt3 elt4 elt5elt1 elt2 elt3 elt4 ListList elt2 elt3 elt4 elt5elt1 elt2 elt3 elt4 elt5elt1 elt2 elt3 elt4elt5 List(c) Derivation with Left Recursion(d) Derivation with Right Recursionelt5elt4elt3elt1 elt2(e) AST with Left Recursionn FIGURE 3.28 Left- and Right-Recursive List Grammars.elt1elt2elt3elt4elt5(f) AST with Right Recursion146 CHAPTER 3 Parserselti s using rule one.

Thus, its maximum stack depth will be five and itsaverage will be206= 3 13 .The right-recursive grammar requires more stack space; its maximum stackdepth is bounded only by the length of the list. In contrast, the maximumstack depth with the left-recursive grammar depends on the grammar ratherthan the input stream.For short lists, this is not a problem. If, however, the list represents thestatement list in a long run of straight-line code, it might have hundredsof elements.

In this case, the difference in space can be dramatic. If all otherissues are equal, the smaller stack height is an advantage.AssociativityAbstract syntax treeAn AST is a contraction of the parse tree. SeeSection 5.2.1 on page 227.Left recursion naturally produces left associativity, and right recursion naturally produces right associativity. In some cases, the order of evaluationmakes a difference. Consider the abstract syntax trees (asts) for the two fiveelement lists, shown in Figures 3.28e and 3.28f. The left-recursive grammarreduces elt1 to a List, then reduces List elt2 , and so on.

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