Tạo hướng dẫn hiệu quả cho các mô hình ngôn ngữ lớn: Phần mở rộng cho phân tích cú pháp lặp

Bảng liên kết

• Tóm tắt và giới thiệu
• Lấy mẫu LLM và tạo hướng dẫn
• Xử lý và lập chỉ mục FSM lặp
• Phần mở rộng cho phân tích lặp
• Thảo luận, Tài liệu tham khảo và Lời cảm ơn

4. Phần mở rộng cho phân tích cú pháp lặp

Trong phần này, chúng tôi chuyển trọng tâm sang thế hệ chung được hướng dẫn bởi trình phân tích cú pháp và bắt đầu bằng phần hướng dẫn đơn giản về ngữ pháp giống Python được cung cấp dưới dạng CFG.

Hãy xem xét một từ vựng bao gồm các chuỗi như "d" và "ef" có thể được kết hợp để tạo ra cú pháp giống Python theo một CFG ẩn và giả sử rằng các chuỗi này được lấy mẫu và nối liên tục theo một quy trình như Thuật toán 1.

Hơn nữa, hãy xem xét ký hiệu đầu cuối DEF trong CFG tương ứng với chuỗi "def" và được cho bởi biểu thức chính quy tầm thường def. Ngoài ra, hãy xem xét ký hiệu TÊN được cung cấp bởi biểu thức chính quy [^\W\d]\w* (ví dụ: mã định danh Python). Chúng tôi muốn phân tích tuần tự các chuỗi được lấy mẫu từ từ vựng nói trên theo cách tuân thủ cú pháp Python.

Ví dụ: chuỗi sau đây có thể là một chuỗi như vậy: ["d", "ef", " f", "oo(", "):", " ", "pass"]. Tất cả các phần tử của chuỗi đều là các phần tử định nghĩa của từ vựng. Việc ghép chuỗi sẽ tạo ra "def foo(): pass", đây là một chuỗi mã thông báo hợp lệ xác định một hàm. Trong tình huống chúng ta đang xem xét, chúng ta sẽ quan sát tất cả các token cho đến một thời điểm nhất định và không biết gì về những token sau thời điểm đó.

Ví dụ, ở lần quan sát thứ ba trong chuỗi ví dụ, chúng ta có chuỗi nối "def f". Nếu chúng tôi phân tích/phân tích chuỗi này, cách tiếp cận truyền thống sẽ trả về chuỗi ký hiệu DEF NAME, xác định nhầm "f" là mã thông báo NAME hoàn chỉnh. Như chúng ta có thể thấy từ phần còn lại của chuỗi, mã thông báo NAME chính xác sẽ là "foo".

Nói chung, các chuỗi hợp lệ tiếp theo có thể được lấy mẫu từ từ vựng là các chuỗi

1. tiếp tục mở rộng/nâng cao TÊN hiện bắt đầu bằng "f" (như chuỗi đầy đủ trong ví dụ của chúng tôi) và/hoặc

   
   

