Scanning

Cắn miếng to vào. Bất cứ việc gì đáng làm thì cũng đáng làm tới mức “quá tay”.

Robert A. Heinlein, Time Enough for Love

Bước đầu tiên trong bất kỳ compiler hay interpreter nào là scanning. Scanner nhận vào mã nguồn thô dưới dạng một chuỗi ký tự và nhóm chúng thành một chuỗi các mảnh mà ta gọi là token. Đây là những “từ” và “dấu câu” mang ý nghĩa, tạo nên ngữ pháp của ngôn ngữ.

Scanning cũng là một điểm khởi đầu tốt cho chúng ta vì phần code này không quá khó — về cơ bản là một câu lệnh switch nhưng “mơ mộng” hơn một chút. Nó sẽ giúp ta khởi động trước khi bước vào những phần thú vị hơn ở phía sau. Đến cuối chương này, ta sẽ có một scanner đầy đủ tính năng, chạy nhanh, có thể nhận bất kỳ chuỗi mã nguồn Lox nào và tạo ra các token để đưa vào parser trong chương tiếp theo.

4 . 1Khung Interpreter

Vì đây là chương thực sự đầu tiên, trước khi bắt tay vào quét code, ta cần phác thảo hình hài cơ bản của interpreter jlox. Mọi thứ bắt đầu với một class trong Java.

package com.craftinginterpreters.lox;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;

public class Lox {
  public static void main(String[] args) throws IOException {
    if (args.length > 1) {
      System.out.println("Usage: jlox [script]");
      System.exit(64); 
    } else if (args.length == 1) {
      runFile(args[0]);
    } else {
      runPrompt();
    }
  }
}

Hãy lưu nó vào một file văn bản, rồi mở IDE hoặc Makefile hay bất cứ công cụ nào bạn dùng để thiết lập. Tôi sẽ ở đây chờ bạn sẵn sàng. Xong chứ? OK!

Lox là một ngôn ngữ scripting, nghĩa là nó execute trực tiếp từ mã nguồn. Interpreter của ta hỗ trợ hai cách chạy code. Nếu bạn khởi động jlox từ dòng lệnh và truyền vào đường dẫn tới một file, nó sẽ đọc file đó và execute.

  private static void runFile(String path) throws IOException {
    byte[] bytes = Files.readAllBytes(Paths.get(path));
    run(new String(bytes, Charset.defaultCharset()));
  }

Nếu bạn muốn “trò chuyện” gần gũi hơn với interpreter, bạn cũng có thể chạy nó ở chế độ tương tác. Khởi động jlox mà không truyền đối số nào, nó sẽ đưa bạn vào một prompt nơi bạn có thể nhập và execute code từng dòng một.

  private static void runPrompt() throws IOException {
    InputStreamReader input = new InputStreamReader(System.in);
    BufferedReader reader = new BufferedReader(input);

    for (;;) { 
      System.out.print("> ");
      String line = reader.readLine();
      if (line == null) break;
      run(line);
    }
  }

Hàm readLine(), đúng như tên gọi, đọc một dòng nhập từ người dùng trên dòng lệnh và trả về kết quả. Để thoát một ứng dụng dòng lệnh tương tác, bạn thường nhấn Control-D. Thao tác này gửi tín hiệu “end-of-file” tới chương trình. Khi điều đó xảy ra, readLine() trả về null, nên ta kiểm tra điều này để thoát vòng lặp.

Cả prompt và trình chạy file đều là các lớp bọc mỏng quanh hàm lõi này:

  private static void run(String source) {
    Scanner scanner = new Scanner(source);
    List<Token> tokens = scanner.scanTokens();

    // For now, just print the tokens.
    for (Token token : tokens) {
      System.out.println(token);
    }
  }

Hiện tại nó chưa hữu ích lắm vì ta chưa viết interpreter, nhưng cứ từ từ từng bước một. Lúc này, nó sẽ in ra các token mà scanner sắp viết sẽ tạo ra, để ta có thể thấy mình đang tiến triển thế nào.

4 . 1 . 1Xử lý lỗi

Khi đang thiết lập mọi thứ, một phần hạ tầng quan trọng khác là xử lý lỗi. Sách giáo khoa đôi khi lướt qua phần này vì nó mang tính thực tiễn nhiều hơn là một vấn đề khoa học máy tính “hàn lâm”. Nhưng nếu bạn muốn tạo ra một ngôn ngữ thực sự dùng được, thì xử lý lỗi một cách mượt mà là điều sống còn.

