Gồm các xâu mà các ký tự a tạo thành tiền tố, các ký tự b tạo thành hậu tố và có chứa xâu rỗng

Gồm các xâu có số ký tự a bằng ký tự b, có chứa xâu rỗng

Gồm các xâu có số ký tự a bằng ký tự b và các ký tự a tạo thành tiền tố, các ký tự b tạo thành hậu tố

Tiền tố

Hậu tố

Xâu con

Không xác định

Tiền tố

Hậu tố

Xâu con

Không xác định

Tiền tố

Hậu tố

Xâu con

Không xác định

Tiền tố

Hậu tố

Xâu con

Không xác định

Gồm các xâu mà các ký tự a tạo thành tiền tố, các ký tự b tạo thành hậu tố, không chứa xâu rỗng

Gồm các xâu có số ký tự a bằng ký tự b và các ký tự a tạo thành tiền tố, các ký tự b tạo thành hậu tố

Gồm các xâu mà các ký tự a tạo thành tiền tố, các ký tự b tạo thành hậu tố, có chứa xâu rỗng

Các nút trong có nhánh là ký hiệu trong V_N

Các nút lá có nhãn là ký hiệu trong V_N

Nếu có sản xuất A → x1 x2 … x_n thì nút A có các con lần lượt là x1, x2, …, x_n

Các nút trong có nhánh là ký hiệu trong V_T

Các nút lá có nhãn là ký hiệu trong V_T ∪ {ε}

Văn phạm chính quy → Văn phạm phi ngữ cảnh → Văn phạm cảm ngữ cảnh → Văn phạm không hạn chế

Văn phạm cảm ngữ cảnh → Văn phạm phi ngữ cảnh → Văn phạm chính quy → Văn phạm không hạn chế

Văn phạm phi ngữ cảnh → Văn phạm chính quy → Văn phạm cảm ngữ cảnh → Văn phạm không hạn chế

Văn phạm không hạn chế → Văn phạm cảm ngữ cảnh → Văn phạm phi ngữ cảnh → Văn phạm chính quy

Nhãn các lá từ trái qua phải lần lượt là a, b, ε, b

Gốc có nhãn là S

Nhãn các lá từ trái qua phải lần lượt là a, b, b

Gốc có nhãn là A

Mọi sản xuất, vế trái là 1 ký hiệu không kết thúc, vế phải là 1 xâu bất kỳ trên bộ chữ V_T ∪ V_N, vế phải khác rỗng

Mọi sản xuất, vế trái là xâu gồm các ký hiệu không kết thúc, vế phải là 1 xâu bất kỳ trên bộ chữ V_T ∪ V_N

Mọi sản xuất, vế trái là 1 ký hiệu không kết thúc, vế phải là 1 xâu bất kỳ trên bộ chữ V_T ∪ V_N

Là các quy luật để sản sinh ngôn ngữ

Là các luật để kiểm tra cú pháp của ngôn ngữ

Là các luật để sản sinh và kiểm tra cú pháp của ngôn ngữ

3

4

5

6

Nhiều văn phạm khác nhau có thể sản sinh ra cùng một ngôn ngữ

Một văn phạm chỉ sản sinh ra một ngôn ngữ

Một văn phạm có thể sản sinh ra nhiều ngôn ngữ

Ký hiệu bắt đầu

Ký hiệu kết thúc

Ký hiệu không kết thúc

Các sản xuất (luật suy dẫn)

Xâu rỗng

Ký hiệu bắt đầu

Ký hiệu kết thúc

Ký hiệu không kết thúc

Các sản xuất (luật suy dẫn)

Xâu rỗng

Ký hiệu bắt đầu

Ký hiệu kết thúc

Ký hiệu không kết thúc

Các sản xuất (luật suy dẫn)

Xâu rỗng

Ký hiệu bắt đầu

Ký hiệu kết thúc

Ký hiệu không kết thúc

