aParser

เอพาร์เซอร์

โปรเจ็กต์นี้เป็นคอมไพเลอร์ที่ใช้โปรแกรมต้นฉบับที่เขียนด้วย C# (อินพุต) จากนั้นแปลเป็นโปรแกรมเป้าหมายที่เขียนด้วย Visual Basic (เอาต์พุต) กระบวนการนี้ทำได้โดยผ่านสามโมดูล ( Tokenizer , Parser และ Translator ) ตามลำดับ แต่ละโมดูลจะมีการอธิบายแยกกันในรายงานนี้

โทเค็นไนเซอร์

Tokenizer คืออะไร?

Tokenizer / Lexical Analyzer เป็นโปรแกรมที่รับลำดับอักขระ (อินพุต) และเอาต์พุตลำดับของโทเค็น (เอาต์พุต)

คำจำกัดความโทเค็น

โทเค็นไนเซอร์มีรายการคำจำกัดความสำหรับแต่ละโทเค็นที่เป็นไปได้ที่อาจสร้างขึ้นโดยการจัดกลุ่มลำดับของอักขระ แต่ละคำจำกัดความของโทเค็นประกอบด้วย:

• ประเภท : ใช้เพื่อแยกความแตกต่างระหว่างโทเค็น
• Regular Expression (RegEx) : ใช้เพื่อจับ (จับคู่) ค่า

ตารางต่อไปนี้แสดงถึงคำจำกัดความทั้งหมดที่ใช้ในโปรเจ็กต์ พร้อมตัวอย่างของค่าที่ตรงกันสำหรับแต่ละรายการ

คำหลัก

พิมพ์	การแสดงออกปกติ	ค่าที่ตรงกัน
โดยใช้	โดยใช้	using
ระดับ	ระดับ	class
ถ้า	ถ้า	if
อื่น	อื่น	else
สำหรับ	สำหรับ	for
ทำ	ทำ	do
ในขณะที่	ในขณะที่	while
สวิตช์	สวิตช์	switch
กรณี	กรณี	case
หยุดพัก	หยุดพัก	break
ค่าเริ่มต้น	ค่าเริ่มต้น	default
กลับ	กลับ	return
โมฆะ	โมฆะ	null
จริง	จริง	true
เท็จ	เท็จ	false
เท็จ	(เป็นโมฆะ | var) | (bool | char | short | int | long | float | double | decimal | string | String) ([] | ?)?	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 -

ผู้ประกอบการ

พิมพ์	การแสดงออกปกติ	ค่าที่ตรงกัน
และ	- -	&& &
หรือ	- - -	|| |
ไม่	-	!
เท่ากัน	-	=
พลัสอีควล	-	+=
ลบเท่ากับ	-	-=
สองเท่าเท่ากัน	-	==
ไม่เท่ากัน	-	!=
น้อยกว่า	-	<
ยิ่งใหญ่กว่า	-	>
น้อยกว่าหรือเท่ากับ	-	<=
มากกว่าหรือเท่ากับ	-	>=

สัญลักษณ์

พิมพ์	การแสดงออกปกติ	ค่าที่ตรงกัน
OpenRoundBracket	-	(
ปิดวงเล็บกลม	-	)
OpenCurlyBracket	-	{
ปิด CurlyBracket	-	}
OpenSquareBracket	-	[
CloseSquareBracket	-	]
บวก	-	+
ลบ	-	-
ดับเบิ้ลพลัส	-	++
DoubleMinuses	-	--
เปอร์เซ็นต์	-	%
เครื่องหมายดอกจัน	-	*
แบ็กสแลช	-
ฟอร์เวิร์ดสแลช	-	/
DoubleForwardSlashes	-	//
ฟอร์เวิร์ดสแลชเครื่องหมายดอกจัน	-	/*
เครื่องหมายดอกจันไปข้างหน้าสแลช	-	*/
จุด	-	.
จุลภาค	-	,
ลำไส้ใหญ่	-	:
อัฒภาค	-	;

การนำไปปฏิบัติ

ประเภทโทเค็นทั้งหมดนี้จะถูกจัดกลุ่มเป็น enum ในไฟล์ 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
ตอนนี้ tokenizer จะไม่สับสนระหว่าง + และ += อีกต่อไป และจะใช้อันที่มีลำดับความสำคัญสูงกว่า +=

2. โทเค็นภายในโทเค็น

เมื่อ tokenizer เผชิญกับลำดับอักขระเช่น "String + String = String" มันจะสร้างโทเค็น สามประเภท ได้แก่:

• สตริง : "String + String = String"
• บวก : +
• เท่ากับ : =

แต่เราต้องการแค่โทเค็นประเภท String เท่านั้น !!

สารละลาย:

