Xây dựng trình phân tích cú pháp (Phần I)

Question

Tôi đang tạo ngôn ngữ lập trình dựa trên javascript của riêng mình (vâng, nó thật điên rồ, nhưng chỉ để tìm hiểu ... có thể?). Vâng, tôi đang đọc về phân tích cú pháp và đèo đầu tiên là để chuyển đổi các mã nguồn để thẻ, như:

if(x > 5) 
    return true; 

Tokenizer tới:

T_IF   "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_NUMBER  "5" 
T_RPAREN  ")" 
T_IDENTIFIER "return" 
T_TRUE  "true" 
T_TERMINATOR ";" 

Tôi không biết nếu logic của tôi là đúng cho điều đó trong một thời gian. Về phân tích cú pháp của tôi nó thậm chí còn tốt hơn (hay không?) Và dịch nó (yeah, mảng đa chiều):

T_IF    "if" 
    T_EXPRESSION  ... 
    T_IDENTIFIER  "x" 
    T_GT    ">" 
    T_NUMBER   "5" 
    T_CLOSURE  ... 
    T_IDENTIFIER  "return" 
    T_TRUE   "true" 

Tôi có một số nghi ngờ:

1. là cách của tôi tốt hơn hoặc tồi tệ hơn mà cách ban đầu? Lưu ý rằng mã của tôi sẽ được đọc và biên dịch (được dịch sang ngôn ngữ khác, như PHP), thay vì được giải thích mọi lúc.
2. Sau I tokenizer, những gì tôi cần làm chính xác? Tôi thực sự bị mất trên đèo này!
3. Có một số hướng dẫn hay để tìm hiểu cách tôi có thể làm điều đó?

Vâng, đúng vậy. Tạm biệt!

Answer 1

Nói chung, bạn muốn tách các chức năng của tokeniser (còn được gọi là lexer) từ các giai đoạn khác của trình biên dịch hoặc thông dịch viên của bạn. Lý do cho điều này là mô đun cơ bản: mỗi lượt vượt qua tiêu thụ một loại điều (ví dụ: ký tự) và tạo một loại khác (ví dụ: mã thông báo).

Vì vậy, bạn đã chuyển đổi ký tự thành mã thông báo. Giờ đây, bạn muốn chuyển đổi danh sách mã thông báo dạng phẳng thành các biểu thức lồng nhau có ý nghĩa và đây là thông thường được gọi là phân tích . Đối với ngôn ngữ giống như JavaScript, bạn nên xem xét recursive descent parsing. Để phân tích các biểu thức với các toán tử infix với các mức ưu tiên khác nhau, Pratt parsing rất hữu ích và bạn có thể quay trở lại phân tích cú pháp gốc đệ quy thông thường cho các trường hợp đặc biệt.

Chỉ cần cung cấp cho bạn một ví dụ cụ thể hơn dựa trên trường hợp của bạn, tôi giả sử bạn có thể viết hai hàm: accept(token) và expect(token), kiểm tra mã thông báo tiếp theo trong luồng bạn đã tạo. Bạn sẽ tạo một hàm cho từng loại câu lệnh hoặc biểu thức trong ngữ pháp ngôn ngữ của bạn. Dưới đây là Pythonish giả cho một hàm statement(), ví dụ:

def statement(): 

    if accept("if"): 
    x = expression() 
    y = statement() 
    return IfStatement(x, y) 

    elif accept("return"): 
    x = expression() 
    return ReturnStatement(x) 

    elif accept("{") 
    xs = [] 
    while True: 
     xs.append(statement()) 
     if not accept(";"): 
     break 
    expect("}") 
    return Block(xs) 

    else: 
    error("Invalid statement!") 

này mang đến cho bạn những gì được gọi là một cây cú pháp trừu tượng (AST) của chương trình của bạn, sau đó bạn có thể thao tác (tối ưu hóa và phân tích), đầu ra (biên soạn), hoặc chạy (diễn giải).

Answer 2

Cách của tôi tốt hơn hoặc tệ hơn là cách cách ban đầu? Lưu ý rằng mã của tôi sẽ được đọc và biên dịch (được dịch sang ngôn ngữ khác, như PHP), thay vì được giải thích mọi lúc.

cách gốc là gì? Có nhiều cách khác nhau để thực hiện ngôn ngữ. Tôi nghĩ rằng bạn là tốt thực sự, tôi đã từng cố gắng để xây dựng một ngôn ngữ bản thân mình mà dịch sang C#, hack programming language. Nhiều trình biên dịch ngôn ngữ dịch sang một ngôn ngữ trung gian, nó khá phổ biến.

