Phân tích cú pháp dự đoán không đệ qui cần:

Phương pháp phân tích cú pháp "Shift reduce" là một phương pháp phân tích từ dưới lên. Trong phương pháp này, chúng ta bắt đầu từ các token (từ vựng) của ngôn ngữ và cố gắng "shift" (đẩy) chúng vào một stack, sau đó "reduce" (rút gọn) các token trên stack thành các non-terminal theo các luật sinh của ngữ pháp. Quá trình này tiếp tục cho đến khi stack chỉ còn lại non-terminal gốc (start symbol), hoặc không thể thực hiện thêm thao tác nào nữa. Vì vậy, đáp án B là đáp án chính xác. Đáp án D "Phân tích thu gọn" là một cách diễn đạt khác của phân tích từ dưới lên, tuy nhiên đáp án B chính xác hơn khi chỉ rõ đây là phương pháp "từ dưới lên". Đáp án A "Phân tích từ trên xuống" là một phương pháp khác biệt, bắt đầu từ non-terminal gốc và cố gắng suy dẫn ra chuỗi token. Đáp án C không đúng vì phương pháp Shift reduce chỉ thuộc loại phân tích từ dưới lên.

Trong câu lệnh x = 1.5*y + 3.2, quá trình phân tích từ vựng sẽ tách các thành phần sau:

• x: Định danh (biến)
• =: Toán tử gán
• 1.5: Hằng số thực
• *: Toán tử nhân
• y: Định danh (biến)
• +: Toán tử cộng
• 3.2: Hằng số thực

Như vậy, có hai từ tố số thực là 1.5 và 3.2.

Một ngôn ngữ được gọi là chính quy (Regular Language) nếu và chỉ nếu nó có thể được chấp nhận bởi một máy hữu hạn trạng thái xác định (Deterministic Finite Automaton - DFA). Các loại máy khác như PDA, LBA, và máy Turing chấp nhận các lớp ngôn ngữ rộng hơn, không chỉ ngôn ngữ chính quy.

• DFA (Deterministic Finite Automaton): Chấp nhận ngôn ngữ chính quy.
• PDA (Pushdown Automaton): Chấp nhận ngôn ngữ phi ngữ cảnh (Context-Free Language).
• LBA (Linear Bounded Automaton): Chấp nhận ngôn ngữ ngữ cảnh phụ thuộc (Context-Sensitive Language).
• Máy Turing: Chấp nhận ngôn ngữ đệ quy liệt kê được (Recursively Enumerable Language).

Do đó, đáp án đúng là A.

Biểu thức chính quy (Regular Expression) là một chuỗi ký tự đặc biệt dùng để mô tả một tập hợp các chuỗi khác, theo một cú pháp nhất định. Các phép toán cơ bản trong biểu thức chính quy bao gồm: phép hợp (union), phép nối (concatenation), và phép lặp (Kleene star). Phương án A: `[(a+b)*-(aa+bb)]*` - Có vẻ như có sử dụng ký tự '-' không đúng cách trong biểu thức chính quy. Dấu '-' thường không được sử dụng trực tiếp như một toán tử trong biểu thức chính quy theo nghĩa này. Tuy nhiên, cần xem xét ngữ cảnh cụ thể để xác định chính xác. Giả sử '-' là một ký tự literal, biểu thức có thể đúng. Phương án B: `[(0+1)-(0b+a1)*(a+b)]*` - Tương tự như phương án A, sự xuất hiện của '-' và các ký tự 'b', 'a' có thể không phù hợp nếu không được định nghĩa trước hoặc sử dụng đúng cách. Nếu 'b' và 'a' là ký tự trong bảng chữ cái, biểu thức có thể đúng nếu '-' là một ký tự literal. Tuy nhiên, cách sử dụng này không phổ biến. Phương án C: `(01+11+10)*` - Đây là một biểu thức chính quy hợp lệ. Nó mô tả một chuỗi bao gồm các chuỗi con "01", "11", hoặc "10", lặp lại không hoặc nhiều lần. Phương án D: `(1+2+0)*(1+2)*` - Đây là một biểu thức chính quy hợp lệ. Nó mô tả một chuỗi bao gồm các ký tự "1", "2", hoặc "0", lặp lại không hoặc nhiều lần, sau đó là các ký tự "1" hoặc "2" lặp lại không hoặc nhiều lần. Trong các phương án trên, phương án B có vẻ không phải là một biểu thức chính quy chuẩn do sự xuất hiện của các ký tự 'b' và 'a1' mà không có định nghĩa rõ ràng về chúng trong ngữ cảnh biểu thức chính quy thông thường, cũng như cách sử dụng dấu '-'. Tuy nhiên, phương án A cũng gây tranh cãi. Vì câu hỏi yêu cầu chọn biểu thức *không* phải là biểu thức chính quy, phương án B phù hợp hơn do cách sử dụng các ký tự và toán tử không chuẩn.