Главная страница>Связанные с программированием>Визуальный Бейсик
Скачать

aParser

Проект представляет собой компилятор, который принимает исходную программу, написанную на C# (вход), а затем преобразует ее в целевую программу, написанную на Visual Basic (выход) . Этот процесс выполняется путем прохождения трех модулей ( Tokenizer , Parser и Translator ) соответственно. В этом отчете каждый модуль будет описан отдельно.

токенизатор

Что такое токенайзер?

Токенизатор/Лексический анализатор — это программа, которая принимает последовательность символов (ввод) и выводит последовательность токенов (выход).

Определения токенов

Токенизатор имеет список определений для каждого возможного токена, который он может создать путем группировки последовательности символов. Каждое определение токена состоит из:

  • Тип : используется для различения токенов.
  • Регулярное выражение (RegEx) : используется для захвата (сопоставления) значений.

В следующих таблицах представлены все определения, использованные в проекте, с примером сопоставления значений для каждого из них.

Ключевые слова

Тип Регулярное выражение Соответствующие значения
С использованием с использованием using
Сорт сорт class
Если если if
Еще еще else
Для для for
Делать делать do
Пока пока while
Выключатель выключатель switch
Случай случай case
Перерыв перерыв break
По умолчанию по умолчанию default
Возвращаться возвращаться return
Нулевой нулевой null
Истинный истинный true
ЛОЖЬ ЛОЖЬ false
ЛОЖЬ (недействительно | вар) | (bool | char | short | int | long | float | double | decimal | string | String) ([] | ?)? void
bool
char?
int[]

Ценности

Тип Регулярное выражение Соответствующие значения
Число d*.d+ | д+ 77
.25
3.14
Нить "[^"]*" "This is string"
Идентификатор [a-zA-Z_]w* fact
_private
iD_1
Комментарий (?<=//) .*? (?=(r | n | //)) // inline comment
Многострочный комментарий (?<=/*) (?:(?!*/)(?:.|[rn]))* (?=*/) /*
multi line
comment
*/

Операторы

Тип Регулярное выражение Соответствующие значения
И && | & &&
&
Или || | | ||
|
Нет ! !
Равный = =
ПлюсРавно += +=
МинусРавно -= -=
Двойное равенство == ==
Неравен != !=
Меньше, чем < <
Больше, чем > >
МеньшеТханОРавно <= <=
БольшеЧОлиРавно >= >=

Символы

Тип Регулярное выражение Соответствующие значения
OpenRoundBracket ( (
ЗакрытьКраундКробка ) )
OpenCurlyBracket { {
ЗакрытьВьющиесяКрешка } }
OpenSquareBracket [ [
ЗакрытьКвадратСкоба ] ]
Плюс + +
Минус - -
ДаблПлюсы ++ ++
ДвойнойМинус -- --
Процент % %
Звездочка * *
обратная косая черта \
Косая черта вперед / /
Двойные косые черты вперед // //
ВпередСлешЗвездочка /* /*
AsteriskForwardSlash */ */
Точка . .
Запятая , ,
Колон : :
Точка с запятой ; ;

Выполнение

Все эти типы токенов сгруппированы как перечисления в файле 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            // ;
}

их определения создаются и сохраняются в List<TokenDefinition> в файле 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 , @";" ) ,
} ;
.. .

Исправленные проблемы

1. Когда токены перекрываются

