Parsing Bottom-Up

Parsing bottom-up de "2 + 3 * 4":

Pilha                   Entrada              Ação
-----                   -------              ----
                        2 + 3 * 4 $          shift
2                       + 3 * 4 $            reduce (factor → NUMBER)
factor                  + 3 * 4 $            reduce (term → factor)
term                    + 3 * 4 $            reduce (expr → term)
expr                    + 3 * 4 $            shift
expr +                  3 * 4 $              shift
expr + 3                * 4 $                reduce (factor → NUMBER)
expr + factor           * 4 $                reduce (term → factor)
expr + term             * 4 $                shift (NÃO reduce! * tem precedência)
expr + term *           4 $                  shift
expr + term * 4         $                    reduce (factor → NUMBER)
expr + term * factor    $                    reduce (term → term * factor)
expr + term             $                    reduce (expr → expr + term)
expr                    $                    ACEITAR

A decisão crítica: quando a pilha tem "expr + term" e a entrada tem "*",
o parser faz SHIFT (não reduce), porque * tem precedência maior que +.
Isso garante que 3*4 seja avaliado antes de 2+3.

Handle: a substring β tal que S ⇒*rm αAw ⇒rm αβw,
onde ⇒rm denota derivação rightmost.

Parsing bottom-up reconstrói a derivação rightmost EM REVERSO:
cada reduce corresponde a um passo da derivação, mas de trás para frente.

Derivação rightmost de "2 + 3 * 4":
  expr
  ⇒ expr + term
  ⇒ expr + term * factor
  ⇒ expr + term * 4
  ⇒ expr + factor * 4
  ⇒ expr + 3 * 4
  ⇒ term + 3 * 4
  ⇒ factor + 3 * 4
  ⇒ 2 + 3 * 4

O parser bottom-up lê "2 + 3 * 4" e reconstrói essa derivação
de baixo para cima (invertendo a sequência acima).

Identificar o handle correto é a questão central:
  Em "expr + term" com "*" na entrada, o handle NÃO é "expr + term",
  porque reduzir agora produziria a árvore errada (2+3 primeiro).

Variantes de parsers LR:

LR(0)  - Sem lookahead. Decide apenas pelo estado da pilha.
           Muito restritivo — poucas gramáticas práticas.
SLR(1) - Simple LR. Usa conjuntos FOLLOW para desambiguar reduces.
           Simples de implementar, mas limitado.
LALR(1)- Look-Ahead LR. Mescla estados do LR(1) canônico com
           mesmo core, mantendo lookaheads distintos.
           Compromisso prático (usado por yacc/bison/PLY).
LR(1)  - Canonical LR. Cada item carrega um token de lookahead.
           Mais poderoso, mas tabelas podem ser enormes.

Poder:               LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1)
Tamanho da tabela:   LR(0) < SLR(1) = LALR(1) << LR(1)
Uso na prática:      LALR(1) é o padrão

Tabela de ação (ACTION) e tabela de desvio (GOTO):
  ACTION[estado, terminal] → shift s / reduce p / accept / error
  GOTO[estado, não-terminal] → novo estado

Para a produção: expr → expr '+' term

Os itens possíveis são:
  expr → . expr '+' term    (nada lido ainda)
  expr → expr . '+' term    (expr lido, esperando '+')
  expr → expr '+' . term    ('+' lido, esperando term)
  expr → expr '+' term .    (tudo lido, pronto para reduce)

Operação CLOSURE(I):
  Para cada item [A → α . B β] em I,
  adicione [B → . γ] para toda produção B → γ.
  (Se o ponto está antes de um não-terminal, expanda-o.)

Operação GOTO(I, X):
  Para cada item [A → α . X β] em I,
  adicione [A → α X . β] ao novo conjunto.
  Depois aplique closure.

Autômato LR(0) para a gramática:
  S' → expr             (produção aumentada)
  expr → term | expr '+' term
  term → NUMBER

