Análise Sintática – Parte 2

• Árvores Sintáticas Abstratas (ASTs)

• Scanning

Representação da árvore (Programa)

Program

C

ASTs em Java – Programas

public abstract class AST { … }public class Program extends AST { public Command C; …}

Representação da árvore (Comando)

IfCommand

E C2

WhileCommand

E C

LetCommand

D C

AssignCommand

E

CallCommand

Identifier E

spelling

SequentialCommand

C1 C2V

C1

ASTs em Java – Comandos

public abstract class Command extends AST { … }public class AssignCommand extends Command { public Vname V; public Expression E; …}public class CallCommand extends Command { public Identifier I; public Expression E; …}

ASTs em Java – Comandos (2)

public class SequentialCommand extends Command { public Command C1,C2; …}public class IfCommand extends Command { public Expression E; public Command C1,C2; …}

ASTs em Java – Comandos (3)

public class WhileCommand extends Command { public Expression E; public Command C; …}public class LetCommand extends Command { public Declaration D; public Command C; …}

Representação da árvore (Expressão)

BinaryExpression

E1 E2

UnaryExpression

Operator E

IntegerExpression

IntegerLiteral

spelling

VnameExpression

V

Operator

spelling spelling

ASTs em Java – Expressões

public abstract class Expression extends AST { … }public class UnaryExpression extends Expression { public Operator O; public Expression E; …}public class BinaryExpression extends Expression { public Operator O; public Expression E1,E2; …}

Representação da árvore (V-name)

SimpleVname

Identifier

spelling

ASTs em Java – Vname

public abstract class Vname extends AST { … }public class SimpleVname extends Vname { public Identifier I; …}

Representação da árvore (Declaração)

SequentialDeclaration

D2

ConstDeclaration

Identifier E

spelling

D1

VarDeclaration

Identifier E

spelling

ASTs em Java – Declaração

public abstract class Declaration extends AST { … }public class ConstDeclaration extends Declaration { public Identifier I; public Expression E; …}public class VarDeclaration extends Declaration { public Identifier I; public TypeDenoter T; …}

Representação da árvore (Denotador de Tipos)

SimpleTypeDenoter

Identifier

spelling

ASTs em Java – Denotador de Tipos

public abstract class TypeDenoter extends AST { … }public class SimpleTypeDenoter extends TypeDenoter { public Identifier I; …}

ASTs em Java – Terminais

public abstract class Terminal extends AST { public String spelling; … }public class Identifier extends Terminal { …}public class IntegerLiteral extends Terminal { …}public class Operator extends Terminal { …}

ASTs em Java – Construção da árvore

private ASTN parseN ( ) { ASTN itsAST; parse N, at the same time constructing itsAST return itsAST;}

ASTs em Java – Exemplo: ParseSingleDeclaration

private Declaration parseSingleDeclaration ( ) { Declaration declAST; switch (currentToken.kind) { case Token.CONST: { acceptIt( ); Identifier iAST = parseIdentifier( ); accept(Token.IS); Expression eAST = parseExpression( ); declAST = new ConstDeclaration(iAST, eAST); } break; case Token.VAR: … return declAST;}

ASTs em Java – Exemplo: ParseCommand

private Declaration parseCommand ( ) { Command c1AST = parseSingleCommand( ); while (currentToken.kind == Token.SEMICOLON) { acceptIt( ); Command c2AST = parseSingleCommand( ); c1AST = new SequentialCommand(c1AST, c2AST); } return c1AST;}

ASTs em Java – Exemplo: ParseIdentifier

private Identifier parseIdentifier ( ) { Identifier idAST; if (currentToken.kind == Token.IDENTIFIER) { idAST = new Identifier(currentToken.spelling); currentToken = scanner.scan( ); } else report error return idAST;}

ASTs em Java – Exemplo: Parser

public class Parser { private Token currentToken; … public Program parse ( ) { currentToken = scanner.scan( ); Program progAST = parseProgram( ); if (currentToken.kind != Token.EOT) report error return progAST;}

Scanning (Análise léxica)

• funciona de forma semelhante ao parser, mas em um maior nível de detalhe.

• Especificado usando expressões regulares/EBNF (Gramática léxica)

• Símbolos terminais são caracteres

Especificação do Scanner

Token ::= Identifier | Integer-Literal | Operator | ; | : | := | ~ | ( | ) | eotIdentifier ::= Letter | Identifier Letter | Identifier DigitInteger-Literal ::= Digit | Integer-Literal DigitOperator ::= + | - | * | / | < | > | = | \Separator ::= Comment | space | eolComment ::= ! Graphic* eol

Especficação do Scanner (2)

Token ::= Letter (Letter | Digit)* | Digit Digit* | + | - | * | / | < | > | = | \ | ; | : | := | ~ | ( | ) | eot

Separator ::= ! Graphic* eol | space | eol

Exemplo: Scanner

private byte scanToken( ) { switch (currentChar) { case ‘a’: case ‘b’: … case ‘z’: takeIt( ); while (isLetter(currentChar) || isDigit(currentChar)) takeIt( ); return Token.IDENTIFIER; … case ‘\n’ : takeIt( ); return Token.EOL case ‘:’ : takeIt( ); if (currentChar == ‘=’) { takeIt(); return Token.BECOMES; } else return Token.COLON; …

Exemplo: Scanner (2)

public class Scanner { private char currentChar = … private byte currentKind; private String currentSpelling; private void take (char expectedChar) {…} private void takeIt ( ) {…} private byte scanToken( ) {…} private void scanSeparator( ) {…}

Exemplo: Scanner (3)

public class Scanner { … public Token scan ( ) { while (currentChar == ‘!’ || currentChar == ‘ ’ || currentChar == ‘\n’) scanSeparator( ); currentSpelling = new StringBuffer(“”); currentKind = scanToken( ); return new Token(currentKind, currentSpelling.toString); }}

Exemplo: Token

public class Token { public byte kind; public String spelling; public Token (byte kind, String spelling) { this.kind = kind; this.spelling = spelling; if (kind == IDENTIFIER) verifica se é palavra reservada e muda o kind }}