Task 3

Syntax analysis for English

The grammar to use

S -> NP VP
NP -> Det N | Det N PP
VP -> V NP | V NP PP
PP -> P NP
Det -> 'the' | 'a'
N -> 'man' | 'dog' | 'cat' | 'park'
V -> 'chased' | 'saw' | 'walked'
P -> 'in' | 'on' | 'by'

The implementation of CFG analyzer in Python

import nltk
from nltk import CFG

# Define the CFG
cfg_rules = """
    S -> NP VP
    NP -> Det N | Det N PP
    VP -> V NP | V NP PP
    PP -> P NP
    Det -> 'the' | 'a'
    N -> 'man' | 'dog' | 'cat' | 'park'
    V -> 'chased' | 'saw' | 'walked'
    P -> 'in' | 'on' | 'by'
"""

# Create CFG object
cfg = CFG.fromstring(cfg_rules)

# Create parser
parser = nltk.ChartParser(cfg)

# Function to check if sentence follows CFG rules
def check_sentence(sentence):
    words = sentence.split()
    try:
        for tree in parser.parse(words):
            print("Sentence follows CFG rules:")
            print(tree)
            return True
    except ValueError:
        pass
    print("Sentence does not follow CFG rules.")
    return False

# Test sentences
sentences_to_check = [
    "the man chased the dog",
    "a cat walked in the park",
    "the dog saw a cat in the park",
    "the park by the man chased the dog"  # Invalid sentence
]

# Check sentences
for sentence in sentences_to_check:
    print("\nAnalyzing sentence:", sentence)
    check_sentence(sentence)