Lab 2 a

First Point of Failure



Wrong Decision


Second Deadend


Question 1

After 14 steps, srparser finds a complete sentence "My dog saw a man". Further steps, finds the prepositional phrases "in the park", " with a statue" but parsing fails because the parse did not span whole of this input and there is no backtracking to try a new parse. After correctly parsing "my dog" as an NP, `saw` as a Verb, `a man` as a NP, the parser chooses to reduce and "saw a man" becomes a VP, the failure point is when NP and VP is merged as a sentence. (14th step) The parser should have shifted "in" instead of merging NP and VP as a S.
The parser gets stuck for the second time, after 'in the park' is reduced to a PP, ('in the park') merged with 'saw a man' to form a VP, at the point where the new VP->VP-PP pairing can combine with former NP to form an S, leaving 'with a statue' dangling out of the sentence
It had to continue to shift instead because "in the park with a statue" must have been parsed as a whole PP.

Question 2(a)
The parser uses a reduce>shift strategy. Whenever a conflict occurred , the parser chose to reduce instead of shifting. (e.g. "in the park", "with a statue" as two seperate PP instead of a single PP, or making a sentence parse for "My dog saw a man" without shifting the remaining tokens.)

Question 2(b)

A single strategy of shift>reduce would not work.

If our strategy involves first shift & reduce each token with
all words are reduced to their word parts (N, V etc) but no further reduction until the end

then "a statue" is reduced to an NP ( Det N)
"with a statue" is found (PP -> P NP)
the deadend comes when 'park' (N) is tried to reduced with with a statue (PP) because there is no production rule that would reduce N PP to a nonterminal.

On the other hand, if we assume we can defer S -> NP VP until the end, the reduce> shift approach would work. As we can see from both point of failures for shift-reduce, deadends happened as NP VP were reduced to a premature S


Question 2(c)


Correct parse with reduce>shift, deep tree (deferring S->NP VP)


Tokens parsed with 5 shift and 7 reduces

shift>reduce would produce flatter trees
reduce>shift would produce straggly trees

Reduce>shift strategy, reduces tokens with nonterminals on left hand sides as soon as an item is pushed to the stack with a corresponding production rule. This would create a slant towards branching further down compared to shift>reduce where branching down (reduction) can be deferred until all the tokens are shifted. This is also the reason why shift-reduce would be more likely to straggly, it may wait arbitrary number of steps before reduce

Question 2(d)

reduce>shift minimizes the number of elements in the stack because, nonterminals are reduced to other nonterminals immediately. This contrasts with shift>reduce strategy where tokens in the stack wait to be combined with other nonterminals at a later time. Shift>reduce, keeps tokens in the stack as long as there is a conflict between shift and reduce.

Question2(e)

"Human parsing" seems to follow reduce>shift with backtracking. As humans have short stacks (memory), they try to group together words as they hear them. So the sentence could have been parsed like
my dog = NP
saw a man= VP
in the park= PP
with a statue = PP
(a little bit better than pure reduce>shift)
realizing the parse does not make sense (seeing a man with a statue), humans would backtrack to find the correct parse

Question 3.

3-a
There are no competing rules with same RHS and different resulting nonterminals on LHS in this grammar.
The recursions are self contained, too so
eg

NP -> X Y
VP -> NP V

there exist no rules such as
XP -> X Y V

So reduce-reduce conflicts cannot occur

3-b
A strategy to resolve reduce-reduce conflicts might involve constructing look-up tables for terminals coming right after each of multiple non-terminals for a parse.
e.g. X -> V NP
Y -> V NP
D -> X M
F -> Y C
by looking ahead whether a next token is C or M we can resolve the conflict
Of course, this still wouldn't resolve conflicts where an ambiguous parse for a terminal is followed by same tokens
in that case we might choose the non-terminal (X,Y) which comes first in the rule table of grammar

Question 4

4(a)
As n grows large, the stack can grow as deep as in the order of O(n)

e.g. a sentence like
V PP PP PP PP
where each token form children of a node, which in turn becomes the right hand sibling of another constituent on the left (the rightmost PPs form a constituent X which in turn forms a constituent with the third PP, and the procedure goes on like this)


4(b)
SRparser is not real-time. There's not a fixed number of steps before a symbol is shifted onto the stack. This is because we might reduce items
in a stack or shift them in no pre-determined fashion

Any of tokens may wait for variable number of reduce/shift actions before it is processed.

