| Ticket UUID: | aa6f1708188134ba602d6bb230462b21c3509cce | |||
| Title: | Augmented and Active grammars | |||
| Type: | RFE | Version: | ||
| Submitter: | lars_h_again | Created on: | 2024-01-21 21:34:51 | |
| Subsystem: | pt (parsetools) | Assigned To: | ||
| Priority: | 5 Medium | Severity: | Important | |
| Status: | Open | Last Modified: | 2024-01-23 12:12:49 | |
| Resolution: | None | Closed By: | nobody | |
| Closed on: | ||||
| Description: |
RFE: Augmented and Active grammars
==================================
Summary
-------
This report suggests two new features for **pt** grammars:
1. **Augmented grammars**: attaching arbitrary information to the
nonterminals in the grammar, not just the *is* and *mode* entries needed
by the parser engine.
2. **Active grammars**: the ability to define actions on abstract syntax
trees from within the grammar.
The proposed solution for the second point depends on the first point.
Motivation
----------
It turns out that there is more to the problem of parsing data than just
obtaining the abstract syntax tree (AST) of the input — you still need to
convert this to whatever your target format is, and although a Simple
Matter Of Programming, that is not as straightforward as one might
imagine. The problem of converting the *pe-grammar-for-peg* AST (now that
the typos are fixed, so that it parses) into the grammar serialisation
format may serve as example. Obviously the **pt::peg::from::peg** command
implementation includes that step, so if looking for examples of how to do
it, then surely this would provide inspiration?
Well, after looking at how it's implemented — the code sits in the
**::pt::peg::from::peg::GEN** namespace — I would say no. You can do it
that way, but it's not very natural. The approach of a bottom-up
evaluation makes sense when the nodes of the AST correspond to operations
that are applied to their children, so for example
`pt::peg::from::peg::GEN::Sequence` is natural, but
`pt::peg::from::peg::GEN::Suffix` has to take apart one child to
discover which operation to apply to the other child — quite unnatural,
particularly so when the code otherwise abstracts away the serialisation
of parsing expressions through the use of `pt::pe` subcommands.
If you're feeling functional you can have `PLUS`, `STAR`, and `QUESTION`
return lambdas that `Suffix` is supposed to apply to the result of the
other child, but that would only be dressing on an abstraction that
doesn't quite fit. The ugly truth is that in practical syntaxes, there
arise AST nodes which don't have a sensible interpretation independent
of context, so we need a method of interpretation which acknowledges that.
The *pe-grammar-for-peg* AST is better served by a top-down recursion of
the AST, because then the `Prefix` and `Suffix` actions can simply look
at the child which does not denote a subexpression, and recurse only into
the other child; the result can be constructed without breaking the
abstraction provided by the **pt::pe** subcommands. The **::pt::ast
topdown** command is too inflexible to be used that way, but a procedure
that calls itself can achieve this end with elementary means.
### Elementary top-down recursion (example)
This is a bit long, but included in full for the sake of completeness. The
**::pt::peg::from::peg::GEN** code is about twice as long.
```
proc pt_grammar_from_tree {ast string} {
if {[lindex $ast 0] ne "Grammar"} then {
return -code error "Tree does not appear to be a grammar"
}
set res [dict create start [
pt_pe_from_tree [lindex $ast 3 4 3] $string
]]
foreach def [lrange $ast 4 end] {
set name [string range $string\
[lindex $def end-1 3 1] [lindex $def end-1 3 2]]
dict set res rules $name is [
pt_pe_from_tree [lindex $def end] $string
]
if {[lindex $def 3 0] ne "Attribute"} then {
dict set res rules $name mode value
} elseif {[lindex $def 3 3 0] eq "VOID"} then {
dict set res rules $name mode void
} else {
dict set res rules $name mode leaf
}
}
return [dict create pt::grammar::peg $res]
}
proc pt_pe_from_tree {ast string} {
switch -- [lindex $ast 0] Expression - Sequence {
if {[llength $ast] == 4} then {
return [pt_pe_from_tree [lindex $ast 3] $string]
}
set res [list\
[lindex {/ x} [expr {[lindex $ast 0] eq "Sequence"}]]]
foreach subtree [lrange $ast 3 end] {
lappend res [pt_pe_from_tree $subtree $string]
}
return $res
} Prefix {
switch -- [lindex $ast 3 0] AND {
return [list & [pt_pe_from_tree [lindex $ast 4] $string]]
} NOT {
return [list ! [pt_pe_from_tree [lindex $ast 4] $string]]
} Suffix {
return [pt_pe_from_tree [lindex $ast 3] $string]
}
} Suffix {
set res [pt_pe_from_tree [lindex $ast 3] $string]
switch -- [lindex $ast end 0] {
QUESTION {return [list ? $res]}
STAR {return [list * $res]}
PLUS {return [list + $res]}
Primary {return $res}
}
} Primary {
tailcall pt_pe_from_tree [lindex $ast 3] $string
} Literal {
set res [list x]
foreach subtree [lrange $ast 3 end] {
set char [string range $string\
[lindex $subtree 1] [lindex $subtree 2]]
if {[string match {\\*} $char]} then {
set char [subst -nocommands -novariables $char]
}
lappend res [list t $char]
}
if {[llength $res] == 2} then {return [lindex $res 1]}
return $res
} Class {
set ranges {}
foreach subtree [lrange $ast 3 end] {
set L {}
foreach subtree2 [lrange $subtree 3 end] {
set char [string range $string\
[lindex $subtree2 1] [lindex $subtree2 2]]
if {[string match {\\*} $char]} then {
set char [subst -nocommands -novariables $char]
}
lappend L $char
}
if {[llength $L] == 2} then {
lappend ranges [list .. {*}$L]
} else {
lappend ranges [list t [lindex $L 0]]
}
}
if {[llength $ranges] == 1} then {
return [lindex $ranges 0]
} else {
return [linsert $ranges 0 /]
}
} Identifier {
return [list n [
string range $string [lindex $ast 3 1] [lindex $ast 3 2]
]]
} DOT {
return dot
} ALNUM {
return alnum
} ALPHA {
return alpha
} ASCII {
return ascii
} CONTROL {
return control
} DDIGIT {
return ddigit
} DIGIT {
return digit
} GRAPH {
return graph
} LOWER {
return lower
} PRINTABLE {
return print
} PUNCT {
return punct
} SPACE {
return space
} UPPER {
return upper
} WORDCHAR {
return wordchar
} XDIGIT {
return xdigit
}
error "This should not happen!"
}
```
### Reasons to not be satisfied with that
One sort-of eyesore here is the large `switch`, when we're dealing with
keys that could be looked up in O(1) time. Another problem is the heavy
reliance on indexing into nested lists — likely efficient, but obscuring
the meaning of the data accessed, and thus the intent. The *major* problem
is however that of fragility: trivial refactorings of the grammar,
preserving the language recognised, can still change the ASTs enough to
invalidate how further processing is done. It is hard to spot where
changes have to be made, and even harder when we access adjacent nodes!
A way of countering this fragility would be to collect all information
related to the detail structure of the ASTs with the grammar itself. That
is the aim of the two proposed features.
Augmented grammars
------------------
The idea of augmented grammars is to provide for attaching arbitrary
pieces of information to the nonterminals in the grammar, not just what
the parser needs to produce an AST. Several possible extensions of the
serialisation format would achieve this, but since the serialisation
format already has one level of dictionary which is indexed by nonterminal
name and another level of dictionary inside that, the minimal extension
should be to allow additional entries in this inner dictionary. That
arrangement does not immediately provide for asking which nonterminals
have a particular extra piece of information, but that would still be
trivial to determine, should it turn out to be useful.
Right now **pt::peg verify** screams bloody murder about any of these
inner dictionaries having extra entires, but that could easily be changed.
Also, it suggests nobody is currently using entries beyond `is` and `mode`
for anything else.
The main question is rather how to express these extra pieces of
information in the PEG source of the grammar. The approach of minimal
effort is probably to rely on Tcl string representation of the dictionary.
Given
```
void: TclSpace <- [ \t\n\013\014\r]+ ;
TclWord <- TclBare / TclBrace / TclQuote ;
TclBare <- !["{] # for balance: }
( ![\\ \t\n\013\014\r;] . / '\\' . )+ ;
TclBrace <- '{' ( ![{}\\] . / '\\' . / TclBrace )* '}' ;
TclQuote <- '"' ( ![\\"] . / '//' . )* '"' ;
leaf: TclDict <- ( TclSpace TclWord TclSpace TclWord )* ;
```
we could provide for expressing arbitrary dictionary entries right there
in the PEG grammar, by changing the rule
```
Definition <- Attribute? Identifier IS Expression SEMICOLON ;
```
into
```
Definition <- Attribute? Identifier IS Expression
( "->" TclDict TclSpace? )? SEMICOLON ;
```
Parsing beyond that is trivial: the text under a `TclDict` has the form of
a Tcl dict, so we just start using it as a dict (in particular: set its
`is` and `mode` entries according to the `Attribute` and the `Expression`
of the `Definition`). It could hardly be easier.
### Applications
The main application I've explored is that of that including executable
code, by way of *active grammars* (next section), but systems of "type
declaring" the children would be possible, and could suffice for some
processing of ASTs.
It also seems plausible that help messages, or texts for producing error
messages, are often relative to specific nonterminals and thus could be
usefully kept in the grammar.
### Choices made
The choice of `->` for symbol separating an `Expression` from the
`TclDict` is to mirror the `<-` between `Identifier` and `Expression`; it
could be read as saying the nonterminal is mapped to the `TclDict`
following, which technically happens in the serialisation format.
Additionally, `-` (minus) does not seem to be allowed bare in an
`Expression`, making it a sensible candidate for marking the transition to
something else.
Spacing in the `TclDict` is strictly Tcl spacing, not PEG `WHITESPACE`,
to simplify parsing. In particular, comments are not allowed betweeen
`->` and `;`. Also, spacing in front of `TclWord`s is *mandatory*; this is
in accordance with how the words would appear in a `dict create` command
or similar.
Contrariwise, spacing in front of the semicolon terminating the
`Definition` is *optional*, again because this is how it would be in an
explicit Tcl command: consider `dict create foo "bar baz";`. For the same
reason, semicolon is excluded from appearing unescaped in a bareword, just
like it would be in a command (even if to the string representation of a
dict it has no special role).
It might be an idea to similarly exclude `#` from appearing unescaped in a
`TclBare`; unescaped `#`s are no problem for being parsed as a dict, but
prohibiting them should help catch errors where users attempt to put a
PEG comment in a `TclDict`. On the other hand, the canonical string
representation for a dict may contain bare `#`s:
```
% dict create \#a \#b \#c \#d
{#a} #b #c #d
```
Active grammars
---------------
The idea for an *active* grammar is simply that the extra data attached to
a nonterminal includes general Tcl code, to better support processing of
ASTs. The main question is what interface that code should experience, for
maximal usability.
The simplest interface would be as a script, but that has the major
disadvantage that recursive actions on an AST may require a piece of code
to be reentrant; each invocation needs to have a separate local context.
Also, with scripts it gets cumbersome to pass in data (such as the range
and children of the current node). Command prefixes instead place most of
the code outside the grammar, which defeats the entire purpose.
The simplest self-contained unit would be a lambda, which suggests
employing functional programming idioms where appropriate. How would one,
in a functional programming setting, permit a user-supplied worker function
to recursively call itself (or a sibling)? By passing as one of its
arguments a callback function for making that call! The argument structure
for a grammar action can thus be
*rec* *cdata* *from* *to* ?*child* ...?
where "*from* *to* ?*child* ...?" part is `[lrange $node 1 end]` of
the $node being processed, and *cdata* is some arbitrary client data
passed from the caller. For these ASTs, one usually wants to pass the full
string that was parsed as this *cdata*, but we could bundle it with
additional data if such are needed. The *rec* is a command prefix that can
be called as
` {*}$rec $action $cdata {*}$child`
to apply the action named *action* to the AST *child*; the action name is
of course a key used in the dictionary for the nonterminal of that
*child*, and the entry should be another lambda with syntax as above.
Implementing this for serialised augmented grammars is very easy:
```
proc ::pt::ast::recurse {grammar action cdata nonterminal args} {
if {[dict exists $grammar pt::grammar::peg rules $nonterminal $action]} then {
::apply [
dict get $grammar pt::grammar::peg rules $nonterminal $action
] [list ::pt::ast::recurse $grammar] $cdata {*}$args
} else {
return -code error "Nonterminal \"$nonterminal\" has no definition\
of action: $action"
}
}
```
The *rec* interface also supports the augmented grammar being stored in a
container object; in that case the value of *rec* would rather call a
method of this container object, but the code in the PEG would not need to
care.
### Example: Lambda calculus
The purpose of explicitly naming an action is that sometimes there are
several different operations that one applies to an AST, and one operation
may even need to apply other operations to its children. An example that
may be close at hand to computer scientists is that of lambda calculus,
where we have operations such as enumerating free variables, renaming
bound variables (alpha-conversion), and substituting terms for a free
variable (which, as readers may recall, can get rather messy if you want
to avoid variable capture).
```
PEG pure_lambda_term ( <space>* Expression <space>* !. )
#
# The FV action determines which variables have free occurrences in
# a term. It returns a dictionary, whose keys are the names of those
# variables (because removing from a dict is easier than removing from
# a list) and whose values are the number (>0) of free occurrencies of
# these variables.
#
# The name action is only defined for Variable nodes, and returns the
# name of that variable.
#
Expression <-
Primary ( <space>* Primary )*
->
FV {{rec text s e first args} {
set res [{*}$rec FV $text {*}$first]
foreach child $args {
dict for {var val} [{*}$rec FV $text {*}$child] {
dict incr res $var $val
}
}
return $res
}}
;
Primary <-
Variable / Lambda / "(" <space>* Expression <space>* ")"
# Since a Primary always has exactly one child node of more
# specific type, you always just recurse to that.
->
FV {{rec text s e child} {{*}$rec FV $text {*}$child}}
;
Variable <-
<alpha> <alnum>*
->
name {{rec text s e} {string range $text $s $e}}
FV {{rec text s e} {
# This demonstrates recursing to the same node:
dict create [
{*}$res name $text Variable $s $e
] 1
}}
;
Lambda <-
"\\" <space>* Variable <space>* "." <space>* Expression
->
FV {{rec text s e var body} {
dict remove [{*}$rec FV $text {*}$body] [{*}$rec name $text {*}$var]
}}
;
```
It is certainly possible to play around with this, although there are
limitations. In order to do evaluation of lambda-terms, you need
capture-avoiding substitution, and that may need to invent new variable
names, which isn't something you can do purely in the AST, since all
variable names have to be read from the parsed source — there's no room
for putting non-structural data in the AST (as currently defined).
Then again, using AST as an encoding of lambda terms is a bit corny
anyway. Good as example, but not all examples have to be developed
further.
### Variations on the recursion
One obvious variation on the recursion would be to pass two items of
*cdata* instead of one.
```
proc ::pt::ast::recurse2 {grammar action cdata1 cdata2 nonterminal args} {
if {[dict exists $grammar pt::grammar::peg rules $nonterminal $action]} then {
::apply [
dict get $grammar pt::grammar::peg rules $nonterminal $action
] [list ::pt::ast::recurse2 $grammar] $cdata1 $cdata2 {*}$args
} else {
return -code error "Nonterminal \"$nonterminal\" has no definition\
of action: $action"
}
}
```
However, this has the notable disadvantage that callers of some `{*}$rec`
aren't allowed to pick which version of it they're using, hence actions
expecting two *cdata* items cannot call actions expecting one *cdata* item
or vice versa! Bundling (and unbundling) multiple items of data into one
*cdata* argument might seem cumbersome, but it is more flexible and ends
up being cleaner: the data passed can be adapted to the action called.
Therefore `recurse2` ends up being a bad idea.
A better variation is to make sure that all recursive action calls
experiences the same context as `uplevel 1`, because that makes for easy
sharing of (potentially mutable) data. Since each recursion step
introduces two stack levels (`recurse` procedure and action lambda) if we
don't want to rely on `tailcall`, that means going `uplevel 2` at a
suitable point, so we need an extra wrapper level to get the root action
in place. That lets us save some levels for the `dict get`s as well.
```
proc ::pt::ast::level_recurse {grammar action cdata nonterminal args} {
Level_recurse [dict get $grammar pt::grammar::peg rules]\
$action $cdata $nonterminal {*}$args
}
proc ::pt::ast::Level_recurse {rules action cdata nonterminal args} {
if {[dict exists $rules $nonterminal $action]} then {
uplevel 2 [list ::apply [
dict get $rules $nonterminal $action
] [list ::pt::ast::Level_recurse $rules] $cdata {*}$args]
} else {
return -code error "Nonterminal \"$nonterminal\" has no definition\
of action: $action"
}
}
```
Here, an action requiring `level_recurse` has no problem calling an action
that was designed for plain `recurse`.
### Implementation
The attached file `bootstrap_peg.tcl` uses existing **pt** facilities to
create, from PEG source, an active grammar `G1` which can parse its own
source code (to recreate the identical active grammar `G2`).
| |||
| User Comments: |
aku added on 2024-01-23 12:12:49:
When you are logged in the `Attach` should be the leftmost button in the secondary navbar. I.e. pretty much under the `Core` button of the primary navbar. lars_h_again (claiming to be Lars Hellström) added on 2024-01-21 21:39:00: Weird, can't see the button to attach a file.
Pasting the code raw here instead.
##
# bootstrap_peg.tcl
#
# Bootstrap active PEG grammars, using pt packages.
# Aim is to reach an active PEG grammar that can parse itself.
##
# Step 1: Formulate a grammar for the PEG of augmented gramamrs,
# which pt::peg::from::peg can parse as-is.
#
# This is based on modules/pt/include/format/peg.inc commit 05a6cfea10569b41,
# then modified.
set augmented_grammar_peg {
PEG augmented_grammar_peg (Grammar !.) # Change: Don't bury EOF constraint
# --------------------------------------------------------------------
# Tcl syntax nonterminals (new!)
void: TclSpace <- [ \t\n\013\014\r]+ ;
TclWord <- TclBrace / TclQuote / TclBare ;
TclBrace <- '{' ( ![{}\\] . / '\\' . / TclBrace )* '}' ;
TclQuote <- '"' ( ![\\"] . / '//' . )* '"' ;
TclBare <- !["{] # for balance: }
( ![\\ \t\n\013\014\r;] . / '\\' . )+ ;
leaf: TclDict <- ( TclSpace TclWord TclSpace TclWord )* ;
# --------------------------------------------------------------------
# Syntactical constructs
Grammar <- WHITESPACE Header Definition* Final ;
Header <- PEG Identifier StartExpr ;
Definition <- Attribute? Identifier IS
(AugmentedExpr / Expression) SEMICOLON
# The AugmentedExpr/Expression form simplifies
# further processing of the AST.
;
Attribute <- (VOID / LEAF) COLON ;
AugmentedExpr <- Expression "->" TclDict TclSpace? ;
Expression <- Sequence (SLASH Sequence)* ;
Sequence <- Prefix+ ;
Prefix <- (AND / NOT)? Suffix ;
Suffix <- Primary (QUESTION / STAR / PLUS)? ;
Primary <- ALNUM / ALPHA / ASCII / CONTROL / DDIGIT / DIGIT
/ GRAPH / LOWER / PRINTABLE / PUNCT / SPACE / UPPER
/ WORDCHAR / XDIGIT
/ Identifier
/ OPEN Expression CLOSE
/ Literal
/ Class
/ DOT
;
Literal <- APOSTROPH (!APOSTROPH Char)* APOSTROPH WHITESPACE
/ DAPOSTROPH (!DAPOSTROPH Char)* DAPOSTROPH WHITESPACE ;
Class <- OPENB (!CLOSEB Range)* CLOSEB WHITESPACE ;
Range <- Char TO Char / Char ;
StartExpr <- OPEN Expression CLOSE ;
void: Final <- "END" WHITESPACE SEMICOLON
# WHITESPACE # Change because redundant: SEMICOLON already contains WHITESPACE
;
# --------------------------------------------------------------------
# Lexing constructs
Identifier <- Ident WHITESPACE ;
leaf: Ident <- ([_:] / <alpha>) ([_:] / <alnum>)* ;
Char <- CharSpecial / CharOctalFull / CharOctalPart
/ CharUnicode / CharUnescaped
;
leaf: CharSpecial <- "\\" [nrt'"\[\]\\] ;
leaf: CharOctalFull <- "\\" [0-3][0-7][0-7] ;
leaf: CharOctalPart <- "\\" [0-7][0-7]? ;
leaf: CharUnicode <- "\\" 'u' HexDigit (HexDigit (HexDigit HexDigit?)?)? ;
leaf: CharUnescaped <- !"\\" . ;
void: HexDigit <- [0-9a-fA-F] ;
void: TO <- '-' ;
void: OPENB <- "[" ;
void: CLOSEB <- "]" ;
void: APOSTROPH <- "'" ;
void: DAPOSTROPH <- '"' ;
void: PEG <- "PEG" !([_:] / <alnum>) WHITESPACE ;
void: IS <- "<-" WHITESPACE ;
leaf: VOID <- "void" WHITESPACE ; # Implies that definition has no semantic value.
leaf: LEAF <- "leaf" WHITESPACE ; # Implies that definition has no terminals.
void: SEMICOLON <- ";" WHITESPACE ;
void: COLON <- ":" WHITESPACE ;
void: SLASH <- "/" WHITESPACE ;
leaf: AND <- "&" WHITESPACE ;
leaf: NOT <- "!" WHITESPACE ;
leaf: QUESTION <- "?" WHITESPACE ;
leaf: STAR <- "*" WHITESPACE ;
leaf: PLUS <- "+" WHITESPACE ;
void: OPEN <- "(" WHITESPACE ;
void: CLOSE <- ")" WHITESPACE ;
leaf: DOT <- "." WHITESPACE ;
leaf: ALNUM <- "<alnum>" WHITESPACE ;
leaf: ALPHA <- "<alpha>" WHITESPACE ;
leaf: ASCII <- "<ascii>" WHITESPACE ;
leaf: CONTROL <- "<control>" WHITESPACE ;
leaf: DDIGIT <- "<ddigit>" WHITESPACE ;
leaf: DIGIT <- "<digit>" WHITESPACE ;
leaf: GRAPH <- "<graph>" WHITESPACE ;
leaf: LOWER <- "<lower>" WHITESPACE ;
leaf: PRINTABLE <- "<print>" WHITESPACE ;
leaf: PUNCT <- "<punct>" WHITESPACE ;
leaf: SPACE <- "<space>" WHITESPACE ;
leaf: UPPER <- "<upper>" WHITESPACE ;
leaf: WORDCHAR <- "<wordchar>" WHITESPACE ;
leaf: XDIGIT <- "<xdigit>" WHITESPACE ;
void: WHITESPACE <- (" " / "\t" / EOL / COMMENT)* ;
void: COMMENT <- '#' (!EOL .)* EOL ;
void: EOL <- "\n\r" / "\n" / "\r" ;
# --------------------------------------------------------------------
END;
}
#
# Step 2: Extend grammar with actions for getting a grammar serialisation
# from the AST
#
# At this point, it becomes natural to introduce the nonterminals in a
# different order, because when deciding on what to do for a node, you
# need to know what its children are. In particular, you need to know
# which nonterminals are void -- that means you can't present everything
# in a top-down manner.
#
# The actions we use are:
#
# pe - Return parsing expression (nested list serialisation)
# of this node in AST.
# str - Return string counterpart of node, with escapes (if any) decoded.
# rule - Return pair of key (a nonterminal name) and value (a dict) for
# an entry in the rules dictionary.
# peg - Return full serialisation of the grammar.
#
set active_grammar_peg {
PEG active_grammar_peg (Grammar !.)
# Bottom-up, you begin with whitespace
void: WHITESPACE <- (" " / "\t" / EOL / COMMENT)* ;
void: COMMENT <- '#' (!EOL .)* EOL ;
void: EOL <- "\n\r" / "\n" / "\r" ;
# Next subsystem is Identifier, which brings us our first actions.
leaf: Ident <- ([_:] / <alpha>) ([_:] / <alnum>)*
-> str {{rec text s e} {
string range $text $s $e
}};
Identifier <- Ident WHITESPACE
-> pe {{rec text s e child} {
list n [{*}$rec str $text {*}$child]
}};
# The named character classes are boring, but self-contained,
# so we can do those next.
leaf: ALNUM <- "<alnum>" WHITESPACE -> pe {args {return alnum}};
leaf: ALPHA <- "<alpha>" WHITESPACE -> pe {args {return alpha}};
leaf: ASCII <- "<ascii>" WHITESPACE -> pe {args {return ascii}};
leaf: CONTROL <- "<control>" WHITESPACE -> pe {args {return control}};
leaf: DDIGIT <- "<ddigit>" WHITESPACE -> pe {args {return ddigit}};
leaf: DIGIT <- "<digit>" WHITESPACE -> pe {args {return digit}};
leaf: GRAPH <- "<graph>" WHITESPACE -> pe {args {return graph}};
leaf: LOWER <- "<lower>" WHITESPACE -> pe {args {return lower}};
leaf: PRINTABLE <- "<print>" WHITESPACE -> pe {args {return print}};
leaf: PUNCT <- "<punct>" WHITESPACE -> pe {args {return punct}};
leaf: SPACE <- "<space>" WHITESPACE -> pe {args {return space}};
leaf: UPPER <- "<upper>" WHITESPACE -> pe {args {return upper}};
leaf: WORDCHAR <- "<wordchar>" WHITESPACE -> pe {args {return wordchar}};
leaf: XDIGIT <- "<xdigit>" WHITESPACE -> pe {args {return xdigit}};
leaf: DOT <- "." WHITESPACE -> pe {args {return dot}};
# That was the majority of the atomic PEs, so we might as well
# get on with those that remain. That means we need to decode
# Chars.
leaf: CharSpecial <- "\\" [nrt'"\[\]\\] ; # " (match quote for syntax highlighting)
leaf: CharOctalFull <- "\\" [0-3][0-7][0-7] ;
leaf: CharOctalPart <- "\\" [0-7][0-7]? ;
leaf: CharUnicode <- "\\" 'u' HexDigit (HexDigit (HexDigit HexDigit?)?)? ;
void: HexDigit <- [0-9a-fA-F] ;
leaf: CharUnescaped <- !"\\" . ;
Char <- CharSpecial / CharOctalFull / CharOctalPart
/ CharUnicode / CharUnescaped
-> str {{rec text s e child} {
# We could do fancy custom code for decoding
# each kind of Char, but all the PEG escapes
# are also valid Tcl escapes, so we can let
# [subst] do all of them for us.
if {[lindex $child 0] eq "CharUnescaped"} then {
string range $text $s $e
} else {
subst -novariables -nocommands [string range $text $s $e]
}
}};
# Having decoded Char's, Literal's are easy.
void: APOSTROPH <- "'" ;
void: DAPOSTROPH <- '"' ; # " (match quote for syntax highlighting)
Literal <- APOSTROPH (!APOSTROPH Char)* APOSTROPH WHITESPACE
/ DAPOSTROPH (!DAPOSTROPH Char)* DAPOSTROPH WHITESPACE
-> pe {{rec text s e args} {
set res [list x]
foreach child $args {
lappend res [list t [{*}$rec str $text {*}$child]]
}
if {[llength $res] == 2} then {
return [lindex $res 1]
} else {
return $res
}
}};
# That leaves only Class. One way to handle it is to have each
# Range produce a pe of type .. or t, and then have the Class
# gather these in a /.
void: TO <- '-' ;
Range <- Char TO Char / Char
-> pe {{rec text s e args} {
if {[llength $args] == 1} then {
list t [{*}$rec str $text {*}[lindex $args 0]]
} else {
list .. [{*}$rec str $text {*}[lindex $args 0]] [{*}$rec str $text {*}[lindex $args 1]]
}
}};
void: OPENB <- "[" ;
void: CLOSEB <- "]" ;
Class <- OPENB (!CLOSEB Range)* CLOSEB WHITESPACE
-> pe {{rec text s e args} {
set res [list /]
foreach child $args {
lappend res [{*}$rec pe $text {*}$child]
}
if {[llength res] == 2} then {
return [lindex $res 1]
} else {
return $res
}
}};
# Next order of business is then the compound parsing expressions.
# Recursion makes it unavoidable that we encounter one not seen
# before, but it is hardly a surprise that Expression is a value
# nonterminal.
void: OPEN <- "(" WHITESPACE ;
void: CLOSE <- ")" WHITESPACE ;
Primary <- ALNUM / ALPHA / ASCII / CONTROL / DDIGIT / DIGIT
/ GRAPH / LOWER / PRINTABLE / PUNCT / SPACE / UPPER
/ WORDCHAR / XDIGIT
/ Identifier
/ OPEN Expression CLOSE
/ Literal
/ Class
/ DOT
-> pe {{rec text s e child} {{*}$rec pe $text {*}$child}};
leaf: QUESTION <- "?" WHITESPACE ;
leaf: STAR <- "*" WHITESPACE ;
leaf: PLUS <- "+" WHITESPACE ;
Suffix <- Primary (QUESTION / STAR / PLUS)?
-> pe {{rec text s e body args} {
set pe [{*}$rec pe $text {*}$body]
switch -- [lindex $args 0 0] {
QUESTION {list ? $pe}
STAR {list * $pe}
PLUS {list + $pe}
default {set pe}
}
}};
leaf: AND <- "&" WHITESPACE ;
leaf: NOT <- "!" WHITESPACE ;
Prefix <- (AND / NOT)? Suffix
-> pe {{rec text s e args} {
set pe [{*}$rec pe $text {*}[lindex $args end]]
switch -- [lindex $args end-1 0] {
AND {list & $pe}
NOT {list ! $pe}
default {set pe}
}
}};
Sequence <- Prefix+
-> pe {{rec text s e args} {
set res [list x]
foreach child $args {
lappend res [{*}$rec pe $text {*}$child]
}
if {[llength $res] == 2} then {
return [lindex $res 1]
} else {
return $res
}
}};
void: SLASH <- "/" WHITESPACE ;
Expression <- Sequence (SLASH Sequence)*
-> pe {{rec text s e args} {
set res [list /]
foreach child $args {
lappend res [{*}$rec pe $text {*}$child]
}
if {[llength $res] == 2} then {
return [lindex $res 1]
} else {
return $res
}
}};
# --------------------------------------------------------------------
# Above the recursive parts of the grammar, things are more
# one-off, so let's explore a less recursive style of coding.
void: IS <- "<-" WHITESPACE ;
leaf: VOID <- "void" WHITESPACE ; # Implies that definition has no semantic value.
leaf: LEAF <- "leaf" WHITESPACE ; # Implies that definition has no terminals.
void: COLON <- ":" WHITESPACE ;
Attribute <- (VOID / LEAF) COLON ;
void: TclSpace <- [ \t\n\013\014\r]+ ;
TclWord <- TclBrace / TclQuote / TclBare ;
TclBrace <- '{' ( ![{}\\] . / '\\' . / TclBrace )* '}' ;
TclQuote <- '"' ( ![\\"] . / '//' . )* '"' ;
TclBare <- !["{] # for balance: }
( ![\\ \t\n\013\014\r;] . / '\\' . )+ ;
leaf: TclDict <- ( TclSpace TclWord TclSpace TclWord )* ;
AugmentedExpr <- Expression "->" TclDict TclSpace? ;
void: SEMICOLON <- ";" WHITESPACE ;
Definition <- Attribute? Identifier IS
(AugmentedExpr / Expression) SEMICOLON
-> rule {{rec text s e args} {
if {[lindex $args end 0] eq "Expression"} then {
set val [dict create is [
{*}$rec pe $text {*}[lindex $args end]
]]
} else {
set val [string range $text [lindex $args end end 1] [lindex $args end end 2]]
dict set val is [
{*}$rec pe $text {*}[lindex $args end end-1]
]
}
if {[lindex $args 0 0] ne "Attribute"} then {
dict set val mode value
} elseif {[lindex $args 0 3 0] eq "VOID"} then {
dict set val mode void
} else {
dict set val mode leaf
}
return [list [
{*}$rec str $text {*}[lindex $args end-1 3]
] $val]
}};
# That took care of most of the variant stuff, so the top level is
# pretty easy.
void: PEG <- "PEG" !([_:] / <alnum>) WHITESPACE ;
StartExpr <- OPEN Expression CLOSE ;
Header <- PEG Identifier StartExpr ;
void: Final <- "END" WHITESPACE SEMICOLON ;
Grammar <- WHITESPACE Header Definition* Final
-> peg {{rec text s e header args} {
set rules [dict create]
foreach def $args {
dict set rules {*}[{*}$rec rule $text {*}$def]
}
return [dict create pt::grammar::peg [
dict create rules $rules start [
{*}$rec pe $text {*}[lindex $header end end]
]
]]
}};
# --------------------------------------------------------------------
END;
}
# If I later decide to get rid of e.g. StartExpr as a separate nonterminal,
# then I don't need to go hunting very far to find the piece of code that
# would have to be modified because of this.
# Step 3: Compile the above
#
package require pt::ast
package require pt::peg::from::peg
package require pt::peg::container
package require pt::peg::interp
# Getting a grammar that can parse augmented grammars is no problem.
set G0 [pt::peg::from::peg convert $augmented_grammar_peg]
pt::peg::container G0C deserialize $G0
pt::peg::interp G0parser
G0parser use G0C
set AST1 [G0parser parset $active_grammar_peg]
# But that is only the AST, not the active grammar it encodes. How to do
# the next step, without needlessly reinventing the wheel? Well, the
# action definitions we need are fairly close to the root of that AST, so
# we can go get them and then forcibly insert these augmentations into the
# plain grammar G0 (shamelessly exploiting knowledge of where the
# Definition nodes are and what their children look like).
set G0a $G0
foreach def [lrange $AST1 4 end] {
if {[lindex $def end 0] eq "AugmentedExpr"} then {
set name [string range $active_grammar_peg\
[lindex $def end-1 end 1] [lindex $def end-1 end 2]]
foreach {key val} [
string range $active_grammar_peg\
[lindex $def end end 1] [lindex $def end end 2]
] {
dict set G0a pt::grammar::peg rules $name $key $val
}
}
}
# That means we should be ready to have an action transform AST1 into the
# active grammar G1, as soon as we've defined the ::pt::ast::recurse
# procedure.
proc ::pt::ast::recurse {grammar action cdata nonterminal args} {
if {[dict exists $grammar pt::grammar::peg rules $nonterminal $action]} then {
::apply [
dict get $grammar pt::grammar::peg rules $nonterminal $action
] [list ::pt::ast::recurse $grammar] $cdata {*}$args
} else {
return -code error "Nonterminal \"$nonterminal\" has no definition\
of action: $action"
}
}
set G1 [::pt::ast::recurse $G0a peg $active_grammar_peg {*}$AST1]
# Now, it turns out the current container objects scream when given
# augmented grammars, so we need to dumb it down for them.
set G1dumb $G1
dict set G1dumb pt::grammar::peg rules [
dict map {key val} [dict get $G1dumb pt::grammar::peg rules] {
dict filter $val key is mode
}
]
pt::peg::container G1C deserialize $G1dumb
pt::peg::interp G1parser
G1parser use G1C
set AST2 [G1parser parset $active_grammar_peg]
set G2 [::pt::ast::recurse $G1 peg $active_grammar_peg {*}$AST2]
# Grammars G1 and G2 are now [string equal].
| |||
Home
Blog
Docs
Downloads
Tickets
Timeline
Branches
Tags
Wiki