You are looking at historical revision 21159 of this page. It may differ significantly from its current revision.

genturfa'i

lo la .ckim. ke pe'a jajgau ratcu ke'e genturfa'i

Description

genturfa'i is a Scheme packrat parser.

Packrat parsing is a memoizing, backtracking, recursive descent parsing technique that runs in time and space linear to the size of the input text O(n).

Packrat parsers require more memory than traditional LL(k) parsers, but are more expressive. Unlike traditional LL(k) parsers, which have a separate tokenization step, Packrat parsers combine lexical analysis and grammar parsing into a single step, using the same language for both.

The word genturfa'i is a Lojban lujvo, consisting of the gismu gerna, stura, and facki. It translates to "grammar structure discover."

Authors

.alyn.post.. Inspired by the packrat parser authored by Tony Garnock-Jones.

Requirements

Requires srfi-1 (list library), srfi-6 (string ports), srfi-9 (records), srfi-13 (string libraries), and srfi-28 (basic string formatting).

The filter procedure from srfi-1 is used.

srfi-6 (with Chicken Scheme's extensions) is used for reading parse input from a port. It can be removed if you do not need to parse input from a port.

srfi-9 is used to construct records with no more than two elements. These calls could be replaced by cons if you wish to remove this dependency.

srfi-13 is required only to return the remaining characters in the input buffer after a successful parse. If your grammar manually checks for the end of the input, this dependency could be removed.

srfi-28 is used to format the module version number and for debugging support. It could be excluded with minor modification to the code.

The srfi-9 and srfi-28 eggs are built into chicken.

The srfi-1 and srfi-13 eggs must be installed.

Documentation

Usage

With genturfa'i, A parser is expressed using a parsing expression grammar, or PEG. This language describes the grammar that genturfa'i is parsing. It is also possible to construct a grammar directly in scheme.

This module implements two methods for writing parsers. The recommended method is to write your grammar in PEG and compile the grammar to scheme code.

'This method of writing parsers has not yet been written.'

Your grammar can also be written directly in scheme, using the primitive grammar construction operators provided by genturfahi. As this is the only mode that currently exists, it will be covered in this documentation.

A Note About Lojban

Lojban is a carefully constructed spoken language

with an ''unambiguous grammar''.

I've written this parser with the intention of parsing Lojban's PEG grammar.,

as expressed in the

main grammar, morphology, and morphology header files.

Just like the name of this module, the routines in this module are named with Lojban words. If you are unfamiliar with Lojban, a translation of the words that appear in the API is provided below.

English translation of Lojban words

This table provides an english glass for each Lojban word that appears in the API documentation. This table is not intended to have any truth value outside of this document. For formal English glosses of these words, please consult the Lojban to English Translation Dictionary.

Lojban word English gloss
cfari begin
cmene, cme name
fanmo end
genturfa'i parse
jalge result
javni rule
je logical and
jonai logical exclusive or
lerfu character
mapti match
midju middle
morji memoize
namapti nonmatch
naselci nonterminal
nunjalge result generator
nunjavni rule generator
pabalvi next
porsi, poi ordered sequence
rodacmene names
rodajavni rules
rodajalga results
rodanunjavni rules generator
rodanunjalga results generator
rodavalsi tokens
secuxna option
sezvati, zva location
samselpla code
sumti function argument
tolmohi clear memoization
valsi, val token

Writing A Parser

'This section describes features that are not yet implemented.'

This section will eventually document how to write a parser in PEG. As that code is not yet written, please refer to the API documents.

Configuration

'This section describes features that are not yet implemented.'

Debugging

'Debugging is not yet implemented.'

Debugging is used to see what rules are being called as the parser tries to parse the input.

;;
;; enable debug output
;;
(secuxna debug #t)
Profiling

'Profiling is not yet implemented.'

Profiling is used to determine how much time is being spent in each grammar rule.

;;
;; enable profiling
;;
(secuxna profile #t)
Memoization

'This option is not yet implemented.'

By default, memoization is enabled to ensure that the parser runs in linear space and time. For some grammars, memoization does not provide any performance benefit, while the extra cache lookup slows the parser down.

Memoization can be turned completely off:

;;
;; turn memoization completely off.
;;
(secuxna memoize #f)

Or it can be turned off for specific non-terminal rules:

;;
;; turn memoization off for non-terminal rule
;; 'javnipa' and 'javnire'.
;;
(secuxna memoize ((javnipa #f) (javnire #f)))
Changing the sentinel character

'This option is not yet implemented.'

A sentinel character is placed at the end of the parse input to indicate the end of input. This character cannot be a valid terminal character in the grammar. Placing a sentinal character at the end of the parse input is an optimization that allows the terminal matching rules to avoid checking for the end of the parse input when they try to match the parse input. As these rules are called frequently, removing this check can speed up parsing.

This is also the character that is returned when the end of input is explicitely matched.

By default, #\nul is used as a sentinal character in the parse input to indicate an end of input. If this character appears in your grammar, you'll need to change the sentinal character to something else:

;;
;; change the sentinal character used to
;; detect the end of the parse input.
;;
(secuxna sentinal #\nul) ; default

Changing the empty string

'This option is not yet implemented.'

The empty string is a parse rule matching zero characters. By default, the token generated by this rule is the zero length string "". To change the token produced by the empty string:

;;
;; change the token returned when we
;; match against the empty string.
;;
(secuxna empty-string "") ; default

Changing non-matching parse result

'This option is not yet implemented.'

When parse input does not match the grammar, a token is returned indicated non-match. By default, the non-matching token is #f. To change the token returned when the parse input does not match the grammar:

;;
;; change the token returned when the parse
;; input does not match the grammar.
;;
(secuxna nonmatch-token #f) ; default

API Documentation

This is the low-level interface for writing parsers directly in Scheme. The only reason you would want to use this interface is that I haven't written the PEG parser yet.

This interface was written specifically to support the PEG parser. While expressive, it is not concise. Aside from the PEG parser, a more concise syntax could be written on top of this API. I do not plan on developing this syntax, but if you would like to write parsers directly in Scheme, please feel free to add support for a more concise syntax. See the History section of this document for a starting idea.

This API defines the following components:

javni-jalge
The parse result (token and parse input) generated by a grammar rule.
lerfu-porsi
The parse input with an associated position.
nunjavni
A generator that creates grammar rules.
javni
A grammar rule that creates a token from the parse input and advances the input position.
mapti
A match continuation for a grammar rule.
namapti
A non-match continuation for a grammar rule.
nunvalsi
A generator that returns parse results.
javni-valsi
The token generated by a grammar rule.
samselpla
Code that modifies the syntax tree generated by the parser.
genturfahi
The parser, containing all of the grammar rules.

The parser runs as follows:

A lerfu-porsi encapsulates the input to parse. It tracks the current position of the input based on the parse.

A nunjavni expects zero or more javni and generates a new javni. The parser is constructed by linking together javni through nunjavni generators.

A javni expects a lerfu-porsi, mapti, and namapti. mapti and namapti are continuations representing the next rule in the grammar. The set of all javni describe the grammar to parse.

Both mapti and namapti expect a lerfu-porsi (possibly advanced by the previous javni). mapti also expects a nunvalsi, the generator for the parse tree. mapti and namapti are used for backtracking and general control flow during the parse.

A nunvalsi generates either a javni-valsi or a list of javni-valsi. javni-valsi are not immediately generated, as future backtracking could invalidate a currently matched result. nunvalsi generate the parse tree resulting from the input when called.

A javni-valsi is a name and associated token. The token can be a single character or the entire syntax tree. names must be symbols, and are used to associate a piece of the abstract syntax tree with a variable name when executing samselpla. The parser converts the input in lerfu-porsi to javni-valsi.

samselpa is code embedded in the grammar. It is executed after a successful parse, modifying the syntax tree before it is returned from the parser. Often it is easier to work with the syntax tree "in place" rather than working on the entire syntax tree at once. samselpla is the mechanism for working with the syntax tree "in place."

genturfahi expects a lerfu-porsi and javni containing the starting grammar rule. It provides the terminal mapti and namapti continuations that generate the parse results by generating a javni-valsi from the nunvalsi and returning the parsed syntax tree.

Details on each component are below.

lerfu-porsi

[record] lerfu-porsi

The string to parse and the current parse position of that string. This structure is used by the parser to store the input to the parser.

It contains the following members:

zva
An integer which is the current index of poi.
poi
The string which will be parsed.
[procedure] (make-lerfu-porsi zva poi) => lerfu-porsi
zva
An integer describing the current position of the parse input.
poi
The parse input, as a specially formatted string. (See make-lerfu-porsi-string and make-lerfu-porsi-port.)

Create a lerfu-porsi from the integer index zva and the parse input poi. poi is specially formatted, and must come from calling make-lerfu-porsi-string or make-lerfu-porsi-port. It has an appended character acting as a "sentinel" for purposes of detecting the end of the input buffer.

zva must be less than or equal to the string-length of poi.

[procedure] (make-lerfu-porsi-pabalvi-lerfu porsi) => lerfu-porsi
porsi
the parse position to advance.

Create a lerfu-porsi from an existing lerfu-porsi by advancing the index zva by a single character.

It is an error if porsi is not of type lerfu-porsi.

Behavior is undefined if this procedure is called when lerfu-porsi-fanmo? returns #t for this porsi.

[procedure] (lerfu-porsi? porsi) => boolean
porsi
the object to test.

Return #t if porsi is of type lerfu-porsi and #f otherwise.

[procedure] (lerfu-porsi-zva porsi) => zva
porsi
A lerfu-porsi.

Return the zva member from porsi.

It is an error if porsi is not of type lerfu-porsi.

[procedure] (lerfu-porsi-poi porsi) => poi
porsi
A lerfu-porsi.

Return the poi member from porsi.

It is an error if porsi is not of type lerfu-porsi.

[procedure] (lerfu-porsi->string porsi) => string
porsi
A lerfu-porsi.

Return A string representation of porsi. This string representation is for debug use only, and cannot be converted back to a lerfu-porsi.

It is an error if porsi is not of type lerfu-porsi.

[procedure] (make-lerfu-porsi-string string) => porsi
string
The input string to parse.

Return a lerfu-porsi with string as the parse input. string is copied into the lerfu-porsi.

[procedure] (make-lerfu-porsi-port port) => porsi
port
The input port to parse.

Return a lerfu-porsi with port as the parse input. port is read into a string before being copied into the lerfu-porsi, as the parser may need to backtrack to any previous location in the string.

[procedure] (lerfu-porsi-string porsi) => string
porsi
A lerfu-porsi.

Return the characters that have not been parsed from porsi. This routine copies the characters from the buffer into a new string.

If all of the characters were parsed from lerfu-porsi, return "".

[procedure] (lerfu-porsi-lerfu porsi) => character
porsi
A lerfu-porsi.

Return the character at the current parse position zva in the parse input poi.

It is an error if porsi is not of type lerfu-porsi.

[procedure] (lerfu-porsi-fanmo? porsi) => boolean
porsi
A lerfu-porsi.

Return #t if this porsi has no more input to parse, #f otherwise.

It is an error if porsi is not of type lerfu-porsi.

javni-valsi

[record] javni-valsi

A javni-valsi is a token with an (optionally) associated name generated from a javni as part of a javni-jalge indicating a match of that javni.

It contains the following members:

cme
The name associated with this token, or #f if there is no associated name.
val
The token generated from matching a rule.
[procedure] (make-javni-valsi cme val) => javni-valsi
cme
The name associated with this token, or #f if there is no associated name.
val
The token generated from matching a rule.

Create a javni-valsi from the name cme and the token val. If this javni-valsi has no associated cmene, cme can be #f.

val may be an object of any type, and is the current abstract syntax tree generated from this parse, as modified by samselpla executed after the parse succeeds.

[syntax] (make-javni-valsi-nacmene val) => javni-valsi
val
The token generated from matching a rule.

Expands to make-javni-valsi with a cme parameter of #f.

[procedure] (javni-valsi? valsi) => boolean
valsi
the object to test.

Return #t if valsi is of type javni-valsi and #f otherwise.

[procedure] (javni-valsi-cme valsi) => cmene
valsi
A javni-valsi.

Return the cmene member from valsi.

It is an error if valsi is not of type javni-valsi.

[procedure] (javni-valsi-val valsi) => val
valsi
A javni-valsi.

Return the val member from valsi.

It is an error if valsi is not of type javni-valsi.

[procedure] (javni-valsi->string valsi) => string
valsi
A javni-valsi.

Return A string representation of valsi. This string representation is for debug use only, and cannot be converted back to a javni-valsi.

It is an error if valsi is not of type javni-valsi.

nunjavni

A routine that generates a javni.

[procedure] (nunjavni-lerfu lerfu) => javni
lerfu
The character to match.

Generate a javni that matches a single lerfu.

nunjavni-lerfu corresponds to a nonterminal symbol in PEG syntax.

[procedure] (nunjavni-fanmo) => javni

Generate a javni that matches the end of the lerfu-porsi.

nunjavni-fanmo corresponds to a nonterminal symbol in PEG syntax.

[procedure] (nunjavni-e) => javni

Generate a javni that matches the empty string.

nunjavni-fanmo corresponds to the empty string expression in PEG syntax.

[procedure] (nunjavni-* sumti-javni) => javni
sumti-javni
The rule to match zero-or-more times.

Generate a javni that runs the passed in sumti-javni until it generates a namapti. The javni returned by nunjavni-* never calls its namapti continuation, always calling mapti.

nunjavni-* corresponds to the zero-or-more expression in PEG syntax.

[procedure] (nunjavni-+ sumti-javni) => javni
sumti-javni
The rule to match one-or-more times.

Generate a javni that runs the passed in sumti-javni until it generates a namapti. The javni returned by nunjavni-+ calls mapti if the passed in sumti-javni matches one or more times, and calls namapti if sumti-javni does not match.

nunjavni-+ corresponds to the one-or-more expression in PEG syntax.

[procedure] (nunjavni-? sumti-javni) => javni
sumti-javni
The rule to optionally match.

Generate a javni that runs the passed in sumti-javni. The javni returned by nunjavni-? never calls its namapti continuation, always calling mapti.

nunjavni-? corresponds to the optional expression in PEG syntax.

[procedure] (nunjavni-& sumti-javni) => javni
sumti-javni
The rule to match.

Generate a javni that runs the passed in sumti-javni. The javni returned by nunjavni-& calls mapti or namapti according to the result from sumti-javni, but it does not advances the lerfu-porsi when mapti is called.

nunjavni-* corresponds to the and-predicate expression in PEG syntax.

[procedure] (nunjavni-! sumti-javni) => javni
sumti-javni
The rule to match.

Generate a javni that runs the passed in sumti-javni. The javni returned by nunjavni-& calls mapti if the sumti-javni calls namapti, and it calls mapti if the sumti-javni calls namapti.

nunjavni-! corresponds to the not-predicate expression in PEG syntax.

[procedure] (nunjavni-je . rodajavni) => javni
rodajavni
one or more rules to match in sequence.

Generate a javni that runs each javni in the passed in rodajavni in order. The javni returned by nunjavni-je calls mapti if every javni in rodajavni matches, and namapti if any javnri in rodajavni does not match.

nunjavni-je corresponds to the sequence expression in PEG syntax.

[procedure] (nunjavni-jonai . rodajavni) => javni
rodajavni
one or more rules to match in sequence.

Generate a javni that runs each javni in the passed in rodajavni in order. The javni returned by nunjavni-jonai calls mapti with the result from the first javni in rodajavni that matches, ignoring all remaining javni in rodajavni. nunjavni-je calls namapti if all the javni in rodajavni do not match.

nunjavni-je corresponds to the ordered-choice expression in PEG syntax.

[procedure] (nunjavni-morji sumti-javni) => javni
sumti-javni
the rule to match.

Generate a javni that runs the passed in sumti-javni and stores the result. If the javni returned by nunjavni-morji is called again with the same lerfu-porsi, the stored mapti or namapti is called instead of calling sumti-javni again.

nunjavni-je corresponds to memoization in packrat parsing.

[syntax] (nunjavni-naselci sumti-javni) => javni
sumti-javni
the rule defined in the environment being captured.

nunjavni-nasleci encloses sumti-javni in a lambda, which captures the environment in which sumti-javni is defined.

This macro is used in the letrec used to define the non-terminals in a grammar to allow mutual recursion.

[syntax] (nunjavni-samselpla samselpla javni) => nunjavni-samselpla-midju
samselpla
the code to enclose in the generated lambda.
javni
the rule to search for cmene used as arguments to the generated lambda.

nunjavni-samselpla defines the lambda that encloses samselpla. This lambda is defined by searching for references to nunjavni-cmene in javni, and extracting each cmene argument to construct the argument list for samselpla.

[syntax] (nunjavni-samselpla-midju rodacmene samselpla javni rest ...) => nunjavni-samselpla-fanmo
rodacmene
A list of cmene to pass as arguments to samselpla.
samselpla
The code to enclose in a lambda.
javni
The current portion of the rule generator expression being evaluated.
rest
The portion of the rule generator expression that remains to be evaluated.

nunjavni-samselpla-midju recursively searches javni for calls to nunjavni-cmene, building an argument list for samselpla.

nunjavni-samselpla-midju is the intermediate macro used by nunjavni-samselpla. It is not intended to be used by itself.

[syntax] (nunjavni-samselpla-fanmo rodacmene samselpla javni) => nunjavni-samselpla->mapti
rodacmene
A list of cmene to pass as arguments to samselpla.
samselpla
The code to enclose in a lambda.
javni
The rule generator expression passed to nunjavni-samselpla-mapti.

nunjavni-samselpla-fanmo formats the search results collected by nunjavni-samselpla-midju into scheme code, generating a call to nunjavni-samselpla-mapti.

nunjavni-samselpla-fanmo is the finalization macro used by nunjavni-samselpla-midju. It is not intended to be used by itself.

[procedure] (nunjavni-samselpla-mapti samselpla sumti-javni) => javni
samselpla
the code to execute if the generated javni calls mapti.
sumti-javni
The rule generating javni-valsi for samselpla.

Generate a javni that runs the passed in sumti-javni and, if the sumti-javni calls mapti, calls samselpla by passing the tokens in the jalga with the associated cmene tagged by nunjavni-cmene.

If sumti-javni does not match, samselpla is not called. There is no matching nunjavni-samselpla-namapti procedure, as there is only a single namapti called during a parse. Code that should be executed when a parse fails can be run after the parse completes; see genturfahi.

[syntax] (nunjavni-cmene cmene javni) => nunjavni-cmene*
cmene
The valsi to be quoted.
sumti-javni
the rule generator pattern passed to nunjavni-cmene*.

nunjavni-cmene quotes cmene and transforms its argument list into a call to nunjavni-cmene*.

[procedure] (nunjavni-cmene* cmene sumti-javni) => javni
cmene
The name for the jalge-valsi generated by sumti-javni.
sumti-javni
the rule to match.

Generate a javni that runs the passed in sumti-javni and, if the sumti-javni matches, associates cmene with the jalge-valsi associated with the mapti.

If sumti-javni does not match, call namapti without associating cmene with the result.

javni

A routine that, given a lerfu-porsi, creates a javni-jalge indicating match or nonmatch of that javni for that lerfu-porsi. This javni-jalge is then forwarded to the next javni by means of calling mapti for a match or namapti for a non-match.

A javni is provided the following parameters:

[procedure] (javni lerfu-porsi mapti namapti) => jalge
lerfu-porsi
the current parse position.
{{mapti</parameter>
continuation for rule match.
{{namapti</parameter>
continuation for rule non-match.

Note that jalge is not returned until the entire parse succeeds, and may not return at all on failure, if another path succeeds in the parse.

mapti .ijo namapti

A mapti is a continuation called by a javni when that javni matches the current lerfu-porsi.

A namapti is a continuation called by a javni when that javni does not match the current {lerfu-porsi}.

mapti and namapti have the signatures:

[procedure] (mapti lerfu-porsi nunjalge) => jalge
[procedure] (namapti lerfu-porsi) => object
lerfu-porsi
The current parse position.
nunjalge
A generated returning the current parse result.

genturfahi accepts the top-level parse rule and returns the result to the caller, rather than calling any additional mapti or namapti.

genturfahi

[procedure] (genturfahi-tolmohi) => '()

Clear the memoization cache. This is done automatically after each parse.

[procedure] (genturfahi javni) => rodavalsi
javni
The starting rule of the grammar.

Parse the javni, which is assumed to be the initial rule of the grammar. Return rodavalsi, the result of the parse.

If the parse succeed, rodavalsi is the abstract syntax tree as modified by any samselpla embedded in the grammar. If the parse failed, #f is returned. In both cases, the lerfu-porsi representing the input remaining after the parse is returned as a second value.

[procedure] (genturfahi* javni) => (rodavalsi lefpoi)
javni
The starting rule of the grammar.

genturfahi* calls genturfahi and converts the multiple arguments returned by genturfahi to a list and returns them.

This routine is used in the test framework, and might be useful elsewhere.

[constant] genturfahi-version-major

A number representing the major version of this module.

[constant] genturfahi-version-minor

A number representing the minor version of this module.

[constant] genturfahi-version-patch

A number representing the patch version of this module.

[constant] genturfahi-version

A string representing the version number of this module.

Examples

These examples show how to use the genturfahi API to construct a parser.

Operators
;;;; lerfu.scm

(use genturfahi)
(use test)

;;;
;;; terminal:
;;;
;;; a <- \#a
;;;
(define (lerfu)
  (set! genturfahi-lerfu
        (genturfahi* (nunjavni-lerfu #\a)))

  ; match the only character this parser matches.
  ;
  (test '(#\a "") (genturfahi-lerfu "a"))

  ; There is no rule to match any other character,
  ; so they don't match.
  ;
  (test '(#f "b") (genturfahi-lerfu "b"))
  (test '(#f "c") (genturfahi-lerfu "c"))

  ; there is no rule for the emtpy
  ; string, no match
  ;
  (test '(#f "") (genturfahi-lerfu ""))

  ; there is no rule for the end-of-file
  ; These match, but they don't parse the
  ; whole buffer!
  ;
  ; this rule won't even match two #\a,
  ; only one.
  ;
  (test '(#\a "a") (genturfahi-lerfu "aa"))
  (test '(#\a "b") (genturfahi-lerfu "ab"))
  (test '(#\a "c") (genturfahi-lerfu "ac"))

  ; later characters that would match
  ; don't if there is no rule to match
  ; earlier characters.
  ;
  (test '(#f "da") (genturfahi-lerfu "da"))
  0)

(lerfu)
;;;; optional.scm

(use genturfahi)
(use test)

;;;
;;; optional: e?
;;;
;;; a <- \#a?
;;;
(define (optional?)
  (set! genturfahi-optional
        (genturfahi* (nunjavni-? (nunjavni-lerfu #\a))))

  ; match the only character this parser matches.
  ;
  (test '(#\a "") (genturfahi-optional "a"))

  ; There is no rule to match any other character,
  ; but since this rule is optional, the empty string
  ; is returned.
  ;
  (test '("" "b") (genturfahi-optional "b"))
  (test '("" "c") (genturfahi-optional "c"))

  ; there is no rule for the emtpy string, but the
  ; optional rule matches anyway.
  ;
  (test '("" "") (genturfahi-optional ""))

  ; there is no rule for the end-of-file
  ; These match, but they don't parse the
  ; whole buffer!
  ;
  ; this rule won't even match two #\a,
  ; only zero or one.
  ;
  (test '(#\a "a") (genturfahi-optional "aa"))
  (test '(#\a "b") (genturfahi-optional "ab"))
  (test '(#\a "c") (genturfahi-optional "ac"))

  ; later characters that would match don't if there
  ; is no rule to match earlier characters.  We match
  ; zero #\a at the beginning of the parser input and
  ; return.
  ;
  (test '("" "da") (genturfahi-optional "da"))
  0)

(optional?)
;;;; zero-or-more.scm

(use genturfahi)
(use test)

;;;
;;; zero-or-more: e*
;;;
;;; a <- \#a*
;;;
(define (zero-or-more)
  (set! genturfahi-zero-or-more
        (genturfahi* (nunjavni-* (nunjavni-lerfu #\a))))

  ; match the only character this parser matches.
  ; notice that it returns a list of characters,
  ; even if it only matches a single character.
  ;
  (test '((#\a) "") (genturfahi-zero-or-more "a"))

  ; though the rule matches even when the character isn't present
  ; the empty list indicates no characters matched.
  ;
  (test '(() "") (genturfahi-zero-or-more ""))

  ; We match as many #\a as we can.
  ;
  (test '((#\a #\a) "") (genturfahi-zero-or-more "aa"))
  (test '((#\a #\a #\a) "") (genturfahi-zero-or-more "aaa"))

  ; There is no rule to match any other character,
  ; but since this rule matches zero-or-more, it
  ; succeeds in matching zero #\a.
  ;
  (test '(() "b") (genturfahi-zero-or-more "b"))
  (test '(() "c") (genturfahi-zero-or-more "c"))

  ; As well, it will match all #\a before ending
  ; the parse.  These match, but they don't parse
  ; the whole buffer!
  ;
  (test '((#\a) "b") (genturfahi-zero-or-more "ab"))
  (test '((#\a) "c") (genturfahi-zero-or-more "ac"))

  (test '((#\a #\a) "b") (genturfahi-zero-or-more "aab"))
  (test '((#\a #\a) "c") (genturfahi-zero-or-more "aac"))

  (test '((#\a #\a #\a) "b") (genturfahi-zero-or-more "aaab"))
  (test '((#\a #\a #\a) "c") (genturfahi-zero-or-more "aaac"))

  ; later characters that would match don't if there is no rule
  ; to match earlier characters.  This rule matches the empty
  ; list, but can't access the #\a later in the parse input.
  ;
  (test '(() "da") (genturfahi-zero-or-more "da"))
  (test '(() "daa") (genturfahi-zero-or-more "daa"))
  (test '(() "daaa") (genturfahi-zero-or-more "daaa"))
  0)

(zero-or-more)
;;;; one-or-more.scm

(use genturfahi)
(use test)

;;;
;;; one-or-more: e+
;;;
;;; a <- \#a+
;;;
(define (one-or-more)
  (set! genturfahi-one-or-more
        (genturfahi* (nunjavni-+ (nunjavni-lerfu #\a))))

  ; match the only character this parser matches.
  ; notice that it returns a list of characters,
  ; even if it only matches a single character.
  ;
  (test '((#\a) "") (genturfahi-one-or-more "a"))

  ; We match as many #\a as we can.
  ;
  (test '((#\a #\a) "") (genturfahi-one-or-more "aa"))
  (test '((#\a #\a #\a) "") (genturfahi-one-or-more "aaa"))

  ; but we don't match zero #\a.
  ;
  (test '(#f "") (genturfahi-one-or-more ""))
  (test '(#f "b") (genturfahi-one-or-more "b"))
  (test '(#f "c") (genturfahi-one-or-more "c"))

  ; As well, it will match all #\a before ending
  ; the parse.  These match, but they don't parse
  ; the whole buffer!
  ;
  (test '((#\a) "b") (genturfahi-one-or-more "ab"))
  (test '((#\a) "c") (genturfahi-one-or-more "ac"))

  (test '((#\a #\a) "b") (genturfahi-one-or-more "aab"))
  (test '((#\a #\a) "c") (genturfahi-one-or-more "aac"))

  (test '((#\a #\a #\a) "b") (genturfahi-one-or-more "aaab"))
  (test '((#\a #\a #\a) "c") (genturfahi-one-or-more "aaac"))

  ; later characters that would match don't if there is no rule
  ; to match earlier characters.  These rules don't match, as
  ; the input does not begin with #\a.
  ;
  (test '(#f "da") (genturfahi-one-or-more "da"))
  (test '(#f "daa") (genturfahi-one-or-more "daa"))
  (test '(#f "daaa") (genturfahi-one-or-more "daaa"))
  0)

(one-or-more)
;;;; je.scm

(use genturfahi)
(use test)

;;;
;;; ordered sequence: e_1 e_2
;;;
;;; je <- \#a \#b \#c
;;;
(define (je)
  (set! genturfahi-je
        (genturfahi* (nunjavni-je (nunjavni-lerfu #\a)
                                  (nunjavni-lerfu #\b)
                                  (nunjavni-lerfu #\c))))

  ; matches each lerfu in sequence 
  ;
  (test '((#\a #\b #\c) "") (genturfahi-je "abc"))

  ; matches the first rule (#\a), but not the second or
  ; third (#\b and #\c), so this match fails.
  ;
  (test '(#f "a") (genturfahi-je "a"))
  (test '(#f "ac") (genturfahi-je "ac"))

  ; matches the first two rules (#\a and #\b), but not
  ; the third one.
  ;
  (test '(#f "ab") (genturfahi-je "ab"))
  (test '(#f "abd") (genturfahi-je "abd"))

  ; "abc" is the only correct sequence.  Every other
  ; combination of #\a, #\b, and #\c does not match.
  ;
  (test '(#f "acb") (genturfahi-je "acb"))
  (test '(#f "bac") (genturfahi-je "bac"))
  (test '(#f "bca") (genturfahi-je "bca"))
  (test '(#f "cab") (genturfahi-je "cab"))
  (test '(#f "cba") (genturfahi-je "cba"))

  ; there is no rule for #\d, no match
  ;
  (test '(#f "d") (genturfahi-je "d"))

  ; there is no rule for the emtpy
  ; string, no match
  ;
  (test '(#f "") (genturfahi-je ""))

  ; there is no rule for the end-of-file
  ; These match, but they don't parse the
  ; whole buffer!
  ;
  (test '((#\a #\b #\c) "a") (genturfahi-je "abca"))
  (test '((#\a #\b #\c) "b") (genturfahi-je "abcb"))
  (test '((#\a #\b #\c) "c") (genturfahi-je "abcc"))

  ; later characters that would match
  ; don't if there is no rule to match
  ; earlier characters.
  ;
  (test '(#f "dabc") (genturfahi-je "dabc"))
  0)

(je)
;;;; jonai.scm

(use genturfahi)
(use test)

;;;
;;; ordered-choice: e_1 / e_2
;;;
;;; jonai <- \#a / \#b / \#c
;;;
(define (jonai)
  (set! genturfahi-jonai
        (genturfahi* (nunjavni-jonai (nunjavni-lerfu #\a)
                                     (nunjavni-lerfu #\b)
                                     (nunjavni-lerfu #\c))))

  ; matches (nunjavni-jonai (nunjavni-lerfu #\a) ...)
  ;
  (test '(#\a "") (genturfahi-jonai "a"))

  ; matches (nunjavni-jonai ... (nunjavni-lerfu #\b) ...)
  ;
  (test '(#\b "") (genturfahi-jonai "b"))

  ; matches (nunjavni-jonai ... (nunjavni-lerfu #\c))
  ;
  (test '(#\c "") (genturfahi-jonai "c"))

  ; there is no rule for #\d, no match
  ;
  (test '(#f "d") (genturfahi-jonai "d"))

  ; there is no rule for the emtpy
  ; string, no match
  ;
  (test '(#f "") (genturfahi-jonai ""))

  ; there is no rule for the end-of-file
  ; These match, but they don't parse the
  ; whole buffer!
  ;
  (test '(#\a "a") (genturfahi-jonai "aa"))
  (test '(#\a "b") (genturfahi-jonai "ab"))
  (test '(#\a "c") (genturfahi-jonai "ac"))

  ; later characters that would match
  ; don't if there is no rule to match
  ; earlier characters.
  ;
  ; none of these match.
  ;
  (test '(#f "da") (genturfahi-jonai "da"))
  (test '(#f "db") (genturfahi-jonai "db"))
  (test '(#f "dc") (genturfahi-jonai "dc"))
  0)

(jonai)
;;;; and-predicate.scm

(use genturfahi)
 use test)
;;;
;;; and-predicate: &e
;;;
;;; a <- &\#a
;;;
(define (and-predicate)
  (set! genturfahi-and-predicate
        (genturfahi* (nunjavni-& (nunjavni-lerfu #\a))))

  ; the and-predicate matches as normal, but does not advance
  ; the input.
  ;
  (test '(#\a "a") (genturfahi-and-predicate "a"))

  ; It behaves like all other rules when there is no match,
  ; indicating no match.
  ;
  (test '(#f "b") (genturfahi-and-predicate "b"))
  (test '(#f "c") (genturfahi-and-predicate "c"))

  ; there is no rule for the emtpy
  ; string, no match
  ;
  (test '(#f "") (genturfahi-and-predicate ""))

  ; there is no rule for the end-of-file
  ; These match, but they don't parse the
  ; whole buffer!
  ;
  ; this rule won't even match two #\a,
  ; only one.
  ;
  (test '(#\a "aa") (genturfahi-and-predicate "aa"))
  (test '(#\a "ab") (genturfahi-and-predicate "ab"))
  (test '(#\a "ac") (genturfahi-and-predicate "ac"))

  ; later characters that would match
  ; don't if there is no rule to match
  ; earlier characters.
  ;
  (test '(#f "da") (genturfahi-and-predicate "da"))
  0)

(and-predicate)
;;;; not-predicate.scm

(use genturfahi)
(use test)

;;;
;;; not-predicate: !e
;;;
;;; a <- !\#a
;;;
(define (not-predicate)
  (set! genturfahi-not-predicate
        (genturfahi* (nunjavni-! (nunjavni-lerfu #\a))))

  ; this not-predicate matches everything *but* \#a.
  ; not-predicate never advances the input.
  ;
  ; on match, we return the empty string.
  ;
  (test '(#f "a") (genturfahi-not-predicate "a"))
  (test '("" "b") (genturfahi-not-predicate "b"))
  (test '("" "c") (genturfahi-not-predicate "c"))

  ; we match the empty string (because the empty string
  ; isn't #\a.)
  ;
  (test '("" "") (genturfahi-not-predicate ""))

  ; there is no rule for the end-of-file
  ; These don't parse the whole buffer!
  ;
  (test '(#f "aa") (genturfahi-not-predicate "aa"))
  (test '(#f "ab") (genturfahi-not-predicate "ab"))
  (test '(#f "ac") (genturfahi-not-predicate "ac"))
  (test '("" "ba") (genturfahi-not-predicate "ba"))
  (test '("" "bb") (genturfahi-not-predicate "bb"))
  (test '("" "bc") (genturfahi-not-predicate "bc"))
  (test '("" "ca") (genturfahi-not-predicate "ca"))
  (test '("" "cb") (genturfahi-not-predicate "cb"))
  (test '("" "cc") (genturfahi-not-predicate "cc"))
  0)

(not-predicate)
;;;; empty-string.scm

(use genturfahi)
(use test)

;;;
;;; empty-string:
;;;
;;; empty-string <- [empty-string]
;;;
(define (empty-string)
  (set! genturfahi-empty-string (genturfahi* (nunjavni-e)))

  ; the empty string is zero characters long, so
  ; it always matches.
  ;
  (test '("" "") (genturfahi-empty-string ""))
  (test '("" "a") (genturfahi-empty-string "a"))
  (test '("" "b") (genturfahi-empty-string "b"))
  (test '("" "c") (genturfahi-empty-string "c"))
  (test '("" "abc") (genturfahi-empty-string "abc"))
  0)

(empty-string)
;;;; end-of-input.scm

(use genturfahi)
(use test)
;;;
;;; end-of-input
;;;
;;; eof <- [eof]
;;;
(define (end-of-input)
  (set! genturfahi-eof (genturfahi* (nunjavni-fanmo)))

  ; The end of file only matches when we're at the end of
  ; the parse input.
  ;
  (test '(#\nul "") (genturfahi-eof ""))

  ; it doesn't match if here are any characters left.
  ;
  (test '(#f "a") (genturfahi-eof "a"))
  (test '(#f "b") (genturfahi-eof "b"))
  (test '(#f "c") (genturfahi-eof "c"))

  ; even if those remaining characters are the sentinel. 
  ;
  (test `(#f ,(make-string 1 #\nul)) (genturfahi-eof (make-string 1 #\nul)))
  0)

(end-of-input)
;; jonai-naselci.scm: nonterminal symbols

(use genturfahi)
(use test)
;;;
;;; ordered choice with non-terminals
;;; this test is identical to the ordered choice example, though the
;;; grammar differs.
;;;
;;; grammar <- a / b / c
;;; a       <- #\a
;;; b       <- #\a
;;; c       <- #\a
;;;
(define (jonai-naselci)
  (set! genturfahi-jonai-naselci
    (letrec ((gerna (nunjavni-morji (nunjavni-jonai (nunjavni-naselci a)
                                                    (nunjavni-naselci b)
                                                    (nunjavni-naselci c))))
             (a (nunjavni-morji (nunjavni-lerfu #\a)))
             (b (nunjavni-morji (nunjavni-lerfu #\b)))
             (c (nunjavni-morji (nunjavni-lerfu #\c))))
      (genturfahi* gerna)))

  ; matches (nunjavni-jonai-naselci (nunjavni-lerfu #\a) ...)
  ;
  (test '(#\a "") (genturfahi-jonai-naselci "a"))

  ; matches (nunjavni-jonai-naselci ... (nunjavni-lerfu #\b) ...)
  ;
  (test '(#\b "") (genturfahi-jonai-naselci "b"))

  ; matches (nunjavni-jonai-naselci ... (nunjavni-lerfu #\c))
  ;
  (test '(#\c "") (genturfahi-jonai-naselci "c"))

  ; there is no rule for #\d, no match
  ;
  (test '(#f "d") (genturfahi-jonai-naselci "d"))

  ; there is no rule for the emtpy
  ; string, no match
  ;
  (test '(#f "") (genturfahi-jonai-naselci ""))

  ; there is no rule for the end-of-file
  ; These match, but they don't parse the
  ; whole buffer!
  ;
  (test '(#\a "a") (genturfahi-jonai-naselci "aa"))
  (test '(#\a "b") (genturfahi-jonai-naselci "ab"))
  (test '(#\a "c") (genturfahi-jonai-naselci "ac"))

  ; later characters that would match
  ; don't if there is no rule to match
  ; earlier characters.
  ;
  ; none of these match.
  ;
  (test '(#f "da") (genturfahi-jonai-naselci "da"))
  (test '(#f "db") (genturfahi-jonai-naselci "db"))
  (test '(#f "dc") (genturfahi-jonai-naselci "dc"))
  0)

(jonai-naselci)
Executing Code
;; simple (no-op) example

(use genturfahi)

;; XXX: I haven't written this example yet!
;; samselpla.scm

(use genturfahi)
(use test)
;;;
;;; execute code on syntax tree.
;;;
;;; grammar <- a b c
;;; a       <- #\a
;;; b       <- #\b
;;; c       <- #\c
;;;
(define (samselpla)
  (set! genturfahi-samselpla
    (letrec ((gerna (nunjavni-morji
               ; concatenate the strings
               (nunjavni-samselpla (string-append a b c)
                 (nunjavni-je
                   (nunjavni-cmene a (nunjavni-naselci a))
                   (nunjavni-cmene b (nunjavni-naselci b))
                   (nunjavni-cmene c (nunjavni-naselci c))))))
             (a (nunjavni-morji
               ; convert each character to a string.
               (nunjavni-samselpla (make-string 1 x)
                 (nunjavni-cmene x
                   (nunjavni-lerfu #\a)))))
             (b (nunjavni-morji
               (nunjavni-samselpla (make-string 1 x)
                 (nunjavni-cmene x
                   (nunjavni-lerfu #\b)))))
             (c (nunjavni-morji
               (nunjavni-samselpla (make-string 1 x)
                 (nunjavni-cmene x
                   (nunjavni-lerfu #\c))))))
      (genturfahi* gerna)))

  ; The code runs only after a a syntax tree is successfully
  ; generated.
  ;
  (test '("abc" "") (genturfahi-samselpla "abc"))

  ; It doesn't run at all if we fail to parse.
  ;
  (test '(#f "d") (genturfahi-samselpla "d"))

  ; Even if the parse partially matches before failing.
  ;
  (test '(#f "a") (genturfahi-samselpla "a"))
  (test '(#f "ab") (genturfahi-samselpla "ab"))

  ; But if we don't parse all of the input, that
  ; is a valid parse.
  ;
  (test '("abc" "a") (genturfahi-samselpla "abca"))
  (test '("abc" "b") (genturfahi-samselpla "abcb"))
  (test '("abc" "c") (genturfahi-samselpla "abcc"))
  0)

(samselpla)

Note that a tag should be placed outside of a nunjavni-jonai. If a tag is placed on a javni that is passed to a nunjavni-jonai, that same tag must be placed on every javni that is passed to that nunjavni-jonai.

The following example is undefined:

;; undefined interaction between nunjavni-jonai nunjavni-cmene

(use genturfahi)

;; XXX: This example isn't written yet!

And should instead be written as:

;; defined interaction between nunjavni-jonai nunjavni-cmene

(use genturfahi)

;; XXX: This example isn't written yet!
A Full Example

Here is a complete example for using this API to construct a parser. It is the same grammar presented in Chicken Gazette #5, which documents the packrat parser egg.

(use genturfahi)
(use test)
;;;
;;; This example appeared in chicken gazette #5 as the example for
;;; the packrat parser module:
;;;
;;;  http://gazette.call-cc.org/issues/5.html
;;;
;;; It is here ported to genturfa'i.
;;;
(define (mex)
  (set! javni-lerfu-0 (nunjavni-lerfu #\0))
  (set! javni-lerfu-1 (nunjavni-lerfu #\1))
  (set! javni-lerfu-2 (nunjavni-lerfu #\2))
  (set! javni-lerfu-3 (nunjavni-lerfu #\3))
  (set! javni-lerfu-4 (nunjavni-lerfu #\4))
  (set! javni-lerfu-5 (nunjavni-lerfu #\5))
  (set! javni-lerfu-6 (nunjavni-lerfu #\6))
  (set! javni-lerfu-7 (nunjavni-lerfu #\7))
  (set! javni-lerfu-8 (nunjavni-lerfu #\8))
  (set! javni-lerfu-9 (nunjavni-lerfu #\9))
  (set! javni-lerfu-+ (nunjavni-lerfu #\+))
  (set! javni-lerfu-* (nunjavni-lerfu #\*))
  (set! javni-lerfu-lparen (nunjavni-lerfu #\())
  (set! javni-lerfu-rparen (nunjavni-lerfu #\)))

  (let ((mex
    (letrec
      ((expr   (nunjavni-morji
                 (nunjavni-jonai
                   (nunjavni-samselpla (+ a b)
                     (nunjavni-je
                       (nunjavni-cmene a (nunjavni-naselci mulexp))
                       javni-lerfu-+
                       (nunjavni-cmene b (nunjavni-naselci mulexp))))
                   (nunjavni-naselci mulexp))))
       (mulexp (nunjavni-morji
                 (nunjavni-jonai
                   (nunjavni-samselpla (* a b)
                     (nunjavni-je
                       (nunjavni-cmene a (nunjavni-naselci simple))
                       javni-lerfu-*
                       (nunjavni-cmene b (nunjavni-naselci simple))))
                   (nunjavni-naselci simple))))
       (simple (nunjavni-morji
                 (nunjavni-jonai
                   (nunjavni-naselci num)
                   (nunjavni-samselpla a
                     (nunjavni-je
                       javni-lerfu-lparen
                       (nunjavni-cmene a (nunjavni-naselci expr))
                       javni-lerfu-rparen)))))
       (num    (nunjavni-morji
                 (nunjavni-samselpla (string->number (list->string a))
                   (nunjavni-cmene a (nunjavni-+ (nunjavni-naselci digit))))))
       (digit  (nunjavni-morji
                 (nunjavni-jonai
                   javni-lerfu-0
                   javni-lerfu-1
                   javni-lerfu-2
                   javni-lerfu-3
                   javni-lerfu-4
                   javni-lerfu-5
                   javni-lerfu-6
                   javni-lerfu-7
                   javni-lerfu-8
                   javni-lerfu-9))))
      (genturfahi expr))))

    (test 2  (mex "2"))
    (test 22 (mex "22"))
    (test 4  (mex "2*2"))
    (test 4  (mex "2+2"))
    (test 16 (mex "2+2*7"))
    (test 28 (mex "(2+2)*7"))
    (test 42 (mex "3*4+5*6")))
    0)

(mex)

History

Brian Ford coined the modern terms PEGs and packrat parsing, which was the subject of his Master's Thesis. Much of their formal theory existed earlier, the technique having been discovered by Alexander Birman in 1970. More recent work on the topic has all been done by others. His Master's Thesis is an accessible introduction to the topic of packrat parsing.

Tony Garnock-Jones wrote a packrat parser for scheme in 2005. He later packaged this work with a json parser for mzscheme and published it. Tony has not updated his parser since 2006.

Tony's packrat parser was ported to Chicken Scheme by Christian Kellermann and Felix Winkelmann in 2009. In 2010, it was featured in Chicken Gazette 5.

Alan Post began using the packrat parser after it was introduced in Chicken Gazette #5 and encountered problems translating the Lojban grammar. Some of these problems were anticipated by Tony Garnock-Jones:

"...whereas an extensible parser would require some kind of reified representation of the composite parser, along the lines of

`((expr   (or (seq (num + num) ,(lambda (a _ b) (+ a b)))
              (seq (mulexp)    ,(lambda (a) a))))
  (mulexp (or (seq (num * num) ,(lambda (a _ b) (* a b))))))

which could then be interpreted, in order to parse some input, or stepped through, in order to debug a parser or parser extension, or used in various diagnostic printouts to help pinpoint errors in parsed text or parsing extension grammars."

genturfahi was written to address these shortcomings in Tony's packrat parser, and to continue the work of creating a full PEG parser in Scheme, capably of parsing a Lojban's grammar.

Wish List

License

Copyright (c) 2010 ".alyn.post." <alyn.post@lodockikumazvati.org>
 
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted, provided that the above
copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

Version History

0.0.1
Initial release.