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

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

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

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

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

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

The algorithm in Figure 3.6 eliminates all left recursion from agrammar by thorough application of two techniques: forward substitution toconvert indirect left recursion into direct left recursion and rewriting directleft recursion as right recursion. It assumes that the original grammar has nocycles (A →+ A) and no -productions.The algorithm imposes an arbitrary order on the nonterminals. The outerloop cycles through the nonterminals in this order.

The inner loop looksfor any production that expands Ai into a right-hand side that begins withAj , for j < i. Such an expansion may lead to an indirect left recursion. Toavoid this, the algorithm replaces the occurrence of Aj with all the alternativeright-hand sides for Aj . That is, if the inner loop discovers a productionAi → Aj γ , and Aj →δ1 |δ2 |· · · |δk , then the algorithm replaces Ai → Aj γ witha set of productions Ai →δ1 γ |δ2 γ |· · · |δk γ . This process eventually convertseach indirect left recursion into a direct left recursion.

The final step in theouter loop converts any direct left recursion on Ai to right recursion using thesimple transformation shown earlier. Because new nonterminals are addedat the end and only involve right recursion, the loop can ignore them—theydo not need to be checked and converted.3.3 Top-Down Parsing 103impose an order on the nonterminals,A1 , A2 , . . . , Anfor i ← 1 to n do;for j ← 1 to i - 1 do;if ∃ a production Ai → Aj γthen replace Ai → Aj γ with one or moreproductions that expand Ajend;rewrite the productions to eliminateany direct left recursion on Aiend;n FIGURE 3.6 Removal of Indirect Left Recursion.Considering the loop invariant for the outer loop may make this clearer.

Atthe start of the ith outer loop iteration∀ k < i, no production expanding Ak has Al in its rhs, for l < k.At the end of this process, (i = n), all indirect left recursion has been eliminated through the repetitive application of the inner loop, and all immediateleft recursion has been eliminated in the final step of each iteration.Backtrack-Free ParsingThe major source of inefficiency in the leftmost, top-down parser arises fromits need to backtrack. If the parser expands the lower fringe with the wrongproduction, it eventually encounters a mismatch between that fringe and theparse tree’s leaves, which correspond to the words returned by the scanner.When the parser discovers the mismatch, it must undo the actions that builtthe wrong fringe and try other productions. The act of expanding, retracting,and re-expanding the fringe wastes time and effort.In the derivation of Figure 3.5, the parser chose the correct rule at eachstep.

With consistent choice, such as considering rules in order of appearance in the grammar, it would have backtracked on each name, first tryingFactor → ( Expr ) and then Factor → num before deriving name. Similarly,the expansions by rules 4 and 8 would have considered the other alternativesbefore expanding to .For this grammar, the parser can avoid backtracking with a simple modification. When the parser goes to select the next rule, it can consider boththe focus symbol and the next input symbol, called the lookahead symbol. Using a one symbol lookahead, the parser can disambiguate all of thechoices that arise in parsing the right-recursive expression grammar.

Thus,we say that the grammar is backtrack free with a lookahead of one symbol.A backtrack-free grammar is also called a predictive grammar.Backtrack-free grammara CFG for which the leftmost, top-down parser canalways predict the correct rule with lookahead ofat most one word104 CHAPTER 3 Parsersfor each α ∈ (T ∪ eof ∪ ) do;FIRST(α)← α;end;for each A ∈ N T do;FIRST(A)← ∅;end;while (FIRST sets are still changing) do;for each p ∈ P, where p has the form A→β do;if β is β1 β2 . .

. βk , where βi ∈ T ∪ N T , then begin;rhs ← FIRST(β1 ) − {};i ← 1;while ( ∈ FIRST(βi ) and i ≤ k-1) do;rhs ← rhs ∪ (FIRST(βi+1 ) − {}) ;i ← i + 1;end;end;if i = k and ∈ FIRST(βk )then rhs ← rhs ∪ {};FIRST(A)←FIRST(A)∪rhs;end;end;n FIGURE 3.7 Computing FIRST Sets for Symbols in a Grammar.We can formalize the property that makes the right-recursive expressiongrammar backtrack free.

At each point in the parse, the choice of an expansion is obvious because each alternative for the leftmost nonterminal leadsto a distinct terminal symbol. Comparing the next word in the input streamagainst those choices reveals the correct expansion.FIRST setFor a grammar symbol α, FIRST(α) is the set ofterminals that can appear at the start of asentence derived from α.eof occurs implicitly at the end of everysentence in the grammar. Thus, it is in both thedomain and range of FIRST.The intuition is clear, but formalizing it will require some notation. For eachgrammar symbol α, define the set first(α) as the set of terminal symbolsthat can appear as the first word in some string derived from α. The domainof first is the set of grammar symbols, T ∪ N T ∪ {, eof} and its range isT ∪ {, eof}.

