Tôi làm cách nào để xây dựng Trình tạo bảng thử thách?

Question

Tôi đang tìm cách viết Trình tạo bảng chân lý làm dự án cá nhân.

Có một số trang web trực tuyến dựa trên web here và here.

(Example screenshot of an existing Truth Table Generator)

Tôi có câu hỏi sau:

• Làm thế nào tôi nên đi về phân tích cú pháp biểu thức như: ((P => Q) & (Q => R)) => (P => R)
• Tôi có nên sử dụng trình tạo trình phân tích cú pháp như ANTLr hoặc YACC hoặc sử dụng cụm từ thông dụng thẳng không?
• Khi tôi đã phân tích cú pháp biểu thức, tôi nên tạo bảng chân lý như thế nào? Mỗi phần của biểu thức cần phải được chia thành các thành phần nhỏ nhất của nó và được xây dựng lại từ phía bên trái của bảng bên phải. Làm thế nào tôi sẽ đánh giá một cái gì đó như thế?

Có ai có thể cung cấp cho tôi các mẹo liên quan đến việc phân tích các biểu thức tùy ý này và cuối cùng đánh giá biểu thức được phân tích cú pháp không?

Answer 1

Điều này nghe có vẻ giống như một dự án cá nhân tuyệt vời. Bạn sẽ tìm hiểu rất nhiều về cách các phần cơ bản của trình biên dịch hoạt động. Tôi sẽ bỏ qua cố gắng sử dụng trình tạo trình phân tích cú pháp; nếu điều này là để chỉnh sửa của riêng bạn, bạn sẽ tìm hiểu thêm bằng cách làm tất cả từ đầu.

Cách các hệ thống như vậy hoạt động chính thức là cách chúng tôi hiểu ngôn ngữ tự nhiên. Nếu tôi đưa cho bạn một câu: "Con chó, Rover, ăn đồ ăn của anh ấy", điều đầu tiên bạn làm là chia nó ra thành các từ và dấu chấm câu. "The", "SPACE", "dog", "COMMA", "SPACE", "Rover", ... Đó là "tokenizing" hoặc "lexing".

Điều tiếp theo bạn làm là phân tích luồng mã thông báo để xem câu đó có đúng ngữ pháp hay không. Ngữ pháp tiếng Anh cực kỳ phức tạp, nhưng câu này khá đơn giản. ĐỐI TƯỢNG-TÁC ĐỘNG-ĐỘNG TỪ-ĐỐI TƯỢNG. Đây là "phân tích cú pháp".

Một khi bạn biết rằng câu là ngữ pháp, sau đó bạn có thể phân tích câu để thực sự có được ý nghĩa từ nó. Ví dụ, bạn có thể thấy rằng có ba phần của câu này - chủ đề, sự nhạy cảm, và "của anh ấy" trong đối tượng - tất cả chỉ đến cùng một thực thể, cụ thể là, con chó. Bạn có thể tìm ra rằng con chó là thứ làm việc ăn uống, và thức ăn là thứ đang được ăn. Đây là giai đoạn phân tích ngữ nghĩa.

Trình biên dịch sau đó có giai đoạn thứ tư mà con người không làm, đó là chúng tạo ra mã đại diện cho các hành động được mô tả bằng ngôn ngữ.

Vì vậy, hãy làm tất cả. Bắt đầu bằng cách xác định mã thông báo của ngôn ngữ của bạn là gì, hãy xác định Mã thông báo lớp cơ sở và một nhóm các lớp dẫn xuất cho từng loại. (IdentifierToken, OrToken, AndToken, ImpliesToken, RightParenToken ...). Sau đó viết một phương thức nhận một chuỗi và trả về một IEnumerable '. Đó là lexer của bạn.

Thứ hai, tìm hiểu ngữ pháp của ngôn ngữ của bạn là gì và viết một trình phân tích cú pháp gốc đệ quy lên IEnumerable thành một cây cú pháp trừu tượng đại diện cho các thực thể ngữ pháp trong ngôn ngữ của bạn.

Sau đó viết một trình phân tích nhìn vào cây đó và tìm ra các số liệu, chẳng hạn như "tôi có bao nhiêu biến miễn phí khác nhau?"

Sau đó, viết trình tạo mã kích hoạt mã cần thiết để đánh giá các bảng chân lý. Spitting IL có vẻ như quá mức cần thiết, nhưng nếu bạn muốn thực sự là buff, bạn có thể. Nó có thể dễ dàng hơn để cho thư viện cây biểu thức làm điều đó cho bạn; bạn có thể chuyển đổi cây phân tích cú pháp của bạn thành một cây biểu thức, sau đó biến cây biểu thức thành một đại biểu và đánh giá các đại biểu.

