College Online
0%

Gramaticas Livres de Contexto

Modulo 3 · Aula 1 ~22 min de leitura Nivel: Intermediario

Video da aula estara disponivel em breve

Por que Gramaticas?

Na fase lexica, transformamos caracteres em tokens. Agora, na fase sintatica, precisamos verificar se os tokens estao organizados numa estrutura valida. Para isso, usamos gramaticas livres de contexto (Context-Free Grammars, CFGs).

Uma CFG consiste em quatro elementos:

Notacao BNF

A Backus-Naur Form (BNF) e a notacao padrao para escrever CFGs:

BNF 
# Gramatica para expressoes aritmeticas simples
# Terminais: NUMBER, ID, +, -, *, /, (, )

expr   ::= expr '+' term
         | expr '-' term
         | term

term   ::= term '*' factor
         | term '/' factor
         | factor

factor ::= '(' expr ')'
         | NUMBER
         | ID

# Esta gramatica codifica precedencia:
# * e / tem precedencia maior que + e -
# Parenteses tem precedencia maxima

Derivacoes

Uma derivacao mostra como uma string pode ser gerada a partir do simbolo inicial, aplicando producoes passo a passo:

Diagrama 
Derivar "x + 2 * y" (derivacao mais a esquerda):

expr
=> expr '+' term                    (regra: expr -> expr '+' term)
=> term '+' term                    (regra: expr -> term)
=> factor '+' term                  (regra: term -> factor)
=> ID '+' term                      (regra: factor -> ID)
=> ID '+' term '*' factor           (regra: term -> term '*' factor)
=> ID '+' factor '*' factor         (regra: term -> factor)
=> ID '+' NUMBER '*' factor         (regra: factor -> NUMBER)
=> ID '+' NUMBER '*' ID             (regra: factor -> ID)
=> x + 2 * y


Arvore de derivacao (parse tree):

            expr
           / | \
         expr '+' term
          |      / | \
        term   term '*' factor
          |      |        |
       factor  factor     ID(y)
          |      |
        ID(x)  NUMBER(2)
i
Leftmost vs. Rightmost Na derivacao leftmost (mais a esquerda), sempre expandimos o nao-terminal mais a esquerda primeiro. Na rightmost, o mais a direita. Parsers top-down usam derivacoes leftmost; parsers bottom-up usam rightmost (em reverso). Ambas produzem a mesma arvore se a gramatica nao for ambigua.

Ambiguidade

Uma gramatica e ambigua se existe alguma string que pode ser derivada de duas formas diferentes (gerando duas arvores de derivacao distintas). Isso e um problema serio para compiladores.

BNF 
# Gramatica AMBIGUA para expressoes:
expr ::= expr '+' expr
       | expr '*' expr
       | NUMBER

# A string "2 + 3 * 4" tem DUAS arvores:

# Arvore 1: (2 + 3) * 4 = 20        Arvore 2: 2 + (3 * 4) = 14
#       expr                                expr
#      / | \                               / | \
#   expr '*' expr                       expr '+' expr
#   / | \      |                          |     / | \
# expr '+' expr NUMBER(4)            NUMBER(2) expr '*' expr
#  |         |                                   |         |
# NUMBER(2) NUMBER(3)                         NUMBER(3)  NUMBER(4)

# SOLUCAO: usar a gramatica com precedencia (expr/term/factor)
# que garante uma unica arvore de derivacao

Eliminando Ambiguidade

Tecnicas comuns para eliminar ambiguidade:

BNF 
# 1. Precedencia via niveis de producao (expr > term > factor)
#    Ja vimos acima.

# 2. Associatividade via recursao
#    Recursao a esquerda = associativo a esquerda
expr ::= expr '+' term    # a + b + c = (a + b) + c
#    Recursao a direita = associativo a direita
assign ::= ID '=' assign  # a = b = c = a = (b = c)

# 3. Dangling else: "if a then if b then s1 else s2"
#    Pertence ao if interno ou externo?
# Ambigua:
stmt ::= 'if' expr 'then' stmt
       | 'if' expr 'then' stmt 'else' stmt

# Desambiguada (cada else casa com o if mais proximo):
stmt        ::= matched | unmatched
matched     ::= 'if' expr 'then' matched 'else' matched
              | other_stmt
unmatched   ::= 'if' expr 'then' stmt
              | 'if' expr 'then' matched 'else' unmatched

No harness.os

A estrutura de uma definicao de workflow no harness.os pode ser descrita por uma CFG:

BNF 
# Gramatica para definicoes de workflow do harness.os

workflow     ::= header steps

header       ::= 'slug' ':' IDENTIFIER NEWLINE
                 'title' ':' STRING NEWLINE
                 'description' ':' STRING NEWLINE

steps        ::= step
               | steps step

step         ::= STEP_NUM '.' action NEWLINE

action       ::= 'Call' tool_call result_clause
               | 'Run' tool_call result_clause
               | 'Check' condition result_clause
               | 'Log' tool_call result_clause

tool_call    ::= IDENTIFIER '(' arg_list ')'

arg_list     ::= IDENTIFIER
               | arg_list ',' IDENTIFIER
               | /* vazio */

result_clause ::= '->' DESCRIPTION
                | /* vazio */

condition    ::= IDENTIFIER comparator VALUE

comparator   ::= '==' | '!=' | '>' | '<'

Essa CFG define exatamente quais sequencias de tokens formam um workflow valido. Um parser baseado nessa gramatica pode validar workflows automaticamente e reportar erros precisos.

Resumo

Exercicio

Escreva uma CFG completa para definicoes de workflow do harness.os. A gramatica deve cobrir: cabecalho (slug, title, description), steps numerados, acoes (Call, Run, Check, Log), tool calls com argumentos, e clausulas de resultado. Teste derivando pelo menos 2 workflows completos.

Verifique seu entendimento

Uma gramatica e ambigua quando:

  • Tem mais nao-terminais do que terminais
  • Usa recursao a esquerda e a direita
  • Existe uma string que pode ser derivada de duas formas diferentes, gerando arvores distintas
  • O simbolo inicial aparece no lado direito de alguma producao