Ask Programming Language Expert

Assignment - Haskell Program for Regular Expression Matching

Your assignment is to modify the slowgrep.hs Haskell program presented in class and the online notes, according to the instructions below. You may carry out this assignment in groups of at most 3 students, with the number of items required to complete dependent on group size.

Glushkov Algorithm

You are to modify the matching logic of slowgrep.hs to use the Glushkov NFA method of regular expression search rather than the simpleton search method presented initially. Your modified program should be called hgrep.hs and implement precisely the same command line interface as slowgrep.hs.

Search vs. Match

You are to modify your program to search within lines rather than just find lines that match the regular expression. Thus a line should be selected if there is a match to the regular expression anywhere on the line.

Additional Regular Expression Features

For each of the components identified below, you are to perform the following tasks:

Extend the definition of the RE data type (as necessary) to incorporate the new feature.

Extend the regular expression parser to correctly parse instances of the new feature into the correct AST structures.

Extend the matching logic to correctly deal with the feature.

Depending on your group size you complete additional tasks as follows:

For a student working alone or in groups of 2, you and your group complete Features 1 through 4.

For students working in groups of 3, you and your group complete Features 1 through 5.

Feature 1: Escaped Metacharacters

The initial definition of Haskell regular expressions did not permit matches to metacharacters such as *, (, ), or |. Instead these characters were reserved for their role as metacharacters to indicate particular types of regular expression formation.

In this part, you are to extend the RE system to use the backslash (\) as an escape metacharacter. When the backslash metacharacter is used, the following character loses its meaning as a metacharacter and is instead interpreted as a literal character, instead. Thus the regular expression "ab\*d" stands for the regular expression which matches the 4-character string "ab*d". Backslashes themselves can be escapsed; the regular expression \\\\\\ stands for the 3-character string \\\.

Feature 2: Any Metacharacter

In this part, you are to extend the RE system to use the "." (period or dot) character as a metacharacter that means "any character". For example, , the regular expression a.e will match 3-character strings so long as they begin a and end with e, with any character in between them.

Feature 3: Option Metacharacter

In this part, you are to extend the RE system to use "?" (question mark) as a metacharacter that means zero or one occurrences of the previous item. For example, the regular expression "ab?c" matches both the strings "abc" and "ac". The option metacharacter should have the same precedence and associativity as the "*" metacharacter.

Feature 4: Plus Metacharacter

In this part, you are to extend the RE system to use "+" (plus sign) as a metacharacter that means one or more occurrences of the previous item. For example, the regular expression "ab+c" matches both the strings "abc", "abbc", abbbc and so on. The plus metacharacter should have the same precedence and associativity as the "*" metacharacter.

Feature 5: Character Classes

In this part, you are to extend the RE system to include character classes with the following syntax:

::= ("[" | "[^") "]"

::= { | "-" }

::= | "\"

A character class matches any single character in the class. A range is a set of consecutive characters according to their Unicode codepoint values. If the opening delimiter is "[^", the class is negated, that is, it consists of all characters not explicitly listed.

Attachment:- Assignment Files.rar

Programming Language, Programming

  • Category:- Programming Language
  • Reference No.:- M93110187

Have any Question? 


Related Questions in Programming Language

Task - hand execution of arraysoverviewin this task you

Task - Hand Execution of Arrays Overview In this task you will demonstrate how arrays work by hand executing a number of small code snippets. Instructions Watch the Hand Execution with Arrays video, this shows how to ste ...

Assignment - proposal literature review research method1

Assignment - Proposal, Literature Review, Research Method 1. Abstract - Summary of the knowledge gap: problems of the existing research - Aim of the research, summary of what this project is to achieve - Summary of the a ...

Question 1 what is hadoop explaining hadoop 2 what is

Question: 1. What is Hadoop (Explaining Hadoop) ? 2. What is HDFS? 3. What is YARN (Yet Another Resource Negotiator)? The response must be typed, single spaced, must be in times new roman font (size 12) and must follow t ...

Extend the adworks applicationi add dialogs to allow the

Extend the AdWorks application I. Add Dialogs to allow the user to Add, Edit, Read and Delete a Customer and refresh the view accordingly. 1. The user should be able to select a specific customer from the DataGrid and cl ...

Task silly name testeroverviewcontrol flow allows us to

Task: Silly Name Tester Overview Control flow allows us to alter the order in which our programs execute. Building on our knowledge of variables, we can now use control flow to create programs that perform more than just ...

Task arrays and structsoverviewin this task you will

Task: Arrays and Structs Overview In this task you will continue to work on the knight database to help Camelot keep track of all of their knights. We can now add a kingdom struct to help work with and manage all of the ...

Assignment - haskell program for regular expression

Assignment - Haskell Program for Regular Expression Matching Your assignment is to modify the slowgrep.hs Haskell program presented in class and the online notes, according to the instructions below. You may carry out th ...

Php amp session managment assignment -this assignment looks

PHP & SESSION MANAGMENT ASSIGNMENT - This assignment looks at using PHP for creating cookies and session management. Class Exercise - Web Project: Member Registration/Login This exercise will cover adding data connectivi ...

Structs and enumsoverviewin this task you will create a

Structs and Enums Overview In this task you will create a knight database to help Camelot keep track of all of their knights. Instructions Lets get started. 1. What the topic 5 videos, these will guide you through buildi ...

Assignmentquestion onegiving the following code snippet

Assignment Question One Giving the following code snippet. What kind of errors you will get and how can you correct it. A. public class HelloJava { public static void main(String args[]) { int x=10; int y=2; System.out.p ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As