Skip to content

Latest commit

 

History

History
51 lines (33 loc) · 2.29 KB

README.md

File metadata and controls

51 lines (33 loc) · 2.29 KB
Raw

Grephy

A python script which emulates grep.

  • As a note to begin, this is a brute force method for recognizing a string based on an NFA. In no way shape or form is this the most efficient way of making grep.

  • The project uses the following imports:

argparse, re, networkx, ConfigParser, and io

Please run pip install [PACKAGE] to get these files to run my code.

  • To run the file, do python grephy.py [-n NFA_FILE] [-d DFA_FILE] REGEX FILE. Note: Please wrap your regex in "quotes".

  • The REGEX will recognize characters, the kleene star (*), the or operator (+), and parenthesis.

-n and -d are optional parameters which respectively output the NFA or DFA to a txt file in the format of:

{node, node transitioning to, {transition: transition character} }

All that you need to do is specify what file you want the NFA or DFA to output to.

  • Here is an example of an NFA that will be printed for the regex abc

(0, 1, {'transition': 'a'}) (1, 2, {'transition': 'b'}) (2, 3, {'transition': 'c'})

  • For a DFA, the transitions are a little out of order, however, they still produce a valid DFA. (0, 1, {'transition': ['c', 'b']}) (0, 2, {'transition': 'a'}) (1, 1, {'transition': ['a', 'c', 'b']}) (2, 3, {'transition': ['a', 'c']}) (2, 4, {'transition': 'b'}) (3, 3, {'transition': ['a', 'c', 'b']}) (4, 5, {'transition': ['a', 'b']}) (4, 6, {'transition': 'c'}) (5, 5, {'transition': ['a', 'c', 'b']})

  • The output will be printed either in a list to the console of all of the words of the test file which match. If there are no matches, the program will print "No Matches."

  • There are a few test files which exist in the testFiles/ folder. Here are a few descriptions:

    • pride.txt : Contains the Wikipedia plot summary for the book 'Pride and Prejudice' by Jane Austen.
    • fresh.txt : Contains the lyrics to the song "The Fresh Prince of Belair"
    • roster.txt: Contains the roster to the Pittsburgh Steelers Football Team.

  • There are also nfaExample.txt and dfaExample.txt files which show what an outputted DFA and NFA look like.

  • testing.txt in testFiles which shows sample regex inputs on testFiles and what output that you should recieve.

If there are any questions, email me at [email protected]