Страницы справочника OS X

Эта страница руководства для  версии 10.9 Mac OS X

Читать страницы руководства

pt::rde(n)                                      Parser Tools                                      pt::rde(n)



____________________________________________________________________________________________________________

NAME
       pt::rde - Parsing Runtime Support, PARAM based

SYNOPSIS
       package require Tcl  8.5

       package require pt::rde  ?1.0.1?

       package require snit

       package require struct::stack  1.4

       package require pt::ast  1.1

       ::pt::rde objectName

       objectName destroy

       objectName reset chan

       objectName complete

       objectName chan

       objectName line

       objectName column

       objectName current

       objectName location

       objectName locations

       objectName ok

       objectName value

       objectName error

       objectName errors

       objectName tokens ?from ?to??

       objectName symbols

       objectName known

       objectName reducible

       objectName asts

       objectName ast

       objectName position loc

       objectName i_input_next msg

       objectName i_test_alnum

       objectName i_test_alpha

       objectName i_test_ascii

       objectName i_test_char char

       objectName i_test_ddigit

       objectName i_test_digit

       objectName i_test_graph

       objectName i_test_lower

       objectName i_test_print

       objectName i_test_punct

       objectName i_test_range chars chare

       objectName i_test_space

       objectName i_test_upper

       objectName i_test_wordchar

       objectName i_test_xdigit

       objectName i_error_clear

       objectName i_error_push

       objectName i_error_pop_merge

       objectName i_error_nonterminal symbol

       objectName i_status_ok

       objectName i_status_fail

       objectName i_status_negate

       objectName i_loc_push

       objectName i_loc_pop_discard

       objectName i_loc_pop_rewind

       objectName i:ok_loc_pop_rewind

       objectName i_loc_pop_rewind/discard

       objectName i_symbol_restore symbol

       objectName i_symbol_save symbol

       objectName i_value_clear

       objectName i_value_clear/leaf

       objectName i_value_clear/reduce

       objectName i:ok_ast_value_push

       objectName i_ast_push

       objectName i_ast_pop_rewind

       objectName i:fail_ast_pop_rewind

       objectName i_ast_pop_rewind/discard

       objectName i_ast_pop_discard

       objectName i_ast_pop_discard/rewind

       objectName i:ok_continue

       objectName i:fail_continue

       objectName i:fail_return

       objectName i:ok_return

       objectName si:void_state_push

       objectName si:void2_state_push

       objectName si:value_state_push

       objectName si:void_state_merge

       objectName si:void_state_merge_ok

       objectName si:value_state_merge

       objectName si:value_notahead_start

       objectName si:void_notahead_exit

       objectName si:value_notahead_exit

       objectName si:kleene_abort

       objectName si:kleene_close

       objectName si:voidvoid_branch

       objectName si:voidvalue_branch

       objectName si:valuevoid_branch

       objectName si:valuevalue_branch

       objectName si:voidvoid_part

       objectName si:voidvalue_part

       objectName si:valuevalue_part

       objectName si:value_symbol_start symbol

       objectName si:value_void_symbol_start symbol

       objectName si:void_symbol_start symbol

       objectName si:void_void_symbol_start symbol

       objectName si:reduce_symbol_end symbol

       objectName si:void_leaf_symbol_end symbol

       objectName si:value_leaf_symbol_end symbol

       objectName si:value_clear_symbol_end symbol

       objectName si:void_clear_symbol_end symbol

       objectName si:next_char tok

       objectName si:next_range toks toke

       objectName si:next_alnum

       objectName si:next_alpha

       objectName si:next_ascii

       objectName si:next_ddigit

       objectName si:next_digit

       objectName si:next_graph

       objectName si:next_lower

       objectName si:next_print

       objectName si:next_punct

       objectName si:next_space

       objectName si:next_upper

       objectName si:next_wordchar

       objectName si:next_xdigit

