K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 42
Текст из файла (страница 42)
Lucas appears to have introduced the notion of recursive-descentparsing [255]. Conway applies similar ideas to an efficient single-passcompiler for cobol [96].The ideas behind ll and lr parsing appeared in the 1960s. Lewis and Stearnsintroduced ll(k) grammars [245]; Rosenkrantz and Stearns described theirproperties in more depth [305]. Foster developed an algorithm to transform agrammar into ll(1) form [151]. Wood formalized the notion of left-factoringa grammar and explored the theoretical issues involved in transforming agrammar to ll(1) form [353, 354, 355].Knuth laid out the theory behind lr(1) parsing [228].
DeRemer and others developed techniques, the slr and lalr table-construction algorithms,that made the use of lr parser generators practical on the limited-memorycomputers of the day [121, 122]. Waite and Goos describe a techniquefor automatically eliminating useless productions during the lr(1) tableconstruction algorithm [339]. Penello suggested direct encoding of the tablesinto executable code [282].
Aho and Ullman [8] is a definitive referenceon both ll and lr parsing. Bill Waite provided the example grammar inexercise 3.7.Several algorithms for parsing arbitrary context-free grammars appearedin the 1960s and early 1970s. Algorithms by Cocke and Schwartz [91],Younger [358], Kasami [212], and Earley [135] all had similar computational complexity. Earley’s algorithm deserves particular note because ofits similarity to the lr(1) table-construction algorithm. Earley’s algorithmderives the set of possible parse states at parse time, rather than at runtime,where the lr(1) techniques precompute these in a parser generator.
From ahigh-level view, the lr(1) algorithms might appear as a natural optimizationof Earley’s algorithm.Exercises 157nEXERCISES1. Write a context-free grammar for the syntax of regular expressions.Section 3.22. Write a context-free grammar for the Backus-Naur form (bnf)notation for context-free grammars.3.
When asked about the definition of an unambiguous context-freegrammar on an exam, two students gave different answers. The firstdefined it as “a grammar where each sentence has a unique syntax treeby leftmost derivation.” The second defined it as “a grammar whereeach sentence has a unique syntax tree by any derivation.” Which oneis correct?4. The following grammar is not suitable for a top-down predictiveparser. Identify the problem and correct it by rewriting the grammar.Show that your new grammar satisfies the ll(1) condition.L →|RaQ baR →||abacabaQ →|bbcbcR bc5.
Consider the following grammar:A → BaB → dab| CbC → cB| AcDoes this grammar satisfy the ll(1) condition? Justify your answer. Ifit does not, rewrite it as an ll(1) grammar for the same language.6. Grammars that can be parsed top-down, in a linear scan from left toright, with a k word lookahead are called ll(k) grammars.
In the text,the ll(1) condition is described in terms of first sets. How wouldyou define the first sets necessary to describe an ll(k) condition?7. Suppose an elevator is controlled by two commands: ↑ to move theelevator up one floor and ↓ to move the elevator down one floor.Assume that the building is arbitrarily tall and that the elevator startsat floor x.Write an ll(1) grammar that generates arbitrary command sequencesthat (1) never cause the elevator to go below floor x and (2) alwaysreturn the elevator to floor x at the end of the sequence.
For example,↑↑↓↓ and ↑↓↑↓ are valid command sequences, but ↑↓↓↑ and ↑↓↓are not. For convenience, you may consider a null sequence as valid.Prove that your grammar is ll(1).Section 3.3158 CHAPTER 3 ParsersSection 3.48. Top-down and bottom-up parsers build syntax trees in differentorders. Write a pair of programs, TopDown and BottomUp, that take asyntax tree and print out the nodes in order of construction. TopDownshould display the order for a top-down parser, while BottomUpshould show the order for a bottom-up parser.9.
The ClockNoise language (CN) is represented by the followinggrammar:Goal→ ClockNoiseClockNoise → ClockNoise tick tock| tick tocka.b.c.d.What are the lr(1) items of CN?What are the first sets of CN?Construct the Canonical Collection of Sets of lr(1) Items for CN.Derive the Action and Goto tables.10. Consider the following grammar:Start →S→A→|B→C→SAaBCBCfbca. Construct the canonical collection of sets of lr(1) items for thisgrammar.b. Derive the Action and Goto tables.c. Is the grammar lr(1)?11. Consider a robot arm that accepts two commands: 5 puts an apple inthe bag and 4 takes an apple out of the bag.
Assume the robot armstarts with an empty bag.A valid command sequence for the robot arm should have no prefixthat contains more 4 commands than 5 commands. As examples,5544 and 545 are valid command sequences, but 5445 and54544 are not.a. Write an lr(1) grammar that represents all the value commandsequences for the robot arm.b. Prove that the grammar is lr(1).Exercises 15912. The following grammar has no known ll(1) equivalent:0 Start → A1| B2 A3→ ( A )4 B5→ ( B >||abShow that the grammar is lr(1).13. Write a grammar for expressions that can include binary operators (+and x), unary minus (-), autoincrement (++), and autodecrement (- -)with their customary precedence.
Assume that repeated unary minusesare not allowed, but that repeated autoincrement and autodecrementoperators are allowed.Section 3.614. Consider the task of building a parser for the programming languageScheme. Contrast the effort required for a top-down recursive-descentparser with that needed for a table-driven lr(1) parser. (Assume thatyou already have an lr(1) table generator.)Section 3.715.
The text describes a manual technique for eliminating uselessproductions in a grammar.a. Can you modify the lr(1) table-construction algorithm so that itautomatically eliminates the overhead from useless productions?b. Even though a production is syntactically useless, it may serve apractical purpose. For example, the compiler writer might associatea syntax-directed action (see Chapter 4) with the uselessproduction. How should your modified table-constructionalgorithm handle an action associated with a useless production?This page intentionally left blankChapter4Context-Sensitive AnalysisnCHAPTER OVERVIEWAn input program that is grammatically correct may still contain seriouserrors that would prevent compilation. To detect such errors, a compiler performs a further level of checking that involves considering each statementin its actual context.
These checks find errors of type and of agreement.This chapter introduces two techniques for context-sensitive checking.Attribute grammars are a functional formalism for specifying contextsensitive computation. Ad hoc syntax-directed translation provides a simpleframework where the compiler writer can hang arbitrary code snippets toperform these checks.Keywords: Semantic Elaboration, Type Checking, Attribute Grammars,Ad Hoc Syntax Directed Translation4.1 INTRODUCTIONThe compiler’s ultimate task is to translate the input program into a form thatcan execute directly on the target machine.
For this purpose, it needs knowledge about the input program that goes well beyond syntax. The compilermust build up a large base of knowledge about the detailed computationencoded in the input program. It must know what values are represented,where they reside, and how they flow from name to name.
It must understand the structure of the computation. It must analyze how the programinteracts with external files and devices. All of these facts can be derivedfrom the source code, using contextual knowledge. Thus, the compiler mustperform deeper analysis than is typical for a scanner or a parser.These kinds of analysis are either performed alongside parsing or in a postpass that traverses the ir produced by the parser. We call this analysis eitherEngineering a Compiler.
DOI: 10.1016/B978-0-12-088478-0.00004-9c 2012, Elsevier Inc. All rights reserved.Copyright 161162 CHAPTER 4 Context-Sensitive Analysis“context-sensitive analysis,” to differentiate it from parsing, or “semanticelaboration,” since its elaborates the ir. This chapter explores two techniquesfor organizing this kind of analysis in a compiler: an automated approachbased on attribute grammars and an ad hoc approach that relies on similarconcepts.Conceptual RoadmapTo accumulate the contextual knowledge needed for further translation, thecompiler must develop ways of viewing the program other than syntax. Ituses abstractions that represent some aspect of the code, such as a type system, a storage map, or a control-flow graph.
It must understand the program’sname space: the kinds of data represented in the program, the kinds of datathat can be associated with each name and each expression, and the mapping from a name’s appearance in the code back to a specific instance of thatname. It must understand the flow of control, both within procedures andacross procedures. The compiler will have an abstraction for each of thesecategories of knowledge.This chapter focuses on mechanisms that compilers use to derive contextsensitive knowledge. It introduces one of the abstractions that the compilermanipulates during semantic elaboration, the type system. (Others are introduced in later chapters.) Next, the chapter presents a principled automaticapproach to implementing these computations in the form of attributegrammars.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
