Grammars and Parsing

Grammar

Rules for describing a language.

We are interested in syntactic grammar - here the rules describe the syntax of the grammar. There are also semantic grammars, text grammars, etc.

Parser

An algorithm for analysing sentences given a grammar:

• may just give yes/no answer to the question Does this sentence conform to the given grammar: such a parser is termed an accepter

• may also produce a structure description ("parse tree") for correct sentences:

Different Tree Notations

Here is the same tree in list notation ...

(S (NP (NAME John))
   (VP (V fed)
       (NP (DET the))
           (N numbat))))

s(np(name(john)),
  vp(v(fed),
     np(det(the),
        n(numbat))))

* Numbats are ant-eating marsupials now confined to the south-west corner of Western Australia, though previously they were more widespread.

www.wilderness.org.au

Describing Syntax: Context Free Grammars (CFGs)

Context Free Grammars (CFGs)

• P is a set of context-free productions, i.e. objects of the form X  → β, where X is a member of N, and β is a string over the alphabet A
• A is an alphabet of grammar symbols;
• N is a set of non-terminal symbols;
• T is a set of terminal symbols (and N ∪ T = A);
• S is a distinguished non-terminal called the start symbol (think of it as "sentence" in NLP applications).

CFG Example

T = {fed, John, numbat, the}

N = {S, NP, VP, N, V, NAME, DET}

P = {S → NP VP, VP→ V NP, NP→ NAME, NP→ DET N,
       NAME→ John V→ fed, DET→ the, N→ numbat} .

Notice how the productions were split into grammar rules and lexicon above. N, V, NAME and DET are called pre-terminal or lexical symbols.

Digression

Definition of String

• A string over the alphabet A is a sequence of zero or more symbols from A.
• The string with zero symbols is often written as ε (empty string).
• The length of the string is the number of symbols in it.

Strings 2

• A non-empty string means a string other than ε.

• The strings over the alphabet A are sometimes referred to as A*. (This has nothing to do with the A* in A* search.)

• A⁺ then refers to the non-empty strings over A.

You are now in a position to do the exercises on grammars at http://www.cse.unsw.edu.au/~cs9414/Exercises/grammars.html

Parsing as Reverse of Derivation

Parsing might be the reverse of this process (doing the steps shown above in reverse would constitute a bottom-up right-to-left parse of John fed the numbat.)

Top-Down Parsing with CFGs

Basic Top-Down "predictive" parser

• In this parsing method, we guess ("predict") what the next production to be applied should be

• in case we guess wrong, we stack any alternatives so that we can come back to them if necessary.

• We "cross off" the leading item of our current sentential form if it can be matched against the next word of the sentence.

• This algorithm can take exponential time on bad sentences for bad CFGs.

• With "well-behaved" grammars, it can be a linear time algorithm. NL grammars are not usually all that well-behaved.

Predictive Parsing Example

Example: Using this grammar:

S → NP VP
NP → DET N | NAME
PP → PREP NP
VP → V | V NP | V NP PP | V PP

we parse this sentence: ₁ The ₂ dogs ₃ barked. ₄

Predictive Parsing Example 2

Bottom-up parsing

The dogs barked	→ DET N V
	→ NP V
	→ NP VP
	→ S

Parsing Efficiency

Using bottom-up parsing methods, all CFGs can be parsed in n³ steps, where n is the length of the sentence, whereas predictive parsing can take exponential time (i.e. much slower). The reason predictive parsing may take exponential time is that it may re-parse pieces of the sentence, particularly confusing sentences (like the horse [that was] raced past the barn fell ):

Indication of parsing state	Comment
The horse raced past the barn ...	"past the barn" parsed as PP, "raced" parsed as [main] verb
The horse raced past the barn fell	oops!
The horse ...	backtrack to this point and start over
The horse raced past the barn fell	"past the barn" parsed as PP again: "raced" parsed as ADJ [from past participle] starting the ADJP ["raced past the barn"]

Chart Parsing

• The chart is a record of all the substructures (like past the barn) that have ever been built during the parse.

• A chart is sometimes also called a well-formed substring table.

Chart Parsing Advantages

• Charts help with "elliptical" sentences:

  1: Q. How much are apples?
  2: A. Thirty cents each.
  3: Q. Plums?

• An attempt to parse 3 as a sentence fails, but all is not lost, as the analysis of plums as an NP is on the chart.