____________________________________________________________________________________________________________

DESCRIPTION
       Are you lost ?  Do you have trouble understanding this document ?  In that case please read the over-view overview
       view provided by the Introduction to Parser Tools. This document is the entrypoint to the whole  sys-tem system
       tem the current package is a part of.

       This  package  provides  a  class  whose  instances provide the runtime support for recursive descent
       parsers with backtracking, as is needed for the execution of, for example, parsing  expression  gram-mars. grammars.
       mars.  It  implements the PackRat Machine Specification, as such that document is required reading to
       understand both this manpage, and the package itself. The description below does make numerous short-hand shorthand
       hand references to the PARAM's instructions and the various parts of its architectural state.

       The package resides in the Execution section of the Core Layer of Parser Tools.

       IMAGE: arch_core_transform


       Note:  This  package  not only has the standard Tcl implementation, but also an accelerator, i.e. a C
       implementation, based on Critcl.


   CLASS API
       The package exports the API described here.

       ::pt::rde objectName
              The command creates a new runtime object for a recursive descent parser with backtracking  and
              returns  the  fully qualified name of the object command as its result. The API of this object
              command is described in the section Object API. It may be used to invoke various operations on
              the object.


   OBJECT API
       All  objects created by this package provide the following 63 methods for the manipulation and query-ing querying
       ing of their state, which is, in essence the architectural state of a PARAM.

       First some general methods and the state accessors.

       objectName destroy
              This method destroys the object, releasing all claimed memory,  and  deleting  the  associated
              object command.

       objectName reset chan
              This  method  resets  the state of the runtme to its defaults, preparing it for the parsing of
              the character in the channel chan, which becomes IN.

              Note here that the Parser Tools are based on Tcl 8.5+. In other words, the channel argument is
              not restricted to files, sockets, etc. We have the full power of reflected channels available.

              It should also be noted that the parser pulls the characters from the input stream as it needs
              them. If a parser created by this package has to be operated in a push aka event-driven manner
              it will be necessary to go to Tcl 8.6+ and use the coroutine::auto to wrap it into a coroutine
              where read is properly changed for push-operation.

       objectName complete
              This  method  completes  parsing,  either  returning the AST made from the elements of ARS, or
              throwing an error containing the current ER.

       objectName chan
              This method returns the handle of the channel which is IN.

       objectName line
              This method returns the line number for the position IN is currently at. Note  that  this  may
              not match with the line number for CL, due to backtracking.

       objectName column
              This  method  returns  the  column for the position IN is currently at. Note that this may not
              match with the column for CL, due to backtracking.

       objectName current
              This method returns CC.

       objectName location
              This method returns CL.

       objectName locations
              This method returns the LS. The topmost entry of the stack will be the first  element  of  the
              returned list.

       objectName ok
              This method returns ST.

       objectName value
              This method returns SV.

       objectName error
              This  method  returns ER. This is either the empty string for an empty ER, or a list of 2 ele-ments, elements,
              ments, the location the error is for, and a set of messages which specify which  symbols  were
              expected  at  the  location.  The  messages  are encoded as one of the possible atomic parsing
              expressions (special operators, terminal, range, and nonterminal operator).

       objectName errors
              This method returns ES. The topmost entry of the stack  will  be  the  first  element  of  the
              returned list. Each entry is encoded as described for error.

       objectName tokens ?from ?to??
              This  method returns the part of TC for the range of locations of IN starting at from and end-ing ending
              ing at to. If to is not specified it is taken as identical to from.  If  neither  argument  is
              specified the whole of TC is returned.

              Each  token  in the returned list is a list of three elements itself, containing the character
              at the location, and the associated line and column numbers, in this order.

       objectName symbols
              This method returns a dictionary containing NC. Keys are two-element lists containing  nonter-minal nonterminal
              minal  symbol  and location, in this order. The values are 4-tuples containing CL, ST, ER, and
              SV, in this order. ER is encoded as specified for the method error.

       objectName known
              This method returns a list containing the keys of SC. They are encoded in the same  manner  as
              is done by method symbols.

       objectName reducible
              This  method  returns  ARS.  The  topmost  entry of the stack will be the first element of the
              returned list

       objectName asts
              This method returns AS. The topmost entry of the stack  will  be  the  first  element  of  the
              returned list

       objectName ast
              This is a convenience method returning the topmost element of ARS.

       objectName position loc
              This  method  returns  the  line and column numbers for the specified location of IN, assuming
              that this location has already been reached during the parsing process.

       The following methods implement all PARAM instructions. They all have the prefix "i_".

       The control flow is mainly provided by Tcl's builtin commands, like  if,  while,  etc.,  plus  a  few
       guarded  variants of PARAM instructions and Tcl commands.. That means that these instruction variants
       will do nothing if their guard condition is not fulfilled. They  can  be  recognized  by  the  prefix
       "i:ok_" and "i:fail_", which denote the value ST has to have for the instruction to execute.

       The  instructions  are listed in the same order they occur in the PackRat Machine Specification, with
       the guard variants listed after their regular implementation, if any, or in their place.

       objectName i_input_next msg
              This method implements the PARAM instruction input_next.

       objectName i_test_alnum
              This method implements the PARAM instruction test_alnum.

       objectName i_test_alpha
              This method implements the PARAM instruction test_alpha.

       objectName i_test_ascii
              This method implements the PARAM instruction test_ascii.

       objectName i_test_char char
              This method implements the PARAM instruction test_char.

       objectName i_test_ddigit
              This method implements the PARAM instruction test_ddigit.

       objectName i_test_digit
              This method implements the PARAM instruction test_digit.

       objectName i_test_graph
              This method implements the PARAM instruction test_graph.

       objectName i_test_lower
              This method implements the PARAM instruction test_lower.

       objectName i_test_print
              This method implements the PARAM instruction test_print.

       objectName i_test_punct
              This method implements the PARAM instruction test_punct.

       objectName i_test_range chars chare
              This method implements the PARAM instruction test_range.

       objectName i_test_space
              This method implements the PARAM instruction test_space.

       objectName i_test_upper
              This method implements the PARAM instruction test_upper.

       objectName i_test_wordchar
              This method implements the PARAM instruction test_wordchar.

       objectName i_test_xdigit
              This method implements the PARAM instruction test_xdigit.

       objectName i_error_clear
              This method implements the PARAM instruction error_clear.

       objectName i_error_push
              This method implements the PARAM instruction error_push.

       objectName i_error_pop_merge
              This method implements the PARAM instruction error_pop_merge.

       objectName i_error_nonterminal symbol
              This method implements the PARAM instruction error_nonterminal.

       objectName i_status_ok
              This method implements the PARAM instruction status_ok.

       objectName i_status_fail
              This method implements the PARAM instruction status_fail.

       objectName i_status_negate
              This method implements the PARAM instruction status_negate.

       objectName i_loc_push
              This method implements the PARAM instruction loc_push.

       objectName i_loc_pop_discard
              This method implements the PARAM instruction loc_pop_discard.

       objectName i_loc_pop_rewind
              This method implements the PARAM instruction loc_pop_rewind.

       objectName i:ok_loc_pop_rewind
              This guarded method, a variant of i_loc_pop_rewind, executes only for "ST == ok".

       objectName i_loc_pop_rewind/discard
              This method is a convenient combination  of  control  flow  and  the  two  PARAM  instructions
              loc_pop_rewind  and  loc_pop_discard.  The former is executed for "ST == fail", the latter for
              "ST == ok".

       objectName i_symbol_restore symbol
              This method implements the PARAM instruction symbol_restore.

              The boolean result of the check is returned as the result of the method and can be  used  with
              standard Tcl control flow commands.

       objectName i_symbol_save symbol
              This method implements the PARAM instruction symbol_save.

       objectName i_value_clear
              This method implements the PARAM instruction value_clear.

       objectName i_value_clear/leaf
              This  method  is  a  convenient  combination  of  control  flow and the two PARAM instructions
              value_clear and value_leaf. The former is executed for "ST == fail", the  latter  for  "ST  ==
              ok".

       objectName i_value_clear/reduce
              This  method  is  a  convenient  combination  of  control  flow and the two PARAM instructions
              value_clear and value_reduce. The former is executed for "ST == fail", the latter for  "ST  ==
              ok".

       objectName i:ok_ast_value_push
              This  method  implements  a guarded variant of the the PARAM instruction ast_value_push, which
              executes only for "ST == ok".

       objectName i_ast_push
              This method implements the PARAM instruction ast_push.

       objectName i_ast_pop_rewind
              This method implements the PARAM instruction ast_pop_rewind.

       objectName i:fail_ast_pop_rewind
              This guarded method, a variant of i_ast_pop_rewind, executes only for "ST == fail".

       objectName i_ast_pop_rewind/discard
              This method is a convenient combination  of  control  flow  and  the  two  PARAM  instructions
              ast_pop_rewind  and  ast_pop_discard.  The former is executed for "ST == fail", the latter for
              "ST == ok".

       objectName i_ast_pop_discard
              This method implements the PARAM instruction ast_pop_discard.

       objectName i_ast_pop_discard/rewind
              This method is a convenient combination  of  control  flow  and  the  two  PARAM  instructions
              ast_pop_discard  and  ast_pop_rewind.  The former is executed for "ST == fail", the latter for
              "ST == ok".

       objectName i:ok_continue
              This guarded method executes only for "ST == ok". Then it aborts the current iteration of  the
              innermost loop in the calling Tcl procedure.

       objectName i:fail_continue
              This  guarded  method  executes only for "ST == fail". Then it aborts the current iteration of
              the innermost loop in the calling Tcl procedure.

       objectName i:fail_return
              This guarded method executes only for "ST == fail". Then it aborts the calling Tcl  procedure.

       objectName i:ok_return
              This guarded method executes only for "ST == ok". Then it aborts the calling Tcl procedure.


       The  next  set  of  methods are super instructions, meaning that each implements a longer sequence of
       instructions commonly used in parsers. The combinated instructions of the previous  set,  i.e.  those
       with names matching the pattern "i_*/*", are actually super instructions as well, albeit with limited
       scope, handling 2 instructions with their control flow. The upcoming set is much  broader  in  scope,
       folding as much as six or more PARAM instructions into a single method call.

       In this we can see the reasoning behind their use well:

       [1]    By  using  less instructions the generated parsers become smaller, as the common parts are now
              truly part of the common runtime, and not explicitly written in the  parser's  code  over  and
              over again.

       [2]    Using  less instructions additionally reduces the overhead associated with calls into the run-time, runtime,
              time, i.e. the cost of method dispatch and of setting up the variable context.

       [3]    Another effect of the super instructions is that their internals can  be  optimized  as  well,
              especially  regarding  control flow, and stack use, as the runtime internals are accessible to
              all instructions folded into the sequence.



       objectName si:void_state_push
              This method combines

              i_loc_push
              i_error_clear
              i_error_push

              Parsers use it at the beginning of void sequences and choices with a void initial branch.

       objectName si:void2_state_push
              This method combines

              i_loc_push
              i_error_clear
              i_error_push

              Parsers use it at the beginning of optional and repeated expressions.

       objectName si:value_state_push
              This method combines

              i_ast_push
              i_loc_push
              i_error_clear
              i_error_push

              Parsers use it at the beginning of sequences generating an AST and  choices  with  an  initial
              branch generating an AST.

       objectName si:void_state_merge
              This method combines

              i_error_pop_merge
              i_loc_pop_rewind/discard

              Parsers use it at the end of void sequences and choices whose last branch is void.

       objectName si:void_state_merge_ok
              This method combines

              i_error_pop_merge
              i_loc_pop_rewind/discard
              i_status_ok

              Parsers use it at the end of optional expressions

       objectName si:value_state_merge
              This method combines

              i_error_pop_merge
              i_ast_pop_rewind/discard
              i_loc_pop_rewind/discard

              Parsers use it at the end of sequences generating ASTs and choices whose last branch generates
              an AST

       objectName si:value_notahead_start
              This method combines

              i_loc_push
              i_ast_push

              Parsers use it at the beginning of negative lookahead predicates which generate ASTs.

       objectName si:void_notahead_exit
              This method combines

              i_loc_pop_rewind
              i_status_negate

              Parsers use it at the end of void negative lookahead predicates.

       objectName si:value_notahead_exit
              This method combines

              i_ast_pop_discard/rewind
              i_loc_pop_rewind
              i_status_negate

              Parsers use it at the end of negative lookahead predicates which generate ASTs.

       objectName si:kleene_abort
              This method combines

              i_loc_pop_rewind/discard
              i:fail_return

              Parsers use it to stop a positive repetition when its first, required, expression fails.

       objectName si:kleene_close
              This method combines

              i_error_pop_merge
              i_loc_pop_rewind/discard
              i:fail_status_ok
              i:fail_return

              Parsers use it at the end of repetitions.

       objectName si:voidvoid_branch
              This method combines

              i_error_pop_merge
              i:ok_loc_pop_discard
              i:ok_return
              i_loc_rewind
              i_error_push

              Parsers use it when transiting between branches of a choice when both are void.

       objectName si:voidvalue_branch
              This method combines

              i_error_pop_merge
              i:ok_loc_pop_discard
              i:ok_return
              i_ast_push
              i_loc_rewind
              i_error_push

              Parsers use it when transiting between branches of a choice when the failing branch  is  void,
              and the next to test generates an AST.

       objectName si:valuevoid_branch
              This method combines

              i_error_pop_merge
              i_ast_pop_rewind/discard
              i:ok_loc_pop_discard
              i:ok_return
              i_loc_rewind
              i_error_push

              Parsers  use it when transiting between branches of a choice when the failing branch generates
              an AST, and the next to test is void.

       objectName si:valuevalue_branch
              This method combines

              i_error_pop_merge
              i_ast_pop_discard
              i:ok_loc_pop_discard
              i:ok_return
              i_ast_rewind
              i_loc_rewind
              i_error_push

              Parsers use it when transiting between branches of a choice when both generate ASTs.

       objectName si:voidvoid_part
              This method combines

              i_error_pop_merge
              i:fail_loc_pop_rewind
              i:fail_return
              i_error_push

              Parsers use it when transiting between parts of a sequence and both are void.

       objectName si:voidvalue_part
              This method combines

              i_error_pop_merge
              i:fail_loc_pop_rewind
              i:fail_return
              i_ast_push
              i_error_push

              Parsers use it when transiting between parts of a sequence and the sucessfully matched part is
              void, and after it an AST is generated.

       objectName si:valuevalue_part
              This method combines

              i_error_pop_merge
              i:fail_ast_pop_rewind
              i:fail_loc_pop_rewind
              i:fail_return
              i_error_push

              Parsers use it when transiting between parts of a sequence and both parts generate ASTs.

       objectName si:value_symbol_start symbol
              This method combines

              if/found? i_symbol_restore $symbol
              i:found:ok_ast_value_push
              i:found_return
              i_loc_push
              i_ast_push

              Parsers  use  it  at the beginning of a nonterminal symbol generating an AST, whose right-hand
              side may have generated an AST as well.

       objectName si:value_void_symbol_start symbol
              This method combines

              if/found? i_symbol_restore $symbol
              i:found:ok_ast_value_push
              i:found_return
              i_loc_push
              i_ast_push

              Parsers use it at the beginning of a void nonterminal symbol whose right-hand side may  gener-ate generate
              ate an AST.

       objectName si:void_symbol_start symbol
              This method combines

              if/found? i_symbol_restore $symbol
              i:found_return
              i_loc_push
              i_ast_push

              Parsers  use  it  at  the beginning of a nonterminal symbol generating an AST whose right-hand
              side is void.

       objectName si:void_void_symbol_start symbol
              This method combines

              if/found? i_symbol_restore $symbol
              i:found_return
              i_loc_push

              Parsers use it at  the beginning of a void nonterminal symbol whose right-hand side is void as
              well.

       objectName si:reduce_symbol_end symbol
              This method combines

              i_value_clear/reduce $symbol
              i_symbol_save        $symbol
              i_error_nonterminal  $symbol
              i_ast_pop_rewind
              i_loc_pop_discard
              i:ok_ast_value_push

              Parsers  use  it at the end of a non-terminal symbol generating an AST using the AST generated
              by the right-hand side as child.

       objectName si:void_leaf_symbol_end symbol
              This method combines

              i_value_clear/leaf  $symbol
              i_symbol_save       $symbol
              i_error_nonterminal $symbol
              i_loc_pop_discard
              i:ok_ast_value_push

              Parsers use it at the end of a non-terminal symbol generating an AST whose right-hand side  is
              void.

       objectName si:value_leaf_symbol_end symbol
              This method combines

              i_value_clear/leaf  $symbol
              i_symbol_save       $symbol
              i_error_nonterminal $symbol
              i_loc_pop_discard
              i_ast_pop_rewind
              i:ok_ast_value_push

              Parsers use it at the end of a non-terminal symbol generating an AST discarding the AST gener-ated generated
              ated by the right-hand side.

       objectName si:value_clear_symbol_end symbol
              This method combines

              i_value_clear
              i_symbol_save       $symbol
              i_error_nonterminal $symbol
              i_loc_pop_discard
              i_ast_pop_rewind

              Parsers use it at the end of a void non-terminal symbol, discarding the AST generated  by  the
              right-hand side.

       objectName si:void_clear_symbol_end symbol
              This method combines

              i_value_clear
              i_symbol_save       $symbol
              i_error_nonterminal $symbol
              i_loc_pop_discard

              Parsers use it at the end of a void non-terminal symbol with a void right-hand side.

       objectName si:next_char tok

       objectName si:next_range toks toke

       objectName si:next_alnum

       objectName si:next_alpha

       objectName si:next_ascii

       objectName si:next_ddigit

       objectName si:next_digit

       objectName si:next_graph

       objectName si:next_lower

       objectName si:next_print

       objectName si:next_punct

       objectName si:next_space

       objectName si:next_upper

       objectName si:next_wordchar

       objectName si:next_xdigit
              These methods all combine

              i_input_next $msg
              i:fail_return

              with the appropriate i_test_xxx instruction. Parsers use them for handling atomic expressions.



BUGS, IDEAS, FEEDBACK
       This document, and the package it describes,  will  undoubtedly  contain  bugs  and  other  problems.
       Please   report   such   in   the   category   pt   of   the   Tcllib   SF  Trackers  [http://source -
       forge.net/tracker/? group_id=12883].  Please also report any ideas for enhancements you may  have  for
       either package and/or documentation.

KEYWORDS
       EBNF,  LL(k),  PEG,  TDPL,  context-free  languages,  expression,  grammar, matching, parser, parsing
       expression, parsing expression grammar, push down automaton, recursive descent, state, top-down pars-ing parsing
       ing languages, transducer

CATEGORY
       Parsing and Grammars

COPYRIGHT
       Copyright (c) 2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>




pt                                                  1.0.1                                         pt::rde(n)