me_vm man page on Darwin

Man page or keyword search:  
man Server   23457 pages
apropos Keyword Search (all sections)
Output format
Darwin logo
[printable version]

grammar::me_vm(n)	 Grammar operations and usage	     grammar::me_vm(n)

______________________________________________________________________________

NAME
       grammar::me_vm - Virtual machine for parsing token streams

DESCRIPTION
       Please go and read the document grammar::me_intro first for an overview
       of the various documents and their relations.

       This document specifies a virtual machine for the  controlled  matching
       and  parsing  of token streams, creating an abstract syntax tree (short
       AST) reflecting the structure of the input.  Special  machine  features
       are  the	 caching  and reuse of partial results, caching of the encoun‐
       tered input, and the ability to backtrack in both input	and  AST  cre‐
       ation.

       These  features make the specified virtual machine especially useful to
       packrat parsers based on parsing expression grammars. It is however not
       restricted  to  this  type  of  parser. Normal LL and LR parsers can be
       implemented with it as well.

       The following sections will discuss first the abstract state kept by ME
       virtual machines, and then their instruction set.

MACHINE STATE
       A ME virtual machine manages the following state:

       Current token CT
	      The token from the input under consideration by the machine.

	      This  information	 is  used  and	modified  by  the instructions
	      defined in the section TERMINAL MATCHING.

       Current location CL
	      The location of the current token in the input stream, as offset
	      relative to the beginning of the stream. The first token is con‐
	      sidered to be at offset 0.

	      This information is implicitly used and modified by the instruc‐
	      tions  defined in the sections TERMINAL MATCHING and NONTERMINAL
	      MATCHING, and can	 be  directly  queried	and  modified  by  the
	      instructions defined in section INPUT LOCATION HANDLING.

       Location stack LS
	      In addition to the above a stack of locations, for backtracking.
	      Locations can put on the stack, removed  from  it,  and  removed
	      with setting the current location.

	      This information is implicitly used and modified by the instruc‐
	      tions defined in the sections TERMINAL MATCHING and  NONTERMINAL
	      MATCHING,	 and  can  be  directly	 queried  and  modified by the
	      instructions defined in section INPUT LOCATION HANDLING.

       Match status OK
	      A boolean value, the result of  the  last	 attempt  at  matching
	      input.   It  is  set to true if that attempt was successful, and
	      false otherwise.

	      This information is influenced by the  instructions  defined  in
	      the sections TERMINAL MATCHING, NONTERMINAL MATCHING, and UNCON‐
	      DITIONAL MATCHING.  It is queried by the instructions defined in
	      the section CONTROL FLOW.

       Semantic value SV
	      The  semantic  value  associated	with  (generated  by) the last
	      attempt at matching input. Contains either the empty string or a
	      node for the abstract syntax tree constructed from the input.

	      This  information	 is  influenced by the instructions defined in
	      the sections SEMANTIC VALUES, and AST STACK HANDLING.

       AST stack AS
	      A stack of partial abstract  syntax  trees  constructed  by  the
	      machine during matching.

	      This  information	 is  influenced by the instructions defined in
	      the sections SEMANTIC VALUES, and AST STACK HANDLING.

       AST Marker stack MS
	      In addition to the above a stack of  stacks,  for	 backtracking.
	      This  is	actually  a  stack of markers into the AST stack, thus
	      implicitly snapshooting the state of the AST stack at some point
	      in  time.	 Markers can be put on the stack, dropped from it, and
	      used to roll back the AST stack to an earlier state.

	      This information is influenced by the  instructions  defined  in
	      the sections SEMANTIC VALUES, and AST STACK HANDLING.

       Error status ER
	      Error  information  associated with the last attempt at matching
	      input. Contains either the empty string or a list of 2 elements,
	      a	 location in the input and a list of error messages associated
	      with it, in this order.

	      Note that error information can be set even if the last  attempt
	      at  matching  input  was	successful. For example the *-operator
	      (matching a sub-expression zero or  more	times)	in  a  parsing
	      expression grammar is always successful, even if it encounters a
	      problem further in the input and has to backtrack. Such problems
	      must not be forgotten when continuing to match.

	      This  information	 is queried and influenced by the instructions
	      defined in the sections TERMINAL MATCHING, NONTERMINAL MATCHING,
	      and ERROR HANDLING.

       Error stack ES
	      In  addition to the above a stack of error information, to allow
	      the merging of current and older error information when perform‐
	      ing backtracking in choices after an unsucessful match.

	      This  information	 is queried and influenced by the instructions
	      defined in the sections TERMINAL MATCHING, NONTERMINAL MATCHING,
	      and ERROR HANDLING.

       Return stack RS
	      A	 stack	of  program counter values, i.e. locations in the code
	      controlling the virtual machine, for the management  of  subrou‐
	      tine calls, i.e. the matching of nonterminal symbols.

	      This  information	 is queried and influenced by the instructions
	      defined in the section NONTERMINAL MATCHING.

       Nonterminal cache NC
	      A cache of machine states (A 4-tuple containing  a  location  in
	      the  input, match status OK, semantic value SV, and error status
	      ER) keyed by name of nonterminal	symbol	and  location  in  the
	      input stream.

	      The  key	location is where machine started the attempt to match
	      the named nonterminal symbol, and the location in the  value  is
	      where  machine ended up after the attempt completed, independent
	      of the success of the attempt.

	      This status  is  queried	and  influenced	 by  the  instructions
	      defined in the section NONTERMINAL MATCHING.

