Project 3 Regular Expression Interpreter

Errata:

updated on 10/05: Outgoing edge count list in stats must be returned in lexicographic order

Introduction

In this project, you will write an OCaml module to implement NFAs and regular expressions.

Getting Started

Downloading

• Download the archive file p3.zip and extract its contents.

Along with files used to make direct submissions to the submit server ( submit.jar, .submit, submit.rb), you will find the following project files:

• Your OCaml program
  • nfa.ml
• Testing instructions:
  • README
• Ruby script to run public tests
  • test_all.rb

To test your implementation, you can execute the public tests from the command line by typing commands like ocaml public_RE_to_str.mlin the specific test folder under testing, or you can use the test_all.rbscript. Note that to use test_all.rb, you must first read README.

For this project you are allowed to use the library functions found in the Pervasives module loaded by default, as well as functions from the List and String modules.As in the previous project, you are not allowed to use imperative OCaml, except for the nextfunction to to generate new NFA state numbers. You will receive a 0 for any functions using restricted features we will be checking your code!

Project Description

Your job is to implement a module Nfathat includes an API for implementing both NFAs and regular expressions. The signature and starter implementation for the NFA module is provided. You may notchange the NFAsignature in any way, though your implementation may include more types and functions than are listed in the signature. The implementation contains a parser you can use to make it easier to test your implementation. We say more about the parser, below.

Part 1: NFAs

For the first part of this project, you will write a series of functions to implement NFAs using OCaml.

module type NFA =sigtype nfatype transition = int * char option * intval make_nfa : int -> int list -> transition list -> nfaval e_closure : nfa -> int list -> int listval move : nfa -> int list -> char -> int listval accept : nfa -> string -> boolval stats : nfa -> int * int * (int * int) list...end

Here are descriptions of the elements of this signature, and what you need to do to implement them:

• type nfa This is an abstract type representing NFAs. It is up to you to decide exactly how NFAs are implemented. Since the type is abstract, no client that uses your module will be able to see exactly how they are implemented.
• type transition = int * char option * int This is a (non-abstract) type weve made up for convenience to describe an NFA transition. In the NFAs for this project, states will simply be identified by number. Then (s0, Some c, s1) represents a transition from the state numbered s0 to the state numbered s1 , via an arc labeled with the character c . Notice that the character is optionalthe transition (s0, None, s1) represents an epsilon transition from s0 to s1 .
• make_nfa : int -> int list -> transition list -> nfa . This function takes as input the starting state, a list of final states, and a list of transitions, and returns an NFA. Again, it is up to you to decide exactly how NFAs should be implemented, but you probably do not need to do much more than track these three components (the starting state, final states, and transition list). As one example,

  let m = make_nfa 0 [2] [(0, Some 'a', 1); (1, None, 2)]

  sets mto be an NFA with start state 0, final state 2, a transition from 0 to 1 on character a, and an epsilon transition from 1 to 2.

• e_closure: nfa -> int list -> int list . This function takes as input an nfa and a list of states. The output will be a list of states (in any order, with no duplicates) that the NFA might be in making zero or more epsilon transitions, starting from the list of initial states given as an argument to e_closure. For example, letting m be the NFA above, e_closure would return the following:

  e_closure m [0] (* returns [0] *)e_closure m [1] (* returns [1;2] *)e_closure m [2] (* returns [2] *)e_closure m [0;1] (* returns [0;1;2] *)

• move : nfa -> int list -> char -> int list . This function takes as input an nfa, a list of initial states, and a character. The output will be a list of states (in any order, with no duplicates) that the NFA might be in after making one transition on the character, starting from one of the initial states given as an argument to move. For example, letting m be the NFA above, move would return the following:

  move m [0] 'a'(* returns [1] *)move m [1] 'a'(* returns [] *)move m [2] 'a'(* returns [] *)move m [0;1] 'a'(* returns [1] *)

  Notice that the NFA uses an implicit dead state. If sis a state in the input list and there are no transitions from son the input character, then all that happens is that no states are added to the output list for s.

