14 Aug 2006 15:08:19 -0400

Related articles |
---|

Efficient construction of LALR Parsing Tables yasmina.andreu@gmail.com (Yasmina) (2006-08-14) |

Re: Efficient construction of LALR Parsing Tables boldyrev+nospam@cgitftp.uiggm.nsc.ru (Ivan Boldyrev) (2006-08-15) |

Re: Efficient construction of LALR Parsing Tables yasmina.andreu@gmail.com (Yasmina) (2006-08-19) |

From: | "Yasmina" <yasmina.andreu@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 14 Aug 2006 15:08:19 -0400 |

Organization: | http://groups.google.com |

Keywords: | parse, LALR, question |

Posted-Date: | 14 Aug 2006 15:08:19 EDT |

Hello.

I am writing an LALR(1) parser-generator using the "Efficient

Construction of LALR Parsing Table" techniques from the dragon book. I

have a question regarding the parsing actions generated by I from the

kernel alone.

" Reduction by A -> e is called for on input a if and only if there is

a kernel item [B -> g · Cd, b] such that C => An for some n, and a is

in FIRST(ndb). The set of nonterminals A such that C => An can be

precomputed for each nonterminal C."

"We shift on input a if there is a kernel item [B -> g · Cd, b] where

C => ax in a derivation in which the last step does not use an

e-production. The set of such a's can also be precomputed for each C"

(Note. "e" means the empty string and "=>" means a rightmost derives in

zero or more steps,)

I don't know how to precompute the set of nonterminals A and the set of

terminals a. I think that the only way to precompute this sets is

derive the grammar, but this isn't efficient.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.