programming辅导、Python, C/C++,Java程序语言调试、讲解data

5) ( programming) Write and submit a program written in Perl, Python, C,
C++, or Java, named a4q5.pl, a4q5.py, a4q5.c, a4q5.cc, or a4q5.java, which verifies one or more
bracketed parse trees, and check that their grammar is the Chomsky Normal Form grammar.
The program must read the standard input. It expects one or more parse trees in the input
and the program should process them. The parse trees are in the format discussed in the
class. You should also assume that all non-terminals consist of uppercase letters and
terminals consist of uppercase letters, lowercase letters, and digits, and not necessarily all of
them. In other words, terminals satisfy the regular expression /[A-Za-z0-9]+/. Each parse tree
will start with open parenthesis ‘(’, and there can be spaces between parentheses, terminals,
and non-terminals.
If the trees are all valid and their grammar is in Chomsky Normal Form, the program must
print the following line:
Valid CNF trees.
(Always finish a line with a new-line character.) For
example, the following input:
(S (NP dogs) (VP run)) (S nothing)
should produce output:
Valid CNF trees.
If the trees do not follow specifications, are not proper trees, or not in Chomsky Normal
Form, then the program must print the line:
Not valid CNF trees.
For example, the following input should produce this message:
(S (NP dogs) (VP run) (ADV fast))
As a more complex example, the following input should be accepted as ‘Valid CNF trees’:
(S (WNP (WDT What)
(NN courses))
(VP (BE are)
(VP (VBN offered)
(PP (IN in)
(NN fall)))))
(S (WNP Who)
2
(VP (VBZ teaches)
(NP (NN CSCI)
(NN 1100))))
(S (WNP (WDT (WRB How) (JJ many))
(NN students))
(VP (BE are)
(VB (VBG taking)
(NP (NN CSCI)
(NN 1108)))))