Class ShiftReduceParser
source code
object --+
|
api.ParserI --+
|
ShiftReduceParser
- Known Subclasses:
-
A simple bottom-up CFG parser that uses two operations,
"shift" and "reduce", to find a single parse for a
text.
ShiftReduceParser maintains a stack, which records the
structure of a portion of the text. This stack is a list of
Strings and Trees that collectively cover a
portion of the text. For example, while parsing the sentence "the
dog saw the man" with a typical grammar,
ShiftReduceParser will produce the following stack, which
covers "the dog saw":
[(NP: (Det: 'the') (N: 'dog')), (V: 'saw')]
ShiftReduceParser attempts to extend the stack to cover
the entire text, and to combine the stack elements into a single tree,
producing a complete parse for the sentence.
Initially, the stack is empty. It is extended to cover the text, from
left to right, by repeatedly applying two operations:
-
shift moves a
token from the beginning of the text to the end of the stack.
-
reduce uses a CFG
production to combine the rightmost stack elements into a single
Tree.
Often, more than one operation can be performed on a given stack. In
this case, ShiftReduceParser uses the following heuristics
to decide which operation to perform:
-
Only shift if no reductions are available.
-
If multiple reductions are available, then apply the reduction whose
CFG production is listed earliest in the grammar.
Note that these heuristics are not guaranteed to choose an operation
that leads to a parse of the text. Also, if multiple parses exists,
ShiftReduceParser will return at most one of them.
|
|
__init__(self,
grammar,
trace=0)
Create a new ShiftReduceParser, that uses
grammar to parse texts. |
source code
|
|
|
|
|
|
Tree
|
parse(self,
tokens)
Returns:
A parse tree that represents the structure of the given sentence, or
None if no parse tree is found. |
source code
|
|
None
|
_shift(self,
stack,
remaining_text)
Move a token from the beginning of remaining_text to the
end of stack. |
source code
|
|
boolean
|
_match_rhs(self,
rhs,
rightmost_stack)
Returns:
true if the right hand side of a CFG production matches the rightmost
elements of the stack. |
source code
|
|
Production or None
|
_reduce(self,
stack,
remaining_text,
production=None)
Find a CFG production whose right hand side matches the rightmost
stack elements; and combine those stack elements into a single
Tree, with the node specified by the production's
left-hand side. |
source code
|
|
None
|
trace(self,
trace=2)
Set the level of tracing output that should be generated when parsing
a text. |
source code
|
|
None
|
_trace_stack(self,
stack,
remaining_text,
marker=' ')
Print trace output displaying the given stack and text. |
source code
|
|
None
|
_trace_shift(self,
stack,
remaining_text)
Print trace output displaying that a token has been shifted. |
source code
|
|
None
|
_trace_reduce(self,
stack,
production,
remaining_text)
Print trace output displaying that production was used
to reduce stack. |
source code
|
|
None
|
|
|
Inherited from api.ParserI:
batch_iter_parse,
batch_nbest_parse,
batch_parse,
batch_prob_parse,
iter_parse,
nbest_parse,
prob_parse
Inherited from object:
__delattr__,
__getattribute__,
__hash__,
__new__,
__reduce__,
__reduce_ex__,
__repr__,
__setattr__,
__str__
|
|
Inherited from api.ParserI:
batch_test,
get_parse,
get_parse_dict,
get_parse_list,
get_parse_prob
|
|
Inherited from object:
__class__
|
__init__(self,
grammar,
trace=0)
(Constructor)
| source code
|
Create a new ShiftReduceParser, that uses
grammar to parse texts.
- Parameters:
grammar (Grammar) - The grammar used to parse texts.trace (int) - The level of tracing that should be used when parsing a text.
0 will generate no tracing output; and higher
numbers will produce more verbose tracing output. - Overrides:
object.__init__
|
- Returns:
- The grammar used by this parser.
- Overrides:
api.ParserI.grammar
- (inherited documentation)
|
- Parameters:
sent - The sentence to be parsed - Returns: Tree
- A parse tree that represents the structure of the given sentence,
or
None if no parse tree is found. If multiple
parses are found, then return the best parse.
- Overrides:
api.ParserI.parse
- (inherited documentation)
|
|
Move a token from the beginning of remaining_text to the
end of stack.
- Parameters:
stack (list of String and Tree) - A list of Strings and Trees, encoding
the structure of the text that has been parsed so far.remaining_text (list of String) - The portion of the text that is not yet covered by
stack. - Returns:
None
|
- Parameters:
rhs (list of (terminal and Nonterminal)) - The right hand side of a CFG production.rightmost_stack (list of (String and Tree)) - The rightmost elements of the parser's stack. - Returns:
boolean
- true if the right hand side of a CFG production matches the
rightmost elements of the stack.
rhs matches
rightmost_stack if they are the same length, and
each element of rhs matches the corresponding
element of rightmost_stack. A nonterminal element
of rhs matches any Tree whose node
value is equal to the nonterminal's symbol. A terminal element
of rhs matches any String whose type is
equal to the terminal.
|
_reduce(self,
stack,
remaining_text,
production=None)
| source code
|
Find a CFG production whose right hand side matches the rightmost
stack elements; and combine those stack elements into a single
Tree, with the node specified by the production's left-hand
side. If more than one CFG production matches the stack, then use the
production that is listed earliest in the grammar. The new
Tree replaces the elements in the stack.
- Parameters:
stack (list of String and Tree) - A list of Strings and Trees, encoding
the structure of the text that has been parsed so far.remaining_text (list of String) - The portion of the text that is not yet covered by
stack. - Returns:
Production or None
- If a reduction is performed, then return the CFG production that
the reduction is based on; otherwise, return false.
|
|
Set the level of tracing output that should be generated when parsing
a text.
- Parameters:
trace (int) - The trace level. A trace level of 0 will generate
no tracing output; and higher trace levels will produce more
verbose tracing output. - Returns:
None
|
_trace_stack(self,
stack,
remaining_text,
marker=' ')
| source code
|
Print trace output displaying the given stack and text.
- Parameters:
marker - A character that is printed to the left of the stack. This is
used with trace level 2 to print 'S' before shifted stacks and
'R' before reduced stacks. - Returns:
None
|
|
Check to make sure that all of the CFG productions are potentially
useful. If any productions can never be used, then print a warning.
- Returns:
None
|