Gramáticas Recursivas e Fatoração a esquerda

Prévia do material em texto

Gramáticas Recursivas 
 
Definição: 
Uma gramática é dita recursiva à esquerda se ela tiver um não-terminal A tal 
que A =>A para alguma cadeia w. 
Método de Parsing TOP-DOWN não manipulam gramáticas recursivas à 
esquerda. 
Eliminando Recursividade a Esquerda: 
 Recursividade Direita: 
A  A |  => A A' 
 A'  A' |  
Exemplo: 
 E  E + T | T E TE' 
 T  T * F | F => E'  +TE' |  
 F  (E) | id T  FT' 
 T'  *FT' |  
 F > (E) | id 
A  A| AAAn | | | ... | n 
 A A'| A'  | nA' 
 A'  A'| A'nA' |  
 
 Recursividade Indireta 
Exemplo: S  Aa | b 
 A  Ac | Sd |  
S  Aa  Sda 
Algoritmo para Eliminar Recursividade a Esquerda 
Input: G - gramática sem ciclos 
 1. Sejam A1, A2 ... An os não terminais de G 
 2. for i := 2 to n do 
 for j := 1 to i - 1 do 
 begin 
 (a) substitua cada produção da forma pelas produções da 
forma Ai  Ajpelas produções Ai , se Aj i 
forem produções de G. 
 (b) elimine as recursividades direta das produções Ai. 
 end 
Exemplo: 
 1. S, A 
 2. (a) i = 2, j = 1, A Sd => AAad 
 Abd 
 (b) A bdA' 
 A'adA' | cA' |  
 
Fatoração à Esquerda: 
Para adiar o impasse entre duas regras de produção que podem ser aplicadas. 
 A  =Fatoração a esquerda=> A A' 
 A'  
Método de Fatoração : Para cada não-terminal a, achar o maior prefixo 
comum a 2 ou mais de suas alternativas. Se  é diferente de(prefixo 
comum não-trivial) substituir todas as produções de A 
n, onde representa as alternativas que não começam 
por , por: A A' |  
 A' n 
 
Exemplo: (1) S iEtS | iEtSeS | a 
 E b 
 (1) e (2) são 
ambíguas 
 (2) S iEtSS' | a 
 S'eS |  
E b