Sau khi trình thông báo, tôi cần làm gì chính xác? Tôi thực sự bị mất trên đèo này!

Sau khi mã hóa, bạn cần phải phân tích. Sử dụng một số khung lexer/parser tốt, chẳng hạn như Boost.Spirit hoặc Coco hoặc bất kỳ thứ gì. Có hàng trăm cái giống vậy. Hoặc bạn có thể thực hiện lexer của riêng bạn, nhưng điều đó cần có thời gian và tài nguyên. Có nhiều cách để phân tích mã, tôi thường dựa vào recursive descent parsing.

Tiếp theo bạn cần thực hiện Tạo mã. Đó là phần khó nhất trong quan điểm của tôi. Có những công cụ cho điều đó, nhưng bạn có thể làm điều đó theo cách thủ công nếu bạn muốn, tôi đã cố gắng làm điều đó trong dự án của mình, nhưng nó khá cơ bản và lỗi, có một số mã hữu ích here và here.

Có một số hướng dẫn hay để tìm hiểu cách tôi có thể làm điều đó?

Như tôi đã đề xuất trước đó, hãy sử dụng công cụ để thực hiện. Có rất nhiều khung phân tích cú pháp được viết tài liệu khá tốt.Để biết thêm thông tin, bạn có thể thử hỏi một số người biết về nội dung này. @DeadMG, tại số Lounge C++ đang xây dựng một ngôn ngữ lập trình được gọi là "Rộng". Bạn có thể thử tư vấn cho anh ta.

Answer 3

Hầu hết các bộ công cụ chia quá trình hoàn thành hai riêng phần

• lexer (aka. Tokenizer)
• phân tích cú pháp (hay còn gọi là ngữ pháp.)

Các tokenizer sẽ chia dữ liệu đầu vào vào thẻ. Trình phân tích cú pháp sẽ chỉ hoạt động trên luồng "mã" và tạo cấu trúc.

Câu hỏi của bạn dường như tập trung vào trình mã thông báo. Nhưng giải pháp thứ hai của bạn trộn lẫn trình phân tích cú pháp ngữ pháp và trình thông báo vào một bước. Về mặt lý thuyết điều này cũng có thể nhưng đối với người mới bắt đầu, nó là nhiều dễ dàng hơn để thực hiện theo cách tương tự như hầu hết các công cụ/khung công tác khác: giữ riêng các bước.

Để giải pháp đầu tiên của bạn: Tôi sẽ tokenize ví dụ của bạn như thế này:

T_KEYWORD_IF "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_LITARAL  "5" 
T_RPAREN  ")" 
T_KEYWORD_RET "return" 
T_KEYWORD_TRUE "true" 
T_TERMINATOR ";" 

Trong hầu hết các ngôn ngữ từ khóa không thể được sử dụng như tên phương pháp, tên biến và vân vân. Điều này được phản ánh ở cấp độ trình thông báo (T_KEYWORD_IF, T_KEYWORD_RET, T_KEYWORD_TRUE).

Các cấp độ tiếp theo sẽ mất dòng này và - bằng cách áp dụng một ngữ pháp chính thức - sẽ xây dựng một số datastructure (thường được gọi là AST - cú pháp trừu tượng Tree) mà có thể trông như thế này:

IfStatement: 
    Expression: 
     BinaryOperator: 
      Operator:  T_GT 
      LeftOperand: 
       IdentifierExpression: 
        "x" 
      RightOperand: 
       LiteralExpression 
        5 
    IfBlock 
     ReturnStatement 
      ReturnExpression 
       LiteralExpression 
        "true" 
    ElseBlock (empty) 

Thực hiện phân tích cú pháp bằng tay thường được thực hiện bởi một số khung công tác.Thực hiện một cái gì đó như thế bằng tay và hiệu quả thường được thực hiện tại một trường đại học trong phần tốt hơn của một học kỳ. Vì vậy, bạn thực sự nên sử dụng một số loại khung.

Đầu vào cho khung phân tích cú pháp ngữ pháp thường là ngữ pháp chính thức ở một số loại BNF. Phần "if" của bạn trông giống như thế này:

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ; 

Expression: LiteralExpression | BinaryExpression | IdentifierExpression | ... ; 

BinaryExpression: LeftOperand BinaryOperator RightOperand; 

.... 

Đó chỉ là ý tưởng. Phân tích ngôn ngữ của một thế giới thực như Javascript chính xác không phải là một nhiệm vụ dễ dàng. Nhưng vui mà.