Văn phạm với các luật sinh A->aA; A → XYZ có bao nhiêu ký hiệu chưa kết thúc?

Bộ phân tích từ vựng (Lexical Analyzer) là một giai đoạn trong quá trình biên dịch, có nhiệm vụ đọc chương trình nguồn và phân tích thành các đơn vị cơ bản gọi là từ tố (tokens). Các từ tố này sau đó được chuyển cho bộ phân tích cú pháp (parser) để tiếp tục xử lý.

* A. Chương trình nguồn: Đây là đầu vào của bộ phân tích từ vựng, không phải là đầu ra.
* B. Các từ vựng và biến sử dụng trong chương trình: Mặc dù bộ phân tích từ vựng có thể nhận diện các từ vựng và biến, nhưng mục đích chính của nó là tạo ra các từ tố.
* C. Các từ tố: Đây là đáp án chính xác. Bộ phân tích từ vựng chia chương trình nguồn thành các từ tố.
* D. Các qui tắc ngữ pháp: Các qui tắc ngữ pháp được xử lý bởi bộ phân tích cú pháp, không phải bộ phân tích từ vựng.

Thuật toán phân tích top-down quay lui (hay còn gọi là top-down backtracking parsing) là một phương pháp phân tích cú pháp mà bắt đầu từ ký hiệu bắt đầu của ngữ pháp và cố gắng xây dựng cây phân tích bằng cách thử các luật sản xuất khác nhau. Nếu một lựa chọn không thành công (dẫn đến một nhánh cụt), thuật toán sẽ quay lui (backtrack) để thử một lựa chọn khác. Do đó, nó sẽ đưa ra một phân tích trái (leftmost derivation) đối với xâu vào nếu tồn tại, hoặc đưa ra thông báo sai nếu không có phân tích nào phù hợp. Vì vậy, đáp án C là chính xác nhất. Các đáp án khác không mô tả đúng bản chất của thuật toán này:
- Đáp án A sai vì thuật toán có thể không thành công.
- Đáp án B sai vì thuật toán thực hiện phân tích trái.
- Đáp án D sai vì đây không phải là kết quả duy nhất mà thuật toán có thể đưa ra.

Văn phạm đệ quy trái là một loại văn phạm trong đó một biến có thể dẫn xuất ra một chuỗi bắt đầu bằng chính nó. Điều này có nghĩa là tồn tại một dẫn xuất có dạng A -> Aα, trong đó A là một biến và α là một chuỗi các ký hiệu (biến hoặc ký hiệu kết thúc).

Phương án A, A->AX, thể hiện đúng định nghĩa của văn phạm đệ quy trái. Biến A dẫn xuất trực tiếp ra một chuỗi bắt đầu bằng chính A, sau đó là X.

Phương án B, A->XA, là văn phạm đệ quy phải.

Phương án C, A->By, không phải là đệ quy trái vì A dẫn xuất ra B, không phải A.

Phương án D, A->+Ay, không phải là định dạng chuẩn để biểu diễn dẫn xuất trong văn phạm, và ký hiệu '+' thường không xuất hiện trong các quy tắc sản xuất cơ bản. Dù có thể hiểu là 'một hoặc nhiều lần', nó không trực tiếp thể hiện tính đệ quy trái theo định nghĩa chuẩn.

Chương trình nguồn (source code) là mã lệnh được viết bởi lập trình viên trước khi được biên dịch (compile) hoặc thông dịch (interpret) thành mã máy để máy tính có thể thực thi. Trong giai đoạn viết chương trình nguồn, lập trình viên có thể mắc phải nhiều loại lỗi khác nhau.

* Lỗi từ vựng (Lexical errors): Là lỗi liên quan đến việc sử dụng sai các từ khóa, tên biến, hoặc các ký tự không hợp lệ trong ngôn ngữ lập trình. Ví dụ: viết sai tên một hàm hoặc sử dụng một ký tự đặc biệt không được phép. Chương trình nguồn *có thể* chứa lỗi này.
* Lỗi cú pháp (Syntax errors): Là lỗi liên quan đến việc viết sai cấu trúc câu lệnh theo quy tắc của ngôn ngữ lập trình. Ví dụ: thiếu dấu chấm phẩy, ngoặc không khớp, hoặc sử dụng sai toán tử. Chương trình nguồn *có thể* chứa lỗi này.
* Lỗi ngữ nghĩa (Semantic errors): Là lỗi liên quan đến ý nghĩa của chương trình, mặc dù cú pháp có thể đúng. Ví dụ: sử dụng sai kiểu dữ liệu, thực hiện phép toán không hợp lệ, hoặc truy cập vào một vùng nhớ không được phép. Chương trình nguồn *có thể* chứa lỗi này.
* Lỗi nhập dữ liệu: Lỗi này phát sinh trong quá trình chương trình thực thi khi người dùng nhập dữ liệu không hợp lệ, không phải là lỗi mà chương trình nguồn *chứa*. Chương trình nguồn không thể kiểm soát hoàn toàn dữ liệu đầu vào từ người dùng.

Như vậy, lỗi nhập dữ liệu không phải là lỗi mà chương trình nguồn chứa, mà là lỗi xảy ra trong quá trình thực thi chương trình do dữ liệu đầu vào không hợp lệ.

Văn phạm tăng cường (augmented grammar) G' được xây dựng từ văn phạm G bằng cách thêm một ký hiệu bắt đầu mới S' và luật sinh S' -> S. Mục đích của việc này là để đảm bảo rằng ký hiệu bắt đầu của văn phạm gốc (S) chỉ xuất hiện ở phía bên phải của các luật sinh trong văn phạm tăng cường. Điều này rất hữu ích trong việc xây dựng các bộ phân tích cú pháp (parsers), đặc biệt là các bộ phân tích LR.