QuestionQuestion

CYK Recognizer
1: Write a program which reads a grammar and a lexicon from files and stores them internally in a suitable form. The non-terminal on the left-hand side of the first rule is the start symbol of the grammar.
Here is an example of a grammar and a lexicon:

example grammar:                     example lexicon:
S → NP VP                                     DT → der
                                                         N → Frau
VP → VP PP                                    NP → der
                                                         P → mit
VP → V NP                                     N → Mann
                                                         DT → dem
PP → P NP                                       V → sah
                                                         NP → dem
NP → NP PP                                    DT → die
                                                         N → Teleskop
NP → DT N                                     NP → die

Part 2: Implement a CYK recognizer. The program should print whether the input sentence is grammatical or not. The input could look as follows:
der Mann sah die Frau mit dem Teleskop

Part 3: Evaluate the runtime complexity of the parser empirically. Measure how long the parser needs for sentences of increasing length. You could use the following sequence of
input sentences for this purpose:
Der Mann sah die Frau
Der Mann sah die Frau mit dem Teleskop
Der Mann sah die Frau mit dem Teleskop mit dem Teleskop
...
Store enough copies of each sentence in a file such that the parser needs at least a minute to process it. Measure the time needed by the parser to process each file and compute the average processing time per sentence for the different sentences. (You can use the Unix command time for measuring.) Take care that no other processes are running at the same time.
Plot the results in a diagram with the sentence length on the x axis and the average runtime on the y axis. Try to approximate the curve by a cubic function y = ax³ + b. Choose a and b in such a way that the two curves are as close to each other as possible.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

package parser;

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
      
//CYK Recogniser
//It reads input file with grmmar and lexicon
//and checks whether a sentence is grammatical or not

public class CYK {
private HashMap<String, HashSet<LinkedList<String>>> rules;
private String DELIMITER = " -> ";
private String TOKEN_DELIMITER = " ";
private String START = "S";

private boolean IsEntirelyUpperCase(String s) {
      for (int i = 0; i < s.length(); i++)
          if (!Character.isUpperCase(s.charAt(i)))
             return false;
      return true;
}...
$65.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats