webovyformular.dat_typy
Class Retezec

java.lang.Object
  webovyformular.dat_typy.Retezec

public class Retezec
extends java.lang.Object

Description:

Třída slouží pro práci se seznamem Znaku, tedy pro objekty typu ArrayList <Znak>. Nemá žádný konstruktor a obsahuje pouze statické třídy.

Copyright: Copyright (c) 2005

Constructor Summary

Retezec()

Method Summary

static java.util.HashSet<java.util.ArrayList<Znak>>	first(java.util.ArrayList<Znak> retezec, java.util.HashMap<Znak,java.util.HashSet<java.util.ArrayList<Znak>>> pravidla, int k) Metoda first vypočítá množinu FIRST_k zadaného retezce.
static java.util.HashSet<java.util.ArrayList<Znak>>	follow(Znak neterm, Gramatika gramatika, int k) Metoda follow vypočítá množinu FOLLOW_k pro zadaný neterminál.
static java.util.ArrayList<Znak>	toRetezecZnaku(java.util.HashSet<Znak> neterminaly, java.util.HashSet<Znak> terminaly, java.lang.String str) Metoda toRetezecZnaku převede vstupní řetězec String obsahující jména symbolů na odpovídající seznam Znaků typu ArrayList <Znak>.Tento seznam je vrácen na výstup.
static java.lang.String	toString(java.util.ArrayList<Znak> retezec) Metoda toSting převede retezec na řetězec String, který bude obsahovat jména Znaků v retezci.
static java.lang.String	toString(java.util.HashSet<java.util.ArrayList<Znak>> setRetezcu) Metoda toString převede množinu setRetezcu na řetězec String.
static java.util.ArrayList<Znak>	zretez(java.util.ArrayList<Znak> a, java.util.ArrayList<Znak> b) Metoda zretez zřetezí dva řetězce (seznamy) zadané na vstupu.
static java.util.ArrayList<Znak>	zretez(java.util.ArrayList<Znak> a, java.util.ArrayList<Znak> b, int k) Metoda zretez zřetězí dva zadané řetězce Znaků.
static java.util.HashSet<java.util.ArrayList<Znak>>	zretez(java.util.ArrayList<Znak> retA, java.util.HashSet<java.util.ArrayList<Znak>> setB) Metoda zretez zřetězí řetězec Znaků s prvky množiny obsahující řetězce Znaků.
static java.util.HashSet<java.util.ArrayList<Znak>>	zretez(java.util.HashSet<java.util.ArrayList<Znak>> setA, java.util.HashSet<java.util.ArrayList<Znak>> setB) Metoda zretez zřetězí prvky množin zadaných na vstupu.
static java.util.HashSet<java.util.ArrayList<Znak>>	zretez(java.util.HashSet<java.util.ArrayList<Znak>> setA, java.util.HashSet<java.util.ArrayList<Znak>> setB, int k) Metoda zretez zřetězí prvky množin zadaných na vstupu.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Retezec

public Retezec()

Method Detail

toString

public static java.lang.String toString(java.util.ArrayList<Znak> retezec)

Metoda toSting převede retezec na řetězec String, který bude obsahovat jména Znaků v retezci.

Parameters:

retezec - ArrayList - řetězec Znaků

Returns:

String - Stringová reprezentace retezce

toString

public static java.lang.String toString(java.util.HashSet<java.util.ArrayList<Znak>> setRetezcu)

Metoda toString převede množinu setRetezcu na řetězec String. Výsledný String bude obsahovat nazačátku znak { následovaný Stringovou reprezentací jednotolivých řetězců ze setRetezcu oddělených znakem , a bude ukončený znakem }.

Parameters:

setRetezcu - HashSet - množina řetězců Znaků

Returns:

String - Stringová reprezentace

zretez

public static java.util.ArrayList<Znak> zretez(java.util.ArrayList<Znak> a,
                                               java.util.ArrayList<Znak> b)

Metoda zretez zřetezí dva řetězce (seznamy) zadané na vstupu. Prvky druhého řetězce se vloží v nezměněném pořadí za poslední prvek prvního řetězce. Je-li prvním Znakem prvního vstupního řetězce epsilon, je vrácen druhý vstupní řetězec. Je-li prvním Znakem druhého vstupní řetězec epsilon, je vrácen první vstupní řetězec.

Parameters:

a - ArrayList - první vstupní řetězec Znaků

b - ArrayList - druhý vstupní řetězec Znaků

Returns:

ArrayList - výsledný řetězec Znaků vzniklý zřetězením řetězců a a b

zretez

public static java.util.HashSet<java.util.ArrayList<Znak>> zretez(java.util.HashSet<java.util.ArrayList<Znak>> setA,
                                                                  java.util.HashSet<java.util.ArrayList<Znak>> setB)

Metoda zretez zřetězí prvky množin zadaných na vstupu. Prvky výsledné množiny jsou takové řetězce, jejichž první částí je prvek množiny setA a zbývající částí je prvek množiny setB.
Příklad:
setA = {abc,def}
setB = {uvw,xyz}
setAB = {abcuvw,abcxyz,defuvw,defxyz}
Je-li alespoň jedna ze vstupních množin prázdná, je výsledná množina rázdná.

Parameters:

setA - HashSet - množina řetězců Znaků

setB - HashSet - množina řetězců Znaků

Returns:

HashSet - výsledná množina řetězců Znaků

zretez

public static java.util.HashSet<java.util.ArrayList<Znak>> zretez(java.util.ArrayList<Znak> retA,
                                                                  java.util.HashSet<java.util.ArrayList<Znak>> setB)

