LALR(1) パース表

• LR(1) 表は，多くの状態を伴い大変大規模になる．先読み集合を除いて， アイテムが同一の 2 つの状態をマージすることにより，小さな表にすること を考える．
• このパーサを LALR(1) パーサという(Look-Ahead LR(1))．
• 例えば，Grammar 3.26 の LR(1) パーサの状態 6 と 13 は(図3.27)， 先読みトークン集合を除けば，同一となる．
• また，状態 7 と 12 は，先読みトークン集合を除けば，同一となる． 同様に 8 と 11，10 と 14 である．
• これらの状態の組をマージしたものが，LALR(1) パース表に，図 3.28b に示す．
• LALR(1) 表に conflicts(シフト-還元または，還元-還元) を含んでい る文法でも，LR(1) 表には含まれないかもしれない。しかし，実際にはこの問 題は少ない．
• LALR(1) パース表が必要としているのは，その状態数を減らすことによ り，LR(1) 表を少ないメモリで表現することである．