A bottom-up template grammar has the format of a top-down template grammar (see Top-Down Template Grammar) with a number of differences described in this section.
The main semantic difference between a top-down template grammar and bottom-up template grammar is the following: a top-down template grammar selects an execution alternative from a subset of execution alternatives with FIRST sets containing a look-ahead terminal symbol, whereas a bottom-up template grammar allows for delayed selection of an execution alternative based on terminal symbols consumed while an execution alternative was indeterminate.
Example
Consider the grammar
S: "a" "b" "c" | "a" "b" "d" . . ;If this is a top-down template grammar, it cannot deterministically select the alternative ‘"a" "b" "c"’ or ‘"a" "b" "d" . .’, because they both start with the same terminal symbol
"a". If this is a bottom-up template grammar, it can deterministically select one of the alternatives after processing their common prefix ‘"a" "b"’.
A bottom-up template grammar can have an associated source PCFG with productions inferred from the productions of the bottom-up template grammar.
Named terminal symbol segments can mark the productions of a source PCFG with terminal symbols at the right-hand side (see Named Segments).
The specifiers #l-… and #r… mark the productions of a source PCFG with nonterminal symbols at the right-hand side (see Marking a Left-Hand Side and Marking a Right-Hand Side).
The adaptive bottom-up parser abu-parser cannot use a bottom-up template grammar directly.
A bottom-up template grammar requires conversion to a top-down template grammar for using by abu-parser.
If a bottom-up template grammar contains a source PCFG markup, the conversion preserves source PCFG information.
The conversion typically involves the following steps:
rege-markup-cfg tool.
See rege-markup-cfg, for more information.
rege-vit tool for the ability to process entire parse units up to specified length.
See rege-vit, for more information.
This is an optional step.
rege-bottom-up tool.
See rege-bottom-up, for more information.
The adaptive bottom-up parser abu-parser can use the top-down template grammar.
Example
If the file bu.rg contains a bottom-up template grammar (e.g. from the previous example), the commands
$ rege-markup-cfg -o bu-markup.rg bu.rg $ rege-bottom-up -o td.rg --cfg-markup bu-markup.rgcreate the file td.rg that contains a top-down template grammar for using by
abu-parser.