Sintaxe AbstractaTopAnálise LéxicalAnálise Sintáctica

Análise Sintáctica

Princípios

Precisamos de recursão.

Gramáticas de Contexto Livre

Conjunto de produções da forma:

symbol -> symbol symbol ...symbol

Gramáticas de Contexto Livre: Exemplo

Derivações e Árvores Sintácticas

Derivações podem ser:

Árvores sintácticas obtêm-se ligando cada símbolo ao símbolo de onde foi derivado:

Gramáticas ambíguas

1-2-3 tem 2 soluções:

Gramáticas ambíguas II

Parser Predictivo

Parser Predictivo: Sem Conflitos

enum token { IF, THEN, ELSE, BEGIN,
      END, PRINT, SEMI, NUM, EQ };
extern enum token getToken(void);

enum token tok;
void advance() {tok = getToken();}
void eat(enum token t)
  {if (tok ==t) advance(); else error();}

void S(void){ switch(tok) {
   case IF:     eat(IF); E(); eat(THEN); S();
     eat(ELSE); S(); break;
   case BEGIN:  eat(BEGIN); S(); L(); break;
   case PRINT:  eat(PRINT); E(); break;
   default: error();
}}

void L(void){ switch(tok) {
   case END:   eat(END); break;
   case SEMI:  eat(SEMI); S(); L(); break;
   default: error();
}}

void E(void) {
   eat(NUM); eat(EQ); eat(NUM);
}

Parser Predictivo: Conflitos

Parser Predictivo: Conflitos II

FIRST e FOLLOW

FIRST e FOLLOW: Algoritmo

  1. Inicializar FIRST e FOLLOW como vazio, nullable como falso;
  2. Para cada terminal FIRST[Z] <- Z;
  3. repetir:
    para cada X -> Y1 Y2 ... Yk
      se todos Yi anuláveis, nullable(X) <- TRUE
      para cada i = 1...k, j = i+1...k
        se Y1...Yi-1 anuláveis ou i = 1,
          FIRST[X] <- FIRST[X] UFIRST[Yi]
        se Yi+1...Yk anuláveis ou i = k,
          FOLLOW[Yi] <-
                       FOLLOW[Yi] UFOLLOW[X]
      se Yi+1...Yj-1 anuláveis ou i+1 = j,
        FOLLOW[Yi] <- FOLLOW[Yi] UFIRST[Yj]
    até FIRST,FOLLOW, e nullable fixos.

Parsers Predictivos: Implementação

Eliminação da Recursão à Esquerda

Factores à Esquerda

Recuperação de Erros

Parsing LR

LR: Algoritmo

LR em Acção

1 a := 7 ; b := c + ( d := 5 + 6 , d ) $ shift
1 id4 := 7 ; b := c + ( d := 5 + 6 , d ) $ shift
1 id4 :=6 7 ; b := c + ( d := 5 + 6 , d ) $ shift
1 id4 :=6 num10 ; b := c + ( d := 5 + 6 , d ) $ E -> num
1 id4 :=6 E11 ; b := c + ( d := 5 + 6 , d ) $ S -> id := E
1 S2 ; b := c + ( d := 5 + 6 , d ) $ shift
1 S2 ;3 b :=c + ( d := 5 + 6 , d ) $ shift
1 S2 ;3 id4 := c + ( d := 5 + 6 , d ) $ shift
1 S2 ;3 id4 :=6 c + ( d := 5 + 6 , d ) $ shift
1 S2 ;3 id4 :=6 id20 + ( d := 5 + 6 , d ) $ E -> id
1 S2 ;3 id4 :=6 E11 + ( d := 5 + 6 , d ) $ shift
1 S2 ;3 id4 :=6 E11+16 ( d := 5 + 6 , d ) $ shift
1 S2 ;3 id4 :=6 E11 +16(8 d := 5 + 6 , d ) $ shift

