Làm cách nào để phân tích cú pháp số học cơ bản (ví dụ: "5 + 5") bằng cách sử dụng trình phân tích cú pháp gốc đệ quy đơn giản trong C++?

Question

Điều này đã được ghi nhớ trong một thời gian. Tôi bị hấp dẫn bởi các trình phân tích cú pháp gốc đệ quy, và muốn biết cách thực hiện một. Những gì tôi muốn là một trình phân tích cú pháp đơn giản sẽ hiểu số học đơn giản như "5 + 5" hoặc "(5 + 5) * 3".

Tôi tìm bước đầu tiên là viết 'tokenizer', lấy toàn bộ chuỗi đầu vào và chia thành nhiều chuỗi. Phần này tôi đã làm (thậm chí tôi đã phải hỏi về nó here. Bạn không cần phải theo liên kết nếu bạn không muốn, vì tôi đang đăng mã relavent ở đây là tốt.) Với tokenizer này của tôi, tôi kết thúc bằng một số vector trong số string s hoặc mã thông báo. Bây giờ, phần khó khăn: Tôi muốn phân tích những thẻ đó.

Tôi đã đọc Wikipedia article on recursive descent parsers. Tôi hiểu khái niệm tổng thể, nhưng như mọi khi, việc thực hiện là một chút bối rối. Trong bài viết đó, có một triển khai C của một trình phân tích cú pháp gốc đệ quy cho một ngôn ngữ lập trình rất đơn giản, cũng được thảo luận trong bài viết. Tôi đã nghiên cứu mã đó tốt nhất có thể, và cố gắng viết một cách cơ bản, nhưng đối với chương trình của tôi. Dưới đây là mã đó.

Điều tôi thực sự nhầm lẫn là trình phân tích cú pháp này làm gì. Dường như đi qua chương trình và 'mong đợi' một số phần nhất định của ngữ pháp. Nhưng một khi nó đến đó, nó làm gì? Ví dụ, đây là một trong những chức năng từ mã Wikipedia đó là nghĩa vụ để phân tích một 'hạn':

void term(void) { 
    factor(); 
    while (sym == times || sym == slash) { 
     getsym(); 
     factor(); 
    } 
} 

này có nghĩa là để phân tích ngữ pháp này:

term = factor {("*"|"/") factor} . 

có ý nghĩa. Nhưng nó làm gì với thuật ngữ thực tế? Giả sử thuật ngữ này chỉ đơn giản là "6" hoặc là "3 * 2" và có giá trị 6. Làm cách nào để kết hợp nó vào phần còn lại của đầu vào? Không nên term() trả lại double thay vì void (để trả lại 6)? Hoặc là nó được thực hiện một số cách khác?

Ngoài ra, sự khác biệt giữa việc phân tích cú pháp như thế này với mã đầu ra là gì và ngay lập tức hành động dựa trên đầu vào (tức là trình biên dịch so với trình thông dịch)? Có phải hai (trong ví dụ này ít nhất) về mặt lý thuyết được thực hiện theo cùng một cách, hoặc về cơ bản chúng có khác nhau không?

Mọi đầu vào đều được chào đón. Đây là mã của tôi vậy, đến nay:

#include <iostream> 
#include <string> 
#include <vector> 
#include <ctype.h> 
#include <sstream> 

using namespace std; 

vector<string> symbolize(string); 
bool accept(string); 
void getSymbol(); 
void error(string s); 
bool expect(string); 
void expression(); 
void term(); 
void factor(); 

int currentPosition = -1; 
string symbol; 
vector<string> symbols; 

int main(int argc, const char * argv[]) 
{ 

    string input; 
    getline(cin,input); 

    symbols = symbolize(input); 
    getSymbol(); 
    expression(); 


    return 0; 
} 

void factor(){ 
    if(isdigit(symbol.c_str()[0])){} 
    else if(accept("(")){ 
     expression(); 
     expect(")"); 
    } 
    else { 
     error("Syntax error"); 
    } 

} 

void term(){ 
    factor(); 
    while(symbol=="*"||symbol=="/"){ 
     getSymbol(); 
     factor(); 
    } 
} 