Các công cụ mà ngôn ngữ của ta cung cấp để xử lý lỗi chiếm một phần lớn trong giao diện người dùng của nó. Khi code của người dùng chạy tốt, họ chẳng nghĩ gì về ngôn ngữ của ta cả — tâm trí họ hoàn toàn tập trung vào chương trình của họ. Thường thì chỉ khi mọi thứ trục trặc, họ mới để ý đến phần hiện thực của ta.

Khi điều đó xảy ra, nhiệm vụ của ta là cung cấp cho người dùng tất cả thông tin họ cần để hiểu chuyện gì đã sai và nhẹ nhàng dẫn họ quay lại đúng hướng. Làm tốt điều này nghĩa là phải nghĩ về xử lý lỗi xuyên suốt quá trình hiện thực interpreter, bắt đầu từ bây giờ.

  static void error(int line, String message) {
    report(line, "", message);
  }

  private static void report(int line, String where,
                             String message) {
    System.err.println(
        "[line " + line + "] Error" + where + ": " + message);
    hadError = true;
  }

Hàm error() này và helper report() của nó sẽ báo cho người dùng biết có lỗi cú pháp xảy ra ở một dòng nhất định. Đây thực sự là mức tối thiểu để có thể nói rằng bạn có báo lỗi. Hãy tưởng tượng nếu bạn vô tình để sót một dấu phẩy trong lời gọi hàm và interpreter in ra:

Error: Unexpected "," somewhere in your code. Good luck finding it!

Thế thì chẳng giúp ích gì mấy. Ta cần ít nhất chỉ ra đúng dòng. Tốt hơn nữa là chỉ ra cả cột bắt đầu và kết thúc để họ biết chỗ nào trong dòng. Còn tốt hơn nữa là hiển thị cho người dùng dòng code gây lỗi, như:

Error: Unexpected "," in argument list.

    15 | function(first, second,);
                               ^-- Here.

Tôi rất muốn hiện thực thứ như vậy trong sách này, nhưng thật lòng mà nói thì nó đòi hỏi khá nhiều code xử lý chuỗi lắt nhắt. Rất hữu ích cho người dùng, nhưng không thú vị lắm để đọc trong sách và cũng không quá hấp dẫn về mặt kỹ thuật. Vậy nên ta sẽ chỉ dừng ở mức số dòng. Trong interpreter của riêng bạn, hãy làm như tôi khuyên, đừng như tôi làm ở đây.

Lý do chính mà ta đặt hàm báo lỗi này trong class Lox chính là vì trường hadError. Nó được định nghĩa ở đây:

public class Lox {

  static boolean hadError = false;

Ta sẽ dùng nó để đảm bảo không cố execute code đã biết là có lỗi. Ngoài ra, nó cho phép ta thoát với exit code khác 0 như một “công dân” dòng lệnh gương mẫu.

    run(new String(bytes, Charset.defaultCharset()));

    // Indicate an error in the exit code.
    if (hadError) System.exit(65);

  }

Ta cần reset cờ này trong vòng lặp tương tác. Nếu người dùng mắc lỗi, nó không nên “giết” cả phiên làm việc của họ.

      run(line);

      hadError = false;

    }

Một lý do khác tôi tách phần báo lỗi ra đây thay vì nhét vào scanner hay các giai đoạn khác nơi lỗi có thể xảy ra là để nhắc bạn rằng việc tách biệt code tạo lỗi và code báo lỗi là một thực hành kỹ thuật tốt.

Nhiều giai đoạn của front-end sẽ phát hiện lỗi, nhưng không thực sự là nhiệm vụ của chúng để biết cách hiển thị lỗi cho người dùng. Trong một hiện thực ngôn ngữ đầy đủ tính năng, bạn có thể sẽ có nhiều cách hiển thị lỗi: trên stderr, trong cửa sổ lỗi của IDE, ghi vào file log, v.v. Bạn không muốn code đó bị rải khắp scanner và parser.

Lý tưởng nhất, ta sẽ có một abstraction thực sự, kiểu như một interface “ErrorReporter” được truyền vào scanner và parser để có thể thay đổi chiến lược báo lỗi. Với interpreter đơn giản này, tôi không làm vậy, nhưng ít nhất tôi cũng đã chuyển code báo lỗi sang một class khác.

