Closed cormacmchale closed 5 years ago
Initial thoughts: 1) Changes will have to be made to two things, the function converting from infix to postfix and by virtue of this.. a change will have to be made to the function that builds the NFA.
2) Probably I think that no changes will have to be made to the function that follows the states to build the regular expression so this should make things easier.
Upon inspection of the algorithm I think that the only change that will need to be made is to the NFA algorithm... the + operator will always follow a character so the shunt algorithm holds up for this, all that will need to be added is build the NFA correctly after encountering this operator
Turned out maybe to be as simple as this, more testing to be required to be certain
As suspected.. this is not fully implemented.. this is not regular expression matching as expected
On further testing it is the | operator that has now been affected by the changes made to the code, will have to inspect the code further and possibly change the logic in the function creating the NFA
Progress... By Making the accept state of NFA that has been popped of the stack point back to the initial state of the NFA the | operator is now working for some test cases. However I suspect this might not be the correct solution so more testing will need to be done.
After testing this solution has proven to be sturdy enough, hopefully it's correct
the plus operator must take precedence over the kleene star, to avoid a recursion error
I was wrong about the implementation and precedence.. back to the drawing board..
see above
This is my best solution so far, in so far as it now handles the expression (a.a+)* properly, however it is still not an optimal solution
After deliberations with my lecturer (Ian) there is a small issue in the logic of building up the regular expression. You may build up a circular reference in certain situations that will make you follow the empty string forever. My solution to the problem is to control the order the NFA will get built using the Precedence. It's not optimal or elegant but it will do in so far as I will need to put my energies into other projects
In order to add some extra work effort to the project I will have to add in some logic and handling for using the plus operator in the program, some research will have to be done