• Successful parsing of the entire utterance as any kind of structure can be useful.

A Bottom-Up Chart-Based Parsing Algorithm

• parses a sentence of length N within N³ steps.

• Does better than this (N² or N steps) with well-behaved grammars.

• constructs phrasal or lexical constituents of a sentence.

• use the sentence the green fly flies as an example.

• Annotate the sentence with positions: ₀the₁green₂fly₃flies₄.

Chart Parser 2

• The parsing process succeeds if an S (sentence) constituent is found covering positions 0 to 4.

• Operations (2) to (9) below do not completely specify the order in which parsing steps are carried out: one reasonable order is
  • scan a word (as in (3))
  • perform all possible parsing steps as specified in (4) - (7) before scanning another word.
  • Parsing is completed when the last word has been read and all possible subsequent parsing steps have been performed.

Chart Parser 3

Parser inputs: sentence, lexicon, grammar.

Parser operations:

1. The algorithm operates on two data structures: the active chart - a collection of active arcs (see (4) below) and the constituents (see (3) and (6)). Both are initially empty.

2. The grammar is considered to include lexical insertion rules: for example, if fly is a word in the lexicon/vocabulary being used, and if its lexical entry includes the fact that fly may be a N or a V, then rules of the form N  →   fly and V  →   fly are considered to be part of the grammar.

Chart Parser 4

3. As a word (like fly) is scanned, constituents corresponding to its lexical categories are created:

   N1: N  →   fly FROM 2 TO 3, and

   V1: V  →   fly FROM 2 TO 3

4. If the grammar contains a rule like NP  → DET ADJ N, and a constituent like DET1: DET → the FROM m TO n has been found, then an active arc

   ARC1: NP → DET1 •  ADJ  N FROM m TO n

   is added to the active chart. (In our example sentence, m would be 0 and n would be 1.) The "•" in an active arc marks the boundary between found constituents and constituents not (yet) found.

   

Chart Parser 5

5. Advancing the "•": If the active chart has an active arc like:

   ARC1: NP → DET1 • ADJ N FROM m TO n

   and there is a constituent in the chart of type ADJ (i.e. the first item after the •), say

   ADJ1:  ADJ  →   green FROM n TO p

   such that the FROM position in the constituent matches the TO position in the active arc, then the "•" can be advanced, creating a new active arc:

   ARC2:  NP → DET1  ADJ1  •  N FROM m TO p.

   DET ADJ N" >

Chart Parser 6

6. If the process of advancing the "•" creates an active arc whose "•" is at the far right hand side of the rule: e.g.

   ARC3: NP → DET1 ADJ1 N1•  FROM 0 TO 3

   then this arc is converted to a constituent.

   NP1: NP → DET1 ADJ1  N1 FROM 0 TO 3.

   

   Not all active arcs are ever completed in this sense.

Chart Parser 7

7. Both lexical and phrasal constituents can be used in steps 3 and 4: e.g. if the grammar contains a rule S →   NP VP, then as soon as the constituent NP1 discussed in step 5 is created, it will be possible to make a new active arc

   ARC4: S →   NP1 • VP FROM 0 TO 3

   

Chart Parser 8

8. When subsequent constituents are created, they would have names like NP2, NP3, ..., ADJ2, ADJ3, ... and so on.

9. The aim of parsing is to get phrasal constituents (normally of type S) whose FROM is 0 and whose TO is the length of the sentence. There may be several such constituents.

Final State of Chart for "The green fly flies"

Chart Parsing Example

Grammar: 1. S → NP VP 2. NP → DET ADJ N 3. NP → DET N 4. NP → ADJ N 5. VP → AUX V NP 6. VP → V NP

Lexicon: the... DET large... ADJ can... AUX, N, V hold... N, V water... N, V

Sentence: ₀ The ₁ large ₂ can ₃ can ₄ hold ₅ the ₆ water ₇

Chart Parsing Example 2

Steps in Parsing:

*sentence*: the   *position*: 1
*constituents*:
DET1: DET → "the" from 0 to 1
*active-arcs*:
ARC1: NP → DET1 • ADJ N from 0 to 1 [rule 2]
ARC2: NP → DET1 • N from 0 to 1     [rule 3]

