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:
A context-free grammar G which generates the language L
Some input strings in the alphabet Σ of terminals of G
Descriptions of two algorithms which decide whether or not a grammar generates a string
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.
The source code of another Java class implementation of the second algorithm which also meets the above
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.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
