logo Use SA10RAM to get 10%* Discount.
Order Now logo

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
Aditya ChopraComputer science
(5/5)

704 Answers

Hire Me
expert
Carlos HowardComputer science
(5/5)

937 Answers

Hire Me
expert
Milton BlahaEconomics
(5/5)

887 Answers

Hire Me
expert
Umar AkbarScience
(/5)

746 Answers

Hire Me
Java Programming

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.

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

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

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme

Get Free Quote!

408 Experts Online