MODULE 1

CHAPTER 2
Syntactic Analysis

1 CONTEXT-FREE GRAMMAR

 Context-Free Grammar (CFG) was introduced by Chomsky (1957) for natural languages.
 Used in programming languages, first by Backus (1959) and later by Naur (1960).
 Also known as phrase-structure grammar.

Components of CFG

A CFG consists of four components:

1. A set of non-terminal symbols, N

2. A set of terminal symbols, T

3. A designated start symbol, S, that is one of the symbols from N.

4. A set of productions, P, of the form

1. Non-terminal symbols (N): Represent syntactic categories (e.g., S, NP, VP).

2. Terminal symbols (T): The actual words or tokens of the language.
3. Start symbol (S): A special non-terminal from which derivations begin.
4. Productions (P): Rules of the form A → α, where:

o A is a non-terminal.
o α is a string of terminals and/or non-terminals.

Derivation Process

 The basic operation is rewriting, where a symbol on the left-hand side of a production is replaced
by the right-hand side.
 A CFG can be used to generate a sentence or to assign a structure to a sentence.
 Example derivation (illustrated in Figure 4.1):

1. S → NP VP
2. NP → N, VP → V NP
3. NP → Det N
4. N → Hena, V → reads, Det → a, N → book

 This results in the sentence:

"Hena reads a book."

PAGE \* MERGEFORMAT 11
Parse Tree Representation (Figure 4.1)

 Figure 4.1 illustrates the derivation of the sentence using a parse tree.
 Bracketed notation provides a compact representation of the parse tree.
 The parse tree visually represents the hierarchical structure of the sentence.

Language Definition

 The language generated by a CFG consists of all strings derivable from the start symbol using
the production rules.
 Parsing is the process of mapping a sentence to its parse tree.
 This mapping process is critical for syntax analysis in both natural and programming
languages.

PAGE \* MERGEFORMAT 11
2 CONSTITUENCY

Definition

 Words in a sentence are not just a sequence of part-of-speech but follow specific word order
constraints.
 Some words naturally group together, forming constituents (phrases), which act as single units.
 Constituents combine to form larger constituents, eventually making up a complete sentence.

Examples of Constituents

 Noun Phrases (NPs):

o The bird, The rain, The Wimbledon court, The beautiful garden
o These can function as the subject or object in a sentence.

 Example Sentence Formation:

o NP + VP → Sentence
o The bird (NP) flies (VP) → The bird flies.

2.1 Phrase Level Constructions

 Constituents can be identified by their ability to appear in similar syntactic contexts.

 Substitution Test: A group of words forms a phrase if it can be replaced by another group
without changing the sentence structure.

Example (Sentence 4.1 and Variations):

1. Hena reads a book.

2. Hena reads a storybook.
3. Those girls read a book.
4. She reads a comic book.

 Here, "Hena", "She", "Those girls" can replace each other, proving they form a constituent
(NP).
 Similarly, "a book", "a storybook", "a comic book" are interchangeable (another NP).
 Linguistic Term: This type of interchangeability forms a paradigmatic relationship, meaning
elements belong to the same category and can substitute each other in specific syntactic
positions.

Phrase Structure and Heads

Phrase types are named after their head, the key word that determines the phrase's category:

o Noun Phrase (NP) → Head: Noun

o Verb Phrase (VP) → Head: Verb
o Adjective Phrase (AdjP) → Head: Adjective
o Prepositional Phrase (PP) → Head: Preposition

PAGE \* MERGEFORMAT 11
 Figure 4.2 illustrates a sentence with NP, VP, and PP to show phrase structures.

Noun Phrase (NP)

Definition

 A noun phrase (NP) is a phrase whose head is a noun or a pronoun.

 It may include modifiers such as determiners (Det) or adjective phrases (AP).
 Functions: Noun phrases can act as:
o Subject
o Object
o Complement (Predicate)

Phrase Structure Rules for NP

Phrase structure rules define how a noun phrase is constructed:

Basic NP Rules

o NP → Pronoun
o NP → Det Noun
o NP → Noun
o NP → Adj Noun
o NP → Det Adj Noun

Generalized NP Rule

o NP → (Det) (Adj) Noun Pronoun

o Elements in parentheses are optional.
o This rule accounts for determiners (Det) and adjectives (Adj) before the noun.

Extended NP Rule (Including PP & AP)

o NP → (Det) (AP) Noun (PP)

o AP (Adjective Phrase) allows multiple adjectives.
PAGE \* MERGEFORMAT 11
 o PP (Prepositional Phrase) allows additional post-modification.

Examples of Noun Phrases (4.2a - 4.2e)

1. They (4.2a) → Pronoun as NP

