Apresentação - Parsing Descendente Recursivo

Prévia do material em texto

Análise Sintática (Análise Sintática (ParsingParsing))
João Luís Tavares
2
Analisador SintáticoAnalisador Sintático
A análise sintática verifica se as construções usadas no 
programa estão gramaticalmente corretas:
Programa
fonte
Analisador
Léxico
Analisador
Sintático
Leitura tokens
Tabela de
Símbolos
lex()
 Erros
 Léxicos
 Erros
Sintáticos
Árvore de
derivação
3
Tipos de Tipos de ParsersParsers
Análise Top-down ou descendente : a árvore sintática é 
construída da raiz para as folhas. Em cada passo da 
análise, um lado esquerdo de produção é substituído por 
um lado direito (expansão). Existem 3 tipos:
descendente recursivo com retrocesso (backtracking);
descendente recursivo preditivo;
tabular preditivo;
Análise Bottom-up ou redutiva (ascendente) : a árvore 
sintática é construída das folhas em direção à raiz. Neste 
caso, em cada passo da análise, um lado direito de 
produção é substituído por um símbolo variável (redução)
4
Tipos de Tipos de ParsersParsers
Análise Bottom-up ou redutiva (ascendente) : a árvore 
sintática é construída das folhas em direção à raiz. Neste 
caso, em cada passo da análise, um lado direito de 
produção é substituído por um símbolo variável (redução). 
Podem ser de 3 tipos:
SLR (Simple LR): de fácil implementação abrangendo 
uma classe menor de gramáticas;
LR Canônico: mais poderoso, pode ser aplicado a um 
grande número de linguagens;
LALR (Lookahead LR): nível intermediário, funciona 
para a maioria das linguagens e pode ser implementado 
eficientemente.
5
Análise sintática descendente recursiva c/retrocesso
Um algoritmo informal para os ASD parte do símbolo 
inicial, marcado como um nodo ativo: A  a1| a2 | ... a
k
se o nodo ativo é uma variável (A), escolher a primeira 
alternativa (a1=X1 ... Xk) para A e criar k descendentes 
diretos rotulados X1 ... Xk; X1 é o nodo ativo. Se k=0, o 
nodo à direita de A é o nodo ativo.
se o nodo ativo é um terminal (a= a), comparar o símbolo de 
entrada corrente com o nodo a: 
se combinam, o nodo imediatamente à direita torna-se ativo e o 
símbolo a é consumido;
se não combinam, fazer retrocesso e tentar a próxima alternativa.
Se nenhuma alternativa é possível, voltar ao nodo anterior, e 
assim por diante.
6
Análise sintática descendente recursiva c/retrocesso
Dada a produção de uma GLC, S  aSbS | aS | c, as 
árvores parciais para aacbc são:
 a b S S
 a b
 S
 S S
 a b S S
 a b S S
 a b
 S
 S S
 a S
 a b S S
 a b
 S
 S S
 a b S S
 a b
 S
 S S
 c
 a b S S
 a b
 S
 S S
 c c
 a b
 S
 S S
(c)(b)(a)
(d) (e) (f)
7
Análise sintática descendente recursiva c/retrocesso
Ao chegar a (f) não há mais símbolos para a forma 
sentencial restante bS e, portanto, o backtracking leva de 
volta à árvore (a) para outras alternativas de S :
 a S
 a b
 S
 S S
 c
 a S
 a b
 S
 S S
 c
 c
 a S
 a b
 S
 S S
(a) (b) (c)
8
ASDRR - Implementação
Suponha uma GLC que gera listas: 
{S  a | [L] , L  S ; L | S}
Criar uma função para cada não-terminal:
int S() {
 if( token=='a' ) {
 matchToken('a');
 return true;
 } else {
 if( token=='[' )
 matchToken('[');
 if( L() ) {
 if( token==']' ) {
 matchToken(']');
 return true;
 }
 }
 }
 return false;
}
int L() {
 marcaToken(token);
 if( S() ) {
 if( token==';' ) {
 matchToken(';');
 if( L() )
 return true;
 else
 return false;
 } else {
 retrocede();
 if( S() )
 return true;
 }
 }
 return false;
}
char token;
void main() {
 if( S() )
 printf(“aceita”);
 else
 printf(“rejeita”);
}
9
Análise Sintática PreditivaAnálise Sintática Preditiva
A análise considera o símbolo de entrada na escolha das 
regras de produção. Exige que a gramática:
não seja recursiva à esquerda;
seja fatorada à esquerda;
seja unívoca quanto aos primeiros terminais deriváveis.
10
Exemplo Parser Exemplo Parser (1)(1)
<Program> ::= <DefinitionList>
<DefinitionList> ::= <DefinitionList> <Definition>
 | <Definition>
<Definition> ::= <Template> <ClassDefinition>
 | <ClassDefinition>