Với một chút xử lý lỗi cơ bản, “vỏ” ứng dụng của ta đã sẵn sàng. Khi có class Scanner với phương thức scanTokens(), ta có thể bắt đầu chạy nó. Trước khi đến đó, hãy làm rõ hơn về token.

4 . 2Lexeme & Token

Đây là một dòng code Lox:

var language = "lox";

Ở đây, var là keyword để khai báo biến. Chuỗi ba ký tự “v-a-r” có ý nghĩa. Nhưng nếu ta lấy ba ký tự từ giữa language, như “g-u-a”, thì chúng chẳng có nghĩa gì cả.

Đó chính là điều mà phân tích từ vựng (lexical analysis) xử lý. Nhiệm vụ của ta là quét qua danh sách ký tự và nhóm chúng thành các chuỗi nhỏ nhất vẫn mang ý nghĩa. Mỗi “cục” ký tự như vậy được gọi là lexeme. Trong ví dụ trên, các lexeme là:

Lexeme chỉ là các chuỗi con thô của mã nguồn. Tuy nhiên, trong quá trình nhóm các ký tự thành lexeme, ta cũng thu được một số thông tin hữu ích khác. Khi ta lấy lexeme và gói nó cùng dữ liệu đó, kết quả là một token. Nó bao gồm những thứ hữu ích như:

4 . 2 . 1Loại token (Token type)

Keyword là một phần của cấu trúc ngữ pháp ngôn ngữ, nên parser thường có code kiểu như: “Nếu token tiếp theo là while thì làm…”. Điều đó nghĩa là parser muốn biết không chỉ rằng nó có một lexeme cho một identifier nào đó, mà còn rằng nó là một từ khóa reserved, và là từ khóa nào.

Parser có thể phân loại token từ lexeme thô bằng cách so sánh chuỗi, nhưng cách đó vừa chậm vừa xấu. Thay vào đó, ngay tại thời điểm ta nhận diện được một lexeme, ta cũng ghi nhớ loại lexeme mà nó biểu diễn. Ta có một loại riêng cho mỗi keyword, toán tử, dấu câu, và loại literal.

package com.craftinginterpreters.lox;

enum TokenType {
  // Single-character tokens.
  LEFT_PAREN, RIGHT_PAREN, LEFT_BRACE, RIGHT_BRACE,
  COMMA, DOT, MINUS, PLUS, SEMICOLON, SLASH, STAR,

  // One or two character tokens.
  BANG, BANG_EQUAL,
  EQUAL, EQUAL_EQUAL,
  GREATER, GREATER_EQUAL,
  LESS, LESS_EQUAL,

  // Literals.
  IDENTIFIER, STRING, NUMBER,

  // Keywords.
  AND, CLASS, ELSE, FALSE, FUN, FOR, IF, NIL, OR,
  PRINT, RETURN, SUPER, THIS, TRUE, VAR, WHILE,

  EOF
}

4 . 2 . 2Giá trị literal

Có những lexeme dành cho các giá trị literal — số, chuỗi và những thứ tương tự. Vì scanner phải duyệt qua từng ký tự trong literal để nhận diện chính xác, nó cũng có thể chuyển đổi biểu diễn dạng văn bản của giá trị đó thành đối tượng runtime “sống” sẽ được interpreter sử dụng sau này.

4 . 2 . 3Thông tin vị trí

Khi tôi nói về “phúc âm” của xử lý lỗi, ta đã thấy rằng ta cần cho người dùng biết lỗi xảy ra ở đâu. Việc theo dõi điều đó bắt đầu từ đây. Trong interpreter đơn giản của ta, ta chỉ ghi lại token xuất hiện ở dòng nào, nhưng các hiện thực phức tạp hơn sẽ bao gồm cả cột và độ dài.

Ta gom tất cả dữ liệu này và gói nó trong một class.

package com.craftinginterpreters.lox;

class Token {
  final TokenType type;
  final String lexeme;
  final Object literal;
  final int line; 

  Token(TokenType type, String lexeme, Object literal, int line) {
    this.type = type;
    this.lexeme = lexeme;
    this.literal = literal;
    this.line = line;
  }

  public String toString() {
    return type + " " + lexeme + " " + literal;
  }
}

