Chuyển toán tử trung tố sang hậu tố struct token

Thay vì cung cấp link để tải tôi sẽ cung cấp source code đầy đủ chỉ trong 4 tập tin Token.cs, Scanner.cs, Parser.cs và Program.cs.

Phân tích ngữ pháp

Một bước quan trọng mà ta cần làm trước khi xây dựng chương trình là tìm hiểu và phân tích cú pháp của biểu thức toán học. May mắn thay, việc xây dựng ngữ pháp cho các biểu thức không tốn quá nhiều thời gian vì bạn có thể tìm thấy dễ dàng trong các tài liệu về trình biên dịch hoặc ngôn ngữ lập trình. Trích đoạn ngữ pháp dưới đây tôi sử dụng phần mềm GOLD Parser Builder để tạo ra. Phần mềm này nằm trong dự án “Design And Development Of A Grammar Oriented Parsing System” của Devin D. Cook. Nếu có hứng thú với dự án này, bạn có thể tham khảo đầy đủ tài liệu, ví dụ mẫu cũng như các công cụ cần thiết tại địa chỉ sau: //www.devincook.com/goldparser/.

Quay lại vấn đề chính, ta sẽ phân tích đoạn ngữ pháp sau:

Đầu tiên kí hiệu ::= được hiểu nôm na là “được định nghĩa bởi”, có thể coi những dòng có chứa kí hiệu này là luật hoặc luật sinh. Kí hiệu “|” cũng tương tự như OR hoặc “|” trong regular expression. Ví dụ với luật đơn giản sau:

::= NumberLiteral | ‘[‘ ‘]’

Được hiểu là có thể được tạo thành bởi một dãy chữ số HOẶC một biểu thức được bao trong cặp ngoặc đơn.

Như bạn thấy được tạo ra từ các biểu thức với các toán tử so sánh hoặc cộng/trừ [1]. Biểu thức cộng/trừ lại được tạo thành từ những biểu thức nhân/chia [2] và biểu thức này lại được tạo ra từ các và - với các toán tử unary [+/-].

Như vậy các loại biểu thức được tạo nên từ những loại biểu thức khác với độ ưu tiên cao hơn. Độ ưu tiên lớn nhất là biểu thức trong cặp ngoặc đơn, tiếp đến là toán tử unary [+/-]. Vấn đề này rất cơ bản nên không cần bàn nhiều tới, vấn đề chính của ta là làm sao hiện thực đoạn ngữ pháp trên để xây dựng cấu trúc cho một chuỗi biểu thức. Bạn có thể dễ dàng hiểu toàn bộ mã nguồn của chương trình bằng cách so sánh với đoạn ngữ pháp trên.

Lớp Token

Chứa các định nghĩa và cấu trúc về token:

using System; namespace String2ExpressionTree {

enum TokenType  
{  
    EOF = 0,
    Number,
    Add,  
    Subtract,  
    Multiply,  
    Divide,  
    LParen, // [  
    RParen, // ]  
    Equal,  
    GreaterThan,  
    GreaterThanOrEqual,  
    LessThan,  
    LessThanOrEqual,  
}  
struct Token  
{  
    public string Value;  
    public TokenType Type;
    public Token[string value, TokenType type]  
    {  
        Value = value;  
        Type = type;  
    }  
    public override string ToString[]  
    {  
        return Value;  
    }
    

    public static Token EOF  
    {  
        get { return new Token["EOF", TokenType.EOF]; }  
    }  
    public static Token Add  
    {  
        get { return new Token["+", TokenType.Add]; }  
    }  
    public static Token Subtract  
    {  
        get { return new Token["-", TokenType.Subtract]; }  
    }  
    public static Token Multiply  
    {  
        get { return new Token["*", TokenType.Multiply]; }  
    }  
    public static Token Divide  
    {  
        get { return new Token["/", TokenType.Divide]; }  
    }  
    public static Token LParen  
    {  
        get { return new Token["[", TokenType.LParen]; }  
    }  
    public static Token RParen  
    {  
        get { return new Token["]", TokenType.RParen]; }  
    }  
    public static Token Equal  
    {  
        get { return new Token["==", TokenType.Equal]; }  
    }  
    public static Token GreaterThan  
    {  
        get { return new Token[">", TokenType.GreaterThan]; }  
    }  
    public static Token GreaterThanOrEqual  
    {  
        get { return new Token[">=", TokenType.GreaterThanOrEqual]; }  
    }  
    public static Token LessThan  
    {  
        get { return new Token["