CHAPTER 5 part 2 Flashcards
………………. is the process of analyzing the structure of a sentence based on grammatical rules.
parsing
………………is a formal system that defines how sentences are structured
Context-Free Grammar (CFG)
Why CFG is Important?
–Defines sentence structure: CFG helps define how sentences are constructed and how words are arranged within a sentence.
–Analyzing sentences: It provides the foundation for analyzing sentence structure to understand meaning.
–Sentence generation: CFG allows for the generation of grammatically correct sentences
In a Context-Free Grammar, the language is described
using four key components, which define how sentences can
be constructed and parsed:
–Non-terminal symbols (N): Represent abstract syntactic categories.
–Terminal symbols (Σ):Represent the actual input tokens (e.g., words).
– Production rules (R): Define how non-terminals can be expanded into terminals or other non-terminals.
–Start symbol (S): A special non-terminal from which the grammar starts
T/F The process of Sentence Generation starts from the start symbol (S) and recursively apply the production rules until only terminal symbols remain
T
To determine if a string of terminal symbols can be generated by a given Context-Free Grammar (CFG), and to also return the parse tree(s), we will apply both:
–Top-Down Parsing techniques : Start searching space of derivations for the start symbol.
–Bottom-up Parsing techniques : Start search space of reverse derivations from the terminal symbols in the string.
T/F
Top-down parsing begins with the start symbol
of a grammar and attempts to derive the input
string by recursively expanding non-terminals
using production rules.
- It starts at the top of the parse tree and works its
way down to the leaves.
T/F
- Bottom-up parsing starts with the input string and builds the parse tree in a bottom-up manner.
- It identifies small portions of the input string and
combines them to form larger structures until the entire
string is recognized.
T
T/F Top down vs Bottom up
⚫ Top down never explores options that will not lead to a full parse, but can explore many options that never connect to the actual sentence.
⚫ Bottom up never explores options that do not connect to the actual sentence but can explore options that can never lead to a full parse.
⚫ Relative amounts of wasted search depend on how much the grammar branches in each direction.
the
a
that
this
Det (Determiner) used before nouns
from
to
on
near
through
Prep (Preposition) – shows direction or relation
Examples:
book
flight
meal
money
Noun – a person, place, thing, or idea
Examples:
book
include
prefer
Verb – action or state
Examples:
I
he
she
me
Pronoun – replaces a noun
Examples:
Houston
NWA
Proper-Noun = specific names
does is, are, was, were, have, has, had, do, did, can, will, shall,
Aux (Auxiliary Verb) – helps the main verb