Các sản xuất (luật suy dẫn)

Xâu rỗng

Ký hiệu bắt đầu

Ký hiệu kết thúc

Ký hiệu không kết thúc

Các sản xuất (luật suy dẫn)

Xâu rỗng

A → α, $$α ∈ (V_T ∪ V_N)^*$$

α → β, |α| ≤ |β|

A → $$wB$$ , A → $$w$$ , w ∈ V_T^*

A → $$Bw$$ , A → $$w$$ , $$w ∈ V_T^*$$

A → α, $$α ∈ (V_T ∪ V_N)^*$$

α → β, |α| ≤ |β|

$$A \rightarrow wB$$ , $$A \rightarrow w$$ , w \in V_T^*

A → $$Bw$$ , A → $$w$$ , $$w ∈ V_T^*$$

A → α, $$α ∈ (V_T ∪ V_N)^*$$

α → β, |α| ≤ |β|

$$A \rightarrow wB$$ , $$A \rightarrow w$$ , w \in V_T^*

A → $$Bw$$ , A → $$w$$ , $$w ∈ V_T^*$$

Các xâu chỉ gồm các ký hiệu a, b

Số ký hiệu a bằng số ký hiệu b

Có xâu rỗng

Luôn kết thúc bằng ký hiệu b

Luôn bắt đầu bằng ký hiệu a

abAS ⇒ abS

abAS ⇒ abbAS

abAS ⇒ aAbS

abAS ⇒ aS

Phân tích ngữ nghĩa

Phân tích cú pháp

Sinh mã đích

Sinh mã trung gian

Tối ưu mã trung gian

Biên dịch

Phiên dịch

Thông dịch

Biên dịch

Thông dịch

Phiên dịch

Đọc xong phần câu lệnh trong chương trình chính và phần khai báo

Đọc xong các chương trình con và toàn bộ các phần khai báo

Đọc xong toàn bộ chương trình nguồn hoặc trung gian

Đọc xong phần khai báo

Đọc xong chương trình trung gian

Kiểu

Tên

Độ dài

Phạm vi

Giá trị

Tạo ra mã máy hoặc gần với mã máy cho chương trình nguồn

Tạo ra dạng biểu diễn trung gian cho chương trình nguồn

Tạo ra dạng biểu diễn trung gian cho chương trình nguồn

Tạo ra mã máy cho chương trình nguồn

Cải thiện mã trung gian để sinh mã đích chạy nhanh hơn

Tạo ra bảng ký hiệu cho biến và hàm

Phân tích cú pháp

Phân tích ngữ nghĩa

Phân tích từ vựng

Phân tích cú pháp

Phân tích ngữ nghĩa

Tốc độ kém; bộ nhớ tốt; độ phức tạp tốt; phù hợp cho các ứng dụng lớn

Tốc độ tốt; bộ nhớ kém; độ phức tạp kém; không phù hợp cho các ứng dụng lớn

3

4

NNLT có cấu trúc rõ ràng nên có thể dịch tự động sang ngôn ngữ khác

NNLT phỏng theo ngôn ngữ tự nhiên

NNLT có thể tạo ra sự mập mờ, đa nghĩa

NNLT là ngôn ngữ máy tính hiểu được

Tốc độ tốt; bộ nhớ kém; độ phức tạp kém; ít phù hợp cho các ứng dụng lớn

Tốc độ kém; bộ nhớ tốt; độ phức tạp tốt; phù hợp cho các ứng dụng lớn

chương trình; ngôn ngữ nguồn; tương đương; ngôn ngữ đích

công cụ; ngôn ngữ nguồn; tương đương; ngôn ngữ trung gian

Sinh mã trung gian

Sinh mã đích

Tối ưu mã trung gian

Tách chương trình nguồn thành các từ và xác định loại tương ứng

Kiểm tra các lỗi về phạm vi, kiểu, luồng điều kiện

