Syntax Flashcards
What is a “constituent”?
Words in a sentence often form groupings that can combine with other units to produce meaning. These groupings, called consituents can often be identified by substitution tests.
What is the “head” of a phrase equivalent to?
It is the same as the subject when referring to “subject, verb, object”
Which two properties did Chomsky associate with an “interesting and satisfying” grammar?
It is a finite specificiation of the strings of a language as opposed to a list of valid strings.
It should be revealing, in allowing strings to be associated with meaning (semantics) in a systematic way.
What other property may make a grammar “interesting and satisfying”?
It should capture structural and distributional properties of the language. (E.g. where heads of phrases are located; how a sentence transforms into a question; which phrases can float around the sentence.)
What does a Context-Free Grammar consist of?
A context-free grammar (CFG) G consists of
- a finite set N of non-terminals,
- a finite set Σ of terminals, disjoint from N
- a finite set P of productions of the form X→α, where X∈N, α∈(N∪Σ)∗,
- a choice of start symbol S ∈N.
What is a sentential form?
A sentential form S(G) is any sequence of terminals and non-terminals that can appear in a derivation starting from the start symbol.
What is a language in terms of sententials and grammar?
The language associated with grammar L(G) is the set of sentential forms that contain only terminals.
How do context-free grammars differ to context-sensitive ones?
A rule X→α says that an X can always be expanded to α, no matter where the X occurs.
This contrasts with context-sensitive rules, which might allow us to expand X only in certain contexts, e.g. bXc→bαc.
Broad intuition: context-free languages allow nesting of structures to arbitrary depth.
Give an example of direct recursion
In direct recursion, a non-terminal on the LHS of a rule also appears on its RHS.
The following rules add direct recursion to G1: VP→VP Conj VP
Give an example of indirect recursion
In indirect recursion, some non-terminal can be expanded (via several steps) to a sequence of symbols containing thatnon-terminal: NP→Det N PP PP→Prep NP
What is attachment ambiguity?
When multiple tags can be attached to a word but the structure of the tree-diagram remains valid for a given sentence.
What is left recursion?
A grammar rule of the form A —> Ax, where x is a terminal and A is a non-terminal.
Why are shift-reduce parsers and recursive descent parsers bad to use for ambiguous grammars and syntax trees?
They end up re-calculatin a lot of what has already been calculated.
