課件編譯原理編譯原理課件屬性文法語法制導(dǎo)2005課件說明lrreview-預(yù)覽頁
【正文】 , but your intuition should tell you that an LR(1) parser uses more information the LL(1) parser Parsing miscellany A different way of resolving ambiguity Ambiguity in a grammar means we have two or more leftmost derivations for the same input string, or equivalently, that we can build more than one parse trees for the same input string. Common examples: E – E + E | E * E | (E) | id S – iSeS | iS | a rewriting the grammar to introduce new intermediate nonterminals that force the precedence that we desired. to build an SLR(1) table for this grammar. 3. try to build an LL(1) table for this grammar 。). b) If [S39。 – S? is in Ii then set action[i,] to accept. c) If A – u?av is in Ii and succ(Ii, a) = Ij, then set action[i,a] to shift j (a must be a terminal). 3. The goto transitions for state i are constructed for all nonterminals A using the rule: If GO(Ii, A) = Ij, then goto [i, A] = j. 4. All entries not defined by rules 2 and 3 are errors. 5. The initial state is the one constructed from the configurating set containing S39。 – S? is in Ii then set action[i,] to accept. c) If A – u?av is in Ii and GO(Ii, a) = Ij, then set action[i,a] to shift j (a is a terminal). 3. The goto transitions for state i are constructed for all nonterminals A using the rule: If GO(Ii, A) = Ij, then goto [i, A] = j. 4. All entries not defined by rules 2 and 3 are errors. 5. The initial state is the one constructed from the configurating set containing S39。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。). b) If S39。). b) If S39。 – S). 2. State i is determined from Ii. The parsing actions for the state are determined as follows: a) If [A – u?, a] is in Ii then set Action[i,a] to reduce A – u (note A may not be
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1