Chúc may mắn!

Answer 2

Tôi nghĩ rằng trình tạo trình phân tích cú pháp là quá mức cần thiết. Bạn có thể sử dụng ý tưởng chuyển đổi một biểu thức thành postfix và evaluating postfix expressions (hoặc trực tiếp xây dựng một cây biểu thức ra khỏi biểu thức infix và sử dụng nó để tạo bảng sự thật) để giải quyết vấn đề này.

Answer 3

Vì Mehrdad đề cập đến bạn sẽ có thể tự tay cuộn phân tích cú pháp trong cùng một thời gian như nó sẽ thực hiện để tìm hiểu cú pháp của trình phân tích cú pháp/phân tích cú pháp. Kết quả cuối cùng bạn muốn là một số Cú pháp trừu tượng (AST) của biểu thức mà bạn đã được đưa ra.

Sau đó, bạn cần tạo một số trình tạo đầu vào để tạo kết hợp đầu vào cho các ký hiệu được xác định trong biểu thức.

Sau đó lặp lại trên bộ nhập liệu, tạo kết quả cho mỗi kết hợp đầu vào, với các quy tắc (AST) bạn đã phân tích cú pháp trong bước đầu tiên.

Làm thế nào tôi sẽ làm điều đó:

tôi có thể tưởng tượng được sử dụng các hàm lambda để diễn tả AST/quy tắc như bạn phân tích các cây, và xây dựng một bảng biểu tượng như bạn phân tích, sau đó bạn có thể xây dựng các thiết lập đầu vào , phân tích cú pháp bảng biểu tượng thành cây biểu thức lambda, để tính toán kết quả.

Answer 4

Nếu mục tiêu của bạn đang xử lý biểu thức boolean, trình tạo trình phân tích cú pháp và tất cả các máy móc đi kèm là lãng phí thời gian, trừ khi bạn muốn tìm hiểu cách chúng hoạt động (sau đó bất kỳ mục nào trong số đó sẽ ổn).

Nhưng thật dễ dàng để xây dựng trình phân tích cú pháp đệ quy bằng tay cho các biểu thức boolean, tính toán và trả về kết quả "đánh giá" biểu thức. Một trình phân tích cú pháp như vậy có thể được sử dụng trong lần vượt qua đầu tiên để xác định số lượng biến duy nhất, trong đó "đánh giá" có nghĩa là "couunt 1 cho mỗi tên biến mới". Viết một trình tạo ra để tạo ra tất cả các giá trị chân lý có thể cho các biến N là tầm thường; cho mỗi bộ giá trị, chỉ cần gọi lại trình phân tích cú pháp và sử dụng nó để đánh giá biểu thức, trong đó các đánh giá có nghĩa là "kết hợp các giá trị của các biểu thức con theo toán tử".

Bạn cần một ngữ pháp:

formula = disjunction ; 
disjunction = conjunction 
       | disjunction "or" conjunction ; 
conjunction = term 
       | conjunction "and" term ; 
term = variable 
     | "not" term 
     | "(" formula ")" ; 

Yours có thể phức tạp hơn, nhưng đối với biểu thức boolean nó không thể có nhiều phức tạp hơn.

Đối với từng quy tắc ngữ pháp, viết 1 chương trình con sử dụng một toàn cầu "quét" chỉ số vào chuỗi được phân tích cú pháp:

int disjunction() 
// returns "-1"==> "not a disjunction" 
// in mode 1: 
// returns "0" if disjunction is false 
// return "1" if disjunction is true 
{ skipblanks(); // advance scan past blanks (duh) 
    temp1=conjunction(); 
    if (temp1==-1) return -1; // syntax error 
    while (true) 
    { skipblanks(); 
     if (matchinput("or")==false) return temp1; 
     temp2= conjunction(); 
     if (temp2==-1) return temp1; 
     temp1=temp1 or temp2; 
    } 
    end 

    int term() 
    { skipblanks(); 
    if (inputmatchesvariablename()) 
     { variablename = getvariablenamefrominput(); 
     if unique(variablename) then += numberofvariables; 
     return lookupvariablename(variablename); // get truthtable value for name 
     } 
    ... 
    } 

Mỗi thói quen phân tích cú pháp của bạn sẽ vào khoảng phức tạp này. Nghiêm túc.

Answer 5

Bạn có thể lấy mã nguồn của chương trình pyttgen tại http://code.google.com/p/pyttgen/source/browse/#hg/src Nó tạo ra các bảng chân lý cho các biểu thức logic.Mã dựa trên thư viện lớp, do đó, nó rất đơn giản :)