1 S2 ;3 id4 :=6 E11 +16(8 id4

:= 5 + 6 , d ) $ shift
1 S2 ;3 id4 :=6 E11 +16(8 id4 :=6 5 + 6 , d ) $ shift
1 S2 ;3 id4 :=6 E11 +16(8 id4 :=6 num10 + 6 , d ) $ E -> num
1 S2 ;3 id4 :=6 E11 +16(8 id4 :=6 E11 + 6 , d ) $ shift
1 S2 ;3 id4 :=6 E11 +16(8 id4 :=6 E11 +16 6 , d ) $ shift
1 S2 ;3 id4 :=6 E11 +16(8 id4 :=6 E11 +16 num10 , d ) $ E -> num
1 S2 ;3 id4 :=6 E11 +16(8 id4 :=6 E11 +16 E17 , d ) $ E -> E + E
1 S2 ;3 id4 :=6 E11 +16(8 id4 :=6 E11 , d ) $ S -> id := E
1 S2 ;3 id4 :=6 E11 +16(8 S12 , d ) $ shift
1 S2 ;3 id4 :=6 E11 +16(8 S12 ,18 d ) $ shift
1 S2 ;3 id4 :=6 E11 +16(8 S12 ,18 id20 ) $ E -> id
1 S2 ;3 id4 :=6 E11 +16(8 S12 ,18 E21 ) $ shift
1 S2 ;3 id4 :=6 E11 +16(8 S12 ,18 E21 )22 $ E -> (S,E)

1 S2 ;3 id4 :=6 E11 +16 E17

$ E -> E+E
1 S2 ;3 id4 :=6 E11 $ S -> id := E
1 S2 ;3 S5 $ S -> S;S
1 S2 $ accept

LR: A Tabela

id num print ; , + := ( ) $ S E L
1 s4 s7 g2
2 s3 a
3 s4 s7 g5
4 s6
5 r1 r1 s6 r1
6 s20s10 s8 g11
7 s9
8 s4 s7 g12
9 s20s10 s8 g15g14
10 r5 r5 r5 r5 r5

11

r2 r2 s16 r2
12 s3 s18
13 r3 r3 r3
14 s19 s13
15 r8 r8
16 s20s10 s8 g17
17 r6 r6 s16 r6 r6
18 s20s10 s8 g21
19 s20s10 s8 g23
20 r4 r4 r4 r4 r4

21

s22
22 r7 r7 r7 r7 r7
23 r9 s16 r9

LR(0)

LR(0): os Estados

LR(0): Acções Básicas

As acções principais são então:

LR(0): O Algoritmo

A partir de S' -> S$ :
T <- { Fecho({S' -> .S$})
E -> {}
repita
  para cada estado I em T
    para cada item A -> alpha. X beta em I
        J <=Avance(I,X)
        T <- T U{J}
        E <- E U{I X -> J}
até E e T fixos.

LR(0): Construção da Tabela

LR(0): Resultados

Os estados:

A tabela:

LR(0): Problemas

Gramática:

S -> E $
E -> + E
E -> T
T -> X

SLR(0): Problemas

LR(1)

LR(1): Continuação

LR(1): Grafo Exemplo

LR(1): Tabela Exemplo

LALR

LALR: Exemplo

Hierarquia de Gramáticas

LR: Gramáticas Ambíguas

LR: Resolvendo Ambiguidade

  1. Reescrever a gramática
  2. Aceitar o conflito shift-reduce: preferimos shift.

Só usar:

YACC: Introdução

Programa da forma:
declarações
%%
regras da gramática
%%
programas

onde

Declarações:
lista de terminais, não terminais, etc.
Regras:
da forma
exp: exp PLUS exp {programa em C}
Programas:
código C a usar de dentro das regras.

YACC: Exemplo

%{
int yylex(void);
void yyerror(char *s) {
  EM_error(EM_tokPos, ``%s'', s);
}
%}
%token ID WHILE BEGIN END DO
   IF THEN ELSE SEMI ASSIGN
%start prog
%%
prog: stmlist

stm : ID ASSIGN ID
    | WHILE ID DO stm
    | BEGIN stmlist END
    | IF ID THEN stm
    | IF ID THEN stm ELSE stm

stmlist : stm
        | stmlist SEMI stm

YACC: Conflitos

YACC diz que existem conflitos shift-reduce e reduce-reduce

YACC: Recuperação de Erros

YACC: Recuperação Global

Ideia: ignorar tokens que causaram o problema.


vitor@cos.ufrj.br

Sintaxe AbstractaTopAnálise LéxicalAnálise Sintáctica