*sentence*: the large   *position*: 2
*constituents*: add
ADJ1: ADJ → "large" from 1 to 2
*active-arcs*: add
ARC3: NP → DET1 ADJ1 • N from 0 to 2 [arc1*→]
ARC4: NP → ADJ1 • N from 1 to 2      [rule 4]

Chart Parsing Example 3

*sentence*: the large can  *position*: 3
*constituents*: add
NP2: NP → DET1 ADJ1 N1 from 0 to 3  [arc3*→]
NP1: NP → ADJ1 N1 from 1 to 3       [arc4*→]
N1: N → "can" from 2 to 3
AUX1: AUX → "can" from 2 to 3
V1: V → "can" from 2 to 3
*active-arcs*: add
ARC5: VP → V1 • NP from 2 to 3     [rule 6]
ARC6: VP → AUX1 • V NP from 2 to 3 [rule 5]
ARC7: S → NP1 • VP from 1 to 3     [rule 1]
ARC8: S → NP2 • VP from 0 to 3     [rule 1]

Chart Parsing Example 4

*sentence*: the large can can *position*: 4
*constituents*: add
N2: N → "can" from 3 to 4
AUX2: AUX → "can" from 3 to 4
V2: V → "can" from 3 to 4
*active-arcs*: add
ARC9: VP → AUX1 V2 • NP from 2 to 4 [arc6•→]
ARC10: VP → V2 • NP from 3 to 4     [rule 6]
ARC11: VP → AUX2 • V NP from 3 to 4 [rule 5]

Chart Parsing Example 5

*sentence*: the large can can hold
*position*: 5
*constituents*: add
N3: N → "hold" from 4 to 5
V3: V → "hold" from 4 to 5
*active-arcs*: add
ARC12: VP → AUX2 V3 • NP from 3 to 5 [arc11•→]
ARC13: VP → V3 • NP from 4 to 5      [rule 6]

Chart Parsing Example 6

*sentence*: the large can can hold the
*position*: 6
*constituents*: add
DET2: DET → "the" from 5 to 6
*active-arcs*: add
ARC14: NP → DET2 • ADJ N from 5 to 6 [rule 2]
ARC15: NP → DET2 • N from 5 to 6     [rule 3]

Chart Parsing Example 7

*sentence*: the large can can hold the water
*position*: 7
*constituents*: add
S2: S → NP1 VP2 from 1 to 7         [arc7*→]
S1: S → NP2 VP2 from 0 to 7         [arc8*→]
VP2: VP → AUX2 V3 NP3 from 3 to 7   [arc12*→]
VP1: VP → V3 NP3 from 4 to 7        [arc13*→]
NP3: NP → DET2 N4 from 5 to 7       [arc15*→]
N4: N → "water" from 6 to 7
V4: V → "water" from 6 to 7
*active-arcs*: add
ARC16: VP → V4 • NP from 6 to 7 [rule 6]
ARC17: S → NP3 • VP from 5 to 7 [rule 1]

Chart Parsing Example 8

Doing the same steps diagrammatically:

the large can

the large can can

the large can can hold

the large can can hold the

the large can can hold the water

You are now in a position to do the exercises on grammars at http://www.cse.unsw.edu.au/~cs9414/Exercises/parsing.html

Notes on Chart Parsing

• disadvantage of bottom-up method: will find irrelevant constituents like the VP hold the water which would not be noticed by a top-down parser, because it wouldn't be looking for (the start of) a VP at that point;

• a top-down CFG parser can have a chart (but you have to keep track of which constituents are only hypothesized, and which have actually been substantiated by the text being parsed);

• mixed-mode parsers have best aspects of both methods (disadvantage - more complicated)

Recording Sentence Structure

A frame-like, or slot/filler representation works: John fed the numbat

(S SUBJ (NP NAME "John")
   MAIN-V feed
   TENSE past
   OBJ (NP DET the HEAD numbat))

s(subj(np(name('John'))),
  mainv(feed),
  tense(past),
  obj(np(det(the), head(numbat))))

Grammars and Logic Programming

• Grammar rules can be encoded directly in Prolog:

  S → NP VP

  .....

  s(P1,P3) :- np(P1,P2), vp(P2,P3).

• That is, there is an S FROM sentence position P1 TO position P3 if
  there is an NP FROM P1 TO P2 and
  there is a VP FROM P2 TO P3.
  Similarly:

  VP→ V NP	.....	vp(P1,P3) :- v(P1,P2), np(P2,P3).
  NP→ NAME	.....	np(P1,P2) :- propernoun(P1,P2).
  NP→ DET N	.....	np(P1,P3) :- det(P1,P2), noun(P2,P3).

