Làm thế nào để xác định xem một ngôn ngữ là LL (1)?

Question

Tôi có ngữ pháp và tôi có thể kiểm tra xem có phải là LL (1) hay không. Tuy nhiên, có cách nào để kiểm tra xem ngôn ngữ được tạo ra bởi ngữ pháp là LL (1)? Và những gì chính xác là sự khác biệt giữa LL (1) ngữ pháp và LL (1) ngôn ngữ?

Answer 1

Bất kỳ ngữ pháp nào là LL (1) định nghĩa ngôn ngữ LL (1). Theo định nghĩa, một ngôn ngữ là LL (1) nếu có một số ngữ pháp tạo ra nó là LL (1), do đó thực tế là bạn có một LL (1) ngữ pháp cho ngôn ngữ tự động có nghĩa là ngôn ngữ là LL (1) .

Để xây dựng, một ngôn ngữ là một bộ chuỗi và ngữ pháp cho ngôn ngữ đó là phương tiện mô tả ngôn ngữ đó. Một số ngôn ngữ có LL (1) ngữ pháp trong khi các ngôn ngữ khác thì không. Tuy nhiên, thực tế là ngữ pháp không phải là LL (1) không có nghĩa là ngôn ngữ mô tả không phải là ngôn ngữ. Ví dụ: xem xét ngữ pháp này:

A -> ab | ac 

Ngữ pháp này không phải là LL (1) vì nó chứa xung đột FIRST/FIRST khi cố gắng dự đoán sản xuất cho A khi nhìn thấy thiết bị đầu cuối a. Tuy nhiên, nó mô tả một (1) ngôn ngữ LL, vì ngôn ngữ cũng được mô tả bằng ngữ pháp

A -> aX 
X -> b | c 

Vì vậy, các ngôn ngữ được tạo ra bởi những văn phạm (trong đó chỉ chứa ab và ac) thực sự là LL (1).

Xác định xem ngôn ngữ được mô tả bằng ngữ pháp tùy ý là LL (1) khó hơn và theo hiểu biết của tôi, cách duy nhất để làm điều đó là hiển thị rõ ràng ngữ pháp LL (1) cho ngôn ngữ được tạo bởi ngữ pháp ban đầu (khó hiểu) hoặc toán học chứng minh rằng không có ngữ pháp nào tồn tại.

Hy vọng điều này sẽ hữu ích!