A linguistics class is experimenting with a restricted grammar for English sentences. Their complete grammar for a limited language is shown below with S representing an entire sentence, non-terminals as uppercase single letters, and terminals as themselves (in lowercase, except for the proper nouns). A vertical bar (|) separates alternative productions. The only punctuation in the sentences is the ending period. The ε indicates a null production.
S -> T J N P V R . T -> a | an | the | ε J -> D | D J | ε D -> huge | polite | green | shifty | tired | mean | nice | speckled | rough | innocent N -> dog | horse | Linda | Donald | elephant | snail | chicken P -> E T J N | ε E -> with | on | by V -> eats | is | stands | calls | feeds R -> D | T N | E T J N
There are only 28 words in the language. Sentences do not have the first letter of the first word capitalized. Sentences consist of a sequence of words, each separated from the next with one space; and with a period guaranteed to be at the end (with one space before it).
You are to write a program that can validate sentences for this language (i.e., determine if each of the sentences can be generated by the grammar shown above). The sentences are in a file whose name your program must prompt for and read in; there will be one sentence on each line of the file. The following sentences are in the data file SENTENCE.TXT
the dog feeds a speckled horse . a huge shifty tired elephant with the nice snail is innocent . the Donald stands on a green . the horse with a mean green calls the chicken . Linda eats chicken nice . Linda eats a snail . an elephant stands on the polite dog . the nice elephant with Donald calls on an innocent dog . the tired squirrel stands alone . Linda is with Donald . the chicken by the green horse is an elephant . Linda is polite . the huge mean dog feeds on a speckled horse . Donald calls Linda . a tired innocent elephant feeds a shifty snail .
Your program should display an evaluation in the form "Sentence x is VALID" or "Sentence x is NOT in the language" where x is the number of the sentence. Display each sentence's evaluation on a separate line. Below is the correct evaluation of the 15 sentences in SENTENCE.TXT
Sentence 1 is NOT in the language Sentence 2 is VALID Sentence 3 is NOT in the language Sentence 4 is NOT in the language Sentence 5 is NOT in the language Sentence 6 is VALID Sentence 7 is VALID Sentence 8 is VALID Sentence 9 is NOT in the language Sentence 10 is VALID Sentence 11 is VALID Sentence 12 is VALID Sentence 13 is VALID Sentence 14 is VALID Sentence 15 is NOT in the language