課件，編譯原理，編譯原理課件，屬性文法，語法制導(dǎo)，2005課件說明，lrreview(已修改)
2025-05-21 23:12 本頁面
【正文】 Bottomup parsing Bottomup parsing algorithms are in general more powerful than topdown methods, but not surprisingly, the constructions required in these algorithms are also more plex. It is difficult to write a bottomup parser by hand for anything but the most trivial of grammars, but fortunately,there are excellent parser generator tools like yacc that build a parser from an input specification. Shiftreduce parsing is the most monly used and most powerful of the bottomup techniques. LR parsing LR parsers (“L” for left to right scan of input。 “R” for rightmost derivation) are efficient, tabledriven shiftreduce parsers. The class of grammars that can be parsed using LR methods is a proper superset of the class of grammars that can be parsed with predictive LL parsers. In fact,virtually all programming language constructs for which CFGs can be written can be parsed with LR techniques. . An LR parser uses two tables: 1. The action table Action[s,a] tells the parser what to do when the state on top of the stack is s and terminal a is the next input token. The possible actions are to shift a state onto the stack, to reduce the handle on top of the stack, to accept the input, or to report an error. 2. The goto table Goto[s,X] indicates the new state to place on top of the stack after a reduce of the nonterminal X while state s is on top of the stack. The two tables are usually bined, with the action table specifying entries for terminals, and the goto table specifying entries for nonterminals. Types of LR parsers There are three types of LR parsers: LR(k), simple LR(k), and lookahead LR(k) (abbreviated to LR(k), SLR(k), LALR(k)). The k identifies the number of tokens of lookahead. We will usually only concern ourselves with 0 or 1 tokens of lookahead, but it does generalize to k 1. The different classes of parsers all operate the same way (as shown above, being driven by their action and goto tables), but they differ in how their action and goto tables are constructed, and the size of those tables. Constructing LR(0) parsing tables LR(0) configuration or item. A configuration is a production of the grammar with a dot at some position on its right side. 1. Construct F = {I0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1