Giờ ta đã có một đối tượng với đủ cấu trúc để hữu ích cho tất cả các giai đoạn sau của interpreter.

4 . 3Ngôn ngữ & biểu thức chính quy

Giờ ta đã biết mình muốn tạo ra cái gì, hãy… tạo ra nó. Lõi của scanner là một vòng lặp. Bắt đầu từ ký tự đầu tiên của mã nguồn, scanner xác định ký tự đó thuộc về lexeme nào, rồi tiêu thụ nó cùng bất kỳ ký tự tiếp theo nào thuộc về lexeme đó. Khi tới cuối lexeme, nó phát ra một token.

Sau đó, nó quay lại và làm lại từ đầu, bắt đầu từ ký tự tiếp theo trong mã nguồn. Nó cứ tiếp tục như vậy, “ăn” ký tự và thỉnh thoảng, ờ, “thải” ra token, cho tới khi tới cuối input.

Phần trong vòng lặp nơi ta nhìn vào một vài ký tự để xác định lexeme nó “khớp” có thể nghe quen thuộc. Nếu bạn biết regular expression, bạn có thể nghĩ tới việc định nghĩa một regex cho mỗi loại lexeme và dùng chúng để so khớp ký tự. Ví dụ, Lox có cùng quy tắc với C cho identifier (tên biến và tương tự). Regex này sẽ khớp một identifier:

[a-zA-Z_][a-zA-Z_0-9]*

Nếu bạn nghĩ tới regular expression, thì trực giác của bạn rất sâu sắc. Các quy tắc xác định cách một ngôn ngữ nhóm ký tự thành lexeme được gọi là lexical grammar của nó. Trong Lox, cũng như hầu hết các ngôn ngữ lập trình, các quy tắc của ngữ pháp này đủ đơn giản để ngôn ngữ được xếp loại là regular language. Đây chính là “regular” trong regular expression.

Bạn hoàn toàn có thể nhận diện tất cả các lexeme khác nhau của Lox bằng regex nếu muốn, và có cả một đống lý thuyết thú vị giải thích tại sao và ý nghĩa của điều đó. Các công cụ như Lex hoặc Flex được thiết kế riêng để làm việc này — bạn đưa cho chúng một loạt regex, và chúng sẽ trả lại cho bạn một scanner hoàn chỉnh.

Vì mục tiêu của ta là hiểu cách một scanner làm việc, ta sẽ không giao phó nhiệm vụ này. Chúng ta hướng tới những sản phẩm thủ công tinh xảo.

4 . 4Lớp Scanner

Không dài dòng nữa, hãy bắt tay vào tạo một scanner.

package com.craftinginterpreters.lox;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import static com.craftinginterpreters.lox.TokenType.*; 

class Scanner {
  private final String source;
  private final List<Token> tokens = new ArrayList<>();

  Scanner(String source) {
    this.source = source;
  }
}

Ta lưu mã nguồn thô dưới dạng một chuỗi đơn giản, và có sẵn một danh sách để chứa các token sẽ được tạo ra. Vòng lặp đã nhắc tới trước đó trông như thế này:

  List<Token> scanTokens() {
    while (!isAtEnd()) {
      // We are at the beginning of the next lexeme.
      start = current;
      scanToken();
    }

    tokens.add(new Token(EOF, "", null, line));
    return tokens;
  }

Scanner sẽ duyệt qua mã nguồn, thêm token cho đến khi hết ký tự. Sau đó, nó thêm một token “end of file” cuối cùng. Thực ra thì không bắt buộc, nhưng nó giúp parser của ta gọn gàng hơn một chút.