แต่ละโทเค็นจะได้รับการกำหนดคุณสมบัติ ดัชนีเริ่มต้น และ ดัชนีสิ้นสุด ดังนั้นโทเค็นก่อนหน้าจะมี:

พิมพ์	ค่า	เริ่มดัชนี	ดัชนีสิ้นสุด
สตริง	"String + String = String"	0	25
บวก	+	8	9
เท่ากัน	=	17	18

และเราเพิกเฉยต่อโทเค็นที่เริ่มต้นภายในช่วงของโทเค็นอื่น

ตอนนี้ tokenizer จะสร้างโทเค็นเพียงอันเดียวซึ่งมีประเภท String และไม่สนใจอันที่อยู่ภายใน

พาร์เซอร์

พาร์เซอร์คืออะไร?

Parser / Syntax Analyzer เป็นโปรแกรมที่ใช้ลำดับของโทเค็น - สร้างขึ้นจาก Tokenizer - และจัดกลุ่มโทเค็นเหล่านั้นเพื่อสร้างโครงสร้างที่ระบุโดยการผลิต context free grammar (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

ในวิทยาการคอมพิวเตอร์ รูปแบบ Backus–Naur (BNF หรือรูปแบบปกติของ Backus) เป็นสัญกรณ์ที่ใช้อธิบายไวยากรณ์ของภาษาโปรแกรมหรือภาษาทางการอื่นๆ ได้รับการพัฒนาโดย John Backus และ Peter Naur BNF สามารถอธิบายได้ว่าเป็นสัญลักษณ์ metasyntax สำหรับไวยากรณ์ที่ไม่มีบริบท

-- รูปแบบ Backus–Naur @ Wikipedia

โปรแกรม

นำเข้า_คำชี้แจง

อ้างอิงโดย:

• โปรแกรม

CLASS_STATEMENT

อ้างอิงโดย:

• โปรแกรม

คำแถลง

อ้างอิงโดย:

• BLOCK_STATEMENT
• CASE_STATEMENT
• DEFAULT_STATEMENT
• DO_WHILE_STATEMENT
• FOR_คำชี้แจง
• FUNCTION_STATEMENT
• ถ้า_STATEMENT
• WHILE_STATEMENT

SUPER_STATEMENT

อ้างอิงโดย:

• CLASS_STATEMENT
• คำแถลง

COMMENT_STATEMENT

อ้างอิงโดย:

• SUPER_STATEMENT

ความคิดเห็น

อ้างอิงโดย:

• COMMENT_STATEMENT

MULTILINE_COMMENT

อ้างอิงโดย:

• COMMENT_STATEMENT

FUNCTION_STATEMENT

อ้างอิงโดย:

• SUPER_STATEMENT

INLINE_STATEMENT

อ้างอิงโดย:

• FOR_คำชี้แจง
• SUPER_STATEMENT

DECLARE_STATEMENT

อ้างอิงโดย:

• FUNCTION_STATEMENT
• INLINE_STATEMENT

ASSIGN_STATEMENT

อ้างอิงโดย:

• INLINE_STATEMENT

DECSIGN_STATEMENT

อ้างอิงโดย:

• INLINE_STATEMENT

INC_DEC_STATEMENT

อ้างอิงโดย:

• INLINE_STATEMENT

CALL_STATEMENT

อ้างอิงโดย:

• INLINE_STATEMENT

โครงสร้าง_STATEMENT

อ้างอิงโดย:

• คำแถลง

BLOCK_STATEMENT

อ้างอิงโดย:

• โครงสร้าง_STATEMENT

ถ้า_STATEMENT

อ้างอิงโดย:

• โครงสร้าง_STATEMENT

WHILE_STATEMENT

อ้างอิงโดย:

• โครงสร้าง_STATEMENT

DO_WHILE_STATEMENT

อ้างอิงโดย:

• โครงสร้าง_STATEMENT

FOR_คำชี้แจง

อ้างอิงโดย:

• โครงสร้าง_STATEMENT

RETURN_STATEMENT

อ้างอิงโดย:

• โครงสร้าง_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
• การแสดงออก

ตัวเลข

อ้างอิงโดย:

• ค่า

บูลีน

อ้างอิงโดย:

• เงื่อนไข
• ค่า

STRING

อ้างอิงโดย:

• ค่า

INC_DEC_OPERATOR

อ้างอิงโดย:

• INC_DEC_STATEMENT

ASSIGN_OPERATOR

อ้างอิงโดย:

• ASSIGN_STATEMENT

REL_โอเปอเรเตอร์

อ้างอิงโดย:

• เงื่อนไข

DATA_TYPE

อ้างอิงโดย:

• DECLARE_STATEMENT
• DECSIGN_STATEMENT
• FUNCTION_STATEMENT