Compiladores, Aula Nº 9 João M. P. Cardoso - ppt carregar
Compiladores, Aula Nº 9 João M. P. Cardoso
PublicouHeitor Cubas Alterado mais de 4 anos atrás
Apresentação em tema: "Compiladores, Aula Nº 9 João M. P. Cardoso"— Transcrição da apresentação:
1 Compiladores, Aula Nº 9 João M. P. Cardoso
Análise Sintáctica Compiladores, Aula Nº 9 João M. P. Cardoso Aula 9
2 Sintaxe em Linguagens de Programação
Linguagens regulares deficientes para especificar a sintaxe das linguagens de programação Porquê? Construções com sintaxe encadeada (a+(b-c))*(d-(x-(y-z))) if (x < y) if (y < z) a = 5 else a = 6 else a = 7 Linguagens regulares não têm o estado requerido para modelar encadeamento Nenhuma expressão regular para especificar linguagens com expressões com parêntesis Aula 9
3 Solução Gramáticas independentes do contexto
Reconhecimento realizado por autómatos finitos equipados com uma pilha O que são gramáticas independentes do contexto? Aula 9
4 Gramáticas Notação de Backus Naur Form (BNF) para especificar a gramática Símbolos terminais: letras maiúsculas (por vezes a negrito) e Símbolos não-terminais: iniciados por uma letra maiúscula Ou, símbolos não-terminais delimitados por < e > Numa produção (derivação) os lados esquerdo e direito são separados pelo símbolo  ou ::= Ex.: Expr  Term OP Term Produções alternativas (p1, p2, p3, ..., pn) são representadas por p1 | p2 | p3 |...| pn Ex.: Literal  BINARIO | OCTAL | INT | FLOAT Se o lado direito de uma produção não contém nenhum símbolo, então escreve-se  Ex.: Palavra   Aula 9
5 Gramáticas EBNF, ou BNF estendido
Inclui { } para representar 0 ou mais repetições de símbolos e [ ] para representar elementos opcionais Aula 9
6 Gramáticas (independentes do contexto)
Conjunto de símbolos terminais { OP, INT, OPEN, CLOSE } Cada símbolo terminal definido por expressões regulares Conjunto de símbolos não-terminais { Start, Expr } Conjunto de produções Um único símbolo não-terminal no lado esquerdo da produção (LHS) Sequência de símbolos terminais e não-terminais no lado direito da produção (RHS) OP = + | - | * | / INT = [0-9] [0-9]* OPEN = ( CLOSE = ) Start  Expr Expr  Expr OP Expr Expr  INT Expr  OPEN Expr CLOSE Aula 9
7 Jogo da produção/derivação
Dada a frase corrente Começar pelo símbolo não-terminal Start Repetir até não haver símbolos não-terminais Seleccionar um símbolo não-terminal Seleccionar uma produção com símbolos não-terminais em LHS Substituir símbolo não-terminal com o RHS da produção Substituir a expressão regular com as Strings correspondentes String gerada está na linguagem Nota: selecções diferentes produzem Strings diferentes Aula 9
8 Produção/Derivação Start Expr Expr OP Expr OPEN Expr CLOSE OP Expr
INT = [0-9] [0-9]* OPEN = ( CLOSE = ) 1) Start  Expr 2) Expr  Expr OP Expr 3) Expr  INT 4) Expr  OPEN Expr CLOSE Start Expr Expr OP Expr OPEN Expr CLOSE OP Expr OPEN Expr OP Expr CLOSE OP Expr OPEN INT OP Expr CLOSE OP Expr OPEN INT OP Expr CLOSE OP INT OPEN INT OP INT CLOSE OP INT ( ) + 1 Aula 9