aParser

解析器

該專案是一個編譯器，它接受用C# 編寫的原始程式（輸入），然後將其轉換為用Visual Basic 編寫的目標程式（輸出） 。此過程分別透過三個模組（ Tokenizer 、 Parser和Translator ）來完成。本報告將分別對各個模組進行說明。

分詞器

什麼是分詞器？

分詞器/詞法分析器是一個接受字元序列（輸入）並輸出標記序列（輸出）的程式。

代幣定義

分詞器具有每個可能的標記的定義列表，它可以透過對字元序列進行分組來產生。每個令牌定義包括：

• Type : 用於區分token
• 正規表示式（RegEx） ：用於捕獲（匹配）值

下表代表了專案中使用的所有定義，以及每個定義的符合值範例。

關鍵字

類型	正規表示式	匹配值
使用	使用	using
班級	班級	class
如果	如果	if
別的	別的	else
為了	為了	for
做	做	do
儘管	儘管	while
轉變	轉變	switch
案件	案件	case
休息	休息	break
預設	預設	default
返回	返回	return
無效的	無效的	null
真的	真的	true
錯誤的	錯誤的	false
錯誤的	(void | var) | （布林 | 字元 | 短 | int | 長 | 浮點 | 雙 | 小數 | 字串 | 字串）([] | ?)？	void bool char? int[]

價值觀

類型	正規表示式	匹配值
數位	d*.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 */

營運商

類型	正規表示式	匹配值
和	&& | &	&& &
或者	|| | |	|| |
不是	！	!
平等的	=	=
加等於	+=	+=
減等於	-=	-=
雙等於	==	==
不等於	!=	!=
少於	<	<
大於	>	>
小於或等於	<=	<=
大於或等於	>=	>=

符號

類型	正規表示式	匹配值
開放式圓括號	(	(
關閉圓括號	)	)
開大括號	{	{
關閉大括號	}	}
開方括號	[	[
關閉方括號	]	]
加	+	+
減	-	-
雙加	++	++
雙減	--	--
百分比	%	%
星號	*	*
反斜線	\
正斜槓	/	/
雙正斜槓	//	//
正斜線星號	/*	/*
星號正斜杠	*/	*/
點	.	.
逗號	,	,
冒號	:	:
分號	;	;

執行

所有這些令牌類型都在 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            // ;
}

它們的定義被建立並儲存在 Tokenizer.cs 檔案中的List<TokenDefinition>中。

 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類型的連續標記？此問題也適用於其他重疊標記，例如： { + , += } & { - , -- } & { - , -= } & { / , // }

解決方案：

每個令牌都會被指派一個預設值0 （最高優先權）的Priority屬性，當兩個令牌像+和+=一樣重疊時，我們將長度較短的+的優先權降低為1 。
現在，分詞器不會再混淆+和+= ，並且會採用優先順序更高的+= 。

2. 代幣內的代幣

當分詞器面對某些字元序列（例如"String + String = String"時，它將產生三種類型的標記：

• 字串： "String + String = String"
• 加： +
• 等於： =

但我們只需要String類型的令牌！

解決方案：

每個令牌將分配一個開始索引和結束索引屬性，以便先前的令牌將具有：

類型	價值	開始索引	結束索引
細繩	"String + String = String"	0	25
加	+	8	9
平等的	=	17 號	18

並且我們忽略在另一個令牌範圍內開始的任何令牌。

現在，標記產生器將只產生一個String類型的標記，並忽略內部的標記。

解析器

什麼是解析器？

解析器/語法分析器是一個程序，它採用從 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 或巴科斯範式）是一種用來描述程式語言或其他形式語言語法的符號。它是由約翰·巴克斯和彼得·諾爾開發的。 BNF 可以被描述為上下文無關語法的元語法表示法。

——巴科斯-諾爾形式@維基百科

程式

導入語句

引用者：

• 程式

CLASS_語句

引用者：

• 程式

陳述

引用者：

• 區塊語句
• 案例聲明
• 預設語句
• DO_WHILE_語句
• FOR_語句
• 函數語句
• IF_語句
• WHILE_語句

超級語句

引用者：

• CLASS_語句
• 陳述

評論_聲明

引用者：

• 超級語句

評論

引用者：

• 評論_聲明

多行評論

引用者：

• 評論_聲明

函數語句

引用者：

• 超級語句

內嵌語句

引用者：

• FOR_語句
• 超級語句

DECLARE_語句

引用者：

• 函數語句
• 內嵌語句

分配語句

引用者：

• 內嵌語句

DECSIGN_語句

引用者：

• 內嵌語句

INC_DEC_語句

引用者：

• 內嵌語句

呼叫語句

引用者：

• 內嵌語句

結構語句

引用者：

• 陳述

區塊語句

引用者：

• 結構語句

IF_語句

引用者：

• 結構語句

WHILE_語句

引用者：

• 結構語句

DO_WHILE_語句

引用者：

• 結構語句

FOR_語句

引用者：

• 結構語句

回傳語句

引用者：

• 結構語句

SWITCH_語句

引用者：

• 結構語句

案例聲明

引用者：

• SWITCH_語句

預設語句

引用者：

• SWITCH_語句

狀態

引用者：

• DO_WHILE_語句
• FOR_語句
• IF_語句
• WHILE_語句

表達

引用者：

• 分配語句
• 狀態
• DECSIGN_語句
• 表達
• 回傳語句
• SWITCH_語句

識別碼

引用者：

• 分配語句
• 呼叫語句
• CLASS_語句
• DECLARE_語句
• DECSIGN_語句
• 表達
• 函數語句
• 導入語句
• INC_DEC_語句

價值

引用者：

• 案例聲明
• 表達

數位

引用者：

• 價值

布林值

引用者：

• 狀態
• 價值

細繩

引用者：

• 價值

INC_DEC_OPERATOR

引用者：

• INC_DEC_語句

ASSIGN_OPERATOR

引用者：

• 分配語句

REL_運算符

引用者：

• 狀態

資料類型

引用者：

• DECLARE_語句
• DECSIGN_語句
• 函數語句