Mục lục
LỜI NÓI ĐẦU.1
Danh mục hình.5
Danh mục bảng.5
Chương 1. Mở đầu.7
1.1. Tổng quan vềvấn đềphân tích văn bản.7
1.2. Bài toán phân tích cú pháp.7
1.3. Nội dung khoá luận.8
Chương 2. Văn phạm phingữcảnh.9
2.1. Văn phạmvà ngôn ngữsinh bởi văn phạm.9
2.2. Văn phạmphi ngữcảnh.10
2.3. Biểu diễn cấu trúc câu.11
2.4. Phân tích từtrên xuống.14
2.5. Phân tích từdưới lên.15
2.6. Đánh giá hai phương pháp phân tích trên.20
2.7. Phương pháp phân tích tổng hợp.21
Chương 3. Các mạng chuyển.27
3.1. Văn phạmvà ôtômát.27
3.2. Các yếu tốcơsởcủa mạng chuyển đệquy.29
3.3. Tính thủtục của các RTN.33
3.4. Phân tích từtrên xuống cho mạng chuyển đệquy.34
Chương 4. Xây dựng văn phạm tiếng Việt.37
4.1. Xây dựng tập từloại tiếng Việt.37
4.2. Xây dựng văn phạm tiếng Việt.38
4.2.1. Danh ngữ.39
4.2.2. Động ngữ.41
4.2.3. Tính ngữ.44
4.2.4. Câu đơn hai thành phần.45
4.2.5. Văn phạm tiếng Việt.47
Chương 5. Cài đặt chương trình.49
5.1. Cấu trúc dữliệu.49
5.2. Cài đặt thuật toán.51
5.3. Thểhiện kết quảphân tích.52
5.4. Đánh giá kết quả.57
Phụlục.58
Bài toán tách từvựng tiếng Việt.58
1. Đặt bài toán.58
2. Các bước giải quyết.58
3. Đánh giá kết quả.60
Tài liệu tham khảo.63
63 trang |
Chia sẻ: netpro | Lượt xem: 1925 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Khóa luận Phân tích cú pháp tiếng Việt trong tin học, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ở vị trí 1.
4. Nếu không xảy ra các trường hợp trên thì trạng thái này không thoả, một trạng
thái lưu được lấy ra làm trạng thái hiện tại.
Bây giờ, sử dụng thuật toán này, ta xét lại quá trình phân tích câu The green
water evaporated. Nếu ta bắt đầu bằng ký hiệu S và vị trí 1, viết lại ký hiệu này,
ta được
Trạng thái hiện tại Trạng thái lưu Vị trí
(NP VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1
Viết lại NP theo bước 4 trong thuật toán, ta được
Trạng thái hiện tại Trạng thái lưu Vị trí
(ART NOUN [NP1] VP [S1]) 1
(ART ADJ NOUN [NP1] VP [S1]) 1
(ADJ NOUN [NP1] VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1
Chương 2. Văn phạm phi ngữ cảnh
Khoá luận tốt nghiệp 24
Ta kiểm tra thấy câu vào có một ART và một NOUN là đúng đắn. Sau thao tác
này trạng thái hiện tại là ([NP1] VP [S1]) tại vị trí 3. Theo bước 2 của thuật toán, cờ
dựng [NP1] được xử lý, bằng việc thêm một cấu trúc NP là [NP1] vào biểu đồ từ vị trí
1 tới vị trí 3. Khi đó, ta thu được trạng thái của quá trình phân tích và biểu đồ như sau:
Trạng thái hiện tại Trạng thái lưu Vị trí
(VP [S1]) 3
(ART ADJ NOUN [NP1] VP [S1]) 1
(ADJ NOUN [NP1] VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1
Hình 9. Biểu đồ sau khi phân tích cụm NP đầu tiên
Viết lại VP sẽ có trạng thái sau
Trạng thái hiện tại Trạng thái lưu Vị trí
(AUX VERB NP [VP4] [S1]) 3
(VERB NP [VP4] [S1]) 3
(ART ADJ NOUN [NP1] VP [S1]) 1
(ADJ NOUN [NP1] VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1
Ta không chấp nhận trạng thái hiện tại vì water không phải là một AUX. Trạng
thái lưu đầu tiên trở thành trạng thái hiện tại, trường hợp này mặc dù water là một
VERB, nhưng sau đó vì không có NP nào theo sau VERB nên trạng thái này cũng bị
loại. Trạng thái lưu tiếp theo được lấy ra làm trạng thái hiện tại. Câu cần phân tích có
ART (the) ở vị trí 1, ADJ (green) ở vị trí 2, và NOUN (water) ở vị trí 3 nên sinh
ra một NP thứ hai. Ta có tình huống và biểu đồ sau:
Trạng thái hiện tại Trạng thái lưu Vị trí
(VP [S1]) 4
Chương 2. Văn phạm phi ngữ cảnh
Khoá luận tốt nghiệp 25
(ADJ NOUN [NP1] VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1
Hình 10. Sau khi phân tích khả năng thứ hai của NP đầu tiên
Viết lại VP ở vị trí 4 trong trạng thái hiện tại sinh ra tình huống mới sau
Trạng thái hiện tại Trạng thái lưu Vị trí
(AUX VERB NP [VP3] [S1]) 4
(VERB NP [VP3] [S1]) 4
(ADJ NOUN [NP1] VP [S1]) 1
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1
Vì không có AUX ở vị trí 4 nên trạng thái hiện tại không được chấp nhận. Trạng
thái lưu thứ nhất cũng không thoả mãn, vì tuy có một VERB ở vị trí 4 nhưng sau đó
lại không có NP. Trạng thái tiếp theo (ADJ NOUN [NP1] VP [S1]) cũng bị loại do
the không phải là một ADJ. Chỉ còn lại hai trạng thái và biểu đồ như sau:
Trạng thái hiện tại Trạng thái lưu Vị trí
(NP AUX VERB [S1]) 1
(NP VERB [S1]) 1
Hình 11. Sau khi tìm kiếm một S theo quy tắc 1 bị thất bại
Bây giờ ta đã kết thúc mọi phân tích có thể từ việc bắt đầu bằng S, viết lại nó theo
quy tắc 1. Bây giờ là lúc những thành phần mà biểu đồ đã lưu lại trước đó được mang
Chương 2. Văn phạm phi ngữ cảnh
Khoá luận tốt nghiệp 26
ra để sử dụng. Thay vì áp dụng các quy tắc để viết lại NP tại vị trí 1, trình phân tích sử
dụng hai NP đã có trên biểu đồ, sinh ra
Trạng thái hiện tại Trạng thái lưu Vị trí
(AUX VERB [S1]) 3
(AUX VERB [S1]) 4
(NP VERB [S1]) 1
Trạng thái hiện tại bị loại, do không có AUX nào tại vị trí 3. Tương tự, trạng thái
lưu đầu tiên cũng không được chấp nhận, bởi không có AUX nào ở vị trí 4 cả. Trạng
thái (NP VERB [S1]) là trạng thái cho phân tích đúng đắn duy nhất. Một lần nữa,
dùng 2 NP đã có trên biểu đồ, sinh ra hai trạng thái sau:
Trạng thái hiện tại Trạng thái lưu Vị trí
(VERB [S1]) 3
(VERB [S1]) 4
Trạng thái hiện tại sinh ra một cấu trúc S từ vị trí 1 đến vị trí 4 nhưng lại bỏ sót
evaporated. Trạng thái lưu còn lại sinh ra phân tích mong muốn, câu cần phân tích
có cấu trúc như sau:
Hình 12. Cấu trúc của câu cần phân tích
Rõ ràng, chiến lược phân tích kết hợp từ trên xuống và từ dưới lên ưu việt hơn cả
hai phương pháp phân tích đơn thuần nói trên; so với cách phân tích từ trên xuống thì
cách phân tích này chỉ có một hạn chế là biểu đồ cần nhiều ô nhớ hơn. Nhưng trong
phần lớn các trường hợp, so với lợi thế về thời gian phân tích thì phần ô nhớ mất thêm
này là không đáng kể.
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp
Chương 3. Các mạng chuyển
Ngoài các hệ văn phạm, các mô hình mạng chuyển, nhất là các mạng chuyển đệ
quy cũng được sử dụng rộng rãi để mô tả các cấu trúc cú pháp của ngôn ngữ tự nhiên.
Các mạng chuyển có cơ sở là các máy trừu tượng, chúng được coi là những thiết bị
nhận dạng văn phạm. Chính vì vậy, trước khi đi vào phần trình bày về các mạng
chuyển, em trình bày khái quát về các máy trừu tượng, từ đơn giản nhất tới tổng quát
nhất.
3.1. Văn phạm và ôtômát
Văn phạm một mặt có thể coi là những định nghĩa cho các câu của một ngôn ngữ,
mặt khác còn có thể coi là sự mô tả của một máy trừu tượng có khả năng đoán nhận
hoặc sinh những xâu nằm trong ngôn ngữ đó. Những máy này được gọi (một cách
trừu tượng) là các ôtômát, và độ phức tạp của những máy này tương ứng với độ phức
tạp của các quy tắc sinh trong văn phạm.
Mỗi máy có thể xem là một tập các trạng thái, một thiết bị vào có khả năng truy
nhập mỗi lần một ký hiệu vào, và một đơn vị điều khiển có khả năng kiểm tra và đọc
đầu vào, chuyển máy sang trạng thái khác. Ngoài ra, những máy này có thể có bộ nhớ,
được đơn vị điều khiển truy nhập để lưu giữ hoặc kiểm tra các ký hiệu. Yếu tố quyết
định năng lực tính toán của máy là độ phức tạp của bộ nhớ và những thao tác trên bộ
nhớ.
Những ôtômát đơn giản nhất là các máy hữu hạn trạng thái hay các ôtômát hữu
hạn trạng thái (Finite State Automata -- FSA), các ngôn ngữ mà chúng đoán nhận gọi
là các ngôn ngữ chính quy. Ngôn ngữ chính quy có đầy đủ các tính chất của ngôn ngữ
phi ngữ cảnh và do đó luôn có thể đoán nhận được bằng một ôtômát với số trạng thái
hữu hạn. Các máy hữu hạn trạng thái không có bộ nhớ trong, nên mọi thao tác hoàn
toàn được quyết định bởi ký hiệu hiện đang được đọc và trạng thái hiện tại của máy.
Để minh hoạ sự vận hành của các máy nói trên, ta xét văn phạm đơn giản sau:
S → aB
B → bB
B → c
Văn phạm này sinh ra ngôn ngữ chính quy abnc. Ôtômát tương đương với nó thường
được biểu diễn bằng một sơ đồ trạng thái như hình vẽ sau:
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp 28
trong đó các nút biểu diễn các trạng thái và các cung biểu diễn các bước chuyển. Nút
vuông chỉ rằng đó là trạng thái kết. Với ôtômát này, việc chuyển từ những quy tắc
sinh sang sơ đồ trạng thái là: ký hiệu không kết chuyển thành trạng thái, ký hiệu kết
chuyển thành bước chuyển.
Sự hoạt động của ôtômát này như sau: việc tính toán bắt đầu từ một trạng thái
được xác định trước gọi là trạng thái khởi đầu, ở đây là S; ký hiệu đầu tiên của xâu
vào được kiểm tra xem có cung chuyển nào khớp với nó hay không; nếu có thì máy
theo cung này chuyển tới trạng thái kế tiếp và tiêu thụ ký hiệu đó, đọc tiếp ký hiệu
đứng sau. Quá trình này được tiếp tục cho tới khi máy bị dừng, ví dụ khi không cung
chuyển nào là khớp nữa. Nếu máy dừng tại một trạng thái kết và xâu vào đã được tiêu
thụ thì ta nói xâu đó đã được đoán nhận.
Nếu ta thêm bộ nhớ hoạt động theo nguyên lý của danh sách vào sau ra trước
(LIFO) vào ôtômát (ví dụ một ngăn xếp đẩy xuống), cùng với một số quy tắc điều
khiển thì FSA sẽ chuyển thành ôtômát đẩy xuống (Push Down Automaton -- PDA).
Các PDA chỉ có thể đoán nhận những ngôn ngữ phi ngữ cảnh.
Nếu bỏ đi hạn chế về tổ chức ngăn xếp trong bộ nhớ trong, chỉ áp dụng ràng buộc
quy định kích thước bộ nhớ là hàm tuyến tính theo độ dài của xâu vào, thì ta tạo ra
một ôtômát mạnh hơn gọi là ôtômát bị chặn tuyến tính (Linear Bounded Automaton --
LBA). Nếu cần, ta có thể tổ chức bộ nhớ trong sao cho một phần bộ nhớ được tổ chức
như một ngăn xếp, phần còn lại là bộ nhớ truy nhập ngẫu nhiên, khi đó sẽ giữ lại được
mối liên hệ về mặt cấu trúc với lớp các PDA yếu hơn. Các LBA có khả năng đoán
nhận một lớp rất tổng quát của ngôn ngữ, được định nghĩa bởi các văn phạm tuyến
tính theo chiều dài, các ngôn ngữ này bao gồm cả các thành phần cấu trúc ngữ pháp
cảm ngữ cảnh thường gặp trong ngôn ngữ.
Sau cùng, nếu ta bỏ đi ràng buộc cuối cùng đối với bộ nhớ trong, cho phép nó có
kích thước không hạn chế, khi đó ta được lớp ôtômát tổng quát nhất, gọi là các máy
Turing (Turing Machines -- TMs). Văn phạm tương đương với nó là hệ thống viết lại
không hạn chế, trong đó, các quy tắc sinh được phép viết lại bất kỳ cái gì cũng thành
một thứ bất kỳ. Các máy Turing là sự trừu tượng tương tự của các máy tính tuần tự đa
nhiệm nguyên thuỷ.
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp 29
Một trong những vấn đề đầu tiên của lý thuyết các ôtômát là câu hỏi về tính quyết
định, được diễn tả hình thức là: có hay không một tiên nghiệm cho phép biết được một
lớp các tính toán cho trước có kết thúc trong một thời gian hữu hạn hay không. Cụ thể
là, bài toán đoán nhận một xâu không thuộc ngôn ngữ tương ứng với một ôtômát đã
cho nói chung không thể quyết định được bởi các TM. Câu hỏi này, về nguyên tắc, là
có thể trả lời được đối với các lớp ôtômát yếu hơn.
3.2. Các yếu tố cơ sở của mạng chuyển đệ quy
Mạng chuyển đệ quy (recursive transition networks -- RTNs) được Wood đưa ra
lần đầu tiên vào năm 1970, là một thiết bị nhận dạng các văn phạm phi ngữ cảnh.
Xét văn phạm đơn giản sau
1. (a) S → NP (Aux) V (NP) PP*
1. (b) S → Aux NP V (NP) PP*
2. NP → (Det) (Quant) Adj* N* N PP*
3. PP → Prep NP
Văn phạm này định nghĩa một ngôn ngữ phi ngữ cảnh trên bảng chữ cái {Aux, V, Det,
Quant, Adj, N, Prep}. Ở đây có một mở rộng so với thông thường là các ngoặc tròn,
chứa các phần tử tuỳ chọn, và dấu hoa thị dùng để chỉ ký hiệu đi kèm với nó có thể
không có hoặc xuất hiện nhiều hơn một lần.
Các vế phải của các quy tắc cũng có thể được xem như định nghĩa của các biểu
thức của các ngôn ngữ chính quy, hay các biểu thức chính quy, tương ứng trên các
bảng chữ cái {NP, Aux, V, PP} đối với quy tắc 1, {Det, Quant, Adj, N, PP} đối với
quy tắc 2 và {Prep, PP} đối với quy tắc 3 -- do đó mỗi biểu thức có thể được diễn tả
bằng một ôtômát hữu hạn trạng thái tương đương. Ví dụ, sơ đồ trạng thái của các
ôtômát tương ứng với các quy tắc 1.(a) và 1.(b) là:
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp 30
trong đó ký hiệu JUMP chỉ các bước chuyển không có điều kiện không tiêu thụ ký
hiệu.
Nhìn vào biểu diễn này, ta thấy ngay rằng biểu diễn bước chuyển của các trạng
thái cho phép ta ghép các vế phải của 1.(a) và 1.(b) thành một sơ đồ duy nhất, vì hai
quy tắc là giống nhau kể từ ký hiệu V trở đi. Điều này sẽ làm việc mô tả các thông tin
trong hai quy tắc ngắn gọn hơn so với hình thức viết lại. Ghép hai sơ đồ A1(a) và
A1(b) ta sẽ được ba sơ đồ bước chuyển tương ứng với bốn quy tắc 1-3 như sau:
Ở đây, ta gặp vấn đề với các cung chuyển NP trong A1 và A3 và PP trong A2. Để
biểu diễn đúng theo máy hữu hạn trạng thái thì ta phải coi chúng như những ký hiệu
kết, trong khi rõ ràng chúng là các ký hiệu không kết trong văn phạm ban đầu. Vậy
nếu chúng không kết thì làm thế nào để đoán nhận được bởi các ôtômát hữu hạn trạng
thái tương ứng?
Cách giải thích hiển nhiên ở đây là ta cần có cách nhìn khác đối với những cung
"không kết" này, ta coi ba ôtômát A1-A3 là một hệ. Bây giờ ta không đòi hỏi A1 phải
đoán nhận ký hiệu NP, mà để nó tạm thời chuyển sang A2, và quay lại với thông tin
NP đó có thể đoán nhận được tại vị trí vào hiện tại hay không. Tương tự, A2 phải
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp 31
chuyển trách nhiệm đoán nhận PP cho A3, đến lượt mình, A3 lại gọi A2 để đoán nhận
NP. Rõ ràng là một FSA đơn thuần không thể đáp ứng được tiến trình đệ quy này, bởi
nó không có cách nào để ghi nhớ đã xuất phát từ đâu và làm thế nào để quay lại đó sau
khi kết thúc một quá trình trung gian. Tuy vậy, ta thấy rằng nếu ta dùng thêm một
ngăn xếp để chuyển các FSA này thành một PDA thì thiết bị này hoàn toàn có khả
năng quản lý mọi thao tác phụ gồm ghi nhớ và lấy lại các trạng thái.
Khi điều khiển được chuyển sang một quá trình trung gian thì trạng thái hiện tại
của máy được đẩy vào ngăn xếp, để khi kết thúc quá trình này máy sẽ quay lại đúng
trạng thái đó. Trong thuật ngữ của RTN, việc chuyển điều khiển sang một trạng thái,
giả sử NP, được gọi là PUSH NP. Khi ra khỏi trạng thái kết ta dùng một cung có nhãn
POP để chỉ rằng khi quá trình kết thúc, máy quay lại trạng thái được lưu trong ngăn
xếp.
Ta cũng có thể sử dụng RTN để biểu diễn từ điển, thay vì dùng tập các quy tắc
viết lại dạng
Det → 'a'
Det → 'the'
Det → 'some'
ta có thể sử dụng dạng chuyển như sau và gắn kết quả vào mạng văn phạm tương tự
như A1-A3.
Để tiện cho việc trình bày, ta có thể định nghĩa tập các hàm mà cung chuyển có
thể gọi. Các hàm tìm kiếm trong từ điển hay sử dụng nhất là CAT, hàm này kiểm tra
kiểu từ loại đã định nghĩa trước trong từ điển của từ hiện tại đang đọc vào. Các hàm
khác được tóm lược trong bảng sau:
Các hàm Ví dụ Cách dùng
CAT noun đi qua được chỉ nếu từ loại của từ hiện tại có cùng tên
WRD of đi qua được chỉ nếu từ hiện tại chính là từ này
PUSH NP đẩy tới một mạng khác
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp 32
JUMP jump luôn có thể đi qua được
POP pop chỉ việc đi qua được toàn bộ mạng chuyển
Để kết thúc mục này, ta tóm tắt sự giống và khác nhau giữa mạng chuyển RTN và
các ôtômát hữu hạn trạng thái FSA và ôtômát đẩy xuống PDA như sau:
Giống nhau:
¾ RTN cũng như FSA và PDA đều có thể đoán nhận các câu sinh bởi các văn
phạm cấu trúc câu.
¾ RTN tương đương với PDA về khả năng đoán nhận ngôn ngữ sinh bởi văn
phạm phi ngữ cảnh (CFG) của Chomsky.
¾ Hoạt động của RTN cũng như FSA và PDA đều có thể được biểu diễn
bằng các mạng chuyển.
Khác nhau:
¾ Các cung và các đỉnh (trạng thái): Trong khi các trạng thái trong mạng
chuyển của FSA có nhãn là các từ không kết thúc của văn phạm tương
đương với ôtômat, các cung có nhãn là các từ cuối (cũng như vậy với
PDA, trừ các cung rỗng và cung kết thúc pop), thì các cung của RTN có
nhãn là các từ không kết thúc (trừ một số cung đặc biệt cũng có nhãn là từ
cuối) của văn phạm tương đương, với các trạng thái được đánh dấu tuỳ ý.
¾ Các mạng con: Các mạng chuyển của FSA và PDA là các mạng đầy đủ,
còn mạng chuyển của RTN thì được xử lý như là một tập các mạng con.
Với mỗi ký hiệu có xuất hiện ở vế trái trong các qui tắc sinh của văn phạm
tương đương được biểu diễn bằng một mạng con.
¾ RTN không đơn định, quá trình đoán nhận do vậy phải dùng phương pháp
quay lui.
¾ Do đặc điểm của mô hình RTN là một tập các mạng chuyển con, việc đoán
nhận câu trong RTN phải theo phương pháp xử lý từ trên xuống (xuất phát
từ mạng con S – tức là mạng biểu diễn các quy tắc sinh có vế trái là tiên
đề) và xử lý theo chiều sâu trước (phải đi qua từng mạng con trước khi
chuyển sang cung tiếp theo).
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp 33
3.3. Tính thủ tục của các RTN
Phương pháp biểu diễn nêu trên có mức độ trừu tượng tương đương với một hệ
các quy tắc viết lại của văn phạm phi ngữ cảnh, theo nghĩa mọi quy tắc của văn phạm
phi ngữ cảnh đều có thể chuyển thành một RTN tương đương. Tuy nhiên, cách biểu
diễn bằng RTN có một đặc điểm quan trọng mà trong các hệ quy tắc viết lại không có,
đó là các tiến trình (process). Khi ta sử dụng một văn phạm để xây dựng thủ tục đoán
nhận một ngôn ngữ, thì các quy tắc viết lại chỉ ra cần làm cái gì; còn ôtômát nằm
trong RTN lại mô tả làm như thế nào.
Để so sánh, giả sử ta dùng một hệ sản xuất để đoán nhận một ngôn ngữ phi ngữ
cảnh và dùng một RTN để đoán nhận cũng ngôn ngữ đó. Khi thiết kế hệ sản xuất, ta tự
do quyết định các câu hỏi như áp dụng quy tắc nào tiếp theo, phần dữ liệu nào sẽ xem
xét tiếp theo, và thực hiện các thao tác "viết lại" trên dữ liệu đó như thế nào. Với
RTN, quyền lựa chọn các quyết định tương tự như trên không thuộc về người thiết kế
nữa, bởi vì chúng đã bị ẩn trong biểu diễn ngữ nghĩa của văn phạm. Hình thức biểu
diễn bằng RTN thể hiện nhiều đặc tính của các ngôn ngữ lập trình thủ tục thường gặp,
đặc biệt khi nó được dịch thành biểu diễn tuyến tính cho đầu vào của máy tính - lệnh
nhảy goto có và không có điều kiện (các bước chuyển trạng thái), các nhãn lệnh (các
tên trạng thái), và các lời gọi thủ tục (PUSH và POP).
Các điều khiển thủ tục có một đặc điểm quan trọng không bị ẩn trong ký hiệu, đó
là cách trình thông dịch thực hiện khi nó gặp một trạng thái có nhiều cung chuyển tiếp
theo. Chế độ bình thường là lần lượt đi theo các cung chuyển, bắt đầu từ cung chuyển
đầu tiên, thực hiện từ trên xuống và ưu tiên chiều sâu, đi theo các đường dẫn xa nhất
có thể và chấp nhận đường đi đầu tiên đến được một trạng thái kết với một xâu vào
rỗng và ngăn xếp rỗng.
Ở đây có sự khác nhau cơ bản so với cách tiếp cận hệ sản xuất, với hệ sản xuất,
dạng viết lại của các quy tắc tự nó không giả định trước bất kỳ một tiến trình nào.
Người xây dựng mạng chuyển RTN cần suy nghĩ theo tiến trình nhận dạng từ trên
xuống, từ trái sang phải.
Như vậy, hình thức RTN cho phép ta dễ dàng theo dõi tiến trình phân tích. Các
RTN mô tả tiến trình, còn CFG thì không. Do mỗi chương trình máy tính là một sự
mô tả tiến trình nên các RTN rất có giá trị khi được dùng để viết chương trình phân
tích. Trên thực tế cũng có nhiều trình phân tích được điều khiển bởi các quy tắc của
văn phạm. Sự khác nhau lớn nhất của hai hình thức này là vào thời điểm chạy chương
trình, trình phân tích RTN "biết được" tại mỗi bước đã có sẵn những lựa chọn nào,
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp 34
còn các trình phân tích dựa trên văn phạm phi ngữ cảnh phải tìm trong dãy các quy tắc
những quy tắc nào là có thể áp dụng được.
3.4. Phân tích từ trên xuống cho mạng chuyển đệ quy
Trạng thái phân tích tại một thời điểm nào đó được biểu diễn như sau:
¾ Vị trí hiện tại. Lưu lại phần nào của câu đã được phân tích rồi
¾ Nút hiện tại. Nút ta đang dừng lại để phân tích
¾ Ðiểm quay lại (trở về). Ta đang nằm trong một mạng (B) bởi lời gọi từ
một nút nào đó của mạng (A). Khi đó điểm trở về là nút của mạng A, để
khi quay ra ta lại tiếp tục quá trình phân tích.
Trước hết, ta xét thuật toán đơn giản tìm kiếm trên một mạng chuyển đệ quy. Giả
sử rằng nếu ta có thể đi qua một cung nào đó thì cung đó sẽ là đúng đắn trong phân
tích cuối cùng; và giả sử ta chỉ xét các cung cat, push, và pop. Sau đó ta sẽ sửa đổi
thuật toán này để tìm tất cả các đường đi bằng kỹ thuật quay lui.
Giả sử ta đang đứng ở một nút trung gian nào đó và biết 3 thông tin đã qua. Ta thử
đi theo một cung để ra khỏi nút hiện tại. Có các trường hợp sau xảy ra
¾ Nếu cung này là cung cat và từ kế tiếp trong câu thuộc vào lớp từ loại đó,
thì
- cập nhật lại vị trí hiện tại là từ kế tiếp;
- cập nhật lại nút hiện tại là đích của cung này;
¾ Nếu cung này là cung push đẩy tới một mạng N thì
- đưa đích của cung này vào danh sách các điểm trở về;
- cập nhật lại nút hiện tại là nút bắt đầu của mạng N;
¾ Nếu cung này là cung pop và danh sách các điểm trở về chưa rỗng thì cập
nhật nút hiện tại là điểm đầu tiên trong danh sách này;
¾ Nếu cung này là cung pop, danh sách các điểm trở về là rỗng và không
còn từ nào cả thì việc phân tích là thành công;
Ðể minh hoạ, ta xét văn phạm sau (Hình 13),
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp 35
Hình 13. Mạng chuyển đệ quy làm ví dụ trong phân tích từ trên xuống
cùng với bộ từ vựng
ART the, a
NUMBER one
PRONOUN one
ADJ wild, green
NOUN dogs, man, saw, green
VERB cried, saw, broke, faded, man
Khi đó, câu
1 The 2 wild 3 dogs 4 cried 5
sẽ được phân tích như trên Bảng 3.
Bước Nốt hiện tại Vị trí hiện tại Ðiểm trả về Cung được đi
1. S 1 nil S/1
2. NP 1 {S1} NP/1
3. NP1 2 {S1} NP1/1
4. NP1 3 {S1} NP1/2
5. NP2 4 {S1} NP2/1
6. S1 4 nil S1/1
7. S2 5 nil N2/1
Bảng 3. Quá trình phân tích từ trên xuống
Chương 3. Các mạng chuyển
Khoá luận tốt nghiệp 36
Câu The green faded sẽ không thể phân tích tích được bằng văn phạm này,
bởi đầu tiên trình phân tích coi green là một tính từ, cho nên sau đó nó không tìm
được một danh từ.
Xét câu
1 One 2 saw 3 the 4 man 5,
Ban đầu, trình phân tích thử phân tích câu với cụm danh từ one saw, nhưng sau
đó thất bại khi tìm một động từ tiếp theo, nó quay lại và tìm ra cách phân tích thành
công với cụm danh từ là one. Quá trình phân tích như trên Bảng 4.
Bước Trạng thái hiện tại Ði theo cung Các trạng thái được
lưu lại
1. (S,1,nil) S/1 nil
2. (NP,1,{S1}) NP/2 (và NP/3 để lưu) nil
3. (NP1,2,{S1}) NP1/2 {NP2,2, {S1}}
4. (NP2,3,{S1}) NP2/1 {NP2,2, {S1}}
5. (S1,3,{nil}) không thể đi theo
cung nào cả
{NP2, 2, {S1}}
6. (NP2,2,{S1}) NP2/1 nil
7. (S1,2,nil) S1/1 nil
8. (S2,3,nil) S2/2 nil
9. (NP,3,{S2}) NP/1 nil
10. (NP1,4,{S2}) NP1/2 nil
11. (NP2,5,{S2}) NP2/1 nil
12. (S2,5,nil) S2/1 nil
13. phân tích thành công nil
Bảng 4. Phân tích từ trên xuống kết hợp quay lui cho mạng chuyển đệ quy
Trong bước 2, có hai cung ra khỏi nút NP có thể chấp nhận one. Cung NP/2 coi
one là một số (number) và sinh ra nút kế tiếp; đồng thời one cũng là một đại từ
(pronoun), nên trình phân tích lưu lại khả năng đi qua cung NP/3 để đến nút NP2, như
thế trình phân tích lưu trạng thái (NP2,2,{S1}). Tại bước 6, nó dùng lại trạng thái
này, bởi nhận thấy rằng không có cung nào đi ra khỏi S1 chấp nhận từ the.
Với những ví dụ phức tạp hơn, sẽ có cả một danh sách các điểm được lưu. Tuỳ
theo danh sách này được tổ chức theo thứ tự ra sao, trình phân tích sẽ sinh ra những
thứ tự phân tích khác nhau.
Chương 4. Xây dựng văn phạm tiếng Việt
Khoá luận tốt nghiệp
Chương 4. Xây dựng văn phạm tiếng Việt
4.1. Xây dựng tập từ loại tiếng Việt
Ngữ pháp tiếng Việt hết sức phức tạp. Việc xây dựng một bộ văn phạm hoàn
chỉnh cho tiếng Việt là rất khó khăn. Ngay cả về vấn đề từ loại của tiếng Việt hiện nay
vẫn còn chưa hoàn toàn thống nhất. Sau khi tham khảo nhiều tài liệu chuyên ngành cơ
sở ngôn ngữ học và tiếng Việt, nhóm nghiên cứu đã quyết định sử dụng trước mắt
cách phân loại từ tiếng Việt theo cuốn Ngữ Pháp tiếng Việt (nhà xuất bản KHXH,
1983) và đề nghị bộ nhãn chi tiết như danh sách dưới đây:
1. Danh từ (N)
a. Danh từ riêng Np
b. Danh từ đơn thể Nc
c. Danh từ tổng thể Ng
d. Danh từ loại thể Nt
e. Danh từ đơn vị Nu
f. Danh từ trừu tượng Na
g. Danh từ số lượng Nn
h. Danh từ vị trí Nl
2. Động từ (V)
a. Động từ ngoại động Vt
b. Động từ nội động Vit
c. Động từ cảm nghĩ Vim
d. Động từ phương hướng Vo
e. Động từ tồn tại Vs
f. Động từ biến hoá Vb
g. Động từ ý chí Vv
h. Động từ tiếp thụ Va
i. Động từ so sánh Vc
j. Động từ “là” Vla
3. Tính từ (A)
a. Tính từ hàm chất Aa
b. Tính từ hàm lượng Am
4. Đại từ (P)
a. Đại từ xưng hô Pp
b. Đại từ không gian, thời gian Pd
c. Đại từ số lượng Pn
d. Đại từ hoạt động, tính chất Pa
e. Đại từ nghi vấn Pi
Chương 4. Xây dựng văn phạm tiếng Việt
Khoá luận tốt nghiệp 38
5. Phụ từ (J)
a. Phụ từ thời gian Jt
b. Phụ từ mức độ Jd
c. Phụ từ so sánh Jr
d. Phụ từ khẳng định, phủ địnhJa
e. Phụ từ mệnh lệnh Ji
6. Kết từ (C)
a. Kết từ chính phụ Cm
b. Kết từ liên hợp Cc
7. Trợ từ M
8. Cảm từ I
4.2. Xây dựng văn phạm tiếng Việt
Mục tiêu của ta là xây dựng được một văn phạm vừa đủ để giải quyết bài toán
phân tích. Nếu văn phạm quá rộng thì vừa không cần thiết vừa làm phức tạp thêm vấn
đề. Nhưng nếu văn phạm quá hẹp thì không thể bao quát được hết cấu trúc của các câu
cần phân tích, do đó không đủ mạnh để giải quyết bài toán.
Khi xây dựng câu tiếng Việt, ta triển khai xây dựng theo từng bước từ → ngữ →
câu. Ngữ pháp truyền thống chia ra các loại ngữ sau đây:
Tên ngữ Nhãn Đặc trưng
Danh ngữ (noun phrase) NP Danh từ làm trung tâm
Động ngữ (verb phrase) VP Động từ làm trung tâm
Tính ngữ (adjectival phrase) AP Tính từ làm trung tâm
Giới ngữ (prepositional phrase) PP Giới từ làm trung tâm
Nói chung, mỗi ngữ đều có ba bộ phận: phần phụ trước đứng trước thành tố chính,
phần trung tâm chứa thành tố chính và phần phụ sau đứng sau thành tố chính.
Thành tố chính của ngữ giữ vai trò quan trọng về mặt ngữ pháp đối với ngữ, cần
thiết về mặt tổ chức của ngữ, sự có mặt của nó là bắt buộc, không thể lược bỏ. Thành
tố chính đại diện cho toàn bộ ngữ trong mối liên hệ với các yếu tố khác nằm ngoài
ngữ, chi phối các thành tố khác và quyết định chức vụ ngữ pháp của tất cả các thành tố
phụ có liên quan.
Xét về vị trí, thành tố phụ của ngữ đứng trước hay sau phần trung tâm. Trong
cùng một loại ngữ, những từ có khả năng khi thì làm thành tố phụ sau, khi thì làm
thành tố phụ trước không nhiều. Xét về từ loại, thành tố phụ có thể
Các file đính kèm theo tài liệu này:
- Phân tích cú pháp tiếng Việt trong tin học.pdf