Estado 0 (inicial): closure({S' → . expr})
  S' → . expr
  expr → . term
  expr → . expr '+' term
  term → . NUMBER
  ── NUMBER → Estado 1
  ── term   → Estado 2
  ── expr   → Estado 3

Estado 1: term → NUMBER .       [REDUCE por term → NUMBER]
Estado 2: expr → term .         [REDUCE por expr → term]
Estado 3:
  S' → expr .                   [ACCEPT se lookahead = $]
  expr → expr . '+' term
  ── '+' → Estado 4

Estado 4: expr → expr '+' . term
  term → . NUMBER
  ── NUMBER → Estado 1
  ── term   → Estado 5

Estado 5: expr → expr '+' term . [REDUCE por expr → expr '+' term]

Tabela SLR(1) para a gramática de expressões:

FOLLOW(S') = { $ }
FOLLOW(expr) = { +, $ }
FOLLOW(term) = { +, $ }

         ACTION                          GOTO
Estado | NUMBER |  +   |  $   ||  expr  | term
-------|--------|------|------||--------|------
  0    |  s1    |      |      ||   3    |  2
  1    |        | r3   | r3   ||        |
  2    |        | r2   | r2   ||        |
  3    |        | s4   | acc  ||        |
  4    |  s1    |      |      ||        |  5
  5    |        | r1   | r1   ||        |

Onde: s1 = shift para estado 1
      r1 = reduce por produção 1 (expr → expr + term)
      r2 = reduce por produção 2 (expr → term)
      r3 = reduce por produção 3 (term → NUMBER)
      acc = aceitar

Shift-Reduce Conflict:
  O parser não sabe se deve empilhar o próximo token ou reduzir.
  Exemplo clássico — dangling else:
    if (a) if (b) s1 else s2
    O "else" casa com qual "if"?
  Resolução: preferir shift (else casa com o if mais próximo).

Reduce-Reduce Conflict:
  O parser tem duas produções possíveis para reduzir.
  Exemplo: um identificador pode ser tipo ou variável.
    declaration: type ID | type ID '(' params ')'
    expression:  ID | ID '(' args ')'
  Ambos podem reduzir ID. Resolução: reescrever a gramática.

Em PLY/yacc, conflitos podem ser resolvidos declarativamente:
  %left '+' '-'          # associativo à esquerda, menor precedência
  %left '*' '/'          # associativo à esquerda, maior precedência
  %right UMINUS          # unário, maior precedência de todas
  %nonassoc '==' '!='    # não associativo (a == b == c é erro)

class ShiftReduceParser:
    """Parser shift-reduce com tabela de ação explícita."""

    def __init__(self, action_table, goto_table, productions):
        self.action = action_table   # {(estado,token): ação}
        self.goto = goto_table       # {(estado,nonterminal): estado}
        self.productions = productions  # [(head, body_len), ...]

    def parse(self, tokens):
        """Parse uma lista de tokens usando shift-reduce."""
        stack = [0]     # pilha de estados
        symbols = []     # pilha de símbolos (para a AST)
        pos = 0

        while True:
            state = stack[-1]
            tok = tokens[pos] if pos < len(tokens) else '$'
            key = (state, tok if isinstance(tok, str) else tok[0])

            if key not in self.action:
                raise SyntaxError(f"Erro no estado {state}, token {tok}")

            action = self.action[key]

            if action[0] == 's':  # shift
                stack.append(action[1])
                symbols.append(tok)
                pos += 1
                print(f"  SHIFT {tok} → estado {action[1]}")

            elif action[0] == 'r':  # reduce
                prod_idx = action[1]
                head, body_len = self.productions[prod_idx]
                # Desempilha body_len símbolos
                children = symbols[-body_len:] if body_len > 0 else []
                del stack[-body_len:]
                del symbols[-body_len:]
                # Empilha o não-terminal
                symbols.append((head, children))
                stack.append(self.goto[(stack[-1], head)])
                print(f"  REDUCE {head} ← {body_len} símbolos")

            elif action[0] == 'acc':
                print("  ACCEPT")
                return symbols[0]

import ply.yacc as yacc
import ply.lex as lex

# --- Lexer ---
tokens = ('NUMBER', 'PLUS', 'MINUS', 'STAR', 'SLASH', 'LPAREN', 'RPAREN')
t_PLUS   = r'\+'
t_MINUS  = r'-'
t_STAR   = r'\*'
t_SLASH  = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
t_ignore = ' \t'

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

def t_error(t):
    t.lexer.skip(1)

lexer = lex.lex()

# --- Parser (LALR(1) via PLY) ---
# Precedência: resolve conflitos shift-reduce
precedence = (
    ('left', 'PLUS', 'MINUS'),
    ('left', 'STAR', 'SLASH'),
)

def p_expr_binop(p):
    '''expr : expr PLUS expr
           | expr MINUS expr
           | expr STAR expr
           | expr SLASH expr'''
    p[0] = ('binop', p[2], p[1], p[3])

def p_expr_paren(p):
    '''expr : LPAREN expr RPAREN'''
    p[0] = p[2]

def p_expr_number(p):
    '''expr : NUMBER'''
    p[0] = ('num', p[1])

def p_error(p):
    print(f"Erro de sintaxe em {p}")

parser = yacc.yacc()
result = parser.parse("2 + 3 * 4")
print(result)
# ('binop', '+', ('num', 2), ('binop', '*', ('num', 3), ('num', 4)))

YAML parsing de uma configuração harness.os (simplificado):

Input YAML:
  rules:
    - title: "Commit Hygiene"
      context: git-commit
    - title: "Token Economy"
      context: all

Shift-reduce trace (conceitual):
  shift 'rules'  → shift ':'  → reduce KEY
  shift '-'      → shift 'title' → shift ':' → shift valor → reduce PAIR
  shift 'context' → shift ':' → shift valor → reduce PAIR
  reduce MAPPING (2 pares)
  reduce LIST_ITEM
  ... (repete para segundo item)
  reduce LIST (2 items)
  reduce DOCUMENT

Resolução de regras (bottom-up):
  regra₁ avalia → triggered      ← folha
  regra₂ avalia → not triggered  ← folha
  concern.governance agrega      ← reduce
  domain.build agrega            ← reduce
  project.decision               ← raiz