Parsing Bottom-Up

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

Pilha                   Entrada              Acao
-----                   -------              ----
                        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 (NAO reduce! * tem precedencia)
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

Nota: a decisao entre shift e reduce em "expr + term" com "*" na entrada
e o que torna parsers bottom-up mais poderosos que top-down.

Variantes de parsers LR:

LR(0)  - Sem lookahead. Muito restritivo, poucas gramaticas.
SLR(1) - Simple LR. Usa FOLLOW sets para desambiguar. Simples mas limitado.
LALR(1)- Look-Ahead LR. Compromisso pratico (usado por yacc/bison/PLY).
LR(1)  - Canonical LR. Mais poderoso, mas tabelas enormes.

Poder: LR(0) < SLR(1) < LALR(1) < LR(1)
Tamanho da tabela: LR(0) < SLR(1) = LALR(1) << LR(1)

Na pratica: LALR(1) e o padrao. Aceita a maioria das gramaticas
de linguagens de programacao com tabelas de tamanho razoavel.

Para a producao: expr -> expr '+' term

Os itens possiveis sao:
  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)

Automato LR(0) para expr -> term | expr '+' term:

Estado 0 (inicial):
  S' -> . expr
  expr -> . term
  expr -> . expr '+' term
  term -> . NUMBER

  -- NUMBER --> Estado 1
  -- term   --> Estado 2
  -- expr   --> Estado 3

Estado 1: term -> NUMBER .       [REDUCE]
Estado 2: expr -> term .         [REDUCE]
Estado 3: expr -> expr . '+' term
  S' -> expr .                   [ACCEPT se $]
  -- '+' --> Estado 4

Estado 4: expr -> expr '+' . term
  term -> . NUMBER
  -- NUMBER --> Estado 1
  -- term   --> Estado 5

Estado 5: expr -> expr '+' term . [REDUCE]

Shift-Reduce Conflict:
  O parser nao sabe se deve empilhar o proximo token ou reduzir.
  Exemplo classico: dangling else
  Resolucao tipica: preferir shift (else casa com o if mais proximo)

Reduce-Reduce Conflict:
  O parser tem duas producoes possiveis para reduzir.
  Exemplo: um identificador pode ser tipo ou variavel dependendo do contexto.
  Resolucao: reescrever a gramatica ou usar precedencia

Em PLY/yacc, conflitos podem ser resolvidos declarativamente:
  %left '+' '-'          # associativo a esquerda, menor precedencia
  %left '*' '/'          # associativo a esquerda, maior precedencia
  %right UMINUS          # unario, maior precedencia de todas

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) ---
# Precedencia: 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 configuracao 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