Metoda zretez zřetězí řetězec Znaků s prvky množiny obsahující řetězce Znaků. Výsledná množina obsahuje takové řetězce, jejich první částí je zadaný řetězec retA a zbývající částí je některé z prvků množiny setB zadané na vstupu.
Příklad:
retA = abc
setB = {uvw,xyz}
setAB = {abcuvw,abcxyz}

Parameters:

retA - ArrayList - řetězec Znaků

setB - HashSet - množina řetězců Znaků

Returns:

HashSet - výsledná množina řetězců Znaků

zretez

public static java.util.ArrayList<Znak> zretez(java.util.ArrayList<Znak> a,
                                               java.util.ArrayList<Znak> b,
                                               int k)
                                        throws NekladnyParamException

Metoda zretez zřetězí dva zadané řetězce Znaků. Vznikne-li zřetězením řetězců a a b řetězec delší než k, je výsledný řetězec zkrácen na délku k.
Příklad:
a = abc
b = xyz
k = 4
vysledny_retezec = abcx

Parameters:

a - ArrayList - první řetězec Znaků

b - ArrayList - druhý řetězec Znaků

k - int - parametr k

Returns:

ArrayList - výsledný řetězec Znaků délky nejvýše k

Throws:

NekladnyParamException - když je parametr k nekladné číslo

zretez

public static java.util.HashSet<java.util.ArrayList<Znak>> zretez(java.util.HashSet<java.util.ArrayList<Znak>> setA,
                                                                  java.util.HashSet<java.util.ArrayList<Znak>> setB,
                                                                  int k)
                                                           throws NekladnyParamException

Metoda zretez zřetězí prvky množin zadaných na vstupu. Prvky výsledné množiny jsou takové řetězce délky maximálně k, jejichž první částí je prvek množiny setA a zbývající částí je prvek množiny setB.
Příklad:
setA = {abc,def}
setB = {uvw,xyz}
k = 5 setAB = {abcuv,abcxy,defuv,defxy}
Je-li alespoň jedna ze vstupních množin prázdná, je výsledná množina prázdná.

Parameters:

setA - HashSet - množina řetězců Znaků

setB - HashSet - množina řetězců Znaků

k - int - parametr k

Returns:

HashSet - výsledný množina řetězců Znaků délky nejvýše k

Throws:

NekladnyParamException - když je parametr k nekladné číslo

toRetezecZnaku

public static java.util.ArrayList<Znak> toRetezecZnaku(java.util.HashSet<Znak> neterminaly,
                                                       java.util.HashSet<Znak> terminaly,
                                                       java.lang.String str)
                                                throws ZnakyNerozeznanyException,
                                                       ParamPrazdnyStringException

Metoda toRetezecZnaku převede vstupní řetězec String obsahující jména symbolů na odpovídající seznam Znaků typu ArrayList <Znak>.Tento seznam je vrácen na výstup.

Parameters:

neterminaly - HashSet - množina neterminálů

terminaly - HashSet - množina terminálů

str - String - řetězec, který má být převeden na seznam Znaků

Returns:

ArrayList - výstupní seznam Znaků

Throws:

ZnakyNerozeznanyException - když zadaný String obsahuje podřetězec, který není jméno terminálu ani neterminálu a ani jmenoEps

ParamPrazdnyStringException - když vstupní řetězec je prázdný nebo obsahuje pouze řetězec prázdných znaků.

first

public static java.util.HashSet<java.util.ArrayList<Znak>> first(java.util.ArrayList<Znak> retezec,
                                                                 java.util.HashMap<Znak,java.util.HashSet<java.util.ArrayList<Znak>>> pravidla,
                                                                 int k)
                                                          throws NekladnyParamException

Metoda first vypočítá množinu FIRST_k zadaného retezce. Výsledná množina obsahuje řetězce terminálů délky maximálně k, na které se může retezec přepsat za použití přepisovacích pravidel.

Parameters:

retezec - ArrayList - řetězec Znaků

pravidla - HashMap - pravidla gramatiky

k - int - parametr k

Returns:

HashSet - množina řetězců Znaků (terminálů)

Throws:

NekladnyParamException - když parametr k není kladné číslo

follow

public static java.util.HashSet<java.util.ArrayList<Znak>> follow(Znak neterm,
                                                                  Gramatika gramatika,
                                                                  int k)
                                                           throws NekladnyParamException

Metoda follow vypočítá množinu FOLLOW_k pro zadaný neterminál. Ve výsledné množině jsou všechny řetězce délky maximálně k takové, které se mohou po použití některých pravidel gramatiky vyskytovat bezprostředně vpravo od zadaného neterminálu.
Popis algoritmu:
Je dána gramatika G = (N,E,P,S).
Postupně počítáme hodnoty:
FO_1(A) pro všechny A z N,
FO_2(A) pro všechny A z N,
...
FO_k(A) pro všechny A z N

Při výpočtu FO_i(A) postupujeme následovně:
1. FO_i(S) := {eps} pro počáteční symbol S,
FO_i(A) := "prázdná množina" pro ostatní neterminály

2. Pro každé pravidlo tvaru:
B -> pAq z P, kde p,q jsou řetězce a q != eps
FO_i(A) = FO_i(A) "sjednoceno s" [(FI_i(q)-{eps}) (+)_i FO_(i-1)(B)]

3. opakuj {
pro každé pravidlo tvaru:
B -> pAq z P, kde p,q jsou řetězce a (q == eps nebo eps je prvkem FI_1(q))
FO_i(A) := FO_i(A) "sjednoceno s" FO_i(B)
}dokud se nedosáhne pevného bodu

Parameters:

neterm - Znak - neterminál

pravidla - HashMap - množina pravidel

pocatek - Znak - počáteční neterminál gramatiky

k - int - parametr k

Returns:

HashSet - množina FOLLOW_k pro neterminál neterm

Throws:

NekladnyParamException - když parametr k je nekladné číslo