PeterBURG Description

Table of contents:

1. PeterBURG synopsis.
2. PeterBURG parameters:

  • tree intrface
  • nonterminals set
  • attributes data type

  • 2. Grammar functor:
  • semantic
  • remantic
  • predicate
  • rule
  • module Table
  • module Labeler
  • module Reducer
  • module Verify

  • 3. Additional functors


    The PetersBURG logical structure is shown at the picture below. In order to use BURS algorithm provided by PeterBURG one need to supply three modules of certain module types.

    First of all an interface to tree for rewriting needs to be provided. This interface can be considered as a wrapper of the actual tree representation. It seems any reasonable tree-like data structure could easily be wrapped in such a way and so be adapted for PeterBURG exploration.

    In addition to tree interfaces to nonterminals set and attributes data type must be supplied.

    Being instantiated for modules described above PeterBURG provides facilities for labeling and reducing of tree and also for verification of the interfaces and printing of intermediate data for debugging purposes.

    Tree interface

    Tree interface for PeterBURG is defined as module type Tree and constists of the following entities:

  • type t - type of the tree
  • val terminals : int - number of terminals. Terminals values must fit into interval 0..terminals-1
  • val degree : int - degree of the tree
  • val term : t -> int - gets terminal label of given node
  • val node : int -> t - shallow conversion from terminal to tree node (for debugging purposes)
  • val sons : t -> t list - gets list of sons from given node
  • val toString : t -> string - shallow string representation

  • Nonterminals set

    Nonterminals set interface must be provided by module of module type Nonterminals consisting of two items:

  • val number : int - number of nonterminals in BURS grammar. Nonterminals values must fit into interval 0..number-1
  • val toString : int -> string - string representation of given nonterminal

  • Attributes data type

    Atribute is a value derived in tree node together with some nonterminal. This value is calculated from given rule, nonterminals labels of all sons of the node and their attribute values. module type Attribute comprises all needed entities:

  • type t - the type of attribute value
  • val cost : t -> int - the cost of the attribute. This cost actually participates in dynamic programming decision
  • val (<=) : t -> t -> int - ordering function. This function can be used by PeterBURG to define order of reductions during reduce stage (subtree with least attribute value will be reduced first). a <= b returns 1 if a < b, 0 if a = b and 1 if a > b. PeterBURG also provides default function nosort to use when there is no need to control order of reductions
  • val toString : t -> string - string representation of attribute value
  • Grammar functor

    Functor Grammar takes interfaces for tree (Tree), nonterminals set (Nonterm) and attribute data type (Attr) and instantiates all BURS functions for them.

    Both nonterminals and terminals are treated as integers inside Grammar module since appropriate functions provided by Tree and Nonterminals interfaces.

    type sema = Tree.t -> Attr.t list -> Attr.t represents semantic action performed on tree node and attributes of it's sons during labeling stage.

    type 'a rema = Tree.t -> Attr.t -> 'a list -> 'a is the type of action performed over tree node, it's attribute and result of reduce for all it's sons during reduce stage. The polymorphic parameter 'a represents type of value obtained as a result of reduce.

    type predic = Tree.t -> Attr.t list -> bool is the type of predicate that can guard application of rule. The predicated rule can only be applied when predicate being tested for tree node and attributes of all it's sons returns true.

    Two types provided by Grammar functor to denote BURS rule. First of them - type 'a core - is actually the rule comprising miscellaneous parts (deriving nonterminal, tree node terminal, semantic actions for label and reduce etc.) The second one - type 'a rule = 'a core * string - is just the same structure decorated by string label identifying rule for debugging purposes.

    Several functions are provided to handle rules:

  • val rule : nonterm * Tree.t * nonterm list * sema * 'a rema -> 'a core - creates non-predicated rule. rule n t [n1; n2; ...; nk] lab red creates rule deriving nonterminal n for tree node t with labeling action lab and reducing action red when all sons of the node have labeled with nonterminals n1, n2, ..., nk correspondingly
  • val rule_p: nonterm * Tree.t * nonterm list * predic * sema * 'a rema -> 'a core - the same, but creates predicated rule
  • val chain : nonterm * nonterm * sema * 'a rema -> 'a core - creates chain non-predicated rule
  • val chain_p: nonterm * nonterm * predic * sema * 'a rema -> 'a core - creates chain predicated rule
  • val toString: 'a rule -> string - converts rule to readable format

  • module Table represents parsing table. This table used to simplify matching of rules with the tree and logically can be considered as two-dimensional table indexed by node degree and terminal number.

    Following entities are defined in the module:

  • type 'a t - type of the table
  • type 'a rc = Ok of 'a t | Fail of string - type of return code of table build function
  • val build: 'a rule list -> 'a rc - function to build table from list of rules
  • val toString: 'a rc -> string - readable representation for debugging purposes

  • module Labeler collects functions and types for labeling stage of BURS process. There are:

  • exception Nomatch of Tree.t - exception raised when no rule could be applied to node passed with exception as a parameter
  • type 'a t - type representing labeling result
  • type 'a rc = Ok of 'a t | Fail of string - return code of labeling function
  • val toString : 'a rc -> string - debugging function
  • val run : Tree.t -> 'a Table.rc -> 'a rc - labeling function

  • module Reducer collects functions and types for reduce stage of BURS process. There are:

  • type 'a rc = Ok of 'a t | Fail of string - return code of reducing function
  • val toString : 'a rc -> string - debugging function
  • val run : 'a Labeler.rc -> 'a rc - reducing function

  • module Verify serves to verification of some guard properties of modules provided as parameters. For example, it checks that Tree.term (Tree.node i) = i for all i in [0..Tree.terminals-1] etc. It is recommended to use verification after first instantiation of functor for its parameters to check consistency of interfaces. Verification entities are:

  • type t = Yes | No of string - result of verification
  • val run : unit -> t - verification function

  • Additional functors

    Two additional functors are provided besides Grammar. First of all, functor BURS implements conventional BURS e.g. dynamic programming without labeling attributes. Then, functor ConstBURS implements BURS without predicates and with constant costs.

    Both of these functors are implemented as re-instantiations of main Grammar functor and so have near the same interfaces.


    Copyright © OOPS Team