If α is either a terminal, , or eof, then first(α) has exactlyone member, α. For a nonterminal A, first(A) contains the complete set ofterminal symbols that can appear as the leading symbol in a sentential formderived from A.Figure 3.7 shows an algorithm that computes the first sets for each symbol in a grammar. As its initial step, the algorithm sets the first sets for the3.3 Top-Down Parsing 105simple cases, terminals, , and eof. For the right-recursive expression grammar shown in Figure 3.4 on page 101, that initial step produces the followingfirst sets:FIRSTnumname+-×÷()eofnumname+-x÷()eofNext, the algorithm iterates over the productions, using the first sets for theright-hand side of a production to derive the first set for the nonterminal onits left-hand side. This process halts when it reaches a fixed point.

For theright-recursive expression grammar, the first sets of the nonterminals are:FIRSTExprExpr’TermTerm’Factor(, name, num+, -, (, name, numx, ÷ , (, name, numWe defined first sets over single grammar symbols. It is convenient toextend that definition to strings of symbols. For a string of symbols,s = β1 β2 β3 . . .

βk , we define first(s) as the union of the first sets forβ1 , β2 , . . . , βn , where βn is the first symbol whose first set does not contain, and ∈ first(s) if and only if it is in the set for each of the βi , 1 ≤ i ≤ k.The algorithm in Figure 3.7 computes this quantity into the variable rhs.Conceptually, first sets simplify implementation of a top-down parser. Consider, for example, the rules for Expr 0 in the right-recursive expressiongrammar:2 Expr 0 →3|4|+ Term Expr 0- Term Expr 0When the parser tries to expand an Expr 0 , it uses the lookahead symbol andthe first sets to choose between rules 2, 3, and 4.

With a lookahead of +,the parser expands by rule 2 because + is in first(+ Term Expr 0 ) and not infirst(- Term Expr 0 ) or first(). Similarly, a lookahead of - dictates a choiceof rule 3.Rule 4, the -production, poses a slightly harder problem. first() is just{}, which matches no word returned by the scanner. Intuitively, the parsershould apply the production when the lookahead symbol is not a memberof the first set of any other alternative. To differentiate between legal inputs106 CHAPTER 3 Parsersfor each A ∈ N T do;FOLLOW(A)← ∅;end;FOLLOW(S)← { eof } ;while (FOLLOW sets are still changing) do;for each p ∈ P of the form A → β1 β2 · · · βk do;TRAILER ← FOLLOW(A);for i ← k down to 1 do;if βi ∈ N T then begin;FOLLOW(βi )←FOLLOW(βi ) ∪TRAILER;if ∈ FIRST(βi )then TRAILER ← TRAILER ∪ (FIRST(βi ) − );else TRAILER ← FIRST(βi );end;else TRAILER ← FIRST(βi );// is {βi }end;end;end;n FIGURE 3.8 Computing FOLLOW Sets for Non-Terminal Symbols.and syntax errors, the parser needs to know which words can appear as theleading symbol after a valid application of rule 4—the set of symbols thatcan follow an Expr 0 .FOLLOW setFor a nonterminal α, FOLLOW(α) contains theset of words that can occur immediately after αin a sentence.To capture that knowledge, we define the set follow(Expr 0 ) to contain allof the words that can occur to the immediate right of a string derived fromExpr 0 .

Figure 3.8 presents an algorithm to compute the follow set for eachnonterminal in a grammar; it assumes the existence of first sets. The algorithm initializes each follow set to the empty set and then iterates overthe productions, computing the contribution of the partial suffixes to thefollow set of each symbol in each right-hand side. The algorithm haltswhen it reaches a fixed point. For the right-recursive expression grammar,the algorithm produces:FOLLOWExprExpr’TermTerm’Factoreof, )eof, )eof, +, -, )eof, +, -, )eof, +, -, x, ÷, )The parser can use follow(Expr 0 ) when it tries to expand an Expr 0 . If thelookahead symbol is +, it applies rule 2.

If the lookahead symbol is -, itapplies rule 3. If the lookahead symbol is in follow(Expr 0 ), which containseof and ), it applies rule 4. Any other symbol causes a syntax error.3.3 Top-Down Parsing 107Using first and follow, we can specify precisely the condition that makesa grammar backtrack free for a top-down parser. For a production A → β,define its augmented first set, first+ , as follows:first(β)if ∈/ first(β)first+ (A→β) =first(β) ∪ follow(A) otherwiseNow, a backtrack-free grammar has the property that, for any nonterminal Awith multiple right-hand sides, A→β1 | β2 | · · · | βnfirst+ (A→βi ) ∩ first+ (A→βj ) = ∅, ∀ 1 ≤ i, j ≤ n, i 6= j.Any grammar that has this property is backtrack free.For the right-recursive expression grammar, only productions 4 and 8 havefirst+ sets that differ from their first sets.48ProductionFIRST setFIRST+ setExpr 0 → Term 0 → { }{ }{ , eof, ) }{ , eof, +, -, ) }Applying the backtrack-free condition pairwise to each set of alternate righthand sides proves that the grammar is, indeed, backtrack free.Left-Factoring to Eliminate BacktrackingNot all grammars are backtrack free.

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