void expression(){ 
    if(symbol == "+" || symbol == "-") getSymbol(); 
    term(); 
    while(symbol == "+" || symbol == "-"){ 
     getSymbol(); 
     term(); 
    } 
} 

void error(string s){ 
    cout << endl << "ERROR: " << s << endl; 
} 

void getSymbol(){ 
    currentPosition++; 
    if(currentPosition>=symbols.size())error("Unexpectedly reached end of input"); 

} 

bool expect(string s){ 
    if(accept(s))return true; 
    else error("Expected '" + s + "'"); 
    return false; 
} 

bool accept(string s){ 
    if(s==symbol){getSymbol();return true;} 
    return false; 
} 

// Takes a string and breaks it into substrings 
vector<string> symbolize(string input){ 
    int position = 0; 
    char c; 
    //stringstream s; 
    vector<string> symbols; 
    enum symbolType {TEXT,OPERATOR}symbolType,charType; 

    while(position < input.size()){ 
     stringstream s; 
     c = input.at(position); 
     if(isalnum(c))symbolType = TEXT; 
     else symbolType = OPERATOR; 
     charType = symbolType; 

     while(symbolType == charType){ 
      s << c; 
      position++; 
      if(position>=input.length())break; 
      c = input.at(position); 
      if(isspace(c)||c=='\n'){position++; break;} 
      if(isalnum(c)) charType = TEXT; 
      else charType = OPERATOR; 
     } 

     symbols.push_back(s.str()); 
    } 

    return symbols; 
} 

Edit: tôi nên đề cập rằng mã của tôi luôn in: ERROR: syntax error, từ factor() chức năng.

Answer 1

Bài viết wikipedia chứa một trình phân tích cú pháp tìm kiếm rất hoàn chỉnh (nhưng không có lexer!) Không có gì khác.

Để thực sự diễn giải kết quả, ý tưởng chung là, mỗi chức năng phân tích cú pháp trả lại kết quả được giải thích một phần cho phụ huynh/người gọi. Kết quả có thể là một loại khác nhau cho mỗi quy tắc trong cây. Nếu bạn đang viết một trình phân tích cú pháp cho một ngôn ngữ hoàn chỉnh, một kết quả giải nghĩa một phần có thể là một hằng số đơn giản (có thể là bất kỳ kiểu nào) hoặc nó có thể là toàn bộ hàm (mà bạn có thể cần biên dịch sau). Trong trường hợp của một trình phân tích cú pháp phương trình, mỗi quy tắc sẽ chỉ thực hiện thao tác được yêu cầu trên các phần tử mà nó nhận được từ việc gọi các hàm khác, và chuyển kết quả ngược lại cho hàm đã gọi nó.

Có hai phương pháp mà tôi suy nghĩ:

1. có mỗi chức năng chấp nhận một tham số something* result. Trong trường hợp của một trình phân tích phương trình đơn giản, điều này có thể là float* result cho tất cả các phần tử.

2. Chỉ cần trả lại kết quả, bằng cách thay đổi tất cả các chức năng từ void rule_x()... thành float rule_x()....

Trong cả hai trường hợp, bạn sẽ cần một số cách để xử lý lỗi. Nếu bạn đang ở trong C bạn không có ngoại lệ, do đó bạn có lẽ sẽ là tốt nhất bằng cách sử dụng tùy chọn 1 và sử dụng giá trị trả về để cho biết thành công. Sau đó, sẽ có rất nhiều

if(!expression(&result)) return 0; 

Nhưng trong C++ bạn có thể quấn phân tích cú pháp trong một trình xử lý ngoại lệ, và ném một ngoại lệ về lỗi đó bị hủy bỏ phần còn lại của phân tích cú pháp.

Mọi thứ trở nên thú vị hơn nhiều khi bạn muốn, nói biên dịch toàn bộ ngôn ngữ với tối ưu hóa hoặc JIT và cố khôi phục một cách duyên dáng từ các lỗi cú pháp và tiếp tục phân tích cú pháp.

Sách để xem chủ đề là dragon book.