e.g.
I shot the good inadvertently
'The' (det) may wait for two shift+two reduce operations and/or two shift + three reduce operation before it is moved to the stack

4(c)
The index n-1 of the Catalan numbers is the number of pairs of parenthesis needed to paranthesize n symbols
C(n)= sigma (i=1..n) C(i-1) C (n-1-i)
where C(0)=1

as Catalan numbers C(n) in this case, can be interpreted as number of binary trees with exactly n nodes

*
Design and Analysis of Computer Algorithms -David M. Mount
Department of Computer Science
University of Maryland
Fall 2003 Lecture notes

Question 5

Bottom up produces 54 edges whereas top down produces 74 edges. So roughly bottom up produces approximately 27 % less number of edges than top-down did for this sentence.

This phenomenon occurs because bottom up processing takes advantage of lexicon information. It does not have the overhead listing of all possible parses without processing the input as is the case with top-down processing.
(In fact most of the edges created by top down and not by bottom up is in the form constituent -> 'terminal word' )
On the other hand, top-down parser never creates edges of S -> ... that does not lead to sentences.
With bottom up parsing , we can see attempts at forming an S, in the middle of the sentence even though we don't have recursive production rules for S such as S-> S NP

In general, I believe bottom-up parsing would perform better for grammars with a huge lexicon.
For grammars with many production rules leading to an S and small lexicon, top-down parser may be more advantageous to be used efficiently.

Question 6

Bottom-up parser can create an edge such as

S -> NP*VP for the
'the cookie' part

In fact, bottom-up parser can find sentences in middle of a sentence simply because, given a complete edge ("NP" in this case), it looks for all rules starting with this constituent

Top down parser would not produce sentences in middle positions with this grammar. Because the only production rule for starting sentences is S-> * NP VP and no production rule expects S as a first constituent. In the case of 'the cookie', when top down parser has processed 'John ate', it has only predictions in the form of an NP (coming from VP*NP) and there are no production rules with NP on LHS starting with an S

Top-down parser produces superfluous edges such as

NP -> * I at the start of the parse because it just creates edges based on the grammar without looking up actual word, so instead of immediately acknowledging John is an 'NP', it plots out all possible starts of a sentence in the grammar and gets down to listing all terminals. Because bottom up parser utilizes lexicon information, it does not create such edges.

Question 7



First parse for the sentence



Second parse for the sentence

I found a successful parse with 37 edges. The strategy is as follows

First
!.use bottom up parsing to recognize each individual word e.g.
e.g. N-> * 'table'
N-> 'table' *
2. Apply fundamental rule to edges, to form nonterminals out of terminals created in the first step
3. Make top down initialization
4. Make top down predictions to set out possible productions for a sentence
5. Apply fundamental rule to non-terminals
6. Carry out top-down strategy when non-terminals created in prev. state become "dense" enough. (S-> NP VP VP-> V NP VP-> V NP PP)



Question 8

51 edges are created with earley parse
, which shows higher efficiency for this sentence given other strategies, but not a significantly different performance over bottom up parsing for this sentence. It is better than bottom up processing in the sense that it does not create infeasible S edges (where S cannot start such as in tthe middle of a sentence). It is more efficient than top down processing because knowing a terminal, it can cut down on the proliferation of terminal rules each time e.g. knowing john is a name and a name can be one of feasible constitutent of a start sentence, it can match the NP phrase
without looking up starting possibilities of det->'the' etc. .

Question 9

Even if there are superpolynomial parses for a tree, the chart can fit them because it has subparses of previous states and recursively it can combine the whole parse from its parts by going back to previous states
for example

For example
We understand that at least one successful parse has been made when we see
|================| S -> NP VP
from then on we can check those edges with VP spanning to the end.
we find two VP parses in the form
|. [------------]|
which are the two parses
VP-VP PP
VP->V NP

now lets take VP-> VP PP
we know VP was in the end and within VP, PP is the last constituent. We then proceed to look for edges ending at PP
and this recursion continues until we find all feasible parses subject to
-The sequence of constituents in rules for subtrees whole of sentence
-Number of constituents

e.g. Suppose our sentence length is 7. if we find a VP at the end spanning 6 words but there are no NPs at the start with 1 word token then the parse for this rule (where LHS=VP) is discarded.

Jurafsky-Martin simply adds explicit pointers to previous states to achieve compactness. I believe this approach can also be used even though it may not seem as feasible as doing look ups