in java

PRoJecTs Dr Bassam Haddad ADT-LIST Project-1: Mini-Project Parser based on List implementations 1 Project Description: - Write a simple Parser in Java, that is capable of deciding, whether a simple Arabic or English sentence is syntactic correct or not. - A possible Grammar for such sentences can be defined as follows: >:: :: Verbal Phrase >:: :: a | the | some | certain :: boy |girl| student | dog |school baby| boys | students |Data Structure :: like | likes |speak| speaks| study |studies | ... 2) Alternatively, you can use the following Pattern for your sentences >:: Subject Verb > Object (for English) or :: Verb > (for Arabic) Eexamples Based on the above grammar, the following sentences are correct: [The, baby, speaks, English] [The, boy, studies, English] and even [The, boy, study, English] [a, boy, studies, a, school] However: [speaks, English, baby, a] [study, a, English, like] are not. Hints: - A correct sentence can be regarded as a List "[ the, student, likes, English]" containing sub lists and word object at specific order. - [the, student], represents a List of a Nominal Phrase (NP)and - [likes, English] represents a List of a Verbal Phrase (VP) - Appending a List of VP to a List of NP yields a valid Sentence. - This apply also to a List of a Determiner like [the] and a list of Noun like [student] etc. A possible Solution: To create a parser for such sentences, we need at least the following lists as lexicon 2 : 1. Determiner: a list of determiner such [a, the, some,...] 2. Noun: a list of nouns such as [student, baby, ...] 3. Verb: a list of verbs such that [speak, speaks, study,...] 4. However, the Lists - Nominal Phrase - Verbal Phrase - Sentence represent Lists containing sub lists; for example: - The Noun Phrase list will contain a concatenation of the Determiner and Noun Lists in that order, and the Verbal Phrase list will contain a concatenation of the Verb and NP list, etc. - The final list will be called Sentence, and it will be composed of the concatenation of [ [NP], [VP]] Final Remake: In an advanced stage, you can improve your Parser by: - Using more advanced Data Structures such as a Dictionaries or tables instead of lists on the word levels. - Generating a Parse-Trees of each correct sentence - to optimize the search, you can also employ graph-based search such as Depth-First operating on graph (Stack-based search) or Breath-first Search (based on a queue)