Tìm cấu trúc cú pháp và sự kết hợp các cấu trúc này

Phát hiện lỗi về kiểu dữ liệu và phạm vi

Kiểm tra các lỗi về phạm vi, kiểu, luồng điều kiện

Tạo biểu diễn trung gian cho chương trình nguồn

Phân tích từ vựng

Sinh mã trung gian

Sinh mã đích

Tối ưu mã

Return

i

j

? :

Return

i hoặc j

? hoặc :

;

? và :

i và j

Return

< và >

>

? :

Return

;

Ôtômat hữu hạn

Văn phạm phi ngữ cảnh

Máy Turing

Biểu thức chính quy

1, 3, 2, 4

2, 4, 5

0, 1, 3

0, 1, 2, 3, 4, 5

1, 3

3 cột lần lượt: letter, digit, (+|-|*|/)

8 cột cho 8 cạnh: 2 cột letter, 3 cột digit, 2 cột other, 1 cột (+|-|*|/)

4 cột lần lượt: letter, digit, (+|-|*|/), other

0

1

2

3

5

0

1

2

3

5

0

1

2

3

6 (lỗi)

1

2

5

6 (lỗi)

1

3

5

6 (lỗi)

retract(1); return ident;

installident(); return ident;

retract(1); installident(); return ident;

2

3

4

5

1

2

3

4

0

1

2

3

3

4

5

6

1-2-3-4-5

2-1-3-4-5

1-3-2-4-5

1-2-4-3-5

Ưu điểm của phương pháp diễn giải đồ thị

Nhược điểm của phương pháp diễn giải đồ thị

Ưu điểm của phương pháp tra bảng chuyển trạng thái

Nhược điểm của phương pháp tra bảng chuyển trạng thái

Ưu điểm của phương pháp diễn giải đồ thị

Nhược điểm của phương pháp diễn giải đồ thị

Ưu điểm của phương pháp tra bảng chuyển trạng thái

Nhược điểm của phương pháp tra bảng chuyển trạng thái

Ưu điểm của phương pháp diễn giải đồ thị

Nhược điểm của phương pháp diễn giải đồ thị

Ưu điểm của phương pháp tra bảng chuyển trạng thái

Nhược điểm của phương pháp tra bảng chuyển trạng thái

Ưu điểm của phương pháp diễn giải đồ thị

Nhược điểm của phương pháp diễn giải đồ thị

Ưu điểm của phương pháp tra bảng chuyển trạng thái

Nhược điểm của phương pháp tra bảng chuyển trạng thái

Ký tự bắt đầu từ vựng không đúng

Viết sai từ khóa 'if' thành 'fi' khi bắt đầu câu lệnh

Thiếu từ khóa 'of' trong câu lệnh 'case'

Thiếu phần số sau dấu chấm trong số thập phân

7

8

9

10

1 → 2 → 3 → 4 → 5

1 → 3 → 4 → 2 → 5

2 → 1 → 3 → 4 → 5

1 → 2 → 4 → 3 → 5

chương trình nguồn; một dãy các từ vựng cùng với loại từ tố tương ứng

cú pháp; bảng ký hiệu của chương trình

chương trình trung gian; danh sách lỗi cú pháp

một dãy token; mã máy

a → b → c → d → e

a → c → b → e → d

b → a → c → d → e

a → b → e → d → c

4 cột và 6 dòng

4 cột và 7 dòng

3 cột và 6 dòng

5 cột và 7 dòng

Khi xét đến nút bên phải cùng của cây (tương ứng xét đến ký tự cuối cùng của dạng câu)

Không so khớp được ký hiệu tại nút hoạt động với ký tự đang cần phân tích

Khi xét hết các ký tự trên xâu phân tích

Các ký tự trên xâu phân tích đã xét hết, trên cây phân tích vẫn còn các nút bên phải nút hoạt động

