Please do the following tasks without hardocoding the input files: Task 1: Read grammar from file. Implement a function to read the input context-free grammarfrom a file. The grammar will be specified as a set of production rules in CNF. Each line of the file will represent one or more rules for the same left-hand variable, with the (righthand sides of the) rules separated by a vertical bar “|” as an “or”.Task 2: Read input string from file. Implement a function to read the input string from a file. The input string file contains a sequence of terminals, where each terminal is separated by a space. Each terminal can either be a single character, like a or b, or a multicharacter token like cat or dog. The program should handle these cases dynamically without assuming that terminals are limited to single characters.Task 3: Implement CYK algorithm. Implement the above CYK algorithm using dynamic programming. Return the following two values. 1. An integer value of 1 if the string is accepted, meaning it can be generated by the grammar, or 0 if rejected. 2. The dynamic programming table created during the parsing process in the format specified below, with alphabetically sorted, duplicate-free variables in each cell. Row Separation: Each row should be displayed on a new line. Cell Separation: Cells within the same row should be separated by a semicolon, followed by a space. Value Separation: In each cell, sorted variables should be separated by a comma, followed by a space. For example, if a cell contains the values A and S, it should display as A, S. If a cell has no values, display a dash to clearly indicate that the cell is empty.
Please do the following tasks without hardocoding the input files:
Task 1: Read grammar from file. Implement a function to read the input context-free grammar
from a file. The grammar will be specified as a set of production rules in CNF. Each line of the file will represent one or more rules for the same left-hand variable, with the (righthand sides of the) rules separated by a vertical bar “|” as an “or”.
Task 2: Read input string from file. Implement a function to read the input string from a file. The input string file contains a sequence of terminals, where each terminal is separated by a space. Each terminal can either be a single character, like a or b, or a multicharacter token like cat or dog. The program should handle these cases dynamically without assuming that terminals are limited to single characters.
Task 3: Implement CYK algorithm. Implement the above CYK algorithm using dynamic programming. Return the following two values.
1. An integer value of 1 if the string is accepted, meaning it can be generated by the grammar, or 0 if rejected.
2. The dynamic programming table created during the parsing process in the format specified below, with alphabetically sorted, duplicate-free variables in each cell.
Row Separation: Each row should be displayed on a new line.
Cell Separation: Cells within the same row should be separated by a semicolon, followed by a space.
Value Separation: In each cell, sorted variables should be separated by a comma, followed by a space. For example, if a cell contains the values A and S, it should display as A, S. If a cell has no values, display a dash to clearly indicate that the cell is empty.
Step by step
Solved in 2 steps