Vòng lặp này dựa vào một vài trường để theo dõi vị trí hiện tại của scanner trong mã nguồn.

  private final List<Token> tokens = new ArrayList<>();

  private int start = 0;
  private int current = 0;
  private int line = 1;

  Scanner(String source) {

Các trường start và current là các offset đánh chỉ số vào chuỗi. Trường start trỏ tới ký tự đầu tiên trong lexeme đang được quét, còn current trỏ tới ký tự hiện tại đang được xét. Trường line theo dõi current đang ở dòng nào trong mã nguồn để ta có thể tạo ra các token biết vị trí của mình.

Tiếp theo, ta có một hàm helper nhỏ để cho biết liệu ta đã tiêu thụ hết ký tự hay chưa.

  private boolean isAtEnd() {
    return current >= source.length();
  }

4 . 5Nhận diện Lexeme

Mỗi vòng lặp, ta quét một token. Đây là phần cốt lõi thực sự của scanner. Ta sẽ bắt đầu đơn giản. Hãy tưởng tượng nếu mỗi lexeme chỉ dài một ký tự. Tất cả những gì cần làm là tiêu thụ ký tự tiếp theo và chọn loại token cho nó. Trong Lox, có một số lexeme đúng là chỉ một ký tự, nên hãy bắt đầu với chúng.

  private void scanToken() {
    char c = advance();
    switch (c) {
      case '(': addToken(LEFT_PAREN); break;
      case ')': addToken(RIGHT_PAREN); break;
      case '{': addToken(LEFT_BRACE); break;
      case '}': addToken(RIGHT_BRACE); break;
      case ',': addToken(COMMA); break;
      case '.': addToken(DOT); break;
      case '-': addToken(MINUS); break;
      case '+': addToken(PLUS); break;
      case ';': addToken(SEMICOLON); break;
      case '*': addToken(STAR); break; 
    }
  }

Một lần nữa, ta cần một vài phương thức helper.

  private char advance() {
    return source.charAt(current++);
  }

  private void addToken(TokenType type) {
    addToken(type, null);
  }

  private void addToken(TokenType type, Object literal) {
    String text = source.substring(start, current);
    tokens.add(new Token(type, text, literal, line));
  }

Phương thức advance() tiêu thụ ký tự tiếp theo trong file nguồn và trả về nó. Nếu advance() là để lấy input, thì addToken() là để xuất output. Nó lấy phần văn bản của lexeme hiện tại và tạo một token mới cho nó. Ta sẽ dùng overload khác để xử lý các token có giá trị literal sau.

4 . 5 . 1Lỗi từ vựng (Lexical errors)

Trước khi đi quá xa, hãy dành chút thời gian nghĩ về lỗi ở mức từ vựng. Điều gì xảy ra nếu người dùng đưa vào một file nguồn chứa các ký tự mà Lox không dùng, như @#^? Hiện tại, các ký tự đó sẽ bị bỏ qua trong im lặng. Chúng không được Lox sử dụng, nhưng điều đó không có nghĩa interpreter có thể giả vờ như chúng không tồn tại. Thay vào đó, ta sẽ báo lỗi.

      case '*': addToken(STAR); break; 

      default:
        Lox.error(line, "Unexpected character.");
        break;

    }

Lưu ý rằng ký tự gây lỗi vẫn được tiêu thụ bởi lời gọi advance() trước đó. Điều này quan trọng để tránh bị kẹt trong vòng lặp vô hạn.

Cũng lưu ý rằng ta tiếp tục quét. Có thể còn những lỗi khác ở phần sau của chương trình. Việc phát hiện càng nhiều lỗi trong một lần chạy sẽ mang lại trải nghiệm tốt hơn cho người dùng. Nếu không, họ sẽ thấy một lỗi nhỏ, sửa nó, rồi lại thấy lỗi tiếp theo, cứ thế… Chơi trò “đập chuột” với lỗi cú pháp thì chẳng vui chút nào.

(Đừng lo. Vì hadError đã được đặt, ta sẽ không bao giờ cố execute bất kỳ code nào, dù vẫn tiếp tục quét phần còn lại.)

4 . 5 . 2Toán tử (Operators)

Ta đã xử lý xong các lexeme một ký tự, nhưng điều đó chưa bao quát hết các toán tử của Lox. Còn ! thì sao? Nó là một ký tự đơn, đúng không? Đôi khi đúng, nhưng nếu ký tự ngay sau nó là dấu bằng, thì ta cần tạo lexeme !=. Lưu ý rằng ! và = không phải là hai toán tử độc lập. Bạn không thể viết ! = trong Lox và mong nó hoạt động như toán tử so sánh khác nhau. Đó là lý do ta cần quét != như một lexeme duy nhất. Tương tự, <, >, và = đều có thể theo sau bởi = để tạo ra các toán tử so sánh và bằng khác.

