Parsing Top-Down
Video da aula estara disponivel em breve
Recursive Descent Parsing
Um parser recursive descent e a implementacao mais intuitiva de um parser top-down: cada nao-terminal da gramatica vira uma funcao. O parser comeca pelo simbolo inicial e expande nao-terminais recursivamente, consumindo tokens da esquerda para a direita.
BNF
# Gramatica para recursive descent (sem recursao a esquerda):
# Precisamos eliminar recursao a esquerda da gramatica original
# Original (com recursao a esquerda - NAO funciona):
# expr ::= expr '+' term | term
# Transformada (sem recursao a esquerda - funciona):
expr ::= term expr_rest
expr_rest ::= '+' term expr_rest
| '-' term expr_rest
| /* vazio */
term ::= factor term_rest
term_rest ::= '*' factor term_rest
| '/' factor term_rest
| /* vazio */
factor ::= '(' expr ')'
| NUMBER
| ID
Python
class Parser:
"""Recursive descent parser para expressoes aritmeticas."""
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def peek(self):
if self.pos >= len(self.tokens):
return ('EOF', '')
return self.tokens[self.pos]
def consume(self, expected_type=None):
tok = self.peek()
if expected_type and tok[0] != expected_type:
raise SyntaxError(
f"Esperado {expected_type}, encontrado {tok[0]} ('{tok[1]}')"
)
self.pos += 1
return tok
# expr ::= term (('+' | '-') term)*
def parse_expr(self):
left = self.parse_term()
while self.peek()[0] in ('PLUS', 'MINUS'):
op = self.consume()
right = self.parse_term()
left = ('binop', op[1], left, right)
return left
# term ::= factor (('*' | '/') factor)*
def parse_term(self):
left = self.parse_factor()
while self.peek()[0] in ('STAR', 'SLASH'):
op = self.consume()
right = self.parse_factor()
left = ('binop', op[1], left, right)
return left
# factor ::= '(' expr ')' | NUMBER | ID
def parse_factor(self):
tok = self.peek()
if tok[0] == 'LPAREN':
self.consume('LPAREN')
node = self.parse_expr()
self.consume('RPAREN')
return node
elif tok[0] == 'NUMBER':
return ('num', self.consume()[1])
elif tok[0] == 'ID':
return ('id', self.consume()[1])
else:
raise SyntaxError(f"Token inesperado: {tok}")
# Uso com o tokenizer da aula anterior
tokens = [
('ID', 'x'), ('PLUS', '+'), ('NUMBER', '2'),
('STAR', '*'), ('ID', 'y'),
]
parser = Parser(tokens)
tree = parser.parse_expr()
print(tree)
# ('binop', '+', ('id', 'x'), ('binop', '*', ('num', '2'), ('id', 'y')))Conjuntos FIRST e FOLLOW
Para construir parsers preditivos (sem backtracking), precisamos saber qual producao escolher baseado no proximo token. Os conjuntos FIRST e FOLLOW resolvem isso:
Diagrama
FIRST(X) = conjunto de terminais que podem iniciar uma string derivada de X
FOLLOW(X) = conjunto de terminais que podem aparecer imediatamente apos X
Exemplo para a gramatica de expressoes:
FIRST(expr) = FIRST(term) = FIRST(factor) = { '(', NUMBER, ID }
FIRST('+' term expr_rest) = { '+' }
FIRST('-' term expr_rest) = { '-' }
FOLLOW(expr) = { ')', EOF }
FOLLOW(term) = { '+', '-', ')', EOF }
FOLLOW(factor) = { '*', '/', '+', '-', ')', EOF }
Regra: se o proximo token esta em FIRST(producao), use essa producao.
Se a producao pode derivar vazio (epsilon), verifique FOLLOW.LL(1) Parsing
Um parser LL(1) lê a entrada da Left to right, produz uma derivacao Leftmost, e usa 1 token de lookahead. A tabela de parsing LL(1) usa FIRST e FOLLOW:
Diagrama
Tabela LL(1) para expressoes:
| NUMBER | ID | ( | + | - | ) | EOF
--------------+----------+----------+----------+----------+----------+----------+---------
expr | term e' | term e' | term e' | | | |
expr_rest(e') | | | | + term e'| - term e'| epsilon | epsilon
term | fact t' | fact t' | fact t' | | | |
term_rest(t') | | | | epsilon | epsilon | epsilon | epsilon
| | | | * fact t'| / fact t'| |
Cada celula diz qual producao usar dado o nao-terminal atual e o proximo token.
Recursao a esquerda mata LL(1)
Se a gramatica tem recursao a esquerda (
A ::= A x), o parser LL(1) entra em loop infinito. Sempre elimine recursao a esquerda antes de implementar um parser top-down. A transformacao e mecanica: A ::= A a | b vira A ::= b A' e A' ::= a A' | epsilon.
No harness.os
Vamos construir um parser recursive descent para um formato simplificado de regras do harness.os:
Python
class RuleParser:
"""Parser para condicoes de regras do harness.os.
Gramatica:
condition ::= term (('AND' | 'OR') term)*
term ::= 'NOT'? atom
atom ::= field comparator value
| '(' condition ')'
field ::= 'context' | 'project' | 'concern' | 'phase'
comparator ::= '==' | '!=' | 'contains'
value ::= STRING
Exemplo: context == "git-commit" AND concern != "security"
"""
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def peek(self):
if self.pos >= len(self.tokens):
return ('EOF', '')
return self.tokens[self.pos]
def consume(self, expected=None):
tok = self.peek()
if expected and tok[0] != expected:
raise SyntaxError(f"Esperado {expected}, achei {tok[0]}")
self.pos += 1
return tok
def parse_condition(self):
left = self.parse_term()
while self.peek()[0] in ('AND', 'OR'):
op = self.consume()
right = self.parse_term()
left = ('logic', op[1], left, right)
return left
def parse_term(self):
if self.peek()[0] == 'NOT':
self.consume()
return ('not', self.parse_atom())
return self.parse_atom()
def parse_atom(self):
if self.peek()[0] == 'LPAREN':
self.consume('LPAREN')
node = self.parse_condition()
self.consume('RPAREN')
return node
field = self.consume('FIELD')
comp = self.consume('COMP')
val = self.consume('STRING')
return ('compare', field[1], comp[1], val[1])
# Testar
tokens = [
('FIELD', 'context'), ('COMP', '=='), ('STRING', 'git-commit'),
('AND', 'AND'),
('FIELD', 'concern'), ('COMP', '!='), ('STRING', 'security'),
]
parser = RuleParser(tokens)
tree = parser.parse_condition()
print(tree)
# ('logic', 'AND',
# ('compare', 'context', '==', 'git-commit'),
# ('compare', 'concern', '!=', 'security'))Resumo
- Recursive descent: cada nao-terminal e uma funcao; o mais intuitivo dos parsers
- Recursao a esquerda deve ser eliminada para parsers top-down
- FIRST/FOLLOW determinam qual producao escolher com base no proximo token
- LL(1) usa uma tabela de parsing construida com FIRST/FOLLOW
- Na pratica, recursive descent com operador-precedence (Pratt parsing) e o padrao industrial
Exercicio
Implemente um parser recursive descent para condicoes de regras do harness.os. O parser deve suportar: campos (context, project, concern, phase), comparadores (==, !=, contains), operadores logicos (AND, OR, NOT), e parenteses para agrupamento. Teste com condicoes compostas.
Verifique seu entendimento
Por que um parser LL(1) nao funciona com gramaticas que tem recursao a esquerda?