Beginners programming challenge #27

[cgroza]

Welcome to the 27th Beginners programming challenge.

Because I have a bit of free time, I decided to post this programming challenge early.
This means it will be a bit more complicated and will probably take more work to achieve.

Task
You will have to implement a small regular expression engine that imitates a small subset of the Perl style regular expressions. It will only have to do matching, no need for replace or other complicated features.
You will then use it in a program that will take input and print the text that was first matched by the regular expression. Hopefully, this will introduce you to regular expressions and understand how such an engine works.
These are the operators you will have to implement: * . $ ^ ? + and of course normal letters.

Cookie points

Cookie points will be awarded for the following extras:

1. Implementing the | (or) operator.
2. Implementing character classes (annotated with []).
3. Take input from stdin if a file is not supplied so piping is possible on the command line.
4. Printing every match and not only the first one.

Disqualified Entries:

Any overly obfuscated code will be immediately disqualified without account for programmers skill. Please remember that these challenges are for beginners and therefore the code should be easily readable and well commented.

Any non-beginner entries will not be judged. Please use common sense when posting code examples. Please do not give beginners a copy paste solution before they have had a chance to try this for themselves.


Assistance:

If you require any help with this challenge please do not hesitate to come and chat to the development focus group. We have a channel on irc.freenode.net #ubuntu-beginners-dev
Or you can pm me

Have fun,
Happy coding

cgroza

[Tony Flury]

Great Challenge - I am not a beginner but I might have a go at this, and see how i get on. Any submission from me will be in Python though - and i promise not to use the re module.

[cgroza]

Great Challenge - I am not a beginner but I might have a go at this, and see how i get on. Any submission from me will be in Python though - and i promise not to use the re module.

If you think you are not a beginner and you think it would be unfair for other users, you could post your solution after the winner is announced. And yes, the users are not allowed to use libraries that are directly related with regular expression engines, the goal is to implement it themselves .

[Tony Flury]

No intention of posting my solution until the winner is announced - although right now I am stuck - so unless i can solve that - i wont be able to post anything.

[Lux Perpetua]

In my opinion, the level of this problem is more intermediate than beginner. I'd love to be pleasantly surprised by a bunch of beginners rising to the challenge, though.

[CptPicard]

Yeah, this really is more intermediate, although some undergrad CS education on grammars, formal languages and automata should provide one with references to literature where this is handled. Any ad hoc solutions are almost certainly wrong.

[Odexios]

Just to make sure I got the meaning of "it will print the text that was first matched by the regular expression".

1) If the regex is ".*", should it always match anything and print nothing?

2) If the regex is ".*at", and the string in input is "Matt is at the gym", it should match "Mat", right?

[Tony Flury]

Just to make sure I got the meaning of "it will print the text that was first matched by the regular expression".

1) If the regex is ".*", should it always match anything and print nothing?

This should print the whole input string, as the whole string matches the regex.

2) If the regex is ".*at", and the string in input is "Matt is at the gym", it should match "Mat", right?

I would have assumed that all quantifiers are greedy so in you example the matching string would be : "Matt is at" (as that is longer that "Mat"

[Odexios]

This should print the whole input string, as the whole string matches the regex.


I would have assumed that all quantifiers are greedy so in you example the matching string would be : "Matt is at" (as that is longer that "Mat"

Ok; so I guess that printing "the text that was first matched" means that when more than one line is found, the engine should work only on the first line with a match.

[Barrucadu]

Ok; so I guess that printing "the text that was first matched" means that when more than one line is found, the engine should work only on the first line with a match.

"." does not match newlines, so running .* on "hello\nworld" will have two matches: ["hello", "world"], and so "hello" should be printed.