Tiêu đề lab3-1.pdf ✅

CS236299 Lab 3-1: Context-free grammars introduced May 29, 2022 [ ]: # Initialize Otter import otter grader = otter.Notebook() [1]: # Please do not change this cell because some hidden tests might depend on it. import os # Otter grader does not handle ! commands well, so we define and use our # own function to execute shell commands. def shell(commands, warn=True): """Executes the string `commands` as a sequence of shell commands. Prints the result to stdout and returns the exit status. Provides a printed warning on non-zero exit status unless `warn` flag is unset. """ file = os.popen(commands) print (file.read().rstrip('\n')) exit_status = file.close() if warn and exit_status != None: print(f"Completed with errors. Exit status: {exit_status}\n") return exit_status shell(""" ls requirements.txt >/dev/null 2>&1 if [ ! $? = 0 ]; then rm -rf .tmp git clone https://github.com/cs236299-2022-spring/lab3-1.git .tmp mv .tmp/tests ./ mv .tmp/requirements.txt ./ rm -rf .tmp fi pip install -q -r requirements.txt """) WARNING: You are using pip version 22.0.3; however, version 22.1.1 is available. 1
You should consider upgrading via the '/Users/shakedbr/.pyenv/versions/3.8.6/envs/otter-latest/bin/python3.8 -m pip install --upgrade pip' command. 1 Preparation – Loading packages [2]: import functools import math import nltk 2 Writing CFGs Recall that a context free grammar (CFG) is a set of rules of the form A → β, where A is a nonter- minal symbol and β is a sequence of terminal and nonterminal symbols. The set of nonterminals is N and the set of terminals is Σ. One of the nonterminals is a special start symbol, conventionally denoted S. A CFG generates a string by starting with the start symbol and repeatedly replacing a nonterminal symbol by the right-hand side of a rule whose left-hand side matches that nonterminal. We will use the Natural Language Tool Kit (NLTK) to define, represent, and store context-free grammars and syntactic parse trees in data structures. The toolkit provides for constructing a grammar from a textual description, such as this example: [3]: simple_grammar1 = nltk.CFG.fromstring(""" S -> NP VP NP -> 'dogs' NP -> 'cats' NP -> 'husky' 'dogs' VP -> V VP -> V NP V -> 'bark' V -> 'jump' V -> 'chase' """) Some things to notice about the NLTK encoding of grammars: • Nonterminals are those symbols that appear on the left-hand side of a rule. • Terminals are any other Python object, but typically (as here) a string. (Notice how to write multi-word expressions on the right-hand side: each word needs to be quoted separately.) • By convention, the start symbol is the left-hand side of the first production of the grammar, and typically denoted as “S”. We can print the grammar to observe it: [4]: print(simple_grammar1) 2
Grammar with 9 productions (start state = S) S -> NP VP NP -> 'dogs' NP -> 'cats' NP -> 'husky' 'dogs' VP -> V VP -> V NP V -> 'bark' V -> 'jump' V -> 'chase' Some sentences that are generated by this grammar include “dogs bark”, “cats jump”, “husky dogs chase cats”. The last of these is generated as specified by the following derivation: S => NP VP => husky dogs VP => husky dogs V NP => husky dogs chase NP => husky dogs chase cats This grammar also generates sentences that are ungrammatical in English, such as “dogs bark cats”, as it makes no distinction between intransitive verbs (like “bark”) and transitive verbs (like “chase”). For now, we’ll ignore this issue. The nltk.CFG.fromstring function also accepts grammars in a shorthand notation using the “or” operator | to combine multiple productions with the same left-hand side. [5]: simple_grammar2 = nltk.CFG.fromstring(""" S -> NP VP NP -> 'dogs' | 'cats' | 'husky' 'dogs' VP -> V | V NP V -> 'bark' | 'jump' | 'chase' """) You can verify that the grammar is identical by printing it. [6]: print(simple_grammar2) Grammar with 9 productions (start state = S) S -> NP VP NP -> 'dogs' NP -> 'cats' NP -> 'husky' 'dogs' VP -> V VP -> V NP V -> 'bark' V -> 'jump' V -> 'chase' 3