Когда токенизатор сталкивается с некоторой последовательностью символов, например ++ , он запутывается: это один токен типа DoublePluses ? Или два последовательных токена типа Plus ? Эта проблема также относится к другим перекрывающимся токенам, таким как: { + , += } & { - , -- } & { - , -= } & { / , // }

Решение:

Каждому токену будет присвоено свойство Priority со значением по умолчанию 0 (наивысший приоритет) , и когда два токена перекрываются, например + и += мы уменьшаем приоритет токена с более короткой длиной + до 1 .
Теперь токенизатор больше не будет путаться между + и += и будет брать тот, у которого более высокий приоритет += .

2. Токен внутри токена

Когда токенизатор сталкивается с некоторой последовательностью символов, например "String + String = String" он создает три типа токенов:

  • Строка : "String + String = String"
  • Плюс : +
  • Равно : =

но нам нужен только токен типа String !!

Решение:

Каждому токену будут назначены свойства «Начальный индекс» и «Конечный индекс» , так что предыдущие токены будут иметь:

Тип Ценить Начальный индекс Конечный индекс
Нить "String + String = String" 0 25
Плюс + 8 9
Равный = 17 18

и мы игнорируем любые старты токена в диапазоне другого.

Теперь токенизатор будет создавать только один токен типа String и игнорировать внутренние.

Парсер

Что такое парсер?

Parser / Syntax Analyzer — это программа, которая принимает последовательность токенов, сгенерированную с помощью Tokenizer, и группирует их для формирования структур, заданных используемой продукцией контекстно-свободной грамматики (CFG).

Роли парсера

  • Распознавание контекстно-свободного синтаксиса
  • Выдавайте содержательные сообщения об ошибках
  • Построить промежуточное представление (IR)

Контекстно-свободная грамматика (CFG)

Краткое содержание:

  • CAPITAL_CASE : Нетерминал
  • small_case : Терминал
  • | : Альтернативы (или)
  • ε : Пусто 
  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     --> == | != | > |  >= | < | <=

Синтаксическая диаграмма БНФ

В информатике форма Бэкуса-Наура (BNF или нормальная форма Бэкуса) представляет собой обозначение, используемое для описания синтаксиса языков программирования или других формальных языков. Его разработали Джон Бэкус и Питер Наур. BNF можно описать как метасинтаксическую нотацию для контекстно-свободных грамматик.

-- Форма Бэкуса-Наура @ Wikipedia

ПРОГРАММА

ИМПОРТ_ЗАЯВЛЕНИЕ

на который ссылается:

  • ПРОГРАММА

CLASS_STATEMENT

на который ссылается:

  • ПРОГРАММА

ЗАЯВЛЕНИЕ

на который ссылается:

  • БЛОК_STATEMENT
  • CASE_STATEMENT
  • DEFAULT_STATEMENT
  • DO_WHILE_STATEMENT
  • FOR_STATEMENT
  • FUNCTION_STATEMENT
  • ЕСЛИ_СТЕЙМЕНТ
  • WHILE_STATEMENT

СУПЕР_ЗАЯВЛЕНИЕ

на который ссылается:

  • CLASS_STATEMENT
  • ЗАЯВЛЕНИЕ

КОММЕНТАРИЙ_ЗАЯВЛЕНИЕ

на который ссылается:

  • СУПЕР_ЗАЯВЛЕНИЕ

КОММЕНТАРИЙ

на который ссылается:

  • КОММЕНТАРИЙ_ЗАЯВЛЕНИЕ

MULTILINE_COMMENT

на который ссылается:

  • КОММЕНТАРИЙ_ЗАЯВЛЕНИЕ

FUNCTION_STATEMENT

на который ссылается:

  • СУПЕР_ЗАЯВЛЕНИЕ

INLINE_STATEMENT

на который ссылается:

  • FOR_STATEMENT
  • СУПЕР_ЗАЯВЛЕНИЕ

DECLARE_STATEMENT

на который ссылается:

  • FUNCTION_STATEMENT
  • INLINE_STATEMENT

ASSIGN_STATEMENT

на который ссылается:

  • INLINE_STATEMENT

DECSIGN_STATEMENT

на который ссылается:

  • INLINE_STATEMENT

INC_DEC_STATEMENT

на который ссылается:

  • INLINE_STATEMENT

CALL_STATEMENT

на который ссылается:

  • INLINE_STATEMENT

STRUCT_STATEMENT

на который ссылается:

  • ЗАЯВЛЕНИЕ

БЛОК_STATEMENT

на который ссылается:

  • STRUCT_STATEMENT

ЕСЛИ_СТЕЙМЕНТ

на который ссылается:

  • STRUCT_STATEMENT

WHILE_STATEMENT

на который ссылается:

  • STRUCT_STATEMENT

DO_WHILE_STATEMENT

на который ссылается:

  • STRUCT_STATEMENT

FOR_STATEMENT

на который ссылается:

  • STRUCT_STATEMENT

RETURN_STATEMENT

на который ссылается:

  • STRUCT_STATEMENT

SWITCH_STATEMENT

на который ссылается:

  • STRUCT_STATEMENT

CASE_STATEMENT

на который ссылается:

  • SWITCH_STATEMENT

DEFAULT_STATEMENT

на который ссылается:

  • SWITCH_STATEMENT

СОСТОЯНИЕ

на который ссылается:

  • DO_WHILE_STATEMENT
  • FOR_STATEMENT
  • ЕСЛИ_СТЕЙМЕНТ
  • WHILE_STATEMENT

ВЫРАЖЕНИЕ

на который ссылается:

  • ASSIGN_STATEMENT
  • СОСТОЯНИЕ
  • DECSIGN_STATEMENT
  • ВЫРАЖЕНИЕ
  • RETURN_STATEMENT
  • SWITCH_STATEMENT

ИДЕНТИФИКАТОР

на который ссылается:

  • ASSIGN_STATEMENT
  • CALL_STATEMENT
  • CLASS_STATEMENT
  • DECLARE_STATEMENT
  • DECSIGN_STATEMENT
  • ВЫРАЖЕНИЕ
  • FUNCTION_STATEMENT
  • ИМПОРТ_ЗАЯВЛЕНИЕ
  • INC_DEC_STATEMENT

ЦЕНИТЬ

на который ссылается:

  • CASE_STATEMENT
  • ВЫРАЖЕНИЕ

ЧИСЛО

на который ссылается:

  • ЦЕНИТЬ

БУЛЕВОЕ значение

на который ссылается:

  • СОСТОЯНИЕ
  • ЦЕНИТЬ

НИТЬ

на который ссылается:

  • ЦЕНИТЬ

INC_DEC_OPERATOR

на который ссылается:

  • INC_DEC_STATEMENT

ASSIGN_OPERATOR

на который ссылается:

  • ASSIGN_STATEMENT

REL_OPERATOR

на который ссылается:

  • СОСТОЯНИЕ

ДАННЫЕ_ТИП

на который ссылается:

  • DECLARE_STATEMENT
  • DECSIGN_STATEMENT
  • FUNCTION_STATEMENT
Расширять
Дополнительная информация
Связанные приложения
Рекомендуем вам
Связанные новости Все