path: root/packrat_parser_lib_notes.txt

package structure:

Packrat
Packrat.Parser (generic over memoize enum, input item type, array of input items, graph of output item subarrays)
Packrat.Parser.Combinators
Packrat.Lexer (generic over stamp enum, input item type, array of input items, array of output items wrapped as tokens)
Packrat.Lexer.Combinators
Packrat.Util
Packrat.Errors (nested)
Packrat.Graphs (nested, generic over leaf array type)
Packrat.Tokens (nested, generic over contained array)
Packrat.Instant
Packrat.Instant.Standard (nested, generic over parser/lexer label enums)
Packrat.Instant.Wide (nested, generic over parser/lexer label enums)
Packrat.Instant.Wide_Wide (nested, generic over parser/lexer label enums)

Ratnest.Tests
Ratnest.Examples

Calculator
Tomita
Off_Side




planned order of writing:
(in all cases notes here, then spec, then tests, then body)
(Ratnest not mentioned since that's where all the testing functions will go)

Packrat.Util
Packrat.Errors
Packrat.Tokens
Packrat.Lexer
Packrat.Lexer.Combinators
Packrat.Graphs
Packrat.Parser
Packrat.Parser.Combinators
Packrat.Instant
Packrat.Instant.Standard
Packrat.Instant.Wide
Packrat.Instant.Wide_Wide
Calculator
Tomita
Off_Side






Packrat
 - main package
 - defines parser_component_function, lexer_component_function, syntax_tree, token_list, parser_context types
 - parser_context type is completely opaque and has an empty_context constant
 - syntax_tree is a tagged type container
 - token_list is just an array (so can be any sort of string, or an array of tokens produced by a lexer, etc)
 - is it possible to define parser/lexer components such that an instantiated main parsing/lexing function qualifies?
   - probably not, since the main parsing/lexing functions will be able to throw exceptions for parsing/lexing errors,
     whereas the component functions will only pass a failure up the chain as part of the context
 - possible usage modes include (token_list -> lexer -> token_list -> parser -> syntax_tree) and (token_list ->
   parser -> syntax_tree)

List of funcs:
(primitive operations for syntax_tree)




Packrat.Parser
 - generic over the enum used for memoizing and the input token_list as well as token elements

List of funcs:
Parse
 - may return partial results if incomplete input supplied
 - new input can then be fed back in with the parse_context and initial results to continue parsing
Parse_Only
 - will not return partial results and will always attempt a complete parse
Parse_With
 - must be supplied with a function to acquire more input
Parse_Full
 - will not return partial results and will always require there to be no more input remaining at end
Memoize




Packrat.Parser.Combinators
 - all higher order functions/procedures go in here
 - updating memo_table should be done by overwriting in order to accommodate left recursion
   unwinding properly

List of funcs:
(these are combinators that arrange nodes produced by parsers but do not produce nodes themselves)
Sequence (one of the two that require passing in an array of function accesses)
 - takes an array of component accesses and adds whatever subtrees they produce in order as
   children of the current position on the output structure
Choice (the other that requires passing in an array of function accesses)
 - takes an array of component accesses and trys them in order, first one to succeed has the
   subtree it produces added as a child of the current position on the output structure
Count
 - 
Many
Many_Until
Separate_By
Separate_End_By

(these are parser components that create nodes from input)
Satisfy
 - takes a predicate and if that predicate applied to the next input token is true, creates a
   node with the next input token
Satisfy_With
 - takes a predicate and a transforming function, applies the transform to the next input token
   then tests it with the predicate as above
 - the node created uses the *un*transformed input
Default
 - takes a default argument (same type as input tokens) and a parser component, and either
   returns the subresult from the component if it succeeds, or creates a node with the default
   argument if the component fails
Match
 - for matching one item, eg a char in a string input, or a string in a lex'd string token array
 - checks a supplied argument against the next input token, and if they match, creates a node
   with the next input token
Match_With
 - first uses a transforming function on the next input token then tests against a supplied
   argument as above, creating a node with the untransformed input if there is a match
Multimatch
 - for matching multiple successive items, eg a substring in a string input
 - checks an array argument against the same length subarray of input tokens for a match, if
   successful creates a node with that subarray
Multimatch_With
 - applies a transforming function before the check as above
Take
 - creates a node with the next input token
Take_While
 - takes a predicate and creates a node with the subarray of input tokens corresponding to
   the next N input where the predicate succeeds
Take_Until
 - takes a predicate and creates a node with the subarray of input tokens corresponding to
   the next N input where the predicate fails

(these are recogniser combinators that discard nodes produced by other components)
Skip
 - takes a parser component, executes it, and if it succeeds the result is discarded
   instead of becoming part of the output

(these are recogniser components that do not create nodes)
Empty
End_Of_Input




Packrat.Lexer
 - generic over the enum used for labeling lexemes and the input token_list as well as component token elements
 - should be possible to place an upper limit on the number of tokens scanned, so as to accommodate a statically
   sized output array of tokens (and possibly a statically sized input array)

List of datatypes:
Combinator
Combinator_Result

List of funcs:
(for Combinator_Results)
Create_Result
Join
Status

(each of these is generic over an array of lexer_component functions, either Stamp or Ignore as below)
Scan
 - function that returns an array of lexed tokens
 - uses first applicable lexer component to lex each token
 - if all lexer components return "partial" then also returns with a partial status
 - if all lexer components fail then raises a lexer_error
 - lexer status can be fed back into any of these Scan functions to resume with further input
 - if end of input is reached without any lexer components returning "partial" then returns
   a complete status and feeding the lexer status back into these functions will be the same
   as starting with a blank status
Scan_Set
 - as above, except is a procedure that uses a fixed size array as output with a padding token
Scan_Only
 - function that returns an array of lexed tokens
 - takes a lexer status as input to resuem a lex, but will treat it as a constant unlike the others
 - if all lexer components return "partial" or fail then raises a lexer_error
Scan_Set_Only
 - as above, except is a procedure that uses a fixed size array as output with a padding token
Scan_With
 - function that returns an array of lexed tokens
 - when it runs out of input it uses the supplied function to get more input until that function
   returns an empty array
 - may also return with a partial status as with Scan
Scan_Set_With
 - as above, except is a procedure that uses a fixed size array as output with a padding token

(type signature of these are:
  input of an opaque lex_component_input type
  output of an opaque lex_component_output type
  return of a Fail/Partial/Success result enum)
Stamp
 - one of two available lexer component functions
 - generic over a value of the enum used for labelling lexemes and a lexer combinator
Ignore
 - the other available lexer component function
 - generic over a lexer combinator, as this function will scan for the given token and then ignore it




Packrat.Lexer.Combinators

type signature of these are:
  inputs of input_array and a starting position index
  outputs of the number of elements consumed and the value lexed
  return of a Fail/Partial/Success result enum

List of funcs:
Sequence
Count
Many
Many_Until

Satisfy
Satisfy_With
Match
Match_With
Multimatch
Take
Take_While
Take_Until

Line_End
Input_End




Packrat.Util
 - contains predicates to use in Satisfy parser components and similar
 - has a few string output functions for syntax_tree objects

List of funcs:
In_Set
Not_In_Set
Is_Digit
Is_Hex
Is_Letter
Is_Alphanumeric
Is_Punctuation
Is_ASCII
Is_Extended_ASCII
Is_Space
Is_Linespace
Is_End_Of_Line
Is_Whitespace
Not_Whitespace




Packrat.Error
(actually a nested package, as this functionality is important to parsers/lexers)
 - functions to handle and process exception messages
 - exception messages take the form of one or more "s<SYMBOLNAME>p<POSITION>" substrings joined together,
   with each symbol name being in all capitals and each position being a positive integer
 - this message represents the list of expected symbols at particular positions that would have resulted in a
   more complete parse
 - one of these messages will be raised with an exception of no valid parse is possible with a given input

List of datatypes:
Error_Message
Error_Info (containing a string of the symbol name expected, and a natural of the position)
Error_Info_Array

List of funcs:
Valid_Message
Valid_Identifier
Valid_Identifier_Array
Debug_String

Join
Encode
Encode_Array
Decode
(the message format ensures that using "&" to join messages will still result in a valid message)




Packrat.Tokens
 - nested package, defines a datatype important throughout lexing/parsing
 - generic over the array type of whatever is being lexed/parsed and the enum of valid token labels
 - contains an enum identifier, the start position, the finish position plus one, and the token value

List of datatypes:
Token (tagged, controlled, but not limited)

List of funcs:
Create
Initialized
Debug_String

Label
Value
Start
Finish




Packrat.Graphs

List_of_datatypes:
Parse_Graph

List of funcs:
Debug_String






Ratnest

List of funcs:
Run_Tests




Ratnest.Tests

List of funcs:
Valid_Message_Check
Valid_Identifier_Check
Join_Check
Encode_1_Check
Encode_2_Check
Encode_3_Check
Encode_4_Check
Decode_Check

Token_Adjust_Check
Token_Store_Check

In_Set_Check
Not_In_Set_Check

Is_Digit_Check
Is_Hex_Check
Is_Letter_Check
Is_Alphanumeric_Check
Is_ASCII_Check
Is_Extended_ASCII_Check
Is_Space_Check
Is_Linespace_Check
Is_End_Of_Line_Check
Is_Whitespace_Check
Is_Not_Whitespace_Check




Ratnest.Examples
 - some parser examples

List of funcs:
Scientific
Signed
Decimal
Hexadecimal
Double






Miscellanea:

Where to place C export binding?

Recognisers/combinators implemented as generic functions/procedures if they require more than just input/output.
This is done to get around the lack of first class functions, as combinators usually take the form of higher order functions.

eg Term, Sequence, Choice, Some, Many

How to force functions/procedures of a particular type to be referentially transparent?

Want support for incremental input, so will need Parse function that can return a partially parsed state that can be
supplied with more input.