Có thể sử dụng Recursive Descent Parser để kiểm tra cả ngữ pháp và xây dựng cây phân tích cú pháp cùng một lúc không?

Question

Có thể tạo ra một cây phân tích cú pháp cùng một lúc khi tôi sử dụng trình phân tích cú pháp gốc đệ quy để kiểm tra xem dữ liệu có khớp với ngữ pháp không?

Nếu vậy, cách tiếp cận nào tôi sẽ sử dụng để xây dựng một cây khi tôi đệ quy gốc?

Cảm ơn, Boda Cydo.

Lưu ý: Tôi mới dùng để phân tích cú pháp. (Đã hỏi một số câu hỏi về SO rồi, và tôi đang tốt hơn với nó.)

Answer 1

Có, có thể. Làm thế nào để làm như vậy sẽ phụ thuộc vào việc thực hiện bạn muốn. Dưới đây là một mẫu có thể làm việc cho bạn:

Thứ nhất, xác định nút của bạn:

class ParseTreeNode { 
    private final String name; 
    private final List<ParseTreeNode> children = /* new */; 
    public ParseTreeNode(String name) { 
    this.name = name; 
    } 
    public void addChild(ParseTreeNode child) { 
    children.add(child); 
} 

Tiếp theo, bạn sẽ cần phải tích hợp đó vào chức năng gốc đệ quy của bạn:

class RDParser { 
    ParseTreeNode parse(Input input) { 
    ParseTreeNode root = createParseTreeNodeNamed("Root") 
    switch (input.nextToken()) { 
     case OPT1: 
     root.addChild(createParseTreeNodeNamed("Opt1")); 
     break; 
     case OPT2: 
     while (/*someCondition*/) { 
      root.addChild(createParseTreeNodeNamed("Opt2-sibling" + /* i */)); 
     } 
     case SUBTREE: 
     ParseTreeNode subtree = createParseTreeNodeNamed("Subtree"); 
     root.addChild(subtree); 
     parseSubtree(subtree, input); 
     break; 
     default: 
     error("Input %s was not in the expected first/follow sets", input.nextToken()); 
    } 
    } 
    void parseSubtree(ParseTreeNode node, Input input) { 
    node.addChild(createParseTreeNodeNamed("subtree-child")); 
    /* ... */ 
    } 

    /* and other functions do similarly */ 
    ParseTreeNode createParseTreeNodeNamed(String name) { 
    return new ParseTreeNode(name); 
    } 
} 

Như bạn xuống cây phân tích cú pháp của bạn, có thể bạn sẽ muốn gửi bất kỳ nút "root" mới nào để trẻ có thể được thêm vào nó. Ngoài ra, parseSubtree có thể tạo và trả về một nút, sau đó sẽ được thêm vào nút gốc.

Bạn có thể tạo cây phân tích hoặc cây trừu tượng đơn giản bằng cách sử dụng quy trình trên. Vì hàm phân tích cú pháp trả về nút gốc, nút này sẽ tham chiếu bất kỳ và tất cả các nút con, bạn sẽ có toàn quyền truy cập vào cây phân tích cú pháp sau khi phân tích cú pháp.

Cho dù bạn sử dụng cây phân tích không đồng nhất hoặc đồng nhất, bạn sẽ cần một cách để lưu trữ thông tin đầy đủ để làm cho nó hữu ích.