---

Er der nogle der har erfaringer med java.util.regex?

Mit problem er flg.:

Jeg har et streng der indeholder elementer af forskellig type. Disse
type kan vaere rekursive, f.eks.:

expr ::= expr + expr | int

det vil jo sige at strengen baade kan se ud som 2+2 eller 2+2+2+2 ...

Hvordan faar jeg matchet dette i java?

Med venlig hilsen
Christoffer Magnussen

---

Christoffer Magnussen wrote:

> Jeg har et streng der indeholder elementer af forskellig type. Disse
> type kan vaere rekursive, f.eks.:

"+" (plus) matcher foranstående udtryk én eller flere gange. F.eks.:
(abc)+
- matcher "abc", "abcabc" og "abcabcabc".
"*" (stjerne) matcher nul eller flere gange. - Med en operator imellem,
skal du muligvis bruge noget i retning af:
abc(\+abc)*
- som vil matche:
"abc", "abc+abc" og "abc+abc+abc" (men ikke "abcabc").

M.v.h.

Jonathan

--
Nyt alternativ til egen server: JSP Enterprise hotel med adgang til
Enterprise Java Beans, egen Java Virtual Machine og egen IP-adresse
(giver mulighed for eget SSL-certifikat).
http://www.jsp-hotel.dk/

---

Christoffer Magnussen <stoffer@daimi.au.dk> writes:

> Jeg har et streng der indeholder elementer af forskellig type. Disse
> type kan vaere rekursive, f.eks.:
>
> expr ::= expr + expr | int
>
> det vil jo sige at strengen baade kan se ud som 2+2 eller 2+2+2+2 ...
>
> Hvordan faar jeg matchet dette i java?

Hvis typen kan være rekursiv og du har flere definitioner, kan du
formentlig ikke lave det fornuftigt med regulære udtryk. Du antyder
ovenfor at du skal lave noget der kan regne udtryk ud - det kræver
normalt mere end regulære udtryk kan klare.

I "gamle dage" ville man bruge flex/bison i C til at generere
skeletkoden med - konceptet er helt sikkert porteret til Java, men
spørgsmålet er hvad opgaven lægger op til?

--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn

---

Thorbjoern Ravn Andersen wrote:
> Christoffer Magnussen <stoffer@daimi.au.dk> writes:
>
>
>>Jeg har et streng der indeholder elementer af forskellig type. Disse
>>type kan vaere rekursive, f.eks.:
>>
>>expr ::= expr + expr | int
>>
>>det vil jo sige at strengen baade kan se ud som 2+2 eller 2+2+2+2 ...
>>
>>Hvordan faar jeg matchet dette i java?
>
>
> Hvis typen kan være rekursiv og du har flere definitioner, kan du
> formentlig ikke lave det fornuftigt med regulære udtryk. Du antyder
> ovenfor at du skal lave noget der kan regne udtryk ud - det kræver
> normalt mere end regulære udtryk kan klare.
>
> I "gamle dage" ville man bruge flex/bison i C til at generere
> skeletkoden med - konceptet er helt sikkert porteret til Java, men
> spørgsmålet er hvad opgaven lægger op til?
>
Jeg er ikke helt sikker på, hvad du mener med flere definitioner.
Der skal ikke være nogen form for gensidig rekursivitet. Udtrykket kunne
skrives som:

expr::= int | expr + expr | expr - expr | expr / expr | expr * expr
hvor int, +, -, / og * er terminaler og expr er den eneste nonterminal

Jeg har forsøgt mig en lille smule med en StringTokenizer der kan dele
udtrykket op, men kan ikke helt gennemskue hvordan jeg kan få det til at
virke.

mvh
Christoffer

---

Stoffer <stoffer@daimi.au.dk> writes:

> expr::= int | expr + expr | expr - expr | expr / expr | expr * expr
> hvor int, +, -, / og * er terminaler og expr er den eneste
> nonterminal

Det lyder jo simpelt. Må man spørge hvad du skal bruge det til?

> Jeg har forsøgt mig en lille smule med en StringTokenizer der kan dele
> udtrykket op, men kan ikke helt gennemskue hvordan jeg kan få det til
> at virke.

Hvad er det du skal?

--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn

---

Thorbjoern Ravn Andersen wrote:
> Stoffer <stoffer@daimi.au.dk> writes:
>
>
>>expr::= int | expr + expr | expr - expr | expr / expr | expr * expr
>>hvor int, +, -, / og * er terminaler og expr er den eneste
>>nonterminal
>
>
> Det lyder jo simpelt. Må man spørge hvad du skal bruge det til?
>
>
>>Jeg har forsøgt mig en lille smule med en StringTokenizer der kan dele
>>udtrykket op, men kan ikke helt gennemskue hvordan jeg kan få det til
>>at virke.
>
>
> Hvad er det du skal?
>
Ja, det må du da. Jeg skal finde ud af om en string er en
'well-formed-formula' altså et gyldigt logisk udtryk. Herefter er det
meningen at udtrykkes skal evalueres, og evt at der skal laves
sandhedstabeller.