2. The foggy morning (4.2b) → Det + Adj + Noun
3. Chilled water (4.2c) → Adj + Noun
4. A beautiful lake in Kashmir (4.2d) → Det + Adj + Noun + PP
5. Cold banana shake (4.2e) → Adj + Noun + Noun (Nominal)

 Nominal (Nom): A sequence of nouns forming a compound noun phrase (e.g., "banana shake").

Refining NP Structure to Handle Nominals

 New Rule for NP:

o NP → (Det) (AP) Nom (PP)
o Nom → Noun | Noun Nom
o This allows multiple nouns (e.g., "cold banana shake").

Functions of Noun Phrases in Sentences (4.3a - 4.3c)

1. Subject:

o "The foggy damped weather disturbed the match." (4.3a)

2. Object:

o "I would like a nice cold banana shake." (4.3b)

3. Predicate (Complement):

o "Kula botanical garden is a beautiful location." (4.3c)

Verb Phrase (VP)

Definition

 A verb phrase (VP) is headed by a verb and may include other elements such as noun phrases
(NP), prepositional phrases (PP), or clauses (S).
 The verb determines the structure of the verb phrase by governing its required or optional
elements.

Examples of Verb Phrases (4.4a - 4.4e)

1. Khushbu slept. (4.4a) → VP → Verb

2. The boy kicked the ball. (4.4b) → VP → Verb + NP
3. Khushbu slept in the garden. (4.4c) → VP → Verb + PP
4. The boy gave the girl a book. (4.4d) → VP → Verb + NP + NP
5. The boy gave the girl a book with a blue cover. (4.4e) → VP → Verb + NP + NP + PP

PAGE \* MERGEFORMAT 11
Generalized Phrase Structure Rule for VP

 *VP → Verb (NP) (NP) (PP) **

o (NP) and (PP) are optional.

o Max 2 NPs are allowed, but multiple PPs can be included.
o Objects can also be clauses (S) → VP → Verb S
o Example: "I know that Taj is one of the seven wonders."

Prepositional Phrase (PP)

Definition

 A prepositional phrase (PP) is headed by a preposition and usually includes a noun phrase
(NP).
 PPs function as modifiers in sentences.

Examples

1. We played volleyball on the beach. → PP = Prep + NP

2. John went outside. → PP = Prep (alone)

Phrase Structure Rule

 PP → Prep (NP)

Adjective Phrase (AP)

Definition

 An adjective phrase (AP) is headed by an adjective.

 It may contain:

o An adverb (Adv) modifying the adjective.

o A prepositional phrase (PP) providing additional information.

Examples

1. Ashish is clever. → AP = Adj

2. The train is very late. → AP = Adv + Adj
3. My sister is fond of animals. → AP = Adj + PP

Phrase Structure Rule

 AP → (Adv) Adj (PP)

PAGE \* MERGEFORMAT 11
Adverb Phrase (AdvP)

Definition

 An adverb phrase (AdvP) is headed by an adverb.

 It may be preceded by a degree adverb (Intensifier).

Example

 Time passes very quickly. → AdvP = Intens + Adv

Phrase Structure Rule

 AdvP → (Intens) Adv

Summary of Phrase Structure Rules

Phrase Type Structure Rule

Noun Phrase (NP) NP → (Det) (AP) Nom (PP)

Verb Phrase (VP) VP → Verb (NP) (NP) (PP) (S)*

Prepositional Phrase (PP) PP → Prep (NP)

Adjective Phrase (AP) AP → (Adv) Adj (PP)

Adverb Phrase (AdvP) AdvP → (Intens) Adv

2.2 Sentence Level Constructions

Types of Sentence Structures:

There are four commonly known sentence structures:

1. Declarative Structure
2. Imperative Structure
3. Yes-No Question Structure
4. Wh-Question Structure

1. Declarative Structure:

 Follows the pattern: Subject (NP) + Predicate (VP)

 The subject is a noun phrase (NP) and the predicate is a verb phrase (VP)
 Example: I like horse riding.
 Grammar Rule: S → NP VP

PAGE \* MERGEFORMAT 11
2. Imperative Structure:

 Begins with a verb phrase (VP) and usually lacks an explicit subject
 The subject is understood as 'you' (implicit)
 Used for commands or suggestions
 Examples:

o Look at the door.

o Give me the book.

 Grammar Rule: S → VP

3. Yes-No Question Structure:

 Used to ask questions that can be answered with yes or no

 Structure: Auxiliary Verb + Subject (NP) + Verb Phrase (VP)
 Examples:

o Do you have a red pen?

o Is the game over?

 Grammar Rule: S → Aux NP VP

4. Wh-Question Structure:

 Begins with a wh-word (who, which, where, what, why, how)

 Two types:

o Wh-phrase as Subject:

 Example: Which team won the match?

 Rule: S → Wh-NP VP