Prolog Lexicon

• The lexicon can be defined by predicates like:

  NAME → John	.....	isname(john).
  V → fed	.....	isverb(fed).
  DET → the	.....	isdet(the).
  N → numbat	.....	isnoun(numbat).

Rules to Build Lexical Constituents

• Predicates are needed, to link the lexicon to the grammar.

• For each lexical category, like DET, you define a predicate, like

  det(From, To) :-
      word(Word, From, To),
      isdet(Word).
  

  This predicate is true only if the word between the specified position is of that category.

• Here word(Word, From, To) signifies that Word is there in the input sentence between positions From and To.

Rules to Build Lexical Constituents 2

• Similarly:

  noun(From, To) :-
      word(Word, From, To), isnoun(Word).
  v(From, To) :-
      word(Word, From, To), isverb(Word).
  propernoun(From, To) :-
      word(Word, From, To), isname(Word).
  

Words, Parsing

• To use the system as so far described, assert the words in their sentence positions:

  word(john, 1, 2).
word(fed, 2, 3).
word(the, 3, 4).
word(numbat, 4, 5).

• This is equivalent to annotating the sentence as: ₁ John ₂ fed ₃ the ₄ numbat. ₅

• then use the Prolog query ?- s(1,5). This will result in Yes.

• A more elaborate parser would take a list of words as input, and generate word facts like those above.

Parsing

To get at the structure of the sentence, add extra arguments to pass the structure back across necks as it is built:

   s(P1,P3,s(NP,VP)) :-
       np(P1,P2,NP), vp(P2,P3,VP).

   vp(P1,P3,vp(v(Verb),NP)) :-
       v(P1,P2,Verb), np(P2,P3,NP).
   np(P1,P2,np(name(Name))) :-
       proper(P1,P2,Name).
   np(P1,P3,np(det(Det),noun(Noun))) :-
       det(P1,P2,Det), noun(P2,P3,Noun).

Structure Passing with Lexical Constituents

   det(From, To, Word) :-
       word(Word, From, To), isdet(Word).

   noun(From, To, Word) :-
       word(Word, From, To), isnoun(Word).
   v(From, To, Word) :-
       word(Word, From, To), isverb(Word).
   proper(From, To, Word) :-
       word(Word, From, To), isname(Word).

Query to Start the Parser

• The query to start the parser then becomes
  ?- s(1, 5, Parse).
Parse=
s(np(name(john)), vp(v(fed), np(det(the), noun(numbat))))

• To experiment with this code, see http://www.cse.unsw.edu.au/~billw/cs9414/notes/nlp/dcg2.pl

PP attachment

The boy saw the man on the hill with the telescope

PP Attachment Parse Trees

The two visual interpretations correspond to two different parses (coming from different grammar rules (VP → V NP PP and NP → NP PP):

or

Other Syntax Representation and Parsing Methods

• augmented transition networks (ATN)
• generalised phrase structure grammar (GPSG)
• head driven phrase structure grammar (HDPSG)
• unification-based parsing methods
• lexical functional grammar (LFG)
• shift-reduce parsers (modified to handle ambiguous grammars)
• Marcus parsing (buffers and lookahead)
• systemic grammar (semiotics-driven)
• semantic grammars (specialise lexical categories to a range of semantic subcategories: grammar potentially becomes huge)

Limitations of Syntax in NLP

• it is reasonable to ask for syntactically correct programs, but unrealistic to ask for syntactically correct NL. Written NL material is sometimes correct, but spoken utterances are rarely grammatical. NL systems must be syntactically and semantically robust.

• some approaches have sought to be semantics-driven, to avoid the problem of how to deal with syntactically ill-formed text. However, some syntax is essential - else how do we distinguish between Cyril loves Audrey and Audrey loves Cyril?

Summary: Grammars and Parsing

There are many approaches to parsing and many grammatical formalisms. Some problems in deciding the structure of a sentence turn out to be undecidable at the syntactic level. We have concentrated on a bottom-up chart parser based on a context-free grammar. We will subsequently extend this parser to augmented grammars.

CRICOS Provider Code No. 00098G
Last updated:
Copyright © Bill Wilson, 2007, except where another source is acknowledged.