Ngôn ngữ đồng thời

Question

Đối với lý thuyết của tôi về lớp ngôn ngữ máy tính, chúng tôi có bài tập về nhà để thực hiện một đoạn mã bằng ngôn ngữ chỉ có các câu lệnh kiểm soát luồng (không có câu lệnh). Điều này chủ yếu là để chứng minh rằng bạn có thể viết một ngôn ngữ hoàn chỉnh Turing chỉ với một vòng lặp while.

Đối với những người bạn của những người có thể hiểu được văn phạm tiếng ngôn ngữ, đây là những quy tắc ngôn ngữ:

S -> S;S | while C do S od | id := E 

E -> E + T | T | E - T 

T -> T * F | F | F/T 

F -> id | cons | (E) 

C -> E = E | E > E | E < E | E >= E | E <= E | E != E | C and C | C or C | not(C) 

này được sao chép từ các ghi chú lớp học của tôi, do đó, không đổ lỗi cho tôi nếu có điều gì là thiếu hoặc không chính xác!

Các đoạn mã để thực hiện là:

if d = 0 do 
    x := 1 
else 
    x := a/d 

Dù sao đi nữa, nếu bạn muốn đi trước và viết rằng việc sử dụng các quy tắc ngôn ngữ trên, đi trước. Nếu không, hãy tiếp tục và viết nó bằng bất cứ ngôn ngữ nào mà bạn cảm thấy thoải mái nhất. Nhưng có một vài điều cần lưu ý!

• Không có câu lệnh hoặc bất kỳ loại điều khiển luồng nào khác ngoài vòng lặp.
• Không gian lận: ngữ pháp trên không bao gồm bất kỳ câu lệnh ngắt, câu lệnh trả lại hoặc ngoại lệ nào. Không sử dụng chúng.

Tôi đã nhận được đoạn mã của tôi được viết cho điều này (tôi sẽ đăng bài chỉ để chứng minh đây không phải là hiển thị cho tôi bài đăng codez). Tôi hơi tò mò bất cứ ai khác có thể nghĩ ra.

Answer 1

Dưới đây là mã của tôi:

continue := True 
while d = 0 and continue do 
    x := 1 
    continue := False 
od 
while d != 0 and continue do 
    x := a/d 
    continue := False 
od 

Answer 2

Nó có thể được thực hiện với một duy nhất trong khi vòng lặp, nhưng nó không phải là rõ ràng:

while d == 0 do 
    d := 1; 
    a := 1 
od 
x := a/d; 

Giải thích, nếu d = 0 thì d sẽ 1, cũng sẽ là 1. Điều này kết thúc vòng lặp.

Bây giờ x được thiết lập để a/d đó là tốt, bởi vì nếu d là 0, a/d để đánh giá 1.

Answer 3

Được Turing Complete, bạn cần phải hỗ trợ cả hai lựa chọn và lặp đi lặp lại. Trong khi vòng lặp rõ ràng là lặp đi lặp lại. Lựa chọn có thể được thực hiện bằng cách làm cho nó đi qua vòng lặp một lần nếu điều kiện là đúng, và không phải ở tất cả các cách khác.

Trường hợp xấu nhất bạn có thể làm mọi thứ bạn cần bằng cách áp dụng các kỹ thuật đó. Tôi muốn tưởng tượng một số dòng điều khiển phức tạp sẽ nhận được xấu xí nhanh chóng mặc dù. :-)

Answer 4

Công việc này có hiệu quả không?

td := d 
x := 1 

while td != 0 do 
    x := a/d 
    td := 0 
od 

Answer 5

Nếu không sử dụng các chi tiết của các ngành đúng hay sai, và không lặp lại những vị:

statementIncomplete := True 
while d = 0 and statementIncomplete do 
    x := 1 
    statementIncomplete := False 
od 
while statementIncomplete do 
    x := a/d 
    statementIncomplete := False 
od 

Answer 6

Đây là một mở rộng của Eamon's answer.

Ngữ nghĩa của if <condition> then <stmt> else <stmt> fi như sau:

• đánh giá <condition>;
• nếu đúng, thực hiện tuyên bố giữa then và else;
• nếu không, hãy thực hiện câu lệnh giữa else và fi.

Ngữ nghĩa của while <condition> do <stmt> od như sau:

• đánh giá <condition>;
• nếu sai, câu lệnh while được thực hiện xong;
• nếu không, hãy thực hiện tuyên bố giữa do và od và thực hiện lại tuyên bố while.

Để bày tỏ if A then B else C về while, thực hiện việc chuyển đổi sau:

Hãy gensymN là một tên không được sử dụng cho bất kỳ biến khác; sau đó phát ra đoạn mã sau

gensymN := 0; 
while gensymN = 0 and A do B; gensymN = 1; od; 
while gensymN = 0 do C; gensymN = 1; od 

Ngữ nghĩa của chương trình này là:

• Gán 0 đến gensymN.
• Đánh giá gensymN = 0 and A (đó là sự thật khi và chỉ khi A là đúng)
• Nếu đúng, thì:
  • thực hiện B
  • thực hiện gensymN = 1
  • đánh giá gensymN = 0 and A (đó là sai)
  • đánh giá gensymN = 0 (đó là sai sự thật)
• khác (nếu gensymN = 0 and A là false):
  • đánh giá gensymN = 0 (đó là sự thật)
  • thực hiện C
  • thực hiện gensymN := 1
  • đánh giá gensymN = 0 (đó là sai)

Quan sát cấu trúc con dưới đây:

• Đánh giá (hiệu quả) đánh giá A;
• Nếu đúng, nó thực hiện B, nếu không C.
• Ngoài số A, B và C, chương trình (phân đoạn) chỉ có câu đố với gensymN, không có trong chương trình nhập.

Do đó chương trình này có ngữ nghĩa giống như

if A then B else C fi; gensymN := 1 

Một chú thích: nếu A là đúng khi đánh giá, nó sẽ được đánh giá một lần nữa (trừ khi and là ngắn mạch). Nếu ngôn ngữ cho phép lưu trữ booleans trong các biến, người ta có thể giới thiệu thêm một biến giả và làm dummy := A; <insert the above program here, with dummy instead of A>. Sau đó, hai đánh giá của dummy về cơ bản chỉ là một tải. Nếu việc đánh giá các biểu thức boolean không thể có các tác dụng phụ, việc ngăn chặn việc đánh giá thứ hai là không cần thiết cho tính chính xác; nó có thể (hoặc có thể không) là một tối ưu hóa.

Hãy nêu trên như là một "bằng chứng mềm", với provisos của đoạn trước, rằng đây là một đúng hoàn toàn chung dịch if để while. Toàn bộ toàn bộ đặt câu trả lời này (= của Eamon) ngoài những người khác, theo quan điểm của tôi.