Win a copy of Spring in Action (5th edition) this week in the Spring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Java compiler regular expression related issue  RSS feed

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In this assignment, you will work on regular expression. For simplicity, we will assume that there is a fixed set of regular expressions. We will not consider out of these. But you must not use any built-in method or package in your implementation. If you need any method, you will write that.In Regular Expression (RE), '*' means occurrence of zero of more characters, '+' indicates happening of one or more characters, '?'  means only once or not at all occurrence, '[ ]' indicates happening of inclusive characters, '^' indicates that next characters will not be used in the pattern, '[a-d]{3}' indicates that valid string will be exactly of  length 3 inclusively using a, b, c, d. The following table contains a fixed set of RE that will be used in our assignment.


User will be asked first to input an integer value n followed by n lines of regular expressions. Then user will be asked to input another integer value m followed by m lines of text string. Your job is to say 'YES' with index of RE if the text string is valid according to any of given regular expressions. Otherwise, say 'NO' with zero index. I repeat, you must not use any built-in regular expression method or package.But you can take help from Cloud.



Input:
2
ab*c*d
a*b(cd)+e?f
3
acccd
abbbbbcccc
bcdcdef

Output:
YES, 1
NO, 0
YES, 2


Input:
3
[a-c]{3}cab+(da)*f
db*a[^def]{2}gh
def[k-p]*p+
5
defkmnpmpp
acbcabbf
pqrstdd
dbaabggh
dbbbbamkgh
Output:
YES, 3
YES, 1
NO, 0
NO, 0
YES, 2

I tried like below, but Cant proceed. What should I do now?




 
Marshal
Posts: 61723
193
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Are you supposed to write a program to test those regexes or are you supposed to work them out by hand? Please explain how you are panning that code? Are you supposed to program a regular expression finite state automaton ;(=FSA)? Yes, it would appear you are. What sort of course is this? Compiler writing?

I think you are going to have to go back to first principles. Start by working out how towrite get n lines from the keyboard. For reasons explained here, you will get your inputs out of phase the way you are reading. By the way: please tell us what you have been taught Scanner#nextLine() does. I suggest you start by getting inputs, and test those inputs until you can print things like this:-

Your regexes are in this array:- [ab*c*d, a*b(cd)+e?f]
You are testing them with these Strings:- [acccd, abbbbbcccc, bcdcdef]

Look for the Arrays.toString() method which will probably enable you to get that output.
Get that working, then you will have to think how you are going to create your FSA.

Never use == true or == false which are both poor style and error‑prone because you might write = by mistake.
Never if (b == true)...
Always if (b)...
Never if (b == false)...
Always if (!b)...

As I said, get your input working, then we can consider your FSA later.
 
Bartender
Posts: 19976
95
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's unclear what the exact goal of this exercise is - it sounds like the goal, in simple words, is to create a (limited) regular-expression pattern matcher from first principles. That is, reproduce a subset of the actions of regex processors without resorting to any existing regex functions.

This can be a fun thing to do, actually. And it's worth noting that the venerable Unix grep utility program handles the problem by compiling regexes into what are essentially bytecodes and using a Finite State Machine to process against them. You can see a residue of this in that the built-in regex processors in languages like Java and Python break recommend using methods where the compiling of a regex and the application of that compiled regex against data are two discrete functions.

So you can consider grep to be in a sense, an ancient relative of Java, except that the "JVM" instruction set is oriented towards pattern matching.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!