Với tất cả các trường hợp này, ta cần nhìn vào ký tự thứ hai.

      case '*': addToken(STAR); break; 

      case '!':
        addToken(match('=') ? BANG_EQUAL : BANG);
        break;
      case '=':
        addToken(match('=') ? EQUAL_EQUAL : EQUAL);
        break;
      case '<':
        addToken(match('=') ? LESS_EQUAL : LESS);
        break;
      case '>':
        addToken(match('=') ? GREATER_EQUAL : GREATER);
        break;

      default:

Các trường hợp đó dùng phương thức mới này:

  private boolean match(char expected) {
    if (isAtEnd()) return false;
    if (source.charAt(current) != expected) return false;

    current++;
    return true;
  }

Nó giống như một advance() có điều kiện. Ta chỉ tiêu thụ ký tự hiện tại nếu nó đúng là ký tự ta đang tìm.

Dùng match(), ta nhận diện các lexeme này theo hai bước. Khi gặp, ví dụ, !, ta nhảy vào case tương ứng trong switch. Điều đó nghĩa là ta biết lexeme bắt đầu bằng !. Sau đó, ta nhìn ký tự tiếp theo để xác định xem đó là != hay chỉ là !.

4 . 6Lexeme dài hơn

Ta vẫn còn thiếu một toán tử: / cho phép chia. Ký tự này cần xử lý đặc biệt một chút vì comment cũng bắt đầu bằng dấu gạch chéo.

        break;

      case '/':
        if (match('/')) {
          // A comment goes until the end of the line.
          while (peek() != '\n' && !isAtEnd()) advance();
        } else {
          addToken(SLASH);
        }
        break;

      default:

Điều này tương tự như các toán tử hai ký tự khác, ngoại trừ khi ta tìm thấy dấu / thứ hai, ta chưa kết thúc token ngay. Thay vào đó, ta tiếp tục tiêu thụ ký tự cho đến khi gặp cuối dòng.

Đây là chiến lược chung của ta để xử lý các lexeme dài hơn. Sau khi phát hiện phần bắt đầu của một lexeme, ta chuyển sang đoạn code chuyên biệt cho lexeme đó để tiếp tục “ăn” ký tự cho đến khi gặp điểm kết thúc.

Ta có thêm một helper khác:

  private char peek() {
    if (isAtEnd()) return '\0';
    return source.charAt(current);
  }

Nó giống như advance(), nhưng không tiêu thụ ký tự. Điều này được gọi là lookahead. Vì nó chỉ nhìn vào ký tự hiện tại chưa tiêu thụ, nên ta có lookahead một ký tự. Số này càng nhỏ thì scanner thường chạy càng nhanh. Các quy tắc của lexical grammar quyết định ta cần lookahead bao nhiêu. May mắn thay, hầu hết các ngôn ngữ phổ biến chỉ cần nhìn trước một hoặc hai ký tự.

Comment là lexeme, nhưng chúng không mang ý nghĩa, và parser không muốn xử lý chúng. Vì vậy, khi đến cuối comment, ta không gọi addToken(). Khi vòng lặp quay lại để bắt đầu lexeme tiếp theo, start được đặt lại và lexeme của comment biến mất như một làn khói.

Nhân tiện, đây cũng là lúc tốt để bỏ qua những ký tự vô nghĩa khác: xuống dòng và khoảng trắng.

        break;

      case ' ':
      case '\r':
      case '\t':
        // Ignore whitespace.
        break;

      case '\n':
        line++;
        break;

      default:
        Lox.error(line, "Unexpected character.");

Khi gặp khoảng trắng, ta đơn giản quay lại đầu vòng lặp quét. Điều đó bắt đầu một lexeme mới sau ký tự khoảng trắng. Với xuống dòng, ta làm tương tự, nhưng cũng tăng bộ đếm dòng. (Đây là lý do ta dùng peek() để tìm ký tự xuống dòng kết thúc comment thay vì match(). Ta muốn ký tự xuống dòng đó đưa ta đến đây để cập nhật line.)

Scanner của ta đang trở nên thông minh hơn. Nó có thể xử lý code khá tự do như:

// this is a comment
(( )){} // grouping stuff
!*+-/=<> <= == // operators

4 . 6 . 1String literal

Giờ ta đã quen với lexeme dài hơn, ta sẵn sàng xử lý literal. Ta sẽ làm chuỗi trước, vì chúng luôn bắt đầu bằng một ký tự cụ thể, ".

        break;

      case '"': string(); break;

      default:

