Question 1 Suppose that patients' medical records are kept in a file with the following format The file contains one or more patient records Each patient record has one patient's name, then their registration number, then one or more health conditions, separated by commas Each health condition is a string value followed by one or more stars (to represent the number of visits to the hospital) Here's a CFG for the grade file format file record tail tail file record PTNAME REGNUM healthCondns healthCondns condns condns onehealthCondn onehealthCondn COMMA condns onehealthCondn STRLIT numvisits numvisits stars stars STAR stars STAR Although the patient file CFG given above is not LL(1), some correct inputs can be parsed by a predictive parser This is because those inputs never cause the parser to look at a table entry that contains two or more CFG rules Give the shortest such input (as a sequence of tokens, ending with EOF) Draw the parse tree that the parser would build for the input you gave for Part (i) (Do not include the EOF token in the parse tree ) What is the shortest sequence of tokens that would stump a predictive parser trying to parse the language of this CFG (i e , a sequence of tokens that is a prefix of a valid input, but for which the parser would not know how to continue to build the parse tree top down because it looks at a table entry that contains two or more CFG rules) To answer this question, give all of the following The sequence of tokens (a prefix of a valid input) The (partial) parse tree that the predictive parser would have built before being stumped The CFG rules that the predictive parser can't choose between to continue to grow the parse tree One problem with the patient file CFG is that it has not been left factored Find the CFG rules with a common prefix and transform them by doing left factoring Another problem with the patient file CFG is that is has immediate left recursion Find the CFG rules that cause this and transform them to remove the left recursion

The Answer is in the image, click to view ...

Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 10, 2024

Question 1: Suppose that patients' medical records are kept in a file with the following format: The file contains one or more patient records. Each

Question 1:

Suppose that patients' medical records are kept in a file with the following format:

The file contains one or more patient records.
Each patient record has one patient's name, then their registration number, then one or more health conditions, separated by commas.
Each health condition is a string value followed by one or more stars (to represent the number of visits to the hospital).

Here's a CFG for the grade file format:

file  record tail tail  file |  record  PTNAME REGNUM healthCondns healthCondns  condns condns  onehealthCondn | onehealthCondn COMMA condns onehealthCondn  STRLIT numvisits numvisits  stars stars  STAR | stars STAR

Although the patient file CFG given above is not LL(1), some correct inputs can be parsed by a predictive parser. This is because those inputs never cause the parser to look at a table entry that contains two or more CFG rules.
1. Give the shortest such input (as a sequence of tokens, ending with EOF).
2. Draw the parse tree that the parser would build for the input you gave for Part (i). (Do not include the EOF token in the parse tree.)
What is the shortest sequence of tokens that would "stump" a predictive parser trying to parse the language of this CFG (i.e., a sequence of tokens that is a prefix of a valid input, but for which the parser would not know how to continue to build the parse tree top-down because it looks at a table entry that contains two or more CFG rules)? To answer this question, give all of the following:
1. The sequence of tokens (a prefix of a valid input).
2. The (partial) parse tree that the predictive parser would have built before being stumped.
3. The CFG rules that the predictive parser can't choose between to continue to grow the parse tree.
One problem with the patient file CFG is that it has not been left factored. Find the CFG rules with a common prefix and transform them by doing left factoring.
Another problem with the patient file CFG is that is has immediate left recursion. Find the CFG rules that cause this and transform them to remove the left recursion.