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  *