Ngữ pháp: sự khác biệt giữa từ trên xuống dưới và dưới lên?

Question

Sự khác nhau giữa ngữ pháp từ trên xuống và dưới lên là gì? Một ví dụ sẽ là tuyệt vời.

Answer 1

Trước hết, ngữ pháp không phải là từ trên xuống dưới hoặc dưới lên, trình phân tích cú pháp là (mặc dù có một số ngữ pháp có thể được phân tích cú pháp nhưng không phải là ngữ pháp khác). Từ quan điểm thực tế, sự khác biệt chính là hầu hết các trình phân tích cú pháp viết tay là từ trên xuống, trong khi tỷ lệ phần trăm lớn hơn các trình phân tích cú pháp do máy tạo ra là từ dưới lên (mặc dù, dĩ nhiên, ngược lại chắc chắn là có thể) .

Một phân tích cú pháp từ trên xuống thường sử dụng gốc đệ quy, trong đó thường có nghĩa là một cái gì đó cấu trúc như thế này (sử dụng biểu thức toán học điển hình làm ví dụ):

expression() { term() [-+] expression } 
term() { factor() [*/] term() } 
factor() { operand() | '(' expression() ')' } 

Một từ dưới lên việc phân tích cú pháp theo hướng ngược lại - - nơi phân tích cú pháp gốc đệ quy bắt đầu từ biểu thức đầy đủ, và chia nhỏ thành các phần nhỏ hơn và nhỏ hơn cho đến khi nó đạt đến mức của từng mã thông báo, trình phân tích cú pháp từ dưới lên bắt đầu từ các thẻ riêng lẻ và sử dụng các bảng quy tắc về cách các mã đó phù hợp với nhau thành các cấp cao hơn và cao hơn của hệ thống phân cấp biểu thức cho đến khi nó đạt đến cấp cao nhất (những gì được biểu diễn dưới dạng "biểu thức" ở trên).

Chỉnh sửa: Để làm rõ, có lẽ sẽ có ý nghĩa khi thêm một trình phân tích cú pháp thực sự tầm thường. Trong trường hợp này, tôi sẽ chỉ làm cổ điển cũ của chuyển đổi một phiên bản đơn giản của một biểu thức toán học thông thường từ trung tố để postfix:

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

void expression(void); 

void show(int ch) { 
    putchar(ch); 
    putchar(' '); 
} 

int token() { 
    int ch; 
    while (isspace(ch=getchar())) 
     ; 
    return ch; 
} 

void factor() { 
    int ch = token(); 
    if (ch == '(') { 
     expression(); 
     ch = token(); 
     if (ch != ')') { 
      fprintf(stderr, "Syntax error. Expected close paren, found: %c\n", ch); 
      exit(EXIT_FAILURE); 
     } 
    } 
    else 
     show(ch); 
} 

void term() { 
    int ch; 
    factor(); 
    ch = token(); 
    if (ch == '*' || ch == '/') { 
     term(); 
     show(ch); 
    } 
    else 
     ungetc(ch, stdin); 
} 

void expression() { 
    int ch; 
    term(); 
    ch = token(); 
    if (ch == '-' || ch=='+') { 
     expression(); 
     show(ch); 
    } 
    else 
     ungetc(ch, stdin); 
} 

int main(int argc, char **argv) { 
    expression(); 
    return 0; 
} 

Lưu ý rằng lexing đây là khá ngu ngốc (nó về cơ bản chỉ chấp nhận một ký tự đơn như một mã thông báo) và các biểu thức được cho phép là khá hạn chế (chỉ + - * /). OTOH, nó đủ tốt để xử lý một đầu vào như:

1 + 2 * (3 + 4 * (5/6))

mà từ đó nó tạo ra những gì tôi tin là đúng đầu ra:

1 2 3 4 5 6/* + * +

Answer 2

Afaik nó không tạo ra bất kỳ sự khác biệt nào cho ngữ pháp, nhưng không cho trình phân tích cú pháp.

Wikipedia có lời giải thích khá dài về cả hai số bottom-up và top-down parsing.

Nói chung cách (trực quan) trực quan hơn là từ trên xuống. Bạn bắt đầu với biểu tượng bắt đầu và áp dụng các quy tắc chuyển đổi phù hợp, trong khi với từ dưới lên, bạn cần áp dụng các quy tắc chuyển đổi ngược (thường tạo ra một cơn đau đầu cho tôi).