Jeg har altså flg. udtryk:

wff ::= CHAR | NOT wff | wff AND wff |
wff OR wff | wff -> wff | wff <-> wff

hvor CHAR (som jo bliver til en boolean), NOT, AND, OR, -> og <-> er
terminaler.

Men før jeg kan evaluere udtrykket ville det jo være rart at få
bekræftet om det er en wff, det er tale om

/stoffer

---

Stoffer <stoffer@daimi.au.dk> writes:

> Jeg har altså flg. udtryk:
>
> wff ::= CHAR | NOT wff | wff AND wff |
> wff OR wff | wff -> wff | wff <-> wff

Den passer dårligt til regulære udtryk.

> Men før jeg kan evaluere udtrykket ville det jo være rart at få
> bekræftet om det er en wff, det er tale om

Skriv en parser til at lave det om til tokenformat, som du så
evaluerer. Parseren skal så fejlmelde hvis det ikke er velformet.

Af denne størrelse, er det til at overskue at lave en LL(1) parser.
--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn

---

Thorbjoern Ravn Andersen wrote:

> Stoffer <stoffer@daimi.au.dk> writes:
>
> > Jeg har altså flg. udtryk:
> >
> > wff ::= CHAR | NOT wff | wff AND wff |
> > wff OR wff | wff -> wff | wff <-> wff
>
> Den passer dårligt til regulære udtryk.

Men det kan vel godt lade sig gøre, hvis vi fjerner venstrerekursion:

wff ::= CHAR
| NOT wff
| CHAR AND wff
| CHAR OR wff
| CHAR IMPL wff
| CHAR BIIMPL wff

Så kan det vel skrives som:

(CHAR
((AND CHAR)* | (OR CHAR)* | (-> CHAR)* | (<-> CHAR)* )*
| NOT
(CHAR
((AND CHAR)* | (OR CHAR)* | (-> CHAR)* | (<-> CHAR)* )*

Er det ikke korrekt?

Ulrik Magnusson

PS: Jeg ville nok også lave en "recursive descent parser" - om ikke
andet er muligheden for ordentlige fejlmeldinger noget bedre:


Token token; // class Token{ int type, offset; String value; }
Lexer lexer; // interface Lexer{ Token nextToken(); }
Token lastSuccessToken;

boolean matchWFF( )
{
boolean ch = matchTokenType( CHAR );
if( !ch ) // NOT wff
{
if( matchTokenType( NOT) )
{
return matchWFF();
}
return false;
}
else //CHAR ..
{
if( matchTokenType(AND) ||
matchTokenType(OR) ||
matchTokenType(IMPL) ||
matchTokenType(BIIMPL) ||
)
{
return matchWff();
}
}
return true;// en enkelt CHAR
}

boolean matchTokenType( int type )
{
if( token != null && token.type == type )
{
lastSuccessToken = token;
token = lexer.nextToken();
return true;
}
return false;
}

void match( String str )
{
lexer = new Lexer( str );
token = lexer.nextToken();
if( matchWFF() )
{
// ok
}
else
{
// forkert syntaks ca. ved lastSuccessToken
}
}

Sikke da et langt PS..

---

"Thorbjoern Ravn Andersen" <thunderbear@bigfoot.com> skrev i en meddelelse
news:kk65w9n8rc.fsf@mimer.null.dk...
> Christoffer Magnussen <stoffer@daimi.au.dk> writes:
>
> > Jeg har et streng der indeholder elementer af forskellig type. Disse
> > type kan vaere rekursive, f.eks.:
> >
> > expr ::= expr + expr | int
> >
> > det vil jo sige at strengen baade kan se ud som 2+2 eller 2+2+2+2 ...
> >
> > Hvordan faar jeg matchet dette i java?
>
> Hvis typen kan være rekursiv og du har flere definitioner, kan du
> formentlig ikke lave det fornuftigt med regulære udtryk. Du antyder
> ovenfor at du skal lave noget der kan regne udtryk ud - det kræver
> normalt mere end regulære udtryk kan klare.
>
> I "gamle dage" ville man bruge flex/bison i C til at generere
> skeletkoden med - konceptet er helt sikkert porteret til Java, men
> spørgsmålet er hvad opgaven lægger op til?

Og i dag vil man bruge JavaCC - se evt
http://www.webgain.com/products/java_cc
Og ja, den er gratis.

Men det kan da godt være det er lidt overkill til opgaven.

>
> --
> Thorbjørn Ravn Andersen
> http://homepage.mac.com/ravn

Niels Ull Harremoës