La langue while

Question

Pour ma théorie de classe langages informatiques, nous avons un devoir de mettre en œuvre un morceau de code dans une langue qui a seulement while pour le contrôle de flux (pas si les déclarations). Ceci est principalement de prouver que vous pouvez écrire un langage complet-avec seulement une Turing boucle while.

Pour ceux qui peuvent comprendre des grammaires de langue, voici les règles linguistiques:

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)

est copiée à partir de mes notes de cours, alors ne me blâmez pas si quelque chose est manquant ou incorrect!

Le morceau de code pour la mise en œuvre est la suivante:

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

En tout cas, si vous voulez aller de l'avant et d'écrire que l'utilisation des règles linguistiques ci-dessus, allez-y. Sinon, allez-y et l'écrire dans la langue que vous êtes le plus à l'aise. Mais il y a quelques mises en garde!

• Non si les déclarations ou tout autre type de contrôle de flux autre que while.
• Pas de tricherie: la grammaire ne comprend pas au-dessus de toute déclaration de rupture, le retour des déclarations ou des exceptions. Ne les utilisez pas.

Je l'ai obtenu mon morceau de code écrit pour cela (que je posterai juste pour prouver ce n'est pas moi show Teh post codez). Je suis un peu curieux de ce que quelqu'un d'autre peut venir avec bien.

Answer 1

Voici mon code:

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

Il peut être fait avec une seule boucle while, mais il est pas clair:

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

Explication, si d = 0, d 1 sera, lui aussi aura 1. Ceci met fin à la boucle.

x est fixé à un / d qui est bien, parce que si d est 0, a / d évalue à 1.

Answer 3

Est-ce que ce travail?

td := d
x := 1

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

Answer 4

Pour être complet Turing, vous devez appuyer à la fois la sélection et l'itération. Alors que les boucles itérer évidemment. La sélection peut être accompli en faisant passer par la boucle une fois si la condition est vraie, et pas du tout autrement.

Alors pire des cas, vous pouvez faire tout ce que vous devez en appliquant ces techniques. J'imagine des flux de contrôle compliqués obtiendraient laid vite cependant. : -)

Answer 5

Sans utiliser les détails des branches vraies ou fausses, et sans répéter le prédicat:

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

Answer 6

Ceci est une extension de réponse Eamon .

La sémantique de if <condition> then <stmt> else <stmt> fi est le suivant:

• évaluer <condition>;
• si elle était vraie, exécutez l'instruction entre et then else;
• sinon, exécutez l'instruction entre et fi while <condition> do <stmt> od.

La sémantique de while est le suivant:

• évaluer do;
• si elle est fausse, la déclaration se fait exécuter od;
• sinon, exécutez l'instruction entre et if A then B else C gensymN et exécuter à nouveau la déclaration gensymN = 0 and A.

Pour exprimer A en termes de B, exécuter la transformation suivante:

Soit être un nom gensymN = 1 non utilisé pour toute autre variable; puis émettre le code suivant

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

La sémantique de ce programme est:

• Attribuer 0 à gensymN = 0.
• Évaluer C (il est vrai ssi est vrai gensymN := 1)
• Si cela est vrai, alors:
  • exécuter and
  • exécuter dummy := A; <insert the above program here, with dummy instead of A>
  • évaluer dummy (il est faux)
  • évaluer if (il est faux)
• autre (si était faux <=>):
  • évaluer <=> (il est vrai)
  • exécuter <=>
  • exécuter <=>
  • évaluer <=> (il est faux)

Observer la sous-structure suivante de ce qui précède:

• (efficace) évalue <=>;
• Si cela est vrai, il exécute <=>, sinon <=>.
• En dehors de <=>, <=> et <=>, le programme (fragment) seulement bidule <=>, qui ne figure pas dans le programme d'entrée.

D'où ce programme a la même sémantique que

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

Une note: si est vrai quand <=> évalué, il sera évalué à nouveau (à moins est court <=> circuit). Si la langue permet de stocker des booléens dans des variables, on peut introduire une variable plus factice et faire <=>. Ensuite, les deux évaluations sont essentiellement de juste <=> une charge. Si l'évaluation des expressions booléennes ne peut pas avoir des effets secondaires, ce qui empêche la deuxième évaluation n'est pas nécessaire pour l'exactitude; il peut (ou non) être une optimisation.

Prenez ce qui précède comme une « preuve douce », avec les conditions du paragraphe précédent, que c'est un bon entièrement générale traduction à <=> <=>. La généralité définit ce (= Eamon) répondre à l'écart des autres, à mon avis.