o Wh-phrase with Auxiliary Verb:

 Structure: Wh-NP + Aux + NP + VP

 Example: Which cameras can you show me in your shop?
 Rule: S → Wh-NP Aux NP VP

Summary of Grammar Rules:

Sentence Type Grammar Rule Example

Declarative S → NP VP I like horse riding.

Imperative S → VP Stop talking.

Yes-No Question S → Aux NP VP Is the game over?

Wh-Question (Simple) S → Wh-NP VP Which team won the match?

PAGE \* MERGEFORMAT 11
 Sentence Type Grammar Rule Example

Wh-Question (Complex) S → Wh-NP Aux NP VP Which cameras can you show me in your shop?

Coordination
 Coordination refers to combining phrases using conjunctions like "and," "or," and "but."
 Examples of Coordination:
o Noun Phrases (NP):
I ate [NP [NP an apple] and [NP a banana]].
o Verb Phrases (VP):
It is [VP [VP dazzling] and [VP raining]].
o Sentences (S):
[S [S I am reading the book] and [S I am also watching the movie]].
 Grammar Rules for Coordination:

o NP → NP and NP
o VP → VP and VP
o S → S and S

2. Agreement

Subject-Verb Agreement:

o Verbs in the present tense have different forms based on the subject (singular/plural).
o Third-person singular (3sg) verbs end in -s (e.g., does, sings).
o Non-3sg verbs do not have the -s ending (e.g., do, eat).

PAGE \* MERGEFORMAT 11
 Examples of Correct Agreement:

o Does [NP Priya] sing? (Singular subject → "does")

o Do [NP they] eat? (Plural subject → "do")

Examples of Incorrect Agreement (Ungrammatical Sentences):

o [Does] they eat? ❌

o [Do] she sings? ❌

Grammar Rules for Yes-No Questions with Agreement:

o S → Aux NP VP
o S-> 3sgAux+ 3sg NP + VP

 In a yes-no question with a 3rd person singular subject, the structure is:

Example:
Does the girl like pizza?

o S→ Non3sgAux Non3sgNP VP

 For non-3rd person singular subjects (like I, we, you, they), the structure is:

Example:
Do the girls like pizza?

o Lexicon Rules:

 3sg Aux → does | has | can

 Non3sg Aux → do | have | can

o Noun Phrase Rules:

 3sgNP → (Det) (AP) SgNom (PP)

 Non3sgNP → Det) (AP) PlNom (PP)
 SgNom →SgNoun | Sgnoun SgNom
 PlNom →PlNoun | Plnoun PlNom
 SgNoun →Priya | lake | sister …
 Plnoun →Children |…


1. 3sgNP → (Det) (AP) SgNom (PP)

Explanation: A third-person singular noun phrase may optionally include a determiner (Det), an
adjective phrase (AP), a singular nominal (SgNom), and a prepositional phrase (PP).

Example:

PAGE \* MERGEFORMAT 11
  The beautiful lake near the forest
o Det: The
o AP: beautiful
o SgNom: lake
o PP: near the forest

2. Non3sgNP → (Det) (AP) PlNom (PP)

Explanation: A non-third-person singular noun phrase may optionally include a determiner, adjective
phrase, plural nominal (PlNom), and prepositional phrase.

Example:

 The beautiful lake near the forest

o Det: The
o AP: beautiful
o PlNom: lakes
o PP: near the forest

3. SgNom → SgNoun | SgNoun SgNom

Explanation: A singular nominal can be a single singular noun or a sequence of singular nouns.

Example:

 lake → just a single SgNoun

 sister lake → SgNoun SgNom

4. PlNom → PlNoun | PlNoun PlNom

Explanation: A plural nominal can be a single plural noun or a sequence of plural nouns.

Example:

 children → just a single PlNoun

 children books → PlNoun PlNom

5. SgNoun → Priya | lake | sister | …

Explanation: Some examples of singular nouns.

Example usage:
PAGE \* MERGEFORMAT 11
  Priya is reading.
 The lake is deep.
 Her sister lives nearby.

6. PlNoun → children | …

Explanation: Examples of plural nouns.

Example usage:

 Children are playing.

Feature Structures

 Definition:
o Feature structures consist of feature-value pairs used to capture grammatical properties
efficiently.
o Example Feature:
 NUMBER → SG (Singular) or PL (Plural)
o Representation as an Attribute-Value Matrix (AVM):

 [NUMBER SG] → Represents singular number.

 [NUMBER PL] → Represents plural number.

 Example of Feature Structures for Noun Phrases:

o Third-person singular NP:

[ CAT: NP

NUMBER: SG

PERSON: 3 ]

Third-person plural NP:

[ CAT: NP

NUMBER: PL

PERSON: 3 ]

PAGE \* MERGEFORMAT 11