Viết trình thông dịch stack-based đơn giản bằng C#

Trong bài viết trước tôi có giới thiệu sơ lược về ngôn ngữ lập trình Cat. Đây là một ngôn ngữ lập trình stack-based và chỉ hỗ trợ thông dịch. Việc hiện thực ngôn ngữ này không quá phức tạp tuy nhiên cũng đòi hỏi không ít thời gian. Vì thế, tôi sẽ sử dụng một phương pháp đơn giản để hiện thực một trình thông dịch tương tự mà ai cũng có thể hiểu một cách nhanh chóng. Tôi tạm đặt tên ngôn ngữ này là Mouse phiên bản 1.0 beta 1.

Trước tiên xin nói rõ đây không phải là lựa chọn thích hợp nếu như bạn muốn phát triển một ngôn ngữ lập trình mạnh mẽ và hoàn chỉnh. Phương pháp mà tôi sử dụng ở đây không tổng quát và khó phát triển. Tuy nhiên trong một mức độ nào đó, nó có thể đáp ứng được những yêu cầu tối thiểu của một ngôn ngữ lập trình và ngoài ra, tôi sẽ giới thiệu cách để bổ sung những lệnh (instruction) mà người dùng có thể tự định nghĩa dựa trên những lệnh chuẩn của Mouse (xem link ở cuối bài). Cú pháp của Mouse tương tự như Cat nên bạn có thể tham khảo bài viết giới thiệu về Cat để hiểu rõ hơn.

Các đặc điểm chính

–       Các kiểu dữ liệu mà Mouse hỗ trợ gồm có: integer, bool, string.

–       Trong Mouse không có khái niệm function hay method mà chỉ có lệnh (instruction), bạn cũng có thể hiểu đây là các toán tử vì cả hai khái niệm này được xử lý như nhau trong Mouse.

–       Các lệnh trong Mouse không phân biệt hoa thường.

–       Cặp ngoặc vuông [ ] trong Mouse được dùng để định nghĩa một khối lệnh.

–       Không hỗ trợ các cặp lệnh lồng nhau.

Các lệnh/toán tử mà Mouse hiện có bao gồm:

–       +,-,*,/

–       True, False: push giá trị True/False vào stack

–       Pop: Lấy phần tử ra khỏi stack

–       Dup: sao chép thêm một phần tử ở đỉnh stack

–       Swap: hoán vị hai phần tử ở đỉnh stack

–       Inc: tăng giá trị của phần tử ở đỉnh stack lên 1

–       Eq: push True vào stack nếu hai phần tử ở đỉnh stack bằng nhau, ngược lại là False

–       Lt: push True vào stack nếu phần tử ở đỉnh stack lớn hơn phần tử kế tiếp nó, ngược lại là False

–       Gt: push True vào stack nếu phần tử ở đỉnh stack nhỏ hơn phần tử kế tiếp nó, ngược lại là False

–       Writeln: Xuất một dòng văn bản ra màn hình

–       If: Điều kiện

–       While: Lặp

Hiện thực chương trình

Dự án chi bao gồm hai lớp sau:

Y2MouseInteroreter_ClassDiagram

Y2MouseInteroreter_ClassDiagram

Mã lệnh cho phương thức Main():

public static void Main(string[] args)
{
	Console.WriteLine("Welcome to Mouse programming language");
	Console.WriteLine("version 1.0 beta 1");
	Console.WriteLine("by Yin Yang");
	Console.WriteLine("https://yinyangit.wordpress.com");

	Y2MouseInterpreter mInter=new Y2MouseInterpreter();

	while(true)
	{
		Console.Write(">>");
		string cmd=Console.ReadLine().Trim();
		if(cmd=="#x" || cmd=="#exit")
			break;
		else
			mInter.Execute(cmd);

		if(cmd!="")
			mInter.PrintStack();
	}
 }

Phương thức Execute() của lớp Y2MouseInterpreter:

public void Execute(string input)
{
	if(String.IsNullOrEmpty(input))
		return;
	if(Regex.Match(input,@"^\[.+\]$").Success)
		input=input.Trim('[',']');
	MatchCollection matchs = Regex.Matches(input,"\"[^\\[\\]]+\"|" + @"\[[^\[\]]+\]|\S+", RegexOptions.Multiline | RegexOptions.IgnoreCase);

	foreach(Match m in matchs)
	{
		string s=m.Value;

		int i;
		if(int.TryParse(s,out i))
			_stack.Push(i);
		else if(Regex.Match(s,@"^\[.+\]$").Success)
			_stack.Push(s);
		else if(Regex.Match(s,"^\".+\"$").Success)
			_stack.Push(s.Trim('"'));
		else
		{
			try{
				ExecuteInstruction(s);
			}catch(Exception ex)
			{
				Console.ForegroundColor=ConsoleColor.DarkCyan;
				Console.WriteLine("Error: "+ex.Message);
				Console.ResetColor();
			}

		}

	}
 }

Chuỗi regular expression “\[[^\[\]]+\]|\S+” để so khớp và tách dòng lệnh nhập từ người dùng thành các lệnh riêng biệt. Ví dụ nếu bạn nhập:

1 [dup writeln inc] [dup 10 lteq] while

