「LALR法」の版間の差分

ある LR(0) 文法での状態 <tt>S</tt> におけるアイテム <tt>I</tt> の Follow-set は、文法上 <tt>I</tt> の左辺の非終端記号の後に出現可能な全記号を含む。一方、状態 <tt>S</tt> におけるアイテム <tt>I</tt> の Lookahead-set は、状態 <tt>S</tt> で構文解析を開始したときの <tt>I</tt> の右辺に出現可能な記号のみを含む。''follow''(<tt>I</tt>) は左辺が同じ <tt>I</tt> である全 LR(0)アイテムの Lookahead-set の和集合と等価であり、状態やアイテムの右辺は考慮されていない。従って、Follow-set からは文脈情報が失われている。Lookahead-set は特定の構文解析向けであるため、さらに選別が可能で、Follow-set よりも詳細な識別が可能となる。

 

* Richard Bornat ''Understanding and Writing Compilers'', Macmillan, 1979. （構文解析と構文解析表などの基本原理を解説）