Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * Pilha num * ( num + num ) Buffer com string de entrada SHIFT Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * num * ( num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * SHIFT num * ( num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * REDUCE num * ( num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * REDUCE Expr num * ( num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * SHIFT Expr num * ( num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * SHIFT * Expr num ( num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * REDUCE Op Expr num * ( num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * SHIFT Op Expr num * ( num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * SHIFT ( Op Expr num * num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * SHIFT ( Op Expr num * num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * SHIFT num ( Op Expr num * + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * REDUCE SHIFT Expr ( Op Expr num * num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * SHIFT Expr ( Op Expr num * num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * + SHIFT Expr ( Op Expr num * num num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * Op REDUCE SHIFT Expr ( Op Expr num * num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * Op SHIFT Expr ( Op Expr num * num + num ) num Op Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * SHIFT Expr ( Op Expr num * num + ) Expr Op Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * REDUCE SHIFT Expr ( Op Expr num * num + num ) REDUCE SHIFT Expr ( Op Expr Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * Expr Op Expr num * num + num ) SHIFT Expr ( Op Expr Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * Expr Op Expr num * num + num ) Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * ) SHIFT Expr ( Op Expr Expr Op Expr num * num + num Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * ) REDUCE Expr Op Expr Expr Expr ( num * Op Expr num + num ) Expr Expr Op REDUCE Expr ( Expr Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Expr Op Op Op * Expr num * num + num ) Expr Expr Op ACCEPT! Expr ( Expr Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Expr Op Op Op * Expr num * num + num Conflitos que podem Ocorrer Conflito Reduce/Reduce O topo da pilha pode “casar” com RHS de produções múltiplas Qual a produção a utilizar na redução? Conflito Shift/Reduce Pilha pode “casar” com RHS da produção Mas esse pode não ser o “casamento” correcto Pode ser necessário deslocar a entrada e encontrar mais tarde uma redução diferente Conflitos Gramática Original Expr Expr Op Expr Expr (Expr) Expr - Expr Expr num Op + Op Op * Nova Gramática Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflitos Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * num - num Conflitos SHIFT Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * num - num Conflitos Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * SHIFT num - num Conflitos Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * REDUCE SHIFT Expr num - num Conflitos Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * SHIFT Expr num - num Conflitos Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * SHIFT Expr num num Conflito shift/reduce/reduce Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Opções: Expr Reduce Reduce Shift num num Conflito shift/reduce/reduce O que acontece se escolhernos Reduce REDUCE Expr num num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce O que acontece se escolhernos Reduce Expr SHIFT Expr num num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce O que acontece se escolhernos Reduce num Expr SHIFT Expr num - Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce O que acontece se escolhernos Reduce REDUCE Expr Expr Expr num - num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce O que acontece se escolhernos Reduce Expr Expr FAILS! Expr num - num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Utilizando o outro Reduce Expr num num Conflito shift/reduce/reduce Utilizando o outro Reduce Expr num num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce Utilizando o outro Reduce REDUCE Op Expr num num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce Utilizando o outro Reduce SHIFT num Op Expr num - Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce Utilizando o outro Reduce REDUCE Expr Op Expr num - num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce Utilizando o outro Reduce REDUCE Expr Expr Op Expr num - num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflito shift/reduce/reduce Utilizando o outro Reduce Expr Expr Op ACCEPT Expr num - num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflitos Utilizando o Shift SHIFT Expr num num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflitos Utilizando o Shift SHIFT num Expr num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflitos Utilizando o Shift REDUCE Expr Expr num num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflitos Utilizando o Shift Expr REDUCE Expr Expr num - num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op * Conflitos Utilizando o Shift Expr ACCEPT Expr Expr num - num Expr Expr Op Expr Expr Expr - Expr Expr (Expr) Expr Expr Expr num Op + Op Op *