https://vik.wiki/index.php?action=history&feed=atom&title=A_nyelv_v%C3%A9grehajt%C3%A1si_mechanizmusa_%28redukci%C3%B3s_l%C3%A9p%C3%A9s%2C_visszal%C3%A9p%C3%A9s%29 2026-04-07T12:18:22Z Az oldal laptörténete a wikiben MediaWiki 1.43.6 https://vik.wiki/index.php?title=A_nyelv_v%C3%A9grehajt%C3%A1si_mechanizmusa_(redukci%C3%B3s_l%C3%A9p%C3%A9s,_visszal%C3%A9p%C3%A9s)&diff=137918&oldid=prev 2012-10-21T20:09:43Z

<p>Új oldal, tartalma: „{{GlobalTemplate|Infoalap|PrologElm2}} * fejezetek: 3.2.2, 3.5.1 ==3.2.2 Végrehajtási algoritmus== A végrehajtási algoritmus két pillére: a mintaillesztés és …”</p> <p><b>Új lap</b></p><div>{{GlobalTemplate|Infoalap|PrologElm2}}<br /> <br /> * fejezetek: 3.2.2, 3.5.1<br /> <br /> ==3.2.2 Végrehajtási algoritmus==<br /> A végrehajtási algoritmus két pillére: a mintaillesztés és a visszalépéses mélységi keresés.<br /> <br /> A mintaillesztés alaplépése a redukciós lépés, mely során a bemenetre érkező célsorozatok első célját kíséreljük meg egyesíteni a klóz fejével.<br /> Siker esetén a klóz törzsét az első cél helyébe rakjuk. Két kifejezés egyesíthető, ha a bennük lévő változók helyébe tetszőleges kifejezést helyettesítve a két kifejezés azonossá tehető.<br /> <br /> Ha egy változó többször is előfordul, akkor minden előfordulását azonos kifejezésere kell cserélni.<br /> <br /> ===Redukciós lépés===<br /> Bemenete egy célsorozat és egy klóz, először elkészítjük a klóz másolatát, minden változóját szisztematikusan lecserélve új változókra, ez az ismételt felhasználáshoz (rekurzió) nélkülözhetetlen. Ezután megkísérlejük a célsorozat első hívását egyesíteni a megadott fejjel (link=egyesítési algoritmus). Siker esetén a keletkezett behelyettesíteéseket elvégezzük a klóz belsejében és a maradék célsorozaton. Végül a törzset rakjuk az első hívás helyébe.<br /> <br /> # A klózt lemásoljuk, minden változót szisztematikusan új változóra cserélve. <br /> # A célsorozatot szétbontjuk az első hívásra és a maradékra. <br /> # Az első hívást helyettesítjük a klózfejjel. <br /> # A szükséges behelyettesítéseket elvégezzük a klóz törzsén és a célsorozat maradékán. <br /> # Az új célsorozat: a klóztörzs és utána a maradék célsorozat. <br /> # Ha a hívás és a klózfej nem egyesíthető, akkor a redukciós lépés meghiúsul. <br /> <br /> ===Végrehajtási algoritmus===<br /> Célsorozat futása az adott prolog programra vonatkozatva. Eredménye lehet siker (változók behelyettesítésével járhat) vagy meghiúsulás (nem törtnéneik változó behelyettesítés)<br /> * beépítettt eljárás hívása:&lt;br&gt;<br /> végrehajtása során siker esetén behelyettesítés után új célsorozatott készít az első hívás elhagyásával. Sikertelenség visszalépést eredményez.<br /> * felhasználói eljárás hívása:&lt;br&gt;<br /> első olyan klóz megkeresése, melyre a redukciós lépés sikeresen lefut. Ha nincs ilyen, visszalépés.<br /> <br /> &#039;&#039;&#039;Visszalépés történik tehát akkor, ha&#039;&#039;&#039;<br /> * egy beépített eljárás meghiúsul, vagy <br /> * ha egy felhasználói eljáráshívást nem lehet (több) klózfejjel egyesíteni (nincs olyan klózfej, amelyre a redukciós lépés sikerrel futna le) <br /> <br /> Amennyiben nincs visszalépés az új célsorozat feldolgozása kezdődik meg.<br /> Visszalépés esetén visszatér a legutolsó sikeres redukciós lépéshez (minden azóta történt behelyettesítés érvényét veszti) és új klóz illezstésével próbálkozik, meghiúsulás esetén további visszalépés következik.<br /> * sekély visszalépés: egy eljárás klózából uagyanezen eljárás egy későbbi klózába kerül a vezérlés<br /> * mély visszalépés: egy már lefutott eljárás belsejébe térünk vissza és új megoldásokat keresünk.<br /> Ha nincs hova vissazlépni a teljes hívás meghiúsul.<br /> Ha a visszalépés során üres lesz a célsorozat a hívás sikeres lesz.<br /> <br /> ==3.5.1 Teljes végrehajtási algoritmus==<br /> # &lt;i&gt;(Kezdeti beállítások:)&lt;/i&gt; A verem üres, CS := célsorozat.&lt;br&gt;<br /> # &lt;i&gt;(Beépített eljárások:)&lt;/i&gt; Ha CS első célja beépített, akkor hajtsuk végre.&lt;br&gt;<br /> ** Ha sikertelen =&gt; 6. lépés<br /> ** Ha sikeres, elvégezzük a behelyettesítéseket, CS-ből elhagyjuk az első hívást, =&gt; 5. lépés.<br /> # &lt;i&gt;(Klózszámláló kezdőértékezése:)&lt;/i&gt; I = 1.&lt;br&gt;<br /> # &lt;i&gt;(Redukciós lépés:)&lt;/i&gt; CS első hívásához tartozó eljárásdefinícióban N klóz van.<br /> ** Ha I &gt; N =&gt; 6. lépés<br /> ** Redukciós lépés az I-edik klóz és a CS célsorozat között.<br /> ** Ha sikertelen, akkor I := I+1, és =&gt; 4. lépés.<br /> ** Ha I &lt; N (nem utolsó), akkor vermeljük &amp;lt;CS,I&amp;gt;-t.<br /> ** CS := a redukciós lépés eredménye.<br /> # &lt;i&gt;(Siker:)&lt;/i&gt; Ha CS üres, akkor sikeres vég, egyébként =&gt; 2. lépés.&lt;br&gt;<br /> # &lt;i&gt;(Sikertelenség:)&lt;/i&gt; Ha a verem üres, akkor sikertelen vég.&lt;br&gt;<br /> # &lt;i&gt;(Visszalépés:)&lt;/i&gt; Ha a verem nem üres, akkor leemeljük a veremből &amp;lt;CS,I&amp;gt;-t, I := I+1, és =&gt; 4. lépés.<br /> <br /> <br /> [[Category:Infoalap]]</div>

Unknown user