diff options
| author | Timotej Lazar <timotej.lazar@fri.uni-lj.si> | 2016-05-18 19:30:33 +0200 |
|---|---|---|
| committer | Timotej Lazar <timotej.lazar@fri.uni-lj.si> | 2016-05-18 19:33:14 +0200 |
| commit | 4973979e40dfdc26dafe1cdeddf8e0bce859ba5d (patch) | |
| tree | 58fd0d205f6ac20f3bf5a52cf6247b5fa577589f /prolog | |
| parent | 025254ce93f7ce8b4d175dcb85d228506202583c (diff) | |
Prolog: add introduction for DCG group
Diffstat (limited to 'prolog')
| -rw-r--r-- | prolog/problems/dcg/intro_sl.html | 301 | ||||
| -rw-r--r-- | prolog/problems/dcg/sl.py | 7 | ||||
| -rw-r--r-- | prolog/problems/dcg/syntax_tree.dot | 40 | ||||
| -rw-r--r-- | prolog/problems/dcg/syntax_tree.svg | 133 |
4 files changed, 480 insertions, 1 deletions
diff --git a/prolog/problems/dcg/intro_sl.html b/prolog/problems/dcg/intro_sl.html new file mode 100644 index 0000000..ae94e73 --- /dev/null +++ b/prolog/problems/dcg/intro_sl.html @@ -0,0 +1,301 @@ +<!DOCTYPE html> +<html lang="sl"> +<head> + <meta charset="utf-8" /> + <title>Prolog: Gramatike (DCG)</title> + <link rel="stylesheet" type="text/css" href="../style.css" /> +</head> +<body> + +<h1>Prolog: Gramatike (DCG)</h1> +<p> +Kako se ljudje sporazumevamo med seboj? Z jeziki, seveda. No, saj obstajajo +tudi drugi načini komunikacije, a je vendarle jezik tisti osrednji, +najpogostejši, način. In kako se sporazumevamo z računalnikom, kako mu +razložimo, kaj naj naredi? Prav tako z jeziki, pa čeprav programskimi. Saj tako +velike razlike med naravnimi in programskimi jeziki niti ni, le da so slednji +bolj formalizirani, bolj natančni, bi lahko rekli. In prav vsi jeziki temeljijo na +<em>slovnici</em> oz. <em>gramatiki</em>. Ta natančno opredeli, katere besede +(včasih jim pravimo tudi stavki) so slovnično pravilne (so elementi jezika) in +katere niso (niso elementi danega jezika). +</p> + +<p> +Gramatiko jezika navadno zapišemo v obliki množice produkcij oz. preslikovalnih +pravil. Naredimo to kar na primeru. Imejmo naslednjo množico (dveh) pravil: +</p> +<pre> +s --> []. % pravilo #1 +s --> [a,a], s. % pravilo #2 +</pre> +<p> +Medklic: Pravila načeloma niso videti kot prologov program, a v resnici jih +prolog razume in interno pretvori v kodo, kot si je vajen. A danes se v to ne +bomo spuščali, ker niti ni pomembno. +</p> + +<p> +Poglejmo si sestavne dele enega pravila in kako ga razumemo ter uporabljamo. Za +primer vzemimo pravilo #2 zgoraj. Puščica (<code>--></code>) nam pravilo +razdeli na levi in desni del. Pomeni pa naslednje: simbol na levi strani +preslika v to, kar je na desni. Torej naše konkretno pravilo pomeni „zamenjaj +simbol <code>s</code> s seznamom <code>[a,a]</code> in simbolom +<code>s</code>“. Na enak način pravilo #1 pomeni „zamenjaj simbol +<code>s</code> s praznim seznamom“. +</p> + +<p> +Zakaj so nekatere stvari pisane v seznamih in nekatere ne? Razlika je zelo +pomembna: tistemu, kar je pisano v seznamih (npr. <code>[a,a]</code>), bomo +rekli končni simboli ali terminali, simbolom izven seznamov (npr. +<code>s</code>) pa nekončni simboli oz. neterminali. Nekončne simbole gramatike +moramo vedno preslikati še naprej, medtem ko končnih simbolov ne moremo več +preslikati naprej – od tu tudi njihovo poimenovanje. Ko si nekoč v šoli delal +stavčno analizo pri pouku slovenščine, si stavek verjetno razdelil na +samostalnik, glagol in podobne sintaktične elemente – to so nekončni simboli. +Končni simboli pa so konkretni primeri teh elementov: npr. glagol +„programirati“. +</p> + +<p> +DCG je le en izmed možnih zapisov gramatike. Na levi strani pravil v DCG se +vedno pojavlja en in samo en nekončni simbol. Na desni strani je lahko poljubno +zaporedje končnih in nekončnih simbolov, ločenih z vejicami. Slednje pomenijo +konjunkcijo, kot smo že vajeni. Pravil je lahko poljubno mnogo – katero bomo +uporabili v nekem konkretnem primeru, je stvar izbire. Ko smo že pri +konjunkciji: podpičje tudi tu pomeni disjunkcijo. Zgornji dve pravili bi lahko +zapisali tudi takole: +</p> +<pre> +s --> [] ; [a,a], s. +</pre> +<p> +Oziroma v duhu drugih jezikov za opis gramatik, kot je npr. BNF, tudi takole: +</p> +<pre> +s --> [] | [a,a], s. +</pre> + +<p> +Skratka tudi navpičnica pomeni disjunkcijo: neterminal <code>s</code> se lahko +preslika ali v prazen seznam ali pa v seznam dveh terminalov <code>a</code> in +v neterminal <code>s</code>. +</p> + +<p> +Prav, sedaj poznamo obliko zapisa. Kaj pa lahko s tem počnemo oz. kakšno +povezavo ima to z jeziki? Pri vsaki gramatiki imamo tipično določen tudi nek +začetni nekončni simbol, pri našem primeru bo to kar simbol <code>s</code>, ki +je tudi edini nekončni simbol. Izpeljavo poljubne besede oz. stavka v jeziku +začnemo s tem simbolom in na njem v poljubnem redu uporabljamo preslikovalna +pravilo dokler ne dobimo rezultata sestavljenega samo iz končnih simbolov. +Poglejmo nekaj primerov. +</p> + +<pre> +Primer 1: <strong>s</strong> --(2)--> aa<strong>s</strong> --(1)--> aa +</pre> + +<p> +Za lažji prikaz so odebeljeno prikazani nekončni simboli, z normalno pisavo pa +končni simboli. V prvem primeru na začetnem simbolu najprej uporabimo pravilo +#2 in dobimo <code>aa<strong>s</strong></code>, nato pa na tem pravilo #1 (na +neterminalu <code><strong>s</strong></code>, seveda) in dobimo <code>aa</code>. +Ker po drugem koraku nimamo v rezultatu več nobenih nekončnih simbolov, smo +zaključili. Beseda oz. stavek <code>aa</code> je sintaktično pravilen stavek v +jeziku, ki ga definira naša zgornja gramatika. +</p> + +<pre> +Primer 2: <strong>s</strong> --(2)--> aa<strong>s</strong> --(2)--> aaaa<strong>s</strong> --(1)--> aaaa +</pre> + +<p> +V tem primeru smo izpeljali stavek <code>aaaa</code>. Če malce pomislimo, +opazimo, da naša gramatika generira prazen stavek (nič <code>a</code>-jev), +<code>aa</code>, <code>aaaa</code>, <code>aaaaaa</code>, itd. Skratka, naši +stavki so vedno sestavljeni iz sodega števila <code>a</code>-jev. Lahko se še +tako trudiš, a ti iz začetnega simbola <code><strong>s</strong></code> ne bo +uspelo izpeljati stavka z lihim številom <code>a</code>-jev. Pravzaprav lahko +ta razmislek peljemo še malce dlje. Vsak stavek lahko izpeljemo le na en sam +način! Za stavek z n <code>a</code>-ji moramo najprej n/2-krat uporabiti +pravilo #2 in na koncu enkrat pravilo #1. +</p> + +<p> +Preden to misel razvijemo naprej, naj odgovorim še na vprašanje, kako lahko +zgornje stvari poskusiš v prologu. Preposto, zgornjo gramatiko prepišeš kot +program (kar v resnici je!) in poganjaš poizvedbe v konzoli takole: +</p> +<pre> +?- s(Word, []). +Word = [] ; +Word = [a,a] ; +Word = [a,a,a,a] ; +… +</pre> + +<p> +Poizvedbo torej pokličeš z začetnim simbolom (ki ga prolog v resnici interno +prevede v predikat, kot si jih vajen), ki mu podaš dva argumenta. V bistvu je +ta par argumentov en sam argument, ki tvori besedo (oz. stavek), ki jo bo +gramatika generirala. Zakaj tak zapis z dvema seznamoma? Gre za razliko +seznamov – če drugega pustiš praznega, bo prvi ostal tak, kot je; tako bomo +večinoma pustili. Tak zapis je posledica učinkovite implementacije. Ko prolog +generira besede nekega jezika, to počne s konkatenacijo seznamov. Za slednjo si +videl, da je časovne zahtevnosti O(n), a se jo da s trikom razlike seznamov +narediti v času O(1). +</p> + +<p> +Kot si že vajen, stvari delujejo v več smeri. Zgoraj smo gramatiko uporabili za +generiranje besed jezika. Bolj običajna uporaba pa je v drugi smeri: +računalniški prevajalniki tipično preverjajo, ali je podana beseda sintaktično +pravilna. To pomeni, ali jo lahko izpeljemo z uporabo pravil dane gramatike. +Spodnji poizvedbi sta tak primer uporabe. +</p> + +<pre> +?- s([a,a], []). +true +?- s([a,a,a,a,a], []). +false +</pre> + +<h2>Dvoumnost gramatik</h2> +<p> +Zakaj smo posebej izpostavili, da lahko nek stavek izpeljemo le na en način? +Ker je to verjetno ena najpomembnejših lastnosti gramatik! Predpostavimo, da +imamo poleg zgornjih dveh pravil še tretje: +</p> +<pre> +s --> []. % pravilo #1 +s --> [a,a], s. % pravilo #2 +s --> s, [a,a]. % pravilo #3 +</pre> + +<p> +Sedaj lahko stavek <code>aaaa</code> izpeljem na več kot en način, npr. takole: +</p> +<pre> +Način 1: <strong>s</strong> --(2)--> aa<strong>s</strong> --(2)--> aaaa<strong>s</strong> --(1)--> aaaa +Način 2: <strong>s</strong> --(3)--> <strong>s</strong>aa --(2)--> aa<strong>s</strong>aa --(1)--> aaaa +</pre> + +<p> +Kaj je v tem tako strašnega? Je morda problem v tem, da imamo več izbire? Ne, +problem je v tem, da isti stavek (<code>aaaa</code>) lahko pomeni več stvari. +Če računalniku rečeš „Prištej ena.“, ne želiš, da to pomeni več različnih +stvari, kajne? Predstavljaj si, da bi te računalnik razumel malce po svoje: saj +bi bilo zabavno, ampak jaz si tako sprogramiranega avtopilota na primer ne +želim kaj preveč. +</p> + +<p> +Omenili smo pomen in da je pomen tesno povezan z izpeljavo (zaporedjem uporabe +konkretnih preslikovalnih pravil gramatike). Tako je, kasneje bomo videli, da +tipično vsaki preslikavi pripišemo pomen. +</p> + +<p> +Izpeljavo besed v jeziku tipično predstavimo z drevesi izpeljave. Tako bolj +pregledno pokažemo tisto kar smo zgoraj naredili s puščicami v eni vrstici. Pri +več neterminalih tako točno vemo kateri neterminal smo preslikali v kaj. +Primera zgornjih izpeljav sta podana spodaj. Končni rezultat preberemo z levim +obhodom drevesa, posamezne sezname pa konkateniramo med seboj. +</p> + +<figure> + <img src="syntax_tree.svg" /> + <figcaption>Različni drevesi izpeljave za besedo <code>aaaa</code></figcaption> +</figure> + +<h2>Dodajanje kode v gramatiko</h2> +<p> +Ker v našem primeru gramatiko uporabljamo znotraj programskega jezika +(prologa), nam seveda pride na misel, da bi lahko znotraj gramatike uporabili +tudi običajne prologove predikate. To je dejansko mogoče in nam v nekaterih +primerih pride precej prav. Poglejmo, kako to naredimo na naslednjem primeru. +Recimo, da želimo definirati gramatiko za jezik, kjer imamo večjo izhodno +abecedo kot samo <code>a</code> v prejšnjem primeru, a želimo, da se vse črke +vedno podvajajo. +</p> + +<pre> +s --> []. % pravilo #1 +s --> letter, s. % pravilo #2 +letter --> [X,X], { member(X, [a,b,c,d, …, z]) }. % pravilo #3 +</pre> + +<p> +Pravilo #3 je zanimivo: velike črke nam kot vedno v prologu tudi tu +predstavljajo spremenljivke. Rezultat tega pravila je seznam oblike +<code>[X,X]</code>. S predikatom <code>member/2</code> pa generiramo vse +možnosti za <code>X</code>: v tem primeru vse črke abecede od <code>a</code> do +<code>z</code>. Predikat <code>member/2</code> smo zapisali znotraj zavitih +oklepajev. V tem primeru ne gre za omejitve kot pri CLP(R), ampak prologu na ta +način povemo, da gre za običajno prologovsko kodo. Tako lahko uporabljamo +poljubne predikate znotraj pravil DCG. Celo CLP(R) lahko uporabimo, tako da +znotraj zavitih oklepajev zapišemo še ene zavite oklepaje. +</p> + +<h2>V kakšnem vrstnem redu prolog bere pravila?</h2> +<p> +Vrstni red uporabe pravil je tak, kot smo ga že vajeni pri prologu. Ta poskuša +pravila za posamezni neterminal od zgoraj navzdol. In poskuša vse, torej zopet +generira vse možne izpeljave eno za drugo z mehanizmom vračanja, če seveda tako +zahtevamo. +</p> + +<p> +Vrstni red preslikave znotraj posameznega pravila je od leve proti desni. +Vrstni red je pomemben. Kodo (z zavitimi oklepaji) lahko vključimo na poljubno +mesto in jo ločimo z vejicami. Izvedla se bo takrat, ko bo prolog nanjo +naletel, torej zopet od leve proti desni. +</p> + +<h2>Dodatni argumenti in pomen</h2> +<p> +Nekončnim simbolom gramatike lahko dodajamo dodatne argumente. Ti nam lahko +služijo za različne stvari, a največkrat z njimi definiramo pomen besed, ki jih +generira oz. razpozna dana gramatika. +</p> + +<p> +Definirajmo gramatiko, ki sprejme/generira poljubno zaporedje črk +<code>a</code> in <code>b</code>, njen pomen pa naj bo razlika v številu teh +črk. Z malo domišljije lahko rečemo, da gre za izid nogometne tekme: +<code>a</code> pomeni gol prve ekipe, <code>b</code> pa gol druge ekipe. +Neterminal <code>game</code> naj bo začetni simbol te gramatike. +</p> + +<pre> +game(0) --> []. +game(Diff) --> goal(Diff1), game(Diff2), {Diff is Diff1 + Diff2}. +goal( 1) --> [a]. +goal(-1) --> [b]. +</pre> + +<p> +Pomen lahko razumemo takole. Če je tekma brez golov (oz. ko v rekurziji pridemo +do praznega seznama golov), je razlika 0. Vsak <code>a</code> pomeni gol za +prvo ekipo in je vreden +1, vsak <code>b</code> pa gol za drugo ekipo in je +vreden -1. Pravilo, da je tekma sestavljena iz gola in potem še poljubno golov +v nadaljevanju, pa pove, da je razlika taka kot je v nadaljevanju, ki ji +prištejemo še vrednost gola: plus ali minus 1. Kot vidiš, je precej podobno, +kot če bi to sprogramili v prologu z rekurzijo. Pravzaprav se prevede v točno +to! Pomembno je, da smo dali kodo znotraj zavitih oklepajev na konec pravila +#2. Do takrat namreč že izvemo vrednosti za <code>Diff1</code> in +<code>Diff2</code>. +</p> + +<p> +Primer uporabe: +</p> +<pre> +?- game(Diff, [a,b,a,a], []). % končni rezultat 3-1 za prvo ekipo +Diff = 2. +</pre> + +</body> +</html> diff --git a/prolog/problems/dcg/sl.py b/prolog/problems/dcg/sl.py index 2e5a381..3c1deb7 100644 --- a/prolog/problems/dcg/sl.py +++ b/prolog/problems/dcg/sl.py @@ -1,2 +1,7 @@ name = 'Gramatike (DCG)' -description = 'Sestavljanje in testiranje gramatik, od preprostih do precej realističnih; podlaga za prevajalnike.' +description = '''\ +<p> +<a target="_blank" href="[%@resource intro_sl.html%]">Gramatike</a> +– sestavljanje in testiranje gramatik, od preprostih do precej realističnih; +podlaga za prevajalnike. +</p>''' diff --git a/prolog/problems/dcg/syntax_tree.dot b/prolog/problems/dcg/syntax_tree.dot new file mode 100644 index 0000000..54238d2 --- /dev/null +++ b/prolog/problems/dcg/syntax_tree.dot @@ -0,0 +1,40 @@ +digraph { + ordering=out; + pad=0; + ranksep=0.3; + + node [fontname="sans",height=0.2,penwidth=0]; + edge [fontname="sans",fontsize=8,arrowsize=0.6]; + + subgraph { + sa1 [label="s"]; + sa2 [label="s"]; + sa3 [label="s"]; + + aa1 [label="aa",fontname="mono"]; + aa2 [label="aa",fontname="mono"]; + ea [label="[]",fontname="mono"]; + + sa1 -> aa1 [label=" 2"]; + sa1 -> sa2 [label=" 2"]; + sa2 -> aa2 [label=" 2"]; + sa2 -> sa3 [label=" 2"]; + sa3 -> ea [label=" 1"]; + } + + subgraph { + sb1 [label="s"]; + sb2 [label="s"]; + sb3 [label="s"]; + + ab1 [label="aa",fontname="mono"]; + ab2 [label="aa",fontname="mono"]; + eb [label="[]",fontname="mono"]; + + sb1 -> sb2 [label=" 3"]; + sb1 -> ab1 [label=" 3"]; + sb2 -> ab2 [label=" 2"]; + sb2 -> sb3 [label=" 2"]; + sb3 -> eb [label=" 1"]; + } +} diff --git a/prolog/problems/dcg/syntax_tree.svg b/prolog/problems/dcg/syntax_tree.svg new file mode 100644 index 0000000..a1a8083 --- /dev/null +++ b/prolog/problems/dcg/syntax_tree.svg @@ -0,0 +1,133 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.38.0 (20140413.2041) + --> +<!-- Title: %3 Pages: 1 --> +<svg width="332pt" height="223pt" + viewBox="0.00 0.00 332.00 223.11" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(0 223.108)"> +<title>%3</title> +<polygon fill="white" stroke="none" points="0,-0 0,-223.108 332,-223.108 332,-0 0,-0"/> +<!-- sa1 --> +<g id="node1" class="node"><title>sa1</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="53" cy="-206.844" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="53" y="-203.144" font-family="sans" font-size="14.00">s</text> +</g> +<!-- sa2 --> +<g id="node2" class="node"><title>sa2</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="99" cy="-143.317" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="99" y="-139.617" font-family="sans" font-size="14.00">s</text> +</g> +<!-- sa1->sa2 --> +<g id="edge2" class="edge"><title>sa1->sa2</title> +<path fill="none" stroke="black" d="M63.6689,-191.574C69.9392,-183.187 77.9454,-172.479 84.7505,-163.377"/> +<polygon fill="black" stroke="black" points="86.478,-164.573 88.3889,-158.51 83.1142,-162.058 86.478,-164.573"/> +<text text-anchor="middle" x="82.5" y="-173.181" font-family="sans" font-size="8.00"> 2</text> +</g> +<!-- aa1 --> +<g id="node4" class="node"><title>aa1</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="27" cy="-143.317" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="27" y="-139.617" font-family="mono" font-size="14.00">aa</text> +</g> +<!-- sa1->aa1 --> +<g id="edge1" class="edge"><title>sa1->aa1</title> +<path fill="none" stroke="black" d="M46.7061,-190.95C43.4336,-183.206 39.3803,-173.614 35.8023,-165.147"/> +<polygon fill="black" stroke="black" points="37.6865,-164.211 33.4165,-159.502 33.8177,-165.846 37.6865,-164.211"/> +<text text-anchor="middle" x="45.5" y="-173.181" font-family="sans" font-size="8.00"> 2</text> +</g> +<!-- sa3 --> +<g id="node3" class="node"><title>sa3</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="135" cy="-79.7904" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="135" y="-76.0904" font-family="sans" font-size="14.00">s</text> +</g> +<!-- sa2->sa3 --> +<g id="edge4" class="edge"><title>sa2->sa3</title> +<path fill="none" stroke="black" d="M107.531,-127.736C112.284,-119.614 118.267,-109.388 123.435,-100.555"/> +<polygon fill="black" stroke="black" points="125.312,-101.506 126.53,-95.2667 121.687,-99.3849 125.312,-101.506"/> +<text text-anchor="middle" x="123.5" y="-109.654" font-family="sans" font-size="8.00"> 2</text> +</g> +<!-- aa2 --> +<g id="node5" class="node"><title>aa2</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="63" cy="-79.7904" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="63" y="-76.0904" font-family="mono" font-size="14.00">aa</text> +</g> +<!-- sa2->aa2 --> +<g id="edge3" class="edge"><title>sa2->aa2</title> +<path fill="none" stroke="black" d="M90.4685,-127.736C85.7161,-119.614 79.7328,-109.388 74.5646,-100.555"/> +<polygon fill="black" stroke="black" points="76.3129,-99.3849 71.4703,-95.2667 72.6879,-101.506 76.3129,-99.3849"/> +<text text-anchor="middle" x="87.5" y="-109.654" font-family="sans" font-size="8.00"> 2</text> +</g> +<!-- ea --> +<g id="node6" class="node"><title>ea</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="135" cy="-16.2635" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="135" y="-12.5635" font-family="mono" font-size="14.00">[]</text> +</g> +<!-- sa3->ea --> +<g id="edge5" class="edge"><title>sa3->ea</title> +<path fill="none" stroke="black" d="M135,-63.2645C135,-55.9222 135,-47.0305 135,-39.0293"/> +<polygon fill="black" stroke="black" points="137.1,-38.5712 135,-32.5712 132.9,-38.5712 137.1,-38.5712"/> +<text text-anchor="middle" x="138.5" y="-46.1269" font-family="sans" font-size="8.00"> 1</text> +</g> +<!-- sb1 --> +<g id="node7" class="node"><title>sb1</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="287" cy="-206.844" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="287" y="-203.144" font-family="sans" font-size="14.00">s</text> +</g> +<!-- sb2 --> +<g id="node8" class="node"><title>sb2</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="233" cy="-143.317" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="233" y="-139.617" font-family="sans" font-size="14.00">s</text> +</g> +<!-- sb1->sb2 --> +<g id="edge6" class="edge"><title>sb1->sb2</title> +<path fill="none" stroke="black" d="M275.016,-192.189C267.395,-183.507 257.435,-172.158 249.125,-162.69"/> +<polygon fill="black" stroke="black" points="250.487,-161.058 244.951,-157.934 247.33,-163.829 250.487,-161.058"/> +<text text-anchor="middle" x="267.5" y="-173.181" font-family="sans" font-size="8.00"> 3</text> +</g> +<!-- ab1 --> +<g id="node10" class="node"><title>ab1</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="305" cy="-143.317" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="305" y="-139.617" font-family="mono" font-size="14.00">aa</text> +</g> +<!-- sb1->ab1 --> +<g id="edge7" class="edge"><title>sb1->ab1</title> +<path fill="none" stroke="black" d="M291.449,-190.635C293.64,-183.149 296.318,-173.995 298.713,-165.807"/> +<polygon fill="black" stroke="black" points="300.807,-166.127 300.477,-159.779 296.776,-164.948 300.807,-166.127"/> +<text text-anchor="middle" x="301.5" y="-173.181" font-family="sans" font-size="8.00"> 3</text> +</g> +<!-- sb3 --> +<g id="node9" class="node"><title>sb3</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="279" cy="-79.7904" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="279" y="-76.0904" font-family="sans" font-size="14.00">s</text> +</g> +<!-- sb2->sb3 --> +<g id="edge9" class="edge"><title>sb2->sb3</title> +<path fill="none" stroke="black" d="M243.669,-128.047C249.939,-119.66 257.945,-108.952 264.751,-99.8496"/> +<polygon fill="black" stroke="black" points="266.478,-101.046 268.389,-94.9831 263.114,-98.5311 266.478,-101.046"/> +<text text-anchor="middle" x="262.5" y="-109.654" font-family="sans" font-size="8.00"> 2</text> +</g> +<!-- ab2 --> +<g id="node11" class="node"><title>ab2</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="207" cy="-79.7904" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="207" y="-76.0904" font-family="mono" font-size="14.00">aa</text> +</g> +<!-- sb2->ab2 --> +<g id="edge8" class="edge"><title>sb2->ab2</title> +<path fill="none" stroke="black" d="M226.706,-127.423C223.434,-119.679 219.38,-110.087 215.802,-101.62"/> +<polygon fill="black" stroke="black" points="217.686,-100.684 213.417,-95.9746 213.818,-102.319 217.686,-100.684"/> +<text text-anchor="middle" x="225.5" y="-109.654" font-family="sans" font-size="8.00"> 2</text> +</g> +<!-- eb --> +<g id="node12" class="node"><title>eb</title> +<ellipse fill="none" stroke="black" stroke-width="0" cx="279" cy="-16.2635" rx="27" ry="16.0303"/> +<text text-anchor="middle" x="279" y="-12.5635" font-family="mono" font-size="14.00">[]</text> +</g> +<!-- sb3->eb --> +<g id="edge10" class="edge"><title>sb3->eb</title> +<path fill="none" stroke="black" d="M279,-63.2645C279,-55.9222 279,-47.0305 279,-39.0293"/> +<polygon fill="black" stroke="black" points="281.1,-38.5712 279,-32.5712 276.9,-38.5712 281.1,-38.5712"/> +<text text-anchor="middle" x="282.5" y="-46.1269" font-family="sans" font-size="8.00"> 1</text> +</g> +</g> +</svg> |