<Template> ::= “template” “<” TypeList “>”
<TypeList> ::= <TypeList> “,” <TypeName> | <TypeName>
<ClassDefinition> ::= “class” <TypeName> “{” <Members> “}”
<TypeName> ::= <id>
11
void ClassDefinition() {
matchToken(T_CLASS);
}
<ClassDefinition> ::= “class” <TypeName> “{” <Members> “}”
<TypeName> ::= <id>
lookahead é global;
void matchToken(int expected) {
if( lookahead != expected )
error(“Erro de Sintaxe”);
else
// obtém próximo token
lookahead = Lex(); 
}
Exemplo Parser Exemplo Parser (2)(2)
12
void ClassDefinition() {
matchToken(T_CLASS);
TypeName();
matchToken(T_LBRACE);
Members();
matchToken(T_RBRACE);
}
<ClassDefinition> ::= “class” <TypeName> “{” <Members> “}”
<TypeName> ::= <id>
Exemplo Parser Exemplo Parser (3)(3)
void TypeName() {
matchToken(T_ID);
}
void Members() {
/* ... */;
}
13
Exemplo Parser Exemplo Parser (4)(4)
Program ::= DefinitionList
DefinitionList ::= DefinitionList Definition
 | Definition
Definition ::= Template ClassDefinition
 | ClassDefinition
Template ::= “template” “<” TypeList “>”
TypeList ::= TypeList “,” TypeName | TypeName
ClassDefinition ::= “class” TypeName “{” Members “}”
TypeName ::= <id>
14
void Definition() {
if (lookahead == T_TEMPLATE) {
Template();
ClassDefinition();
} else
if (lookahead == T_CLASS){
ClassDefinition();
} else
error(“Esperado CLASS ou TEMPLATE);
}
Definition ::= Template ClassDefinition | ClassDefinition
Template ::= “template” “<” TypeList “>”
ClassDefinition ::= “class” TypeName “{” Members “}”
Exemplo Parser Exemplo Parser (5)(5)
15
Exemplo Parser Exemplo Parser (6)(6)
Program ::= DefinitionList
DefinitionList ::= DefinitionList Definition
 | Definition
Definition ::= Template ClassDefinition
 | ClassDefinition
Template ::= “template” “<” TypeList “>”
TypeList ::= TypeList “,” TypeName | TypeName
ClassDefinition ::= “class” TypeName “{” Members “}”
TypeName ::= <id>
16
void Typelist() {
TypeName();
TypeList1();
}
void TypeList1() {
matchToken(T_COMMA);
TypeName();
TypeList1();
}
TypeList ::= TypeList “,” TypeName | TypeName
Removendo a recursão direita:
TypeList ::= TypeName TypeList1
TypeList1 ::= “,” TypeName TypeList1 | e
Exemplo Parser Exemplo Parser (7)(7)
void TypeList1() {
if( lookahead == T_COMMA) {
matchToken(T_COMMA);
TypeName();
TypeList1();
} else { /* e */ }
}
17
void commands() {
matchToken(T_IF);
expr();
matchToken(T_then);
...
}
<commands> ::= “if” <expr> “then” <commands> 
 | “while” <expr> “do” <comsands> 
 | “repeat” <list> “until” <expr> 
 | “id” “:=” <expr>
Regras unívocasRegras unívocas
void commands() {
if( lookahead == T_IF) {
Conditional();
else
if( lookahead == T_WHILE ||
 lookahead == T_REPEAT)
Iterative();
else
...
}
Ao invés:
18
First(u): conjunto de todos terminais que começam 
qualquer sequência derivável de u.
Se existe um t Î T e um v Î V* tal que u Þ* tv então t 
Î First(u);
Se u Þ* e então e Î First(u).
EXEMPLO:
Os conjuntos First para <commands> seriam:
First(conditional) = {if}
First(iterative) = {repeat, while}
First(atrib) = {id}
Conjuntos Conjuntos FIRSTFIRST
19
Construindo Construindo FIRSTFIRST((uu))
Dada uma GLC G=(V,T,P,S), para calcular FIRST(u) para todo u 
Î (VT), aplica-se as seguintes regras:
 se t Î T, FIRST( t ) = { t };
 se u  e Î P, FIRST(u) = FIRST(u)  e ;
 se u Î V e a Î T:
 se u  Y
1...k
aa Î P e i=1..k, Y
i
 Þ* e, FIRST(u) = 
FIRST(u)  a;
 se u  Y
1...k
Ba Î P e i=1..k, Y
i
 Þ* e, FIRST(u) = 
FIRST(u)  FIRST(B).
20
Considerando uma GLC geral:
 A  u
1
 |u
2
 | u
3
onde u
i
 é um não-terminal, a implementação deve considerar 
produções que não começam por terminais 
Conjuntos Conjuntos FIRSTFIRST
void A() {
 switch (lookahead) {
 case FIRST(u1): // prever A ::= u1
 /* código para u1 */
return;
 case FIRST(u2): // prever A ::= u2/* código para u2 */
 return;
 ...
 default:
 error(“syntax error”);
 }
}
21
EXEMPLO 2:
 A  B|C|D First(A) = {b,c,d}
 B  b First(B) = {b}
 C  c First(C) = {c}
 D  d First(D) = {d}
Conjuntos Conjuntos FIRSTFIRST
void A() {
 switch (lookahead) {
 case 'b':
 B();
 return;
 case 'c':
 C();
 return;
 ...
 default:
 error(“syntax error”);
 }
}
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21