• accept : nfa -> string -> bool . This function takes an NFA and a string, and returns true if the NFA accepts the string, and false otherwise. You will find functions in the String library to be helpful.
• stats : nfa -> int * int * (int * int) list . This function takes an NFA and returns a tuple containing information about the NFA. The tuple looks like this: (total number of states, number of final states, outgoing edge count list) The list is like a map of the number of outgoing edges of a state, to the number of states with that many outgoing edges. For example: (0,1) means that there is 1 state with 0 outgoing edges The list should contain values that are greater than 0, if there are no states that have 3 outgoing transitions, do not to put (3,0) in the list, we will assume that if its not in the list that the count is 0. stats counts only outgoing egdes.

  An example of this would look like:

  (3, 1, [(0,1);(1,2)])

  This NFA has 3 total states, 1 final state, 1 state with 0 outgoing transitions and 2 states with 1 outgoing transition

  Note: You need to be a bit careful whenever you combine NFA representations to be sure that state names (i.e., integers) dont conflict. You might use the following internal function as an aid in this process:

  • next : unit -> int Return a new integer, different from any values previously returned by next . (This function is defined on the OCaml slides.)

  Part 2: Regular Expressions

  The second part of this project is to implement regular expressions. The signature NFAcontains the following declarations:

  module type NFA =sig ...type regexp =Empty_String| Char of char| Union of regexp * regexp| Concat of regexp * regexp| Star of regexpval regexp_to_string : regexp -> stringval regexp_to_nfa : regexp -> nfa...end

  Here regexpis an user-defined OCaml variant datatype that represents regular expressions:

  • Empty_String represents the regular expression recognizing the empty string (not the empty set!). Written as a formal regular expression, this would be epsilon .
  • Char c represents the regular expression that accepts the single character c . Written as a formal regular expression, this would be c .
  • Union (r1, r2) represents the regular expression that is the union of r1 and r2 . For example, Union(Char 'a', Char'b') is the same as the formal regular expression a|b .
  • Concat (r1, r2) represents the concatenation of r1 followed by r2 . For example, Concat(Char 'a', Char 'b') is the same as the formal regexp ab .
  • Star r represents the Kleene closure of regular expression r . For example, Star (Union (Char 'a', Char 'b')) is the same as the formal regexp (a|b)*

  For this part of the project you need to implement the following:

  • regexp_to_string : regexp -> string takes a a regular expression and returns a string for the regular expression in the postfix notation. Postfix notation is a mathematical notation in which every operator follows all of its operands. For example, the infix expression (3 + (4 * 8)) + ((6 + 7)/5) is expressed as 3 4 8 * + 6 7 + 5 / +. Using the same idea for regular expressions, the infix regular expression ((a|b)*aba*)*(a|b)(a|b) can be represented as a b | * a b a * . . . * a b | a b | . .. You can do this as a postorder DFS traversal over the regexp data structure.
  • regexp_to_nfa : regexp -> nfa takes a regexp and returns an NFA that accepts the same language as the regular expression. Unlike project 2, as long as your NFA accepts the correct language, the structure of the NFA does not matter (since the NFA produced by regexp_to_nfa will only be tested by seeing which strings it accepts).

  Provided: Regular Expressions Parser

  In the starter files we have provided code that parses strings into regexpvalues. In particular, it implements the following elements of the signature:

  module type NFA =sig ...val string_to_regexp : string -> regexpval string_to_nfa : string -> nfaexception IllegalExpression of stringend

  where

  • string_to_regexp : string -> regexp takes a string for a regular expression, parses the string, and outputs its equivalent regexp . If the parser determines that the regular expression has illegal syntax, it will raise an IllegalExpression exception.
  • string_to_nfa : string -> nfa takes a string for a regular expression, parses the string, converts it into a regexp , and transforms it to an nfa, using your regexp_to_nfa function. As such, for this functiont to work, your regexp_to_nfa function must be working.

  Notes about the grammar for regular expressions implemented by the provided parser:

  • The regular expressions can contain only ( , ) , | , * , a, b, , z and E (for epsilon).
  • Note that the precedence for regular expressions are as follows, from highest to lowest:
    
    

    Precedence	Operator	Description
    Highest	( )	parentheses
    |	*	closure
    v	.	concatenation
    Lowest	|	union

  • Note that all the binary operators are right associative .
  • Your function should throw an IllegalExpression exception for invalid regular expressions.

  Some examples of regular expressions and their equivalent regexpdata type are listed in the following table:

  String Input	regexp Output	String Output
  a	Char 'a'	a
  a|b	Union(Char 'a',Char 'b')	a b |
  ab	Concat(Char 'a',Char 'b')	a b .
  aab	Concat(Char 'a',Concat(Char 'a',Char 'b'))	a a b . .
  (a|E)*	Star(Union(Char 'a',Empty_String))	a E | *
  (a|E)*(a|b)	Concat(Star(Union(Char 'a',Empty_String)),Union(Char 'a',Char 'b'))	a E | * a b | .