The aim of this coursework is to construct two versions of a parser for a given context-free language and to run them on a few input strings.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

TASK

• Implement the first algorithm to determine whether a given string w is generated by G

• Implement the second algorithm to determine whether a given string w is generated by G

• For both algorithms, write code which adapts the algorithm to produce a parse tree for a given generated string

The Assignment

The aim of this coursework is to construct two versions of a parser for a given context-free language and to run them on a few input strings.

More precisely, you will be given:

1. A context-free grammar G which generates the language L

2. Some input strings in the alphabet Σ of terminals of G

3. Descriptions of two algorithms which decide whether or not a grammar generates a string

4. Java code which will include:

   • Classes for modelling context free grammars and their associated components

   • Classes for producing and displaying parse trees

   • An interface IParser to which your code must conform

   • A skeleton class Parser which you can start modifying with your own code

   • An interactive script which demos the code

To access these, please go to the following page: Graded Assignment: Parser – The Data **It is pasted below after the grading outline. Please see below**

Guidelines

• The source code for two Java classes (.java files) which implement the interface IParser – one for the first algorithm and one for the

• A txt file which explains which class implements which algorithm and any other details we need to know to run your code.

• A set of screenshots – either in PDF form or as images in a separate folder – which show your code working on the example strings provided on the data

• Your code will be subject to automated testing. If the tests do not correctly run on your code it will be subject to a substantial mark There are sample tests provided in the main script from the skeleton code.

Submission:

The source code of a single Java class implementation of the first algorithm to determine whether a given string is in the language generated by a given grammar. The class must implement (in the Java sense) the interface IParser. This will be subject to automatic code testing so it must perform correctly. There are some sample tests built into the demo script.

1. The source code of another Java class implementation of the second algorithm which also meets the above

2. Screenshots of your code producing correct parse trees (or declaring the string not in the language) for the provided example strings with the respective

 

Graded Assignment: Parser – The Data

 Here, we provide you with the data you will use in this assignment.

Grammar

 The following grammar G generates the language of syntactically correct arithmetic expressions involving addition, multiplication and a single variable name. Being able to parse text is the first step of being able to compile code, and this grammar represents a fragment of the kind of expressions you might find in many common programming languages. This grammar is unambiguous.

Let G= (V,Σ,R,E), where E is the start symbol, and the variables V, terminals Σ, and rules R, are as follows:

V={T,F,E} Σ={+,∗,(,),x} R={

E→E+T, E→T,

T→T∗F, T→F, F→(E),

F→x

}

 

The symbols E, T, and F are abbreviations for expression, term, and factor, respectively.

Note: Read the definition of Σ carefully. The left and right parenthesis symbols are terminals in this alphabet. They are not surrounding the comma.

Example Strings

 Here are example strings for the first algorithm:

• x+x

• xx

• ()

Here are example strings for the second algorithm:

• (((x+(x)∗x)∗x)∗x)

• x∗x+x+x∗(x)

• (x∗x)∗x+x+(x)

• (x+x))∗((x)∗x

You should submit screenshots of your code showing the results when run on each of the example strings. You do not need to build a user interface; the strings can be hard-coded into a script. Please see the demo script for examples.

Your code will also be automatically tested on all of the above strings, plus more.

 Algorithms

 First Algorithm

 We showed in this week’s material that if GG is in Chomsky normal form, then any derivation of a string w ∈ L (G) will have exactly 2n−1 steps where n=|w|. This is the basis for the first algorithm.

On an input w for grammar G:

• List all derivations with 2n−1steps, where n=|w|, unless n=0, then instead list all derivations with 1 step.

• If any of these derivations generate w, then accept. Otherwise,

Second Algorithm (see also Sipser page 290)

We assume that the grammar GG is in Chomsky normal form and the length of the input string is n.

The algorithm (called Cocke-Kasami-Younger algorithm, or CKY) uses a technique called dynamic programming. It uses the accumulation of information about smaller sub-problems to solve larger problems. We record the solution to any sub-problem so that we need to solve it only once. We do so by making a table for all sub-problems and entering their solutions systematically as we find them.

In this case, we consider the sub-problems of determining whether each variable in G generates each substring of ww. The algorithm enters the solution to this sub-problem in an n×n table.

For i≤j the (i,j)th entry of the table contains the collection of variables that generate the substring wiwi+1⋯wj⋯wj. For i>j the table entries are unused.

The algorithm fills in the table entries for each substring of w. First it fills in the entries for the substrings of length 1, then those of length 2, and so on. It uses the entries for the shorter lengths to assist in determining the entries for the longer lengths.

 

For example, suppose the algorithm has already determined which variables generate all substrings up to length k. To determine whether a variable A generates a particular substring of length k+1 the algorithm splits that substring into two non-empty pieces in the k possible ways. For each split, the algorithm examines each rule A→BC to determine whether B generates the first piece and C generates the second piece, using table entries previously computed. If

both B and C generate the respective pieces, A generates the substring and so is added to the associated table entry.

The algorithm starts the process with the strings of length 11 by examining the table for the rules A→x. It accepts the string w if and only if the start symbol SS belongs to the (1,n)th entry of the table.

Here is pseudocode for this algorithm on input w=w1w2…wn:

1 if w=ε and S→ε is a rule then accept 2 for i=1 to n do

• for each variable A do

• if A→x is a rule where x=wᵢ

• place A in table(i,i) 6 for l = 2 to n do

• for i=1 to n-l+1 do

• let j=i+l-1

• for k=i to j-1 do

• for each rule A→BC do

• if table(i,k) contains B AND table(k+1,j) contains C

• place A in table(i,j)

• if table(1,n) contains S then accept, else reject

Modifying these algorithms to produce parse trees is left unguided as a challenge to reach the highest marks for this assignment.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of