Hàm này gọi tới:

  private void string() {
    while (peek() != '"' && !isAtEnd()) {
      if (peek() == '\n') line++;
      advance();
    }

    if (isAtEnd()) {
      Lox.error(line, "Unterminated string.");
      return;
    }

    // The closing ".
    advance();

    // Trim the surrounding quotes.
    String value = source.substring(start + 1, current - 1);
    addToken(STRING, value);
  }

Giống như với comment, ta tiêu thụ ký tự cho đến khi gặp dấu " kết thúc chuỗi. Ta cũng xử lý gọn gàng trường hợp hết input trước khi chuỗi được đóng và báo lỗi cho tình huống đó.

Không vì lý do đặc biệt nào, Lox hỗ trợ chuỗi nhiều dòng. Điều này có ưu và nhược điểm, nhưng việc cấm chúng phức tạp hơn một chút so với cho phép, nên tôi để nguyên. Điều đó có nghĩa là ta cũng cần cập nhật line khi gặp xuống dòng bên trong chuỗi.

Cuối cùng, điểm thú vị là khi tạo token, ta cũng tạo ra giá trị chuỗi thực tế sẽ được interpreter sử dụng sau này. Ở đây, việc chuyển đổi chỉ cần một substring() để bỏ dấu ngoặc kép bao quanh. Nếu Lox hỗ trợ escape sequence như \n, ta sẽ giải mã chúng ở đây.

4 . 6 . 2Number literal

Tất cả số trong Lox đều là số thực dấu chấm động ở runtime, nhưng cả literal nguyên và thập phân đều được hỗ trợ. Một number literal là một chuỗi chữ số tùy chọn theo sau bởi một dấu . và một hoặc nhiều chữ số tiếp theo.

1234
12.34

Ta không cho phép dấu chấm ở đầu hoặc cuối, nên cả hai trường hợp này đều không hợp lệ:

.1234
1234.

Ta có thể dễ dàng hỗ trợ trường hợp đầu, nhưng tôi bỏ qua để giữ mọi thứ đơn giản. Trường hợp thứ hai trở nên rắc rối nếu ta muốn cho phép method trên số như 123.sqrt().

Để nhận diện phần bắt đầu của một number lexeme, ta tìm bất kỳ chữ số nào. Việc thêm case cho từng chữ số thập phân khá tẻ nhạt, nên ta sẽ nhét nó vào case mặc định.

      default:

        if (isDigit(c)) {
          number();
        } else {
          Lox.error(line, "Unexpected character.");
        }

        break;

Điều này dựa vào tiện ích nhỏ này:

  private boolean isDigit(char c) {
    return c >= '0' && c <= '9';
  } 

Khi đã biết mình đang ở trong một số, ta sẽ rẽ sang một phương thức riêng để tiêu thụ phần còn lại của literal, giống như cách ta làm với chuỗi.

  private void number() {
    while (isDigit(peek())) advance();

    // Look for a fractional part.
    if (peek() == '.' && isDigit(peekNext())) {
      // Consume the "."
      advance();

      while (isDigit(peek())) advance();
    }

    addToken(NUMBER,
        Double.parseDouble(source.substring(start, current)));
  }

Ta tiêu thụ càng nhiều chữ số càng tốt cho phần nguyên của literal. Sau đó, ta tìm phần thập phân, tức là một dấu chấm (.) theo sau bởi ít nhất một chữ số. Nếu có phần thập phân, ta lại tiếp tục tiêu thụ càng nhiều chữ số càng tốt.

Nhìn vượt qua dấu chấm đòi hỏi lookahead hai ký tự, vì ta không muốn tiêu thụ dấu . cho đến khi chắc chắn có một chữ số sau nó. Vậy nên ta thêm:

  private char peekNext() {
    if (current + 1 >= source.length()) return '\0';
    return source.charAt(current + 1);
  } 

Cuối cùng, ta chuyển đổi lexeme thành giá trị số. Interpreter của ta dùng kiểu Double của Java để biểu diễn số, nên ta tạo ra một giá trị thuộc kiểu đó. Ta dùng chính phương thức parse của Java để chuyển lexeme thành một số thực Java. Ta có thể tự hiện thực việc này, nhưng thật lòng mà nói, trừ khi bạn đang ôn gấp cho một buổi phỏng vấn lập trình sắp tới, thì không đáng tốn thời gian.

