「LALR法」の版間の差分

m
ロボットによる: 細部の編集
m (ロボットによる 追加: ko:LALR)
m (ロボットによる: 細部の編集)
ある 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 よりも詳細な識別が可能となる。
 
== 参考文献 ==
* Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. ''Compilers: Principles, Techniques, and Tools.'' Addison--Wesley, 1986. (LALR(1)構文解析器の構築に関する従来からの技法の解説)
* Frank DeRemer and Thomas Pennello. Efficient Computation of LALR(1) Look-Ahead Sets. ''ACM Transactions on Programming Languages and Systems (TOPLAS)'' 4:4, pp. 615–649. 1982. (より効率的な LALR(1)構文解析器構築技法の説明)
* Richard Bornat ''Understanding and Writing Compilers'', Macmillan, 1979. (構文解析と構文解析表などの基本原理を解説)
 
251,035

回編集