GLR Actions - RopleyIT/GLRParser GitHub Wiki
When a merge function is called, it is passed two parameters that contain the
two parse trees for the set of tokens that reduced to the non-terminal token at
the left hand side of the rule being merged. Each parameter is an instance of
the class NonTerminalToken, which is described here.
The NonTerminalToken class implements the IToken
interface, just the same as the input sequence of events or tokens that feed the
parser. Hence objects of this class have all the properties and methods expected
for that interface. In addition, objects of this class also have an indexable
property called Children that contains the ordered list of child tokens that
were reduced to the current non-terminal token in a previous reduction. The
details for each of these properties is given below.
| PROPERTY | DESCRIPTION |
int Type |
Returns the integer value of the non-terminal token type from the
parser. This can be used as an index into the parser's Tokens
property to find the character string name of the non-terminal token in
the grammar. This property is required by the IToken
interface that the NonTerminalToken class implements. |
string Position |
This is part of the IToken interface. If filled
in by the input tokeniser for the parser, this gives position
information for a given token, and is typically used to help a developer
spot where an error occurred in a parser's input sequence. For a
NonTerminalToken, this returns the Position
value for the leftmost input token in the reduction. |
IToken[] Children |
This is the list of tokens (terminal and non-terminal) from the
right hand side of the grammar rule that was reduced to the current
NonTerminalToken. Note that some of these might be of type
ParserToken (or some other implementation of IToken
returned by the input tokeniser) if they are terminal tokens, and some
will be of type NonTerminalToken because ther parser has
progressed through several reductions to reach the current
NonTerminalToken. Hence the current object is the root of a parse
tree that describes how all its constituent input tokens were parsed,
and reduced into a particular configuration of non-terminals and
terminals. |
object Value |
Returns the computed value of the current NonTerminalToken.
This is part of the IToken interface. The first time this
is read, it executes the various action functions of the rule reductions
that led to this particular NonTerminalToken. These action
functions each return the values to be assigned to their various
NonTerminalToken objects in the same order they would have been
executed in an LR(1) parse. Hence you should not try to read the
Value property until you are ready for any side effects of these
action functions to take place. Note that the value is cached in the
object after the first time it is read. Equally important to note, it is
possible that none of the action functions have been executed even
though the parse of the input tokens is over. This is because the
execution of the action functions has been deferred until you have
merged, thus selecting just one of the candidate parses. To force
the action functions to be executed, you must read the Value
property of the NonTerminalToken returned by the grammar's top
level non-terminal token. |
When you write the merge code for the reductions to a particular non terminal,
you will need to use the structure of the parse tree as determined by the
hierarchy found in the Children property, and (if safe to call them)
the values returned by the various Value properties for each
token in the tree. This is the information available to you to help decide
which reduction to keep, and which to discard. If you keep both, and let the
decision be made later in the parse, you may have more information to help
you make the correct decision. However, the parse trees passed to the merge
function will be deeper and more complicated to navigate.
Examine the merge code found in the description of
how to write inline merge functions. See
how the top two levels of the tree beneath the expression node are inspected to
see which way round the tree should be based on operator precedence. Notice the
use of the Children property, and the checks that the various child
nodes are NonTerminalTokens. Notice also how the GLR parser will
have produced both the wrong and the correct reductions of the input token
sequence, and passed them both to the merge function. All the merge function is
doing is discarding the one that has interpreted the operator precedence
wrongly.