Thì kết quả sau khi so khớp sẽ là một tập hợp các phần tử sau:

1

[dup writeln inc]

[dup 10 lteq]

while

Cập nhật 16/3/2011: thêm phần regular expression “\”[^\\[\\]]+\”” để so khớp với các chuỗi trong ngoặc kép.

Khi đã có tập hợp các lệnh này, ta sẽ lặp qua và tùy vào loại dữ liệu hay lệnh/toán tử mà phương thức trên sẽ chuyển đổi kiểu và đưa vào stack hay thực thi lệnh bằng phương thức ExecuteInstruction() sau:

private void ExecuteInstruction(string instruction)
{
	switch (instruction.ToUpper())
	{
		case "+":
			_stack.Push((int)_stack.Pop()+(int)_stack.Pop());
			break;
		case "-":
			{
			int o1=(int)_stack.Pop();
			int o2=(int)_stack.Pop();
			_stack.Push(o2-o1);
			break;
			}
		case "*":
			_stack.Push((int)_stack.Pop()*(int)_stack.Pop());
			break;
		case "/":
			{
			int o1=(int)_stack.Pop();
			int o2=(int)_stack.Pop();
			_stack.Push(o2/o1);
			break;
			}
		case "TRUE":
			_stack.Push(true);
			break;
		case "FALSE":
			_stack.Push(false);
			break;
		case "POP":
			_stack.Pop();
			break;
		case "DUP":
			_stack.Push(_stack.Peek());
			break;
		case "SWAP":
			{
				IComparable o1=_stack.Pop();
				IComparable o2=_stack.Pop();
				_stack.Push(o1);
				_stack.Push(o2);
				break;
			}
		case "INC":
			{
				int o1=(int)_stack.Pop();
				_stack.Push(o1+1);
				break;
			}
		case "EQ":
			{
				object o1=_stack.Pop();
				object o2=_stack.Pop();
				_stack.Push(o1.Equals(o2));
				break;
			}
		case "LT":
			{
				IComparable o1=_stack.Pop();
				IComparable o2=_stack.Pop();
				_stack.Push(o2.CompareTo(o1)<0); 				break; 			} 		case "GT": 			{ 				IComparable o1=_stack.Pop(); 				IComparable o2=_stack.Pop(); 				_stack.Push(o2.CompareTo(o1)>0);
				break;
			}
		case "WRITELN":
			Console.WriteLine(_stack.Pop());
			break;
		case "IF":
			{
				IComparable o1=_stack.Pop();
				IComparable o2=_stack.Pop();
				IComparable o3=_stack.Pop();

				if((bool)o3)
					Execute(o2.ToString());
				else
					Execute(o1.ToString());
				break;
			}
		case "WHILE":
			{
				IComparable o1=_stack.Pop();
				IComparable o2=_stack.Pop();

				Execute(o2.ToString());
				Execute(o1.ToString());

				IComparable o3=_stack.Pop();
				if((bool)o3)
					Execute(o2.ToString() + o1 + " while");
				break;
			}
		default:
			throw new Exception("Could not find instruction '"+instruction+"'");
	}
	if(_stack.Count==0)
		return;

	string s =_stack.Peek() as string;
	if(s!=null)
	{
		if(Regex.Match(s,@"^\[.+\]$").Success)
			Execute(s);
	}

 }

Mã nguồn trên khá đơn giản nên tôi không giải thích, dựa vào cơ chế stack-based bạn có thể hiểu và dễ dàng viết thêm những lệnh khác.

Sau khi thực thi lệnh xong, phương thức này cần kiểm tra và thực thi tiếp tục nếu như đỉnh stack có một khối lệnh.

Ví dụ

In 10 số từ 1 đến 10 bằng lệnh while, tôi sử dụng chuỗi lệnh tương tự như trong Cat, tuy nhiên vì chưa có lệnh lteq nên có chút khác biệt:

1 [dup writeln inc] [dup 11 lt] while

Mouse Interpreter Example

Mouse Interpreter Example

Mã nguồn hoàn chỉnh bạn có thể xem tại: Simple Stack-based Interpreter

https://yinyangit.wordpress.com

2 thoughts on “Viết trình thông dịch stack-based đơn giản bằng C#

  1. Anh cho em hỏi làm thế nào để xử lý chuỗi theo 1 cách có hệ thống, mà không cần yêu cầu cấu trúc cho người dùng nhập vào (chỉ cần có các thông tin và dấu hiệu nhận biết).
    Thêm nữa mong anh chỉ dùm e cách xử lý về cắt lấy một số phần tử, viết hoa, viết thường, kí tự nào là string còn cái nào là int.
    Em làm thử bằng cách em nghĩ ra là bằng cách đi vào từng giá trị trong chuỗi nhưng mà khi chuyển về kiểu so sánh thì lại bị báo lỗi do sai kiểu. Mong anh chỉ dùm em

    Trả lời
  2. Ngôn ngữ này mình viết chơi chủ yếu để cho cách hoạt động của stack để tính toán thôi. Nếu bạn học môn trình biên dịch rồi thì sẽ biết phương pháp giải quyết các vấn đề này. Trong blog này, bạn có thể tìm project Y2L Sharp để tham khảo.

    Trả lời

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s