Các literal còn lại là Boolean và nil, nhưng ta xử lý chúng như keyword, và điều đó dẫn ta tới . . . 

4 . 7Reserved Word & Identifier

Scanner của ta gần như xong. Phần còn lại của lexical grammar cần hiện thực là identifier và “họ hàng” gần của chúng — các reserved word. Bạn có thể nghĩ rằng ta có thể khớp keyword như or theo cùng cách ta xử lý các toán tử nhiều ký tự như <=.

case 'o':
  if (match('r')) {
    addToken(OR);
  }
  break;

Hãy nghĩ xem điều gì sẽ xảy ra nếu người dùng đặt tên biến là orchid. Scanner sẽ thấy hai chữ cái đầu or và lập tức phát ra token keyword or. Điều này dẫn ta tới một nguyên tắc quan trọng gọi là maximal munch. Khi hai quy tắc của lexical grammar đều có thể khớp một đoạn code mà scanner đang xét, quy tắc nào khớp được nhiều ký tự hơn sẽ thắng.

Nguyên tắc này nói rằng nếu ta có thể khớp orchid như một identifier và or như một keyword, thì trường hợp đầu sẽ thắng. Đây cũng là lý do ta ngầm giả định trước đó rằng <= nên được quét thành một token <= duy nhất chứ không phải < rồi =.

Maximal munch có nghĩa là ta không thể dễ dàng phát hiện một reserved word cho đến khi đã tới cuối của thứ có thể là một identifier. Suy cho cùng, một reserved word là một identifier, chỉ là một identifier đã bị ngôn ngữ “giữ chỗ” để dùng cho mục đích riêng. Đó là lý do có thuật ngữ reserved word.

Vậy nên ta bắt đầu bằng cách giả định bất kỳ lexeme nào bắt đầu bằng chữ cái hoặc dấu gạch dưới là một identifier.

      default:
        if (isDigit(c)) {
          number();

        } else if (isAlpha(c)) {
          identifier();

        } else {
          Lox.error(line, "Unexpected character.");
        }

Phần còn lại của code nằm ở đây:

  private void identifier() {
    while (isAlphaNumeric(peek())) advance();

    addToken(IDENTIFIER);
  }

Ta định nghĩa nó dựa trên các helper sau:

  private boolean isAlpha(char c) {
    return (c >= 'a' && c <= 'z') ||
           (c >= 'A' && c <= 'Z') ||
            c == '_';
  }

  private boolean isAlphaNumeric(char c) {
    return isAlpha(c) || isDigit(c);
  }

Như vậy là identifier đã hoạt động. Để xử lý keyword, ta kiểm tra xem lexeme của identifier có nằm trong danh sách reserved word hay không. Nếu có, ta dùng loại token đặc biệt cho keyword đó. Ta định nghĩa tập hợp reserved word trong một map.

  private static final Map<String, TokenType> keywords;

  static {
    keywords = new HashMap<>();
    keywords.put("and",    AND);
    keywords.put("class",  CLASS);
    keywords.put("else",   ELSE);
    keywords.put("false",  FALSE);
    keywords.put("for",    FOR);
    keywords.put("fun",    FUN);
    keywords.put("if",     IF);
    keywords.put("nil",    NIL);
    keywords.put("or",     OR);
    keywords.put("print",  PRINT);
    keywords.put("return", RETURN);
    keywords.put("super",  SUPER);
    keywords.put("this",   THIS);
    keywords.put("true",   TRUE);
    keywords.put("var",    VAR);
    keywords.put("while",  WHILE);
  }

Sau đó, sau khi quét một identifier, ta kiểm tra xem nó có khớp với mục nào trong map không.

    while (isAlphaNumeric(peek())) advance();

    String text = source.substring(start, current);
    TokenType type = keywords.get(text);
    if (type == null) type = IDENTIFIER;
    addToken(type);

  }

Nếu có, ta dùng loại token của keyword đó. Nếu không, nó là một identifier do người dùng định nghĩa.

Và với điều đó, ta đã có một scanner hoàn chỉnh cho toàn bộ lexical grammar của Lox. Hãy mở REPL và gõ vào một số code hợp lệ và không hợp lệ. Nó có tạo ra các token như bạn mong đợi không? Hãy thử nghĩ ra vài trường hợp đặc biệt thú vị và xem nó xử lý chúng có đúng như mong muốn không.