E → E + T | T
T → T * F | F
F → id
id + id * id
EE ⇒ E + T⇒ T + T (expande E→T)⇒ F + T (T→F)⇒ id + T (F→id)⇒ id + T * F (T→T*F)⇒ id + F * F (T→F)⇒ id + id * F (F→id)⇒ id + id * id (F→id)EE ⇒ E + T⇒ E + T * F (T→T*F)⇒ E + T * id (F→id)⇒ E + F * id (T→F)⇒ E + id * id (F→id)⇒ T + id * id (E→T)⇒ F + id * id (T→F)⇒ id + id * id (F→id)id + id * id* tenha maior precedência que +, então a redução T → T * F acontece antes de E → E + T. (profluizricardomantovani.com)id * id + id e simule.id + ( id * id ) e mostre que a ordem não muda.+ verificando id + id + id.E → E + T | TT → T * F | FF → id | ( E )id + id * idx, y) ou um operando simples. E
┌────────┴────────┐
E + T
| ├───────────┐
T T F
| | |
F F id
| |
id id
Observação: oTda direita expande paraT * F, e depois esseTviraF → id, resultando no ramoT -> T * F -> F * F -> id * id. OEda esquerda viraT -> F -> id. A estrutura final éE = (id) + (id * id), respeitando a precedência:*é reduzido antes do+.
E
⇒ E + T
⇒ E + T * F
⇒ E + F * F
⇒ E + id * F
⇒ T + id * F
⇒ F + id * F
⇒ id + id * F
⇒ id + id * id
F→id, T→F, E→T constroem o ramo esquerdo (id).shift de +, vêm id e * para formar o ramo direito: primeiro F→id, depois T→F, e só então T→T*F, fechando id * id.E→E+T une os dois ramos, concluindo com accept.E → E + T | TT → T * F | FF → id | ( E )id * id + id (precedência: * antes de +) E
┌────────┴────────┐
E + T
| |
T F
┌─────┴─────┐ |
T * id
| |
F F
| |
id id
T → T * F (id * id), depois E → E + T soma o último id.id + ( id * id ) (parênteses reforçam a mesma ordem) E
┌────────┴────────┐
E + T
| |
T F
| |
F (
| E
id |
T
┌─────┴─────┐
T *
| |
F F
| |
id id
)
F → ( E ) cujo E interno reduz a T → T * F (id * id). Resultado estrutural idêntico ao caso-base.id + id + id (associatividade à esquerda do +) E
┌──────────┴──────────┐
E + T
┌─────────┴─────────┐ |
E + T F
| | |
T F id
| |
F id
|
id
E → E + T aplicado duas vezes encadeia à esquerda: (id + id) + id.ccdd$ ccdd$ → s(c) → s(c) → s(d) → r(C→d) → s(d) → r(C→d) → r(C→cC) → r(S→CC) → accept.c d d (inválida) e indique onde o erro é detectado.A→α se o próximo token ∈ FOLLOW(A). (profluizricardomantovani.com)a A d)A→ε só quando o lookahead ∈ FOLLOW(A) = { d }.ad é aceito (reduz A→ε antes de consumir d) e que abcd também é aceito (reduz A→bc antes).A → b e verifique se surgem conflitos em LR(0) e como o SLR(1) os elimina.if E then if E then S else S, o parser não sabe a qual if associar o else. Em LR, isso aparece como células com shift e reduce simultâneos. (profluizricardomantovani.com)else).id + id * id produz duas árvores.^ (potência) como direita-associativo e simule id ^ id ^ id.$ onde couber).A, os itens LR(1) terão a forma [A→•d, a] etc., carregando o lookahead.A→d na presença de a/c. (Este é um exemplo clássico para comparar LR(0), SLR e LR(1).)%{
#include <stdio.h>
#include <stdlib.h>
void yyerror(const char* s){ fprintf(stderr,"Erro: %s\n", s); }
int yylex(void);
%}
%token ID NUM
%left '+' '-'
%left '*' '/'
%right UMINUS
%%
expr : expr '+' expr { /* ... */ }
| expr '*' expr { /* ... */ }
| '-' expr %prec UMINUS { /* ... */ }
| '(' expr ')' { /* ... */ }
| ID { /* ... */ }
| NUM { /* ... */ }
;
%%
int main(){ return yyparse(); }
^ (potência) como %right '^'.3 + 4 * 5.*.output) e encontre as entradas ACTION/GOTO que correspondem ao Ex. 1.expr : expr error expr { yyerror("faltou operador"); }.tokens = ('ID','NUM','PLUS','TIMES','LP','RP','MINUS')
t_PLUS=r'\+'; t_TIMES=r'\*'; t_LP=r'\('; t_RP=r'\)'
precedence = (
('right', 'UMINUS'),
('left', 'PLUS'),
('left', 'TIMES'),
)
def p_expr_plus(p): 'expr : expr PLUS expr'
def p_expr_times(p): 'expr : expr TIMES expr'
def p_expr_group(p): 'expr : LP expr RP'
def p_expr_id(p): 'expr : ID'
def p_expr_num(p): 'expr : NUM'
def p_expr_uminus(p): 'expr : MINUS expr %prec UMINUS'
def p_error(p): print("Erro sintático")
POW) como direita-associativa e valide em 2^3^2.ID '(' expr ')' e discuta como isso afeta a tabela.id + * id. Simule até o ponto em que a ACTION entra em erro e produza uma mensagem “esperava id ou ( após +”.%error-verbose e compare a mensagem automática com a sua manual."O parser ascendente tenta encontrar a derivação mais à direita em ordem inversa, partindo da sentença de entrada e chegando ao símbolo inicial."
E → E + T | T
T → T * F | F
F → id | (E)
// Exemplo: gramática if-then-else ambígua
S → if E then S | if E then S else S | other
// Exemplo
S → aAc | aBd
A → b
B → b
%{
/* Declarações em C */
%}
/* Declarações Yacc */
%token NUM ID
%left '+' '-'
%left '*' '/'
%%
/* Regras gramaticais */
expr : expr '+' expr { $$ = $1 + $3; }
| NUM { $$ = $1; }
;
%%
/* Código C adicional */
%{
#include
#include
void yyerror(char *s);
int yylex();
%}
%token NUMBER ID
%left '+' '-'
%left '*' '/'
%right '^'
%nonassoc UMINUS
%%
program:
expr { printf("Resultado: %d\n", $1); }
;
expr:
expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr {
if ($3 == 0) {
yyerror("Divisão por zero");
$$ = 0;
} else {
$$ = $1 / $3;
}
}
| expr '^' expr {
int i, result = 1;
for (i = 0; i < $3; i++)
result *= $1;
$$ = result;
}
| '-' expr %prec UMINUS { $$ = -$2; }
| '(' expr ')' { $$ = $2; }
| NUMBER { $$ = $1; }
| ID { $$ = /* valor da variável */; }
;
%%
void yyerror(char *s) {
fprintf(stderr, "Erro: %s\n", s);
}
int main() {
yyparse();
return 0;
}
import ply.yacc as yacc
import ply.lex as lex
# Definição do analisador léxico
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
# Regras léxicas
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = 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):
print(f"Caractere ilegal '{t.value[0]}'")
t.lexer.skip(1)
# Construir o lexer
lexer = lex.lex()
# Regras sintáticas
def p_expression_binop(p):
'''expression : expression PLUS expression
| expression MINUS expression
| expression TIMES expression
| expression DIVIDE expression'''
if p[2] == '+' : p[0] = p[1] + p[3]
elif p[2] == '-': p[0] = p[1] - p[3]
elif p[2] == '*': p[0] = p[1] * p[3]
elif p[2] == '/': p[0] = p[1] / p[3]
def p_expression_group(p):
'expression : LPAREN expression RPAREN'
p[0] = p[2]
def p_expression_number(p):
'expression : NUMBER'
p[0] = p[1]
def p_error(p):
if p:
print(f"Erro de sintaxe em '{p.value}'")
else:
print("Erro de sintaxe no final da entrada")
# Construir o parser
parser = yacc.yacc()
# Função para testar
def parse(s):
return parser.parse(s)
# Ordem de precedência (do menor para o maior)
precedence = (
('left', 'PLUS', 'MINUS'),
('left', 'TIMES', 'DIVIDE'),
('right', 'UMINUS'), # Menos unário
)
def p_expression_uminus(p):
'expression : MINUS expression %prec UMINUS'
p[0] = -p[2]
def p_nome_da_regra(p):
'não_terminal : sequência de símbolos'
# ou
'''não_terminal : alternativa1
| alternativa2
| alternativa3'''
# Ações semânticas aqui
p[0] = ... # Valor retornado pelo não-terminal
def p_declaration(p):
'declaration : TYPE ID ASSIGN expression SEMICOLON'
p[0] = ('declare', p[1], p[2], p[4]) # Cria uma tupla representando a declaração
symbol_table[p[2]] = {'type': p[1], 'value': None} # Adiciona à tabela de símbolos
import ply.yacc as yacc
import ply.lex as lex
# Definição do analisador léxico
tokens = ('NUMBER', 'ID', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN', 'EQUALS')
# Regras léxicas
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
t_EQUALS = r'='
t_ID = r'[a-zA-Z_][a-zA-Z0-9_]*'
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
t_ignore = ' \t'
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
def t_error(t):
print(f"Caractere ilegal '{t.value[0]}'")
t.lexer.skip(1)
# Construir o lexer
lexer = lex.lex()
# Precedência e associatividade
precedence = (
('left', 'EQUALS'),
('left', 'PLUS', 'MINUS'),
('left', 'TIMES', 'DIVIDE'),
('right', 'UMINUS'),
)
# Dicionário para armazenar variáveis
variables = {}
# Regras de gramática
def p_statement_assign(p):
'statement : ID EQUALS expression'
variables[p[1]] = p[3]
p[0] = ('assign', p[1], p[3])
def p_statement_expr(p):
'statement : expression'
p[0] = ('expr', p[1])
def p_expression_binop(p):
'''expression : expression PLUS expression
| expression MINUS expression
| expression TIMES expression
| expression DIVIDE expression'''
if p[2] == '+' : p[0] = ('add', p[1], p[3])
elif p[2] == '-': p[0] = ('sub', p[1], p[3])
elif p[2] == '*': p[0] = ('mul', p[1], p[3])
elif p[2] == '/': p[0] = ('div', p[1], p[3])
def p_expression_uminus(p):
'expression : MINUS expression %prec UMINUS'
p[0] = ('neg', p[2])
def p_expression_group(p):
'expression : LPAREN expression RPAREN'
p[0] = p[2]
def p_expression_number(p):
'expression : NUMBER'
p[0] = ('num', p[1])
def p_expression_id(p):
'expression : ID'
p[0] = ('var', p[1])
def p_error(p):
if p:
print(f"Erro de sintaxe em '{p.value}'")
else:
print("Erro de sintaxe no final da entrada")
# Construir o parser
parser = yacc.yacc()
# Função para testar
def parse(s):
return parser.parse(s)
# Exemplo de uso
resultado = parse("x = 10 + 20 * (30 - 5)")
print(resultado)
# Modo detalhado de depuração
parser = yacc.yacc(debug=True)
# Ou na hora de analisar
resultado = parser.parse(texto, debug=True)
tokens = (
'NUMBER',
'PLUS', 'MINUS', 'TIMES', 'DIVIDE',
'LPAREN', 'RPAREN',
)
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
precedence = (
('left', 'PLUS', 'MINUS'),
('left', 'TIMES', 'DIVIDE'),
('right', 'UMINUS'),
)
def p_expression_binop(p):
'''expression : expression PLUS expression
| expression MINUS expression
| expression TIMES expression
| expression DIVIDE expression'''
# Implemente as operações aqui
program : statement_list
statement_list : statement
| statement_list statement
statement : if_statement
| while_statement
| print_statement
| assign_statement
if_statement : IF condition THEN statement_list END
| IF condition THEN statement_list ELSE statement_list END
while_statement : WHILE condition DO statement_list END
print_statement : PRINT expression SEMICOLON
assign_statement : ID EQUALS expression SEMICOLON
condition : expression GREATER expression
| expression LESS expression
| expression EQUALS EQUALS expression
expression : expression PLUS term
| expression MINUS term
| term
term : term TIMES factor
| term DIVIDE factor
| factor
factor : NUMBER
| ID
| LPAREN expression RPAREN
x = 10;
y = 20;
if x < y then
print x;
else
print y;
end
while x < 100 do
print x;
x = x + 10;
end
# Construir o lexer
lexer = lex.lex()
# Construir o parser usando o lexer
parser = yacc.yacc()
# Analisar uma entrada
resultado = parser.parse(texto, lexer=lexer)