[prs_gen.h] LALR(1) Parser Generator

contents

The module [prs_gen] performs two main tasks.

1) A set of functions will be used to dynamically create a BNF-like context free grammar definition. ( reentrant )
It is possible to define multiple startsymbols and comment tokens.

2) The latter function create the corresponding parse table and nonterminal classes. The parse table is the input for the parse function.
This creation process is not reentrant. You must synchronize the access to the function within threads.

  The following rules define the abstract syntax. On this base the nonterminal
  classes are created.

  A) well-formed productions:
  1. let X :nil#* :            <0 members>
  2. let X :cons#*: Y Z        <2 members: Y = member && Z = nonterminal>
  3. let X :ign#+ : Y          <1 nonterminal>
  4. let X :name  : X1 .. Xn   <n >= 0 && name =/= { ign#+, nil#*, cons#* }>

  Extension for options (styx version >= 1):

  5. let X :none :            <0 members>
  6. let X :some : Y          <1 member>
  7. let X :name : X1 .. Xn   <n >= 0 && name =/= { ign#+, nil#*, cons#*, none, some }>


  B) construction of the token/nonterminal classes:
  1. X <=> X                          reflexiv
  2. X <=> Y --> Y <=> X              symmetric
  3. X <=> Y && Y <=> Z --> X <=> Z   transitiv
  4. let X :ign#+: Y   --> X <=> Y
  5. let X :cons#*: Y Z --> X <=> Z
  6. X <=> Y && let X :idx: X1 .. Xn && let Y :idy: Y1 .. Ym && idx = idy
     --> n = m && forall i, 1 <= i <= n: Type(Xi) = Type(Yi) && Xi <=> Yi,
                                         where Type(Z) = { token, nonterminal }
  7. all tokens are equivalent.

  C) token/nonterminal classes:
     [X] = { Y | Y <=> X }
     class representants:
     - tokens:       "Tok"
     - startsymbols: language name
     - nonterminals: less nonterminal name according the lexical order

  D) correctness:
  1. X <=> Y --> Type(X) = Type(Y), where Type(Z) = { token, nonterminal }
  2. let X^ :id: a && let X^ :id: b --> a <=> b
  3. let X^ :nil#*: a || let X^ :cons#*: b
     --> not exists P: P = let X^ :id: c && id =/= { ign#+, nil#*, cons#* }
  [ 1,2: checked during construction ]

  Extension for options (styx version >= 1):

  4. let X^ :none: a || let X^ :some: b
     --> not exists P: P = let X^ :id: c && id =/= { ign#+, none, some }
  5. let X^ :none: a
     --> exists P: P = let X^ :some: b
  6. let X^ :some: a
     --> exists P: P = let X^ :none: b

  E) abstract context free grammar:
     NT |--> NT^
     T  |--> T^ ( NT^ T^ are the class representants )

     for all "normal" productions there will be one interface function
     of type 'bool' which returns whether the argument term represents
     a production of this kind and in the positive case all required members.

Types

Grammar definition

PLR_Cfg PLR_createCfg(c_string Language, int version)

int PLR_addTK(PLR_Cfg Cfg, c_string Token, int kind)

int PLR_addNT(PLR_Cfg Cfg, c_string NonTerm, c_bool catchError)

void PLR_endSD(PLR_Cfg Cfg)

int PLR_addSN(PLR_Cfg Cfg, c_string StartNt)

int PLR_addST(PLR_Cfg Cfg, c_string SpecTk)

int PLR_addPR(PLR_Cfg Cfg, c_string PName, int Method, c_string NonTerm)

int PLR_addPT(PLR_Cfg Cfg, c_string Token, long sRow, long sCol)

int PLR_addPD(PLR_Cfg Cfg, c_string Token, c_string DToken, long sRow, long sCol)

int PLR_addPK(PLR_Cfg Cfg, c_string Keyword, long sRow, long sCol)

int PLR_addPN(PLR_Cfg Cfg, c_string NonTerm, long sRow, long sCol)

int PLR_addCCtx(PLR_Cfg Cfg, int StateIdx, c_string StateSym, c_string Token)

int PLR_addCRule(PLR_Cfg Cfg, c_string NonTerm, c_string PName)

void PLR_delCfg(PLR_Cfg Cfg)

Parse table creation

PLR_Tab PLR_createTab(PLR_Cfg Cfg, c_bool verbose, c_bool diagnose)

PLR_Tab PLR_createTab_ex
        (
          PLR_Cfg Cfg, void (*prMsg)(c_string msg), c_bool verbose, c_bool diagnose
        )