2. bất cứ điều gì bắt đầu bằng "("–tức là ký hiệu LPAR có biểu thức chính quy (–và tiến hành chỉ định chữ ký đối số hợp lệ.

Trong trường hợp đầu tiên, "f" có thể được xem là ký hiệu NAME khớp một phần trong Python và–nhắc lại rằng biểu thức chính quy của nó là [^\W\d]\w*–chúng ta có thể nói rằng nó khớp với cả hai mẫu phụ (tức là [^\W\d] và \w*) trong biểu thức chính quy. Việc sử dụng FSM của chúng tôi chính thức hóa khái niệm về các mẫu phụ thông qua các trạng thái của FSM. Trong trường hợp này, biểu thức chính quy cho NAME có thể được biểu thị bằng FSM, M, với ba trạng thái: 0 (tức là trạng thái ban đầu q0), 1 (tức là [^\W\d]) và 2 (tức là \w*) , trong đó 1, 2 ∈ F.

Sử dụng Thuật toán 3, chúng ta sẽ thu được các chuỗi trạng thái FSM (0, 1), (1, 2), (2, 2) cho "f" và FSM, M, tương ứng với ký hiệu NAME. Các chuỗi FSM cho "f" cho chúng ta biết rằng việc so khớp có thể bắt đầu với chuỗi từ vựng này ở trạng thái 0, 1 hoặc 2 và nó có thể kết thúc ở trạng thái 1 hoặc 2.

Theo trường hợp 1. ở trên, việc phân tích cú pháp có thể được tiếp tục – đối với ký hiệu NAME – sau khi kết thúc trước đó ở trạng thái 1 hoặc 2. Theo trường hợp 2., chuỗi tiếp theo cũng có thể bắt đầu bằng hoặc chứa LPAR, ngụ ý rằng M sẽ kết thúc , có thể cho rằng 1 và 2 là trạng thái cuối cùng trong M mà tại đó quá trình phân tích cú pháp sẽ dừng sau khi đọc "f". Việc kết thúc M cũng chỉ ra rằng ký hiệu NAME đã được hoàn thành và việc chuyển đổi sang trạng thái chấp nhận LPAR đã được ngữ pháp cho phép.

Trong hình minh họa này, các chuỗi từ vựng hợp lệ tiếp theo ít nhất là "d", "ef", "pass", " ", "oo(", vì tất cả các chuỗi đó sẽ mở rộng TÊN khớp một phần và chuỗi cuối cùng cũng sẽ chuyển trạng thái phân tích cú pháp sang trạng thái đọc LPAR. Chuỗi còn lại, "):", từ tập hợp con từ vựng mà chúng ta đã xem xét sẽ dẫn đến một chuỗi có cú pháp không hợp lệ.

Liên quan đến cách tiếp cận lập chỉ mục FSM, điều này có nghĩa là Thuật toán 4 sẽ ánh xạ các trạng thái FSM 0, 1 và 2 tới tập hợp con "d", "ef", "pass", " ", "oo(" cho ký hiệu NAME và FSM của nó, M.

Hình minh họa này bỏ qua các trạng thái phân tích cú pháp cơ bản xác định ký hiệu ngữ pháp và chuyển tiếp nào được phép. Chúng tôi sử dụng automata đẩy xuống (PDA) như một phương tiện để mở rộng phương pháp FSM và giải quyết các chi tiết còn lại.

4.1 Công thức tự động đẩy xuống

Chúng tôi xác định automata đẩy xuống bằng cách sử dụng biểu diễn 6 bộ sau [Sipser, 1996, Định nghĩa 2.13]:

Để xây dựng phương pháp lập chỉ mục cho trình phân tích cú pháp dựa trên PDA, chúng ta cần sử dụng kết nối giữa các ký hiệu của CFG – thông qua bảng chữ cái của PDA tương ứng – và các bước đọc từ vựng và quét để tạo ra các ký hiệu được PDA đọc.

Cụ thể hơn, các trình phân tích cú pháp được hỗ trợ bởi các từ vựng và máy quét xác định các ký hiệu từ một chuỗi ký tự đầu vào, như chúng tôi đã minh họa ngầm trong Phần 4. Danh sách có thứ tự các ký hiệu đầu cuối có thể được xây dựng cho mỗi trạng thái phân tích cú pháp/PDA dựa trên các chuyển đổi ký hiệu và ngăn xếp được phép bởi bản đồ δ ở mỗi trạng thái. Điều này có nghĩa là chúng ta có thể xây dựng một FSM cho mỗi trạng thái phân tích cú pháp là sự kết hợp của mỗi FSM tương ứng với một ký hiệu đầu cuối được trạng thái đọc.

Sau đó, bước quét sẽ xác định một tập hợp các ký hiệu đầu cuối có thể có V ⊂ Σ cho các ký tự được đọc kể từ ký hiệu được xác định đầy đủ cuối cùng trong quá trình phân tích cú pháp. Ví dụ: ở trạng thái ban đầu q0 của PDA cho Pythonlike CFG trong Phần 4, việc quét và đọc từ vựng chuỗi "de" sẽ cho kết quả là V = {DEF, NAME}: tức là DEF cho bất kỳ chuỗi từ vựng nào hoàn thành chuỗi "def" –theo sau là một chuỗi không được NAME FSM đọc (ví dụ: "def ")– và NAME cho bất kỳ chuỗi nào khác được FSM của nó đọc (ví dụ: "mặc định"). Lưu ý rằng các bước của máy quét – và các bước lấy mẫu của LLM – cuối cùng sẽ giảm tập hợp V cho đến khi xác định được ký hiệu đầu cuối duy nhất v ∈ V.

Bằng cách áp dụng Thuật toán 3 cho mỗi chuỗi trong V bằng cách sử dụng các FSM kết hợp cho từng trạng thái phân tích cú pháp, chúng ta có thể xác định cấu hình trình phân tích cú pháp bao gồm các trạng thái PDA, trạng thái FSM tương ứng và các ký hiệu đầu cuối tiềm năng.

Bằng cách tương tự với các bước trong Thuật toán 3, chúng ta có thể sử dụng hình ảnh trước của bản đồ chuyển tiếp của PDA để xác định các giá trị ngăn xếp PDA sẽ đọc trạng thái PDA q ∈ Q và bộ ký hiệu đầu cuối V của cấu hình trình phân tích cú pháp:

Các giá trị ngăn xếp do bản đồ này cung cấp là cần thiết để tìm các đường dẫn – nếu có – thông qua PDA cho phép phân tích thành công, đầy đủ từng chuỗi trong V bắt đầu từ các cấu hình trình phân tích cú pháp có thể có của chúng. Đối với các kết hợp trạng thái và đầu cuối của trình phân tích cú pháp tương ứng với các hoạt động GIẢM của trình phân tích cú pháp LALR(1), các cấu hình trình phân tích cú pháp này sẽ không chỉ bao gồm các giá trị topof-stack trong Γ; chúng sẽ bao gồm các ngăn xếp con tương ứng với tất cả các tiền tố hợp lệ cho các hoạt động GIẢM GIÁ được đưa ra bởi một chuỗi từ vựng. Cuối cùng, mỗi cấu hình trình phân tích cú pháp cho phép phân tích cú pháp hoàn chỉnh của chuỗi từ vựng sẽ được thêm vào dưới dạng mục nhập trong chỉ mục cho PDA và trong trường hợp này, chỉ mục sẽ cần phải là cấu trúc dữ liệu trie để cho phép truy vấn đối với trình phân tích cú pháp. các giá trị ngăn xếp.