Cố định gốc là ký hiệu bắt đầu và cố định lá là các ký tự trong xâu vào, sử dụng các suy dẫn để ghép thành 1 cây.

Cố định gốc là ký hiệu bắt đầu và cố định lá là các ký tự trong xâu vào, sử dụng các suy dẫn để ghép thành 1 cây.

Cố định lá là các ký tự trong xâu vào, sử dụng các suy dẫn để tìm cây có gốc là ký hiệu bắt đầu.

Chương trình viết đúng luật cú pháp

Kiểm tra chương trình có theo luật cú pháp không

Chương trình được viết bởi ngôn ngữ lập trình

Luật cú pháp của ngôn ngữ lập trình

Chương trình viết đúng luật cú pháp

Kiểm tra chương trình có theo luật cú pháp không

Chương trình được viết bởi ngôn ngữ lập trình

Luật cú pháp của ngôn ngữ lập trình

Chương trình viết đúng luật cú pháp

Kiểm tra chương trình có theo luật cú pháp không

Chương trình được viết bởi ngôn ngữ lập trình

Luật cú pháp của ngôn ngữ lập trình

Chương trình viết đúng luật cú pháp

Kiểm tra chương trình có theo luật cú pháp không

Chương trình được viết bởi ngôn ngữ lập trình

Luật cú pháp của ngôn ngữ lập trình

Lấy ra khỏi Stack $$k$$ ký tự.

Lấy ra khỏi Stack $$k$$ ký tự, sau đó đẩy ký tự $$A$$ vào Stack.

Đẩy ký tự $$A$$ vào Stack.

Đã xét đến nút phải cùng trên cây suy dẫn.

Lá bên phải cùng trên cây suy dẫn so khớp với ký tự cuối cùng của xâu vào.

So khớp được hết các ký tự của xâu vào.

Đã sử dụng hết các sản xuất của văn phạm trong quá trình dựng cây suy dẫn.

Không có đệ quy trái

Không có $$\varepsilon$$ - sản xuất và suy dẫn dạng $$A \Rightarrow^{+} A$$

Mọi sản xuất có dạng $$A \rightarrow BC,\ A \rightarrow a$$

Không có đệ quy trái

Không có $$\varepsilon$$ - sản xuất và suy dẫn dạng $$A \Rightarrow^{+} A$$

Mọi sản xuất có dạng $$A \rightarrow BC,\ A \rightarrow a$$

Không có đệ quy trái

Không có $$\varepsilon$$ - sản xuất và suy dẫn dạng $$A \Rightarrow^{+} A$$

Mọi sản xuất có dạng $$A \rightarrow BC,\ A \rightarrow a$$

Cố định gốc là ký hiệu bắt đầu và cố định lá là các ký tự trong xâu vào, sử dụng các suy dẫn để ghép thành 1 cây.

Cố định gốc là ký hiệu bắt đầu, sử dụng các suy dẫn để xây dựng cây có tập lá trong xâu vào.

Cố định lá là các ký tự trong xâu vào, sử dụng các suy dẫn để tìm cây có gốc là ký hiệu bắt đầu.

Đã thử hết các cách thu gọn khác nhau.

Đã gạt hết các ký tự của xâu cần phân tích và trong Stack chỉ có ký tự bắt đầu $$S$$ .

Đã gạt hết các ký tự của xâu cần phân tích.

Đã sử dụng hết các sản xuất của văn phạm để thu gọn.

Đã gạt hết các ký tự của xâu vào.

Đã dùng hết các sản xuất của văn phạm.

Trong Stack chỉ có một ký tự bắt đầu S và xâu phân tích vẫn còn ký tự chưa gạt vào Stack.

Thay thế nút A bởi k nút có nhãn là X1, X2, ..., Xk.

Tạo ra k con cho nút A từ trái qua phải lần lượt là X1, X2, ..., Xk.

t

a

f

(

n

ε

t

a

o

f