/* cfgparser.h - definitions for the SELVA chart-based CFG syntax parser. */ /* Last edited on 2005-03-03 15:00:43 by stolfi */ #ifndef cfg_types_H #define cfg_types_H #include #include #ifndef FALSE typedef enum {FALSE, TRUE} bool_t; #define FALSE FALSE #endif /* THE GRAMMAR Uma /gramática/ {G} consiste de um conjunto de /símbolos/, e um conjunto de /regras/. Cada símbolo da gramática é identificado por um {GSymbId-t} entre 1 e {NS(G)}. Cada regra {r} da gramática é identificada por um {GRuleId_t} entre 1 e {NR(G)}, e possui três campos {head(r)}, {left(r)}, {right(r)}, que podem ser símbolos ou (no caso de {left(r)}) NULL. Neste último caso a regra é /unária/. Em toda regra unária {A -> B}, o {GSymbId_t} de {B} deve ser maior que o de {A}. Para otimização, as regras são numeradas em ordem crescente do {GSymbId_t} de {left(r)} (???). The pointer {G->firstR[S]} and the field {nextR} in each rule define a linked list of all /binary/ rules that have symbol {S} as their {R} field. In this list, the rules are sorted by their {L} field in /decreasing/ order. The pointer {G->firstU[S]} and the field {nextR} in each rule define a similar list of all /unary/ rules that have symbol {S} as their {R} field. */ /* A non-negative integer that identifies a symbol of the grammar. */ typedef int GSymbId_t; /* A special {GSymbId_t} meaning "no symbol": */ #define NOSYMB 0 /* A non-negative integer that identifies a rule of the grammar. */ typedef int GRuleId_t; /* A special {GRuleId_t} meaning "no rule": */ #define NORULE 0 /* A rule of the grammar: */ typedef struct GRule_t { GSymbId_t H; GSymbId_t L; GSymbId_t R; GRuleId_t nextR; /* Next rule with same {R} field, or {NORULE} if none. */ } GRule_t; /* The grammar: */ typedef struct Grammar_t { int NS; /* Number of symbols. */ int NR; /* Number of rules. */ char **sname; /* {sname[S]} is an external name of symbol {S}. */ GRule_t *rule; /* The rules, indexed by {GRuleId_t}. */ GRuleId_t *firstR; /* {firstR[S]} is a binary rule with {R == S}, or {NORULE}. */ GRuleId_t *firstU; /* {firstU[S]} is an unary rule with {R == S}, or {NORULE}. */ } Grammar_t; /* INPUT PHRASE GRAPH The input string is represented by a /phrase graph/, that consists of /phrase nodes/ connected by /token arcs/. The phrase graph is acyclic and has a single source and a single sink. */ /* A positive number identifying an input graph node, or NONODE: */ typedef int PNodeId_t; #define NONODE 0 /* A positive number identifying an input graph arc, or NOARC. */ typedef int PArcId_t; #define NOARC 0 typedef struct PArc_t /* A token arc */ { GSymbId_t symb; /* Grammar symbol assigned by preprocessor. */ PNodeId_t org; /* Origin node in phrase graph. */ PNodeId_t dst; /* Destination node in phrase graph. */ char *aname; /* A string to print when showing this arc. */ } PArc_t; typedef struct Phrase_t { int NN; /* Number of phrase nodes. */ int NA; /* Number of phrase arcs. */ PArc_t **arc; /* List of {NA} token arcs, indexed by {PArcId_t}. */ } Phrase_t; /* PARSE TREES A /parse tree/ is an abstract concept that describes a single possible parsing of a single path in the phrase graph. Every node {n} of a parse tree is labeled with a symbol {symb(n)} of the grammar. If {n} is an internal node, it is also labeled with a rule {rule(n)} for the symbol {symb(n)}. If that rule is of the form {A -> B C}, then {n} has two ordered children {r} and {s}, with {symb(r) = B} and {symb(s) = C}. The path covered by {r} must end where the path covered by {s} starts. If the rule is of the form {A -> B}, then {n} has a single child If {n} is a terminal node, instead of a rule it has a single arc {iarc(n)} of the input phrase graph. PARSE CHART The output of a parse is a/parse chart/, a data structure describing in a compact form all possible parse trees of all paths through the input phrase graph, according to the given grammar. Each node {n} of this structure describes a set {T(n)} of possible parse trees, covering paths between two specific nodes {org(n)} and {dst{n)} of the input phrase. There are three types of nodes: {CSymb_t} - represents all possible parse trees for all paths between {org(n)} and {dst(n)} that have a specific symbol {symb(n)} as their root. {CRule_t} - represents all possible parse trees for all paths between {org(n)} and {dst(n)} that have a specific rule of the grammar as the root rule. A boolean field {term(n)} in an {CSymb_t} determines whether it is /terminal/ or /non-terminal/. In the first case, {n} points to an arc of the input phrase. In the second case, {n} points to a list {alts(n)} of {CRule_t} nodes. The boolean field {reachable} is used to mark {CSymb_t} nodes that are reachable from a certain top-level axiom symbol. */ typedef struct CSymb_t /* For a certain symbol {S} between certain nodes {i,j}. */ { GSymbId_t symb; /* The symbol {S}. */ bool_t term; /* TRUE for terminal nodes. */ bool_t reachable; /* Node is reachable from the top-level axiom. */ void *info; /* Either one or more {CRule_t}s, or a {PArc_t} if terminal. */ struct CSymb_t *next; /* Next {CSymb_t} for same {i,j}. */ } CSymb_t; typedef struct CRule_t /* For a certain rule {H --> L R} between certain nodes {i,j}. */ { GRuleId_t irule; /* The grammar rule, say {H --> L R}. */ PNodeId_t cut; /* Phrase node where the {L} and {R} parts meet. */ CSymb_t *Ln; /* Subchart for {L} over {i,cut}, or NULL if {L == NOSYMB}. */ CSymb_t *Rn; /* Subchart for {R} over {cut,j}. */ struct CRule_t *next; /* Next {CRule_t} for the same head {H} and same {i,j}. */ } CRule_t; /* Conceptually, the parse chart is a table with an entry {S,i,j} for every pair of nodes {i,j} from the input phrase, and every symbol {S} from the grammar. Each entry contains either an {CSymb_t} or NULL. Hopefully this table is quite sparse. */ typedef struct Chart_t /* The chart. */ { int NN; /* Number of phrase graph nodes. */ CSymb_t **ent; /* Triangular array of lists of {CSymb_t}. */ } Chart_t; typedef struct ChartKey_t /* Key of a chart index. */ { GSymbId_t S; /* Symbol of grammar. */ PNodeId_t i; /* Number of starting phrase node. */ PNodeId_t j; /* Number of ending phrase node. */ } ChartKey_t; #endif