Página Inicial>Relacionado com a programação>Visual Básico
Baixar

aParser

O projeto é um compilador que pega um programa de origem escrito em C# (entrada) e depois o traduz em um programa de destino escrito em Visual Basic (saída) . Este processo é feito passando por três módulos ( Tokenizer , Parser e Translator ) respectivamente. Cada módulo será explicado separadamente neste relatório.

Tokenizador

O que é o tokenizador?

Tokenizer / Lexical Analyzer é um programa que pega uma sequência de caracteres (entrada) e gera uma sequência de tokens (saída).

Definições de tokens

O tokenizer possui uma lista de definições para cada token possível que pode produzir agrupando uma sequência de caracteres. Cada definição de token consiste em:

  • Tipo : usado para distinguir entre tokens
  • Expressão regular (RegEx) : usada para capturar (corresponder) os valores

As tabelas a seguir representam todas as definições utilizadas no projeto, com um exemplo de valor(es) correspondente(s) para cada uma.

Palavras-chave

Tipo Expressão regular Valores correspondentes
Usando usando using
Aula aula class
Se se if
Outro outro else
Para para for
Fazer fazer do
Enquanto enquanto while
Trocar trocar switch
Caso caso case
Quebrar quebrar break
Padrão padrão default
Retornar retornar return
Nulo nulo null
Verdadeiro verdadeiro true
Falso falso false
Falso (vazio | var) | (bool | char | short | int | long | float | double | decimal | string | String) ([] | ?)? void
bool
char?
int[]

Valores

Tipo Expressão regular Valores correspondentes
Número d*.d+ | d+ 77
.25
3.14
Corda "[^"]*" "This is string"
Identificador [a-zA-Z_]w* fact
_private
iD_1
Comentário (?<=//) .*? (?=(r | n | //)) // inline comment
Comentário multilinha (?<=/*) (?:(?!*/)(?:.|[rn]))* (?=*/) /*
multi line
comment
*/

Operadores

Tipo Expressão regular Valores correspondentes
E && | & &&
&
Ou || | | ||
|
Não ! !
Igual = =
MaisIgual += +=
MenosIgual -= -=
DuploIgual == ==
Diferente != !=
Menor que < <
Maior que > >
Menos que ou igual <= <=
Maior que ou igual >= >=

Símbolos

Tipo Expressão regular Valores correspondentes
OpenRoundBracket ( (
CloseRoundBracket ) )
OpenCurlyBracket { {
FecharCurlyBracket } }
AbraSquareBracket [ [
CloseSquareBracket ] ]
Mais + +
Menos - -
DoublePlus ++ ++
DoubleMinuses -- --
Por cento % %
Asterisco * *
Barra invertida \
Barra para frente / /
Barras DoubleForward // //
ForwardSlashAsterisk /* /*
AsteriskForwardSlash */ */
Ponto . .
Vírgula , ,
Cólon : :
Ponto e vírgula ; ;

Implementação

Todos esses tipos de token são agrupados como enum no arquivo TokenType.cs. 

 public enum TokenType
{
    // Keywords
    Using ,               // using
    Class ,               // class
    If ,                  // if
    Else ,                // else
    For ,                 // for
    Do ,                  // do
    While ,               // while
    Switch ,              // switch
    Case ,                // case
    Break ,               // break
    Default ,             // default
    Return ,              // return
    Null ,                // null
    True ,                // true
    False ,               // false
    DataType ,            // void | bool | char? | int[]

    // Values
    Number ,              // 77 | .25 | 3.14
    String ,              // "I am 'Moaz'"
    Comment ,             // Any Character After (//) and Before (r | n | //)
    Identifier ,          // fact | _private | iD_1
    MultilineComment ,    // Any Character After (/*) and Before (*/)

