mã hóa trực tiếp so với bảng điều khiển lexer?

Question

Tôi mới trong thế giới xây dựng trình biên dịch, tôi muốn biết sự khác biệt giữa phân tích lexer được mã hóa trực tiếp so với bảng điều khiển là gì?

Vui lòng sử dụng ví dụ mã nguồn đơn giản nếu có thể.

Cảm ơn.

Edit:

trong Engineering a Compiler cuốn sách, tác giả chia lexers thành ba (3) loại: bảng điều khiển, trực tiếp mã hóa, và tay được mã hóa.

Answer 1

Tôi giả định rằng bạn bằng "mã hóa trực tiếp" nghĩa là từ viết tay chứ không phải là từ được tạo ra dưới dạng đầu ra của trình tạo lexer. Trong trường hợp đó ... (Xem bên dưới.)

... một bảng-driven lexer là một (thường là tự động tạo ra) chương trình có sử dụng một số loại bảng tra cứu để xác định hành động để thực hiện. Hãy xem xét các finite automaton tương ứng với biểu thức chính quy ab*a (cố ý không hạn chế tối đa):

Nếu chúng ta giới hạn mình chỉ xem xét ký tự 'a' và 'b', chúng ta có thể mã hóa nó trong một bảng tra cứu như vậy:

#define REJECT -1 

/* This table encodes the transitions for a given state and character. */ 
const int transitions[][] = { 
    /* In state 0, if we see an a then go to state 1 (the 1). 
    * Otherwise, reject input. 
    */ 
    { /*a*/ 1, /*b*/ REJECT }, 
    { /*a*/ 2, /*b*/ 3  }, 
    { /*a*/ -1, /*b*/ -1  }, /* Could put anything here. */ 
    { /*a*/ 2, /*b*/ 3  } 
}; 

/* This table determines, for each state, whether it is an accepting state. */ 
const int accept[] = { 0, 0, 1, 0 }; 

Bây giờ chúng ta chỉ cần một người lái xe mà thực sự sử dụng bảng:

int scan(void) { 
    char ch; 
    int state = 0; 

    while (!accept[state]) { 
     ch = getchar() - 'a'; /* Adjust so that a => 0, b => 1. */ 
     if (transitions[state][ch] == REJECT) { 
      fprintf(stderr, "invalid token!\n"); 
      return 0; /* Fail. */ 
     } else { 
      state = transitions[state][ch]; 
     } 
    } 
    return 1; /* Success! */ 
} 

Tất nhiên, trong một lexer thực mỗi mã thông báo sẽ có một trạng thái chấp nhận tương ứng, và bạn sẽ phải bằng cách nào đó sửa đổi bảng chấp nhận để chứa mã định danh token. Tuy nhiên, tôi muốn nhấn mạnh hai điều:

1. Lexer điều khiển bảng không nhất thiết phải hoạt động ở cấp trạng thái DFA.
2. Tôi không khuyên bạn nên viết lexers bảng điều khiển bằng tay vì nó là một quá trình tẻ nhạt và dễ bị lỗi.

A viết tay (vì thiếu tên tốt hơn) lexer thường không sử dụng bảng tra cứu. Giả sử chúng ta muốn có một lexer cho một đơn giản ngôn ngữ Lisp giống như có dấu ngoặc đơn, định danh và số nguyên thập phân:

enum token { 
    ERROR, 
    LPAREN, 
    RPAREN, 
    IDENT, 
    NUMBER 
}; 

enum token scan(void) { 
    /* Consume all leading whitespace. */ 
    char ch = first_nonblank(); 
    if (ch == '(') return LPAREN; 
    else if (ch == ')') return RPAREN; 
    else if (isalpha(ch)) return ident(); 
    else if (isdigit(ch)) return number(); 
    else { 
     printf("invalid token!\n"); 
     return ERROR; 
    } 
} 

char first_nonblank(void) { 
    char ch; 
    do { 
     ch = getchar(); 
    } while (isspace(ch)); 
    return ch; 
} 

enum token ident(void) { 
    char ch; 
    do { 
     ch = getchar(); 
    } while (isalpha(ch)); 
    ungetc(ch, stdin); /* Put back the first non-alphabetic character. */ 
    return IDENT; 
} 

enum token number(void) { 
    char ch; 
    do { 
     ch = getchar(); 
    } while (isdigit(ch)); 
    ungetc(ch, stdin); /* Put back the first non-digit. */ 
    return NUMBER; 
} 

Giống như bảng điều khiển dụ lexer, chương trình này không phải là hoàn tất. Đối với một điều, nó cần một số loại đệm để lưu trữ các ký tự là một phần của một mã thông báo như IDENT và NUMBER. Đối với người khác, nó không xử lý EOF đặc biệt một cách duyên dáng. Nhưng hy vọng bạn có được ý chính của nó.

---

Sửa: Dựa vào định nghĩa trong Engineering a Compiler, một trực tiếp mã lexer cơ bản là một hỗn hợp của cả hai. Thay vì sử dụng một bảng, chúng tôi sử dụng các nhãn mã để biểu diễn các trạng thái. Hãy xem nó sẽ trông như thế nào khi sử dụng cùng một DFA như trước đây.

int scan(void) { 
    char ch; 

state0: 
    ch = getchar(); 
    if (ch == 'a') goto state1; 
    else { error(); return 0; } 

state1: 
    ch = getchar(); 
    if (ch == 'a') goto state2; 
    else if (ch == 'b') goto state3; 
    else { error(); return 0; } 

state2: 
    return 1; /* Accept! */ 

state3: 
    ch = getchar(); 
    if (ch == 'a') goto state2; 
    else if (ch == 'b') goto state3; /* Loop. */ 
    else { error(); return 0; } 
} 

---

Trong kinh nghiệm cá nhân của tôi cách tiếp cận "tốt nhất" để viết lexers là phương pháp viết tay tôi nêu ở trên. Nó hoạt động trên mọi nền tảng, trong mọi ngôn ngữ, bạn không cần học các công cụ cổ như lex, và, có lẽ quan trọng nhất, bạn có khả năng linh hoạt để mở rộng lexer với các tính năng khó hoặc không thể thực hiện với một công cụ. Ví dụ, có lẽ bạn muốn lexer của bạn để hiểu indentaiton khối Python-esque, hoặc có thể bạn cần phải tự động mở rộng các lớp mã thông báo nhất định.