Thực hiện phân tích cú pháp

Question

Xin chào Tôi đang cố triển khai trình phân tích cú pháp cho một ngôn ngữ đơn giản với ngữ pháp như thế này.

program ::= "program" declarations "begin" statements "end" 
declaration ::= "var" ident "as" type 
type ::= "string" | "int" 

Tôi đã thực hiện hai bước đầu tiên, làm cách nào để viết ngữ pháp loại?

program(prog(DECLS, STATS)) --> 
[ 'program' ], declarations(DECLS), 
[ 'begin' ], statements(STATS), [ 'end' ]. 

declaration(decl(IDENT, TYPE)) --> 
[ 'var' ], ident(IDENT), [ 'as' ], type(TYPE). 

Answer 1

type(string) --> ['string']. 
type(int) --> ['int']. 

(thực ' không bắt buộc)

Bạn có thể sử dụng | hoặc ; nhưng điều đó sẽ làm phức tạp theo cách bạn trả về kiểu bạn tìm thấy.

Answer 2

Ngữ pháp của bạn có thể bị gạch dưới. Trong thực tế, bạn không xác định cách các từ khóa được tách biệt với các mã thông báo khác như số nhận dạng. Có các ngôn ngữ lập trình, nơi bạn không cần phải tách các từ khóa khỏi mã nhận dạng. Và có những ngôn ngữ lập trình khác, nơi cần một số ký tự trắng hoặc bố cục.

Trong trường hợp của bạn, có phải "varaasint" là khai báo hợp lệ không? Ngữ pháp của bạn gợi ý nó. Hay bạn phải viết "var a as int".

Bạn có thể muốn xem xét this answer for more.

Answer 3

Bạn bỏ lỡ quy tắc statements!

Dù sao, quy tắc DCG chỉ là đường cú pháp đơn giản trên Prolog, sau đó bạn có thể sử dụng bất kỳ tính năng Prolog nào bạn thích. Nếu bạn cần giữ cho ngữ pháp gọn gàng:

type(type(T)) --> [T], {memberchk(T, [int, string])}. 

Niềng răng cho phép trộn chung Prolog với các quy tắc ngữ pháp.

Như @false đã lưu ý, ngữ pháp của bạn chỉ hữu ích nếu bạn có mã thông báo, chia tách dữ liệu nhập của bạn và xóa các khoảng trắng. Hoặc bạn có thể xử lý trực tiếp hơn bằng cách sử dụng lược đồ này (hãy cẩn thận, mã chưa được kiểm tra):

program(prog(DECLS, STATS)) --> 
    s, "program", s, declarations(DECLS), 
    s, "begin", s, statements(STATS), s, "end", s. 

declaration(decl(IDENT, TYPE)) --> 
    "var", s, ident(IDENT), s, "as", s, type(TYPE). 

declarations([D|Ds]) --> declaration(D), declarations(Ds). 
declarations([]) --> []. 

type(type(int)) --> "int". 
type(type(string)) --> "string". 

% skip 1 or more whitespace 
s --> (" " ; "\n"), (s ; []).