    // Operators
    And ,                 // && | &
    Or ,                  // || | |
    Not ,                 // !
    Equal ,               // =
    PlusEqual ,           // +=
    MinusEqual ,          // -=
    DoubleEquals ,        // ==
    NotEqual ,            // !=
    LessThan ,            // <
    GreaterThan ,         // >
    LessThanOrEqual ,     // <=
    GreaterThanOrEqual ,  // >=

    // Symbols
    OpenRoundBracket ,    // (
    CloseRoundBracket ,   // )
    OpenCurlyBracket ,    // {
    CloseCurlyBracket ,   // }
    OpenSquareBracket ,   // [
    CloseSquareBracket ,  // ]
    Plus ,                // +
    Minus ,               // -
    DoublePluses ,        // ++
    DoubleMinuses ,       // --
    Percent ,             // %
    Asterisk ,            // *
    BackSlash ,           // 
    ForwardSlash ,        // /
    DoubleForwardSlashes , // //
    ForwardSlashAsterisk , // /*
    AsteriskForwardSlash , // */
    Dot ,                 // .
    Comma ,               // ,
    Colon ,               // :
    Semicolon            // ;
}

e suas definições são criadas e armazenadas em List<TokenDefinition> no arquivo Tokenizer.cs. 

 private readonly List < TokenDefinition > _tokenDefinitions = new List < TokenDefinition >
{
    // Keywords
    new TokenDefinition ( TokenType . Using , @"using" ) ,
    new TokenDefinition ( TokenType . Class , @"class" ) ,
    new TokenDefinition ( TokenType . If , @"if" ) ,
    new TokenDefinition ( TokenType . Else , @"else" ) ,
    new TokenDefinition ( TokenType . For , @"for" ) ,
    new TokenDefinition ( TokenType . Do , @"do" , 1 ) ,
    new TokenDefinition ( TokenType . While , @"while" ) ,
    new TokenDefinition ( TokenType . Switch , @"switch" ) ,
    new TokenDefinition ( TokenType . Case , @"case" ) ,
    new TokenDefinition ( TokenType . Default , @"default" ) ,
    new TokenDefinition ( TokenType . Break , @"break" ) ,
    new TokenDefinition ( TokenType . Return , @"return" ) ,
    new TokenDefinition ( TokenType . Null , @"null" ) ,
    new TokenDefinition ( TokenType . True , @"true" ) ,
    new TokenDefinition ( TokenType . False , @"false" ) ,
    new TokenDefinition ( TokenType . DataType , @"(void|var)|(bool|char|short|int|long|float|double|decimal|String|string)([]|?)?" ) ,

    // Values
    new TokenDefinition ( TokenType . Number , @"d*.d+|d+" ) ,
    new TokenDefinition ( TokenType . String , @"""[^""]*""" ) ,
    new TokenDefinition ( TokenType . Identifier , @"[a-zA-Z_]w*" , 1 ) ,
    new TokenDefinition ( TokenType . Comment , @"(?<=//).*?(?=(r|n|//))" ) ,
    new TokenDefinition ( TokenType . MultilineComment , @"(?<=/*)(?:(?!*/)(?:.|[rn]))*(?=*/)" ) ,

    // Operators
    new TokenDefinition ( TokenType . And , @"&&|&" ) ,
    new TokenDefinition ( TokenType . Or , @"||||" ) ,
    new TokenDefinition ( TokenType . Not , @"!" , 1 ) ,
    new TokenDefinition ( TokenType . Equal , @"=" , 1 ) ,
    new TokenDefinition ( TokenType . PlusEqual , @"+=" ) ,
    new TokenDefinition ( TokenType . MinusEqual , @"-=" ) ,
    new TokenDefinition ( TokenType . DoubleEquals , @"==" ) ,
    new TokenDefinition ( TokenType . NotEqual , @"!=" ) ,
    new TokenDefinition ( TokenType . LessThan , @"<" , 1 ) ,
    new TokenDefinition ( TokenType . GreaterThan , @">" , 1 ) ,
    new TokenDefinition ( TokenType . LessThanOrEqual , @"<=" ) ,
    new TokenDefinition ( TokenType . GreaterThanOrEqual , @">=" ) ,

    // Symbols
    new TokenDefinition ( TokenType . OpenRoundBracket , @"(" ) ,
    new TokenDefinition ( TokenType . CloseRoundBracket , @")" ) ,
    new TokenDefinition ( TokenType . OpenCurlyBracket , @"{" ) ,
    new TokenDefinition ( TokenType . CloseCurlyBracket , @"}" ) ,
    new TokenDefinition ( TokenType . OpenSquareBracket , @"[" ) ,
    new TokenDefinition ( TokenType . CloseSquareBracket , @"]" ) ,
    new TokenDefinition ( TokenType . Plus , @"+" , 1 ) ,
    new TokenDefinition ( TokenType . Minus , @"-" , 1 ) ,
    new TokenDefinition ( TokenType . DoublePluses , @"++" ) ,
    new TokenDefinition ( TokenType . DoubleMinuses , @"--" ) ,
    new TokenDefinition ( TokenType . Percent , @"%" ) ,
    new TokenDefinition ( TokenType . Asterisk , @"*" , 1 ) ,
    new TokenDefinition ( TokenType . BackSlash , @"\" ) ,
    new TokenDefinition ( TokenType . ForwardSlash , @"/" , 1 ) ,
    new TokenDefinition ( TokenType . DoubleForwardSlashes , @"//" ) ,
    new TokenDefinition ( TokenType . ForwardSlashAsterisk , @"/*" ) ,
    new TokenDefinition ( TokenType . AsteriskForwardSlash , @"*/" ) ,
    new TokenDefinition ( TokenType . Dot , @"." ) ,
    new TokenDefinition ( TokenType . Comma , @"," ) ,
    new TokenDefinition ( TokenType . Colon , @":" ) ,
    new TokenDefinition ( TokenType . Semicolon , @";" ) ,
} ;
.. .

Problemas corrigidos

1. Quando o token se sobrepõe

Quando o tokenizer enfrenta alguma sequência de caracteres como ++ ele fica confuso, é um token do tipo DoublePluses ? Ou dois tokens sequenciais do tipo Plus ? Este problema também se aplica a outros tokens sobrepostos como: { + , += } & { - , -- } & { - , -= } & { / , // }

Solução:

Cada token receberá uma propriedade Priority com valor padrão 0 (Highest Priority) , e quando dois tokens se sobrepõem como + e += diminuímos a prioridade do token com comprimento mais curto + para 1 .
Agora, o tokenizer não vai mais se confundir entre + e += , e vai pegar aquele com maior prioridade += .

2. Token dentro do token

Quando o tokenizer enfrenta alguma sequência de caracteres como "String + String = String" ele produzirá três tipos de tokens que são:

  • Sequência : "String + String = String"
  • Mais : +
  • Igual : =

mas só precisamos do token com tipo String !!

Solução:

Cada token receberá propriedades de índice inicial e índice final , de modo que os tokens anteriores terão:

Tipo Valor Índice inicial Índice final
Corda "String + String = String" 0 25
Mais + 8 9
Igual = 17 18

e ignoramos qualquer início de token dentro do intervalo de outro.

Agora, o tokenizer produzirá apenas um token do tipo String e ignorará os internos.

Analisador

O que é o analisador?

Parser / Syntax Analyzer é um programa que pega uma sequência de tokens - gerados a partir do Tokenizer - e os agrupa para formar estruturas especificadas pelas produções de gramática livre de contexto (CFG) que estão sendo utilizadas.

Funções do analisador

  • Reconhecer sintaxe livre de contexto
  • Produza mensagens de erro significativas
  • Construir Representação Intermediária (RI)

Gramática Livre de Contexto (CFG)

Resumo:

  • CAPITAL_CASE : não terminal
  • small_case : Terminal
  • | : Suplentes (Ou)
  • ε : Vazio 
  PROGRAM --> IMPORTS CLASSES

  IMPORTS          --> IMPORT_STATEMENT IMPORTS | ε
  IMPORT_STATEMENT --> using IDS;

  CLASSES          --> CLASS_STATEMENT CLASSES | ε
  CLASS_STATEMENT  --> class id { SUPER_STATEMENTS }

  SUPER_STATEMENTS --> SUPER_STATEMENT SUPER_STATEMENTS | ε
  SUPER_STATEMENT  --> COMMENT_STATEMENT | FUNCTION_STATEMENT | INLINE_STATEMENT ;

  COMMENT_STATEMENT  --> // comment | /* multiline_comment */
  FUNCTION_STATEMENT --> data_type id (DECLARES) { STATEMENTS }
  INLINE_STATEMENT     --> DECSIGN_STATEMENT | DECLARE_STATEMENT | INC_DEC_STATEMENT | ASSIGN_STATEMENT | CALL_STATEMENT
    DECSIGN_STATEMENT  --> data_type id = EXPRESSION
    DECLARE_STATEMENT  --> data_type id
    INC_DEC_STATEMENT  --> id INC_DEC_OPERATOR
    ASSIGN_STATEMENT   --> id ASSIGN_OPERATOR EXPRESSION
    CALL_STATEMENT     --> IDS(EXPRESSIONS)

  STATEMENTS --> STATEMENT STATEMENTS | ε
  STATEMENT  --> SUPER_STATEMENT | STRUCT_STATEMENT

  STRUCT_STATEMENT --> IF_STATEMENT | WHILE_STATEMENT | DO_WHILE_STATEMENT | FOR_STATEMENT | BLOCK_STATEMENT | RETURN_STATEMENT | SWITCH_STATEMENT
    IF_STATEMENT          --> if (CONDITION) STATEMENT ELSE_STATEMENT
    ELSE_STATEMENT        --> else STATEMENT  | ε
    WHILE_STATEMENT       --> while (CONDITION) STATEMENT
    DO_WHILE_STATEMENT    --> do STATEMENT while (CONDITION);
    FOR_STATEMENT         --> for (INLINE_STATEMENT; CONDITION; INLINE_STATEMENT) STATEMENT
    BLOCK_STATEMENT       --> { STATEMENTS }
    RETURN_STATEMENT      --> return RETURN_STATEMENT_REST;
    RETURN_STATEMENT_REST --> EXPRESSION | ε
    SWITCH_STATEMENT      --> switch (EXPRESSION) { CASES }
    CASES                 --> CASE CASES | ε
    CASE                  --> CASE_STATEMENT | DEFAULT_STATEMENT
    CASE_STATEMENT        --> case VALUE: STATEMENT break;
    DEFAULT_STATEMENT     --> default: STATEMENT break;

  CONDITION  --> EXPRESSION REL_OPERATOR EXPRESSION | true | false
  EXPRESSION --> VALUE | id | ( EXPRESSION )
  VALUE      --> string | number | true | false | null

  IDS              --> id MORE_IDS
  MORE_IDS         --> .IDS | ε

  DECLARES         --> DECLARE_STATEMENT MORE_DECLARES | ε
  MORE_DECLARES    --> , DECLARES | ε

  EXPRESSIONS      --> EXPRESSION MORE_EXPRESSIONS | ε
  MORE_EXPRESSIONS --> , EXPRESSIONS | ε

  INC_DEC_OPERATOR --> ++ | --
  ASSIGN_OPERATOR  --> = | += | -=
  REL_OPERATOR     --> == | != | > |  >= | < | <=

Diagrama de Sintaxe BNF

Na ciência da computação, a forma Backus-Naur (BNF ou forma normal Backus) é uma notação usada para descrever a sintaxe de linguagens de programação ou outras linguagens formais. Foi desenvolvido por John Backus e Peter Naur. BNF pode ser descrito como uma notação metassintaxe para gramáticas livres de contexto.

- Formulário Backus – Naur @ Wikipédia

PROGRAMA

IMPORT_STATEMENT

referenciado por:

  • PROGRAMA

CLASS_STATEMENT

referenciado por:

  • PROGRAMA

DECLARAÇÃO

referenciado por:

  • BLOCO_STATEMENT
  • CASE_STATEMENT
  • DEFAULT_STATEMENT
  • DO_WHILE_STATEMENT
  • FOR_STATEMENT
  • FUNCTION_STATEMENT
  • IF_STATEMENT
  • WHILE_STATEMENT

SUPER_STATEMENT

referenciado por:

  • CLASS_STATEMENT
  • DECLARAÇÃO

COMMENT_STATEMENT

referenciado por:

  • SUPER_STATEMENT

COMENTÁRIO

referenciado por:

  • COMMENT_STATEMENT

MULTILINE_COMMENT

referenciado por:

  • COMMENT_STATEMENT

FUNCTION_STATEMENT

referenciado por:

  • SUPER_STATEMENT

INLINE_STATEMENT

referenciado por:

  • FOR_STATEMENT
  • SUPER_STATEMENT

DECLARE_STATEMENT

referenciado por:

  • FUNCTION_STATEMENT
  • INLINE_STATEMENT

ASSIGN_STATEMENT

referenciado por:

  • INLINE_STATEMENT

DECSIGN_STATEMENT

referenciado por:

  • INLINE_STATEMENT

INC_DEC_STATEMENT

referenciado por:

  • INLINE_STATEMENT

CALL_STATEMENT

referenciado por:

  • INLINE_STATEMENT

STRUCT_STATEMENT

referenciado por:

  • DECLARAÇÃO

BLOCO_STATEMENT

referenciado por:

  • STRUCT_STATEMENT

IF_STATEMENT

referenciado por:

  • STRUCT_STATEMENT

WHILE_STATEMENT

referenciado por:

  • STRUCT_STATEMENT

DO_WHILE_STATEMENT

referenciado por:

  • STRUCT_STATEMENT

FOR_STATEMENT

referenciado por:

  • STRUCT_STATEMENT

RETURN_STATEMENT

referenciado por:

  • STRUCT_STATEMENT

SWITCH_STATEMENT

referenciado por:

  • STRUCT_STATEMENT

CASE_STATEMENT

referenciado por:

  • SWITCH_STATEMENT

DEFAULT_STATEMENT

referenciado por:

  • SWITCH_STATEMENT

DOENÇA

referenciado por:

  • DO_WHILE_STATEMENT
  • FOR_STATEMENT
  • IF_STATEMENT
  • WHILE_STATEMENT

EXPRESSÃO

referenciado por:

  • ASSIGN_STATEMENT
  • DOENÇA
  • DECSIGN_STATEMENT
  • EXPRESSÃO
  • RETURN_STATEMENT
  • SWITCH_STATEMENT

IDENTIFICADOR

referenciado por:

  • ASSIGN_STATEMENT
  • CALL_STATEMENT
  • CLASS_STATEMENT
  • DECLARE_STATEMENT
  • DECSIGN_STATEMENT
  • EXPRESSÃO
  • FUNCTION_STATEMENT
  • IMPORT_STATEMENT
  • INC_DEC_STATEMENT

VALOR

referenciado por:

  • CASE_STATEMENT
  • EXPRESSÃO

NÚMERO

referenciado por:

  • VALOR

BOOLEAN

referenciado por:

  • DOENÇA
  • VALOR

CORDA

referenciado por:

  • VALOR

INC_DEC_OPERATOR

referenciado por:

  • INC_DEC_STATEMENT

ASSIGN_OPERATOR

referenciado por:

  • ASSIGN_STATEMENT

REL_OPERATOR

referenciado por:

  • DOENÇA

DATA_TYPE

referenciado por:

  • DECLARE_STATEMENT
  • DECSIGN_STATEMENT
  • FUNCTION_STATEMENT
Expandir
Informações adicionais
Aplicativos Relacionados
Recomendado para você
Informações Relacionadas Todos