「LALR法」の版間の差分

削除された内容追加された内容

インライン

2008年2月13日 (水) 01:13時点における版

LALR法（英: LALR parser）は、構文解析手法の一種であり、Lookahead（先読み）LR法の略である。単純LR法（SLR法）の構文解析器よりも多くの文脈自由文法を扱うことができる。構文解析表の大きさがあまり大きくなく、多くの文法を扱えることから、最も一般的な構文解析器となっている。yacc や GNU bison といったコンパイラコンパイラの多くもこの種の構文解析器を生成する。

SLR法と同様、LALR法では LR(0) の構文解析表を必要とする。SLR 法では Follow-set を使って reduce アクションを構築するのに対して、LALR法では Lookahead-set を使う。Lookahead-set は構文解析により特化している。Follow-set は関連する記号の集合だが、Lookahead-set はLR(0)アイテムと構文解析状態に特化した集合である。

ある LR(0) 文法での状態 S におけるアイテム I の Follow-set は、文法上 I の左辺の非終端記号の後に出現可能な全記号を含む。一方、状態 S におけるアイテム I の Lookahead-set は、状態 S で構文解析を開始したときの I の右辺に出現可能な記号のみを含む。follow(I) は左辺が同じ I である全 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. （構文解析と構文解析表などの基本原理を解説）

@@ 1行目: / 1行目: @@
 '''LALR法'''（[[英語|英]]: '''LALR parser'''）は、[[構文解析]]手法の一種であり、Lookahead（先読み）[[LR法]]の略である。[[単純LR法]]（SLR法）の[[構文解析器]]よりも多くの[[文脈自由文法]]を扱うことができる。[[構文解析表]]の大きさがあまり大きくなく、多くの文法を扱えることから、最も一般的な構文解析器となっている。[[yacc]] や [[Bison|GNU bison]] といった[[コンパイラコンパイラ]]の多くもこの種の構文解析器を生成する。
-SLR法と同様、LALR法では LR(0) の構文解析表を必要とする。SLR 法では Follow-set を使って reduce アクションを構築するのに対して、LALR法では Lookahead-set を使う。Lookahead-set は構文解析により特化している。Follow-set は関連する記号の集合だが、Lookahead-set は[[LR法#アイテム|LR(0)アイテム]]と構文解析状態に特化した集合である。
+SLR法と同様、LALR法では LR(0) の構文解析表を必要とする。SLR 法では Follow-set を使って reduce アクションを構築するのに対して、LALR法では [[先読み|Lookahead-set]] を使う。Lookahead-set は構文解析により特化している。Follow-set は関連する記号の集合だが、Lookahead-set は[[LR法#アイテム|LR(0)アイテム]]と構文解析状態に特化した集合である。
 ある 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 よりも詳細な識別が可能となる。