MACHINE INSTRUCTIONS
       With  the  machine  state  specified  it is now possible to explain the
       instruction set of ME virtual machines. They are grouped roughly by the
       machine state they influence and/or query.

   TERMINAL MATCHING
       First  the  instructions	 to match tokens from the input stream, and by
       extension all terminal symbols.

       These instructions are the only ones which may  retrieve	 a  new	 token
       from  the  input	 stream.  This	is  a  may  and not a will because the
       instructions will a retrieve new token if,  and	only  if  the  current
       location	 CL  is	 at  the head of the stream.  If the machine has back‐
       tracked (see icl_rewind) the instructions will retrieve	the  token  to
       compare against from the internal cache.

       ict_advance message
	      This instruction tries to advance to the next token in the input
	      stream, i.e. the one after the current location CL. The instruc‐
	      tion  will  fail	if, and only if the end of the input stream is
	      reached, i.e. if there is no next token.

	      The sucess/failure of the instruction is remembered in the match
	      status  OK. In the case of failure the error status ER is set to
	      the current location and the message message.  In	 the  case  of
	      success  the  error  status ER is cleared, the new token is made
	      the current token CT, and the new location is made  the  current
	      location CL.

	      The  argument  message  is a reference to the string to put into
	      the error status ER, if such is needed.

       ict_match_token tok message
	      This instruction tests the current token CT  for	equality  with
	      the  argument tok and records the result in the match status OK.
	      The instruction fails if the current token is not equal to tok.

	      In case of failure the error status ER is	 set  to  the  current
	      location CL and the message message, and the current location CL
	      is moved one token backwards.  Otherwise, i.e. upon success, the
	      error  status  ER	 is cleared and the current location CL is not
	      touched.

       ict_match_tokrange tokbegin tokend message
	      This instruction tests the current token CT  for	being  in  the
	      range  of tokens from tokbegin to tokend (inclusive) and records
	      the result in the match status OK. The instruction fails if  the
	      current token is not inside the range.

	      In  case	of  failure  the error status ER is set to the current
	      location CL and the message message, and the current location CL
	      is moved one token backwards.  Otherwise, i.e. upon success, the
	      error status ER is cleared and the current location  CL  is  not
	      touched.

       ict_match_tokclass code message
	      This  instruction	 tests the current token CT for being a member
	      of the token class code and records the result in the match sta‐
	      tus OK. The instruction fails if the current token is not a mem‐
	      ber of the specified class.

	      In case of failure the error status ER is	 set  to  the  current
	      location CL and the message message, and the current location CL
	      is moved one token backwards.  Otherwise, i.e. upon success, the
	      error  status  ER	 is cleared and the current location CL is not
	      touched.

	      Currently the following classes are legal:

	      alnum  A token is accepted if it is a unicode alphabetical char‐
		     acter, or a digit.

	      alpha  A token is accepted if it is a unicode alphabetical char‐
		     acter.

	      digit  A token is accepted if it is a unicode digit character.

	      xdigit A token is accepted if it is a hexadecimal digit  charac‐
		     ter.

	      punct  A	token is accepted if it is a unicode punctuation char‐
		     acter.

	      space  A token is accepted if it is a unicode space character.

   NONTERMINAL MATCHING
       The instructions in this section handle	the  matching  of  nonterminal
       symbols. They query the nonterminal cache NC for saved information, and
       put such information into the cache.

       The usage of the cache is a performance aid for	backtracking  parsers,
       allowing them to avoid an expensive rematch of complex nonterminal sym‐
       bols if they have been encountered before.

       inc_restore branchlabel nt
	      This instruction checks if the  nonterminal  cache  NC  contains
	      information  about  the  nonterminal  symbol  nt, at the current
	      location CL. If that is the case the instruction will update the
	      machine  state  (current	location CL, match status OK, semantic
	      value SV, and error status ER) with the  found  information  and
	      continue	execution at the instruction refered to by the branch‐
	      label. The new current  location	CL  will  be  the  last	 token
	      matched by the nonterminal symbol, i.e. belonging to it.

	      If no information was found the instruction will continue execu‐
	      tion at the next instruction.

	      Together with icf_ntcall it is possible  to  generate  code  for
	      memoized	and  non-memoized  matching  of	 nonterminal  symbols,
	      either as subroutine calls, or inlined in the caller.

       inc_save nt
	      This instruction saves the current state of the machine (current
	      location	CL, match status OK, semantic value SV, and error sta‐
	      tus ER), to the nonterminal cache NC. It will also pop an	 entry
	      from  the location stack LS and save it as the start location of
	      the match.

	      It is expected to be called at the end of matching a nonterminal
	      symbol,  with nt the name of the nonterminal symbol the code was
	      working on. This allows the instruction inc_restore to check for
	      and  retrieve the data, should we have to match this nonterminal
	      symbol at the same location again, during backtracking.

       icf_ntcall branchlabel
	      This instruction invokes the code for matching  the  nonterminal
	      symbol  nt  as  a	 subroutine. To this end it stores the current
	      program counter PC on the return stack RS, the current  location
	      CL on the location stack LS, and then continues execution at the
	      address branchlabel.

	      The next matching icf_ntreturn will cause the execution to  con‐
	      tinue at the instruction coming after the call.

       icf_ntreturn
	      This  instruction	 will  pop  an entry from the return stack RS,
	      assign it to the program counter PC, and then continue execution
	      at the new address.

   UNCONDITIONAL MATCHING
       The  instructions  in  this  section are the remaining match operators.
       They change the match status OK directly and unconditionally.

       iok_ok This instruction sets the match status OK to true, indicating  a
	      successful match.

       iok_fail
	      This instruction sets the match status OK to false, indicating a
	      failed match.

       iok_negate
	      This instruction negates the match status OK, turning a  failure
	      into a success and vice versa.

   CONTROL FLOW
       The  instructions in this section implement both conditional and uncon‐
       ditional control flow. The conditional jumps query the match status OK.

       icf_jalways branchlabel
	      This instruction sets the program	 counter  PC  to  the  address
	      specified	 by  branchlabel  and  then  continues	execution from
	      there. This is an unconditional jump.

       icf_jok branchlabel
	      This instruction sets the program	 counter  PC  to  the  address
	      specified by branchlabel. This happens if, and only if the match
	      status OK indicates a success.  Otherwise	 it  simply  continues
	      execution at the next instruction. This is a conditional jump.

       icf_jfail branchlabel
	      This  instruction	 sets  the  program  counter PC to the address
	      specified by branchlabel. This happens if, and only if the match
	      status  OK  indicates  a	failure. Otherwise it simply continues
	      execution at the next instruction. This is a conditional jump.

       icf_halt
	      This instruction halts the machine and blocks any further execu‐
	      tion.

   INPUT LOCATION HANDLING
       The  instructions in this section are for backtracking, they manipulate
       the current location CL of the machine state.  They allow a user of the
       machine	to  query  and	save locations in the input, and to rewind the
       current location CL to saved locations, making them one of  the	compo‐
       nents enabling the implementation of backtracking parsers.

       icl_push
	      This instruction pushes a copy of the current location CL on the
	      location stack LS.

       icl_rewind
	      This instruction pops an entry from the location	stack  LS  and
	      then  moves  the	current	 location CL back to this point in the
	      input.

       icl_pop
	      This instruction pops an entry from the location	stack  LS  and
	      discards it.

   ERROR HANDLING
       The  instructions  in this section provide read and write access to the
       error status ER of the machine.

       ier_push
	      This instruction pushes a copy of the current error status ER on
	      the error stack ES.

       ier_clear
	      This instruction clears the error status ER.

       ier_nonterminal message
	      This instruction checks if the error status ER contains an error
	      whose location is just past the location found in the top	 entry
	      of  the  location stack LS.  Nothing happens if no such error is
	      found.  Otherwise the found error is replaced by an error at the
	      location found on the stack, having the message message.

       ier_merge
	      This  instruction	 pops an entry from the error stack ES, merges
	      it with the current error status ER and stores the result of the
	      merge as the new error status ER.

	      The merge is performed as described below:

	      If  one of the two error states is empty the other is chosen. If
	      neither error state is empty, and refering  to  different	 loca‐
	      tions,  then  the	 error	state with the location further in the
	      input is chosen. If both error states refer to the same location
	      their messages are merged (with removing duplicates).

   SEMANTIC VALUES
       The instructions in this section manipulate the semantic value SV.

       isv_clear
	      This instruction clears the semantic value SV.

       isv_terminal
	      This  instruction	 creates  a  terminal AST node for the current
	      token CT, makes it the semantic value SV, and  also  pushes  the
	      node on the AST stack AS.

       isv_nonterminal_leaf nt
	      This  instruction	 creates  a  nonterminal  AST node without any
	      children for the nonterminal nt, and makes it the semantic value
	      SV.

	      This  instruction	 should	 be executed if, and only if the match
	      status OK indicates  a  success.	 In  the  case	of  a  failure
	      isv_clear should be called.

       isv_nonterminal_range nt
	      This  instruction creates a nonterminal AST node for the nonter‐
	      minal nt, with a single terminal node as its  child,  and	 makes
	      this  AST the semantic value SV. The terminal node refers to the
	      input string from the location found  on	top  of	 the  location
	      stack LS to the current location CL (both inclusive).

	      This  instruction	 should	 be executed if, and only if the match
	      status OK indicates  a  success.	 In  the  case	of  a  failure
	      isv_clear should be called.

       isv_nonterminal_reduce nt
	      This  instruction creates a nonterminal AST node for the nonter‐
	      minal nt and makes it the semantic value SV.

	      All entries on the AST stack AS above the marker	found  in  the
	      top  entry of the AST Marker stack MS become children of the new
	      node, with the entry at the stack	 top  becoming	the  rightmost
	      child.  If  the  AST Marker stack MS is empty the whole stack is
	      used. The AST marker stack MS is left unchanged.

	      This instruction should be executed if, and only	if  the	 match
	      status  OK  indicates  a	success.   In  the  case  of a failure
	      isv_clear should be called.

   AST STACK HANDLING
       The instructions in this section manipulate the AST stack AS,  and  the
       AST Marker stack MS.

       ias_push
	      This  instruction	 pushes the semantic value SV on the AST stack
	      AS.

       ias_mark
	      This instruction pushes a marker for the current	state  of  the
	      AST stack AS on the AST Marker stack MS.

       ias_mrewind
	      This  instruction pops an entry from the AST Marker stack MS and
	      then proceeds to pop entries from the AST	 stack	AS  until  the
	      state  represented  by the popped marker has been reached again.
	      Nothing is done if the AST stack	AS  is	already	 smaller  than
	      indicated by the popped marker.

       ias_mpop
	      This  instruction pops an entry from the AST Marker stack MS and
	      discards it.

BUGS, IDEAS, FEEDBACK
       This document, and the package it describes, will  undoubtedly  contain
       bugs and other problems.	 Please report such in the category grammar_me
       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
       grammar, parsing, virtual machine

CATEGORY
       Grammars and finite automata

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

grammar_me			      0.1		     grammar::me_vm(n)
[top]

List of man pages available for Darwin

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Tweet
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
....................................................................
Vote for polarhome
Free Shell Accounts :: the biggest list on the net