rain-1 / racket-peg Goto Github PK
View Code? Open in Web Editor NEWracket scheme peg-parser
License: GNU General Public License v3.0
racket scheme peg-parser
License: GNU General Public License v3.0
https://www.rosettacode.org/wiki/Brace_expansion
#lang peg
item <- [^{},]+ / ~'{' choice ~'}';
choice <- x:item+ xs:(~',' item+)* -> (cons x xs);
; > (peg (+ item) "It{{em,alic}iz,erat}e{d,}")
; '("It" ((("em" . "alic") "iz") . "erat") "e")
The resulting parse is confusing and we can't change the char class to *. it's too hard to parse this simple language.
#lang peg
(define (eval-rpn l [aux '()])
(match l
['() (car aux)]
[(list (? number? a) b ...) (eval-rpn (cdr l) (cons (car l) aux))]
[(list a b ...) (eval-rpn (cdr l) (cons (a (car aux) (cadr aux)) (cddr aux)))]));
_ < [ \t\n]* ;
number <- value:[0-9]+ -> (string->number value);
top <- v:rpn ! . -> (eval-rpn v);
rpn <- number (_ rpn _ Bop)* _ ;
Bop <- v:[+\-] -> (if (equal? v "+") + -) ;
this dont work because the identifier parser dont understand "..."
it needs to produce useful error messages on a parse failure.
#lang peg
a <- '' 'a' ;
this don't work. Because expect to have at least one char inside single quotes
this is a very future functionality.
The peg lang actually generate structs that is cool to do a lot of things, but is not so cool to implement languages inside racket. In #lang peg/syntax
the generate object is a syntax object, so the parser file can be the reader file directly.
We don't need to add lexical information on create a language, just create the semantic, import in the parser, and the parser becomes a reader because generate syntax object.
use case :
#lang peg
, make some tests, extend, etc#lang peg/syntax
and voilà, a reader.The great advantage of peg is composition. Imagine someone write a peg to a language and define expressions only as arithmetic Expressions. I want to put Boolean expressions, function call and other things. I can't just import aritexp.rkt because he export expression. I will need to change the code.
One possible alternative can be import only some Peg's, or import with a prefix.
import aritexp from otherexp.rkt;
import exp as aritexp from otherexp.rkt;
import otherexp.rkt with prefix other;
In this way, the number of languages can be multiplied by 10 because of reuse
to write something like password <- [a-zA-Z0-9]{8}[a-zA-Z0-9]* ;
to the password has minimun length of 8.
or a <- [a-z]{8,10}
to between 8 and 10 char.
or a <- [a-z]{8,}
without upper limit, with the semantics of minimun of 8
put capabilities to get semantic value from "#lang peg"
something like
#lang peg
number <- (name value [0-9]*) (lambda () value) ;
it doesn't cover the full scheme langauge yet. it doesn't need to cover the complete syntax of scheme. but we should add a bit more than this current bare minimum.
A well-formed PEG always accept or fails, never go in a infinite loop.
There's only two ways a PEG is not-well-formed : left recursion or star over nullable expression.
E <- E '+' T ;
is a example of left recursion
A <- ('a'*)* ;
is a example of star over nullable expression
If we can detect this states, we can show to the user, improving error message instead of the user see a infinite parsing time .
Other possibility is allow more permissive rules
There are algorithms that receive a left-recursive grammar, turn in a non-left recursive grammar, obtain the parse tree and transform that to a parse tree compatible with the original grammar. If we use this, mostly grammar can be just ported to peg, without any change.
PEG.js
do this. I am studing this algorithm, but yet don't understand total.
I don't know if there's algorithm to detect star over nullable expression to do this with the second restriction.
peg: parse failed in rule peg-rule:identifier at location 269 with options '(or #\) #\[ #\] #\{ #\} #\" #\, #\' #\` #\; #\# #\| #\\)
#lang peg
a <- 'a' -> #f ;
This don't work because is translated to use #f as semantic value this is a hard-coded code interpreted as don't have semantic action(in real world, this repeat this input) instead of returning #f when I use (peg a "a")
There's only two options to working peg : he match or he dont. When I have problems with peg, I miss some path information
#lang peg
number <- [0-9]+;
identifier <- [a-zA-Z]+ ;
terminal <- number / identifier ;
(peg terminal "123" #:verbose)
outputs :
match "123" with terminal -> number -> "123"
or (peg terminal "foobar" #:verbose)
outputs :
match "foobar" with terminal -> number -> fail -> terminal ->identifier -> "foobar"
or at least closer.
https://www.gnu.org/software/guile/manual/html_node/PEG-Parsing.html
When I think of put other continuation, I bumped into my ignorance about the formal functioning of pegvm.
I took example from Ford's original paper:
A ← aAb/ε
B ← bBc/ε
S ← &(A!b)a∗ B!.
#lang racket
(require peg)
(define-peg A
(or (and (char #\a) A (char #\b)) (epsilon)))
(define-peg B
(or (and (char #\b) B (char #\c)) (epsilon)))
(define-peg S
(and (& (and A (! (char #\b)))) (* (char #\a)) B (! (any-char))))
(peg S "aaabbcc") ; should not match
(peg S "aabbcc") ; works as expected
(peg S "abbcc") ; works as expected
Interesting that this bug is consistent across several implementations.
So, when we do something like
A <- ifElse / if
ifElse <- if else
if <- ....
When try to parse a simple if with A, ifElse will fail, then will try "if", but will remember "Hey, I match a if starting in this text position, so I will apply this result to the continuation sucess and try to parse the rest"
And in this way, the cost of memory can be bigger if not implemented in a clever waty, but the time cost will be smaller
A common idiom is to define rules like OB < '{" ;
What shorthand could be created for this?
"{"
could be used, but it does't seem logical.Make the peg function handle ports instead of just strings
#lang peg
item <-- [^{]+ / '{' item '}' ;
;> (peg item "{abc}")
; {abc}
; ^ here
; peg: parse failed in rule peg-rule:item at location 5 with options '(or (+ (and (! #\{) (any-char))) (and "{" item "}"))
In the same way that positive lookahead, this is a syntatic sugar
epsilon <-- (! .) / (& .) ;
I dont know of a good symbol of that, but I think that will be a good add.
I am just a but frustrated with the way peg-result objects work. There is a fair bit of "magic" involved and the results can be somewhat unpredictable.
do some timing measurements against other parsers e.g. lalr parser in guile scheme. see how efficient this parser is on a range of languages compared to other systems.
this will allow the parser to be integrated in typed racket's programs
add & operator, that is equivalent to !!
&a == ! (! a)
so, if a matchs, !a fails without consume, and !(!a) match, again, without consumes.
Is just a syntatic sugar but make easy write intersection of languages
#lang peg
(define (f l)
(match
[(list a b) a]
[(list a) (list a 1)]))
a <- 'a' ;
This file don't work because we only support (
and don't support [
but [
is normal in racket code
Is there any way we can support (require peg)
as well as the #lang peg
, instead of being forced to do (require peg/peg)
?
I'm not allowed to put [n] in a charclass. fix this.
Currently the system only really works with ASCII. We should support full Unicode. This may be difficult, but here is an issue for it.
the optional operator (?) is not fundamental. He can be written using "or" in the way on title.
If we do that, as we do when add the (&) operator, in a future when a feature must be added, will be less code to alter, less tests to do.
It would be useful to be able to declare a grammar which extends an existing one with new alternatives for a rule, e.g. something like:
expr.rkt:
#lang peg
program <- expr;
expr <- sum;
sum <- (a:product op:('+' / '-') b:sum) / x:product ->
(if x x (list (string->symbol op) a b));
product <- (a:value op:('*' / '/') b:product) / x:value ->
(if x x (list (string->symbol op) a b));
value <- x:number / '(' x:expr ')' -> x;
number <- n:[0-9]+ -> (string->number n);
enhanced-expr.rkt:
#lang peg
(require "expr.rkt");
program <- expr;
value <- 'sqrt(' e:expr ')' -> (list sqrt e);
and then have the REPL behave like
Welcome to Racket v7.4.
> (require "enhanced-expr.rkt")
> (require peg)
> (peg program "1+sqrt(16)")
'(+ 1 (#<procedure:sqrt> 16))
I hope the example is clear enough to express the problem I'm facing. Ideally, I'd like to have a way of adding new alternatives to rules defined in another source file, or to override them and have the ability to access the original alternatives to keep them available.
I'm very new to Racket and I apologize if this isn't a limitation of racket-peg
but of the Racket module system and I'm open to any workaround suggestion. I think I understand why it's not working this way - definitions in a module have nothing to do with definitions in require
d modules, which keep their original bindings - however I have no idea how to workaround the issue. Maybe there is some alternative to require
which "embeds" the specified module in the current one and has some policy for definition overrides?
#lang peg
(struct add (a b) #:transparent);
(define (my-sort lst #:comparator [cmp <])
(sort lst cmp))
Any of this lines works. In parser level we need to add support to keywords.
We will need a primitive that either:
that allows us to easily include s-expressions inside PEG grammars.
(A) would depend on #2
perhaps (B) is the better option though. Even though we have to "re"implement s-expr parsing, it would blend more seamlessly with the rest of the peg parsing system.
In peg.scribble @subsection{define-peg}:
Change 'capture' with 'name'
bad: (code:line (capture name <rule> ))
good: (code:line (name nm <rule>))
phase out the sexp-to-scheme.rkt
file completely.
We would like //
comments.
To study how to resolv #6 I try extend peg-in-peg but the peg don't accept itself
#lang peg
nt-char <- [a-zA-Z0-9_\-] ;
nonterminal <-- nt-char+ !nt-char SP ;
SP < [ \t\n]* ;
literal <-- SQ (BS ['\\] / !['\\] .)* SQ SP ;
SQ < ['] ;
BS < [\\] ;
charclass <-- LB '^'? (cc-range / cc-escape / cc-single)+ RB SP ;
cc-range <-- cc-char DASH cc-char ;
cc-escape <-- BS . ;
cc-single <-- cc-char ;
cc-char <- !cc-escape-char . ;
cc-escape-char <- '[' / ']' / '-' / '^' / '\\' / 'n' / 't' ;
LB < '[' ;
RB < ']' ;
DASH < '-' ;
peg <-- SP grammar+ ;
grammar <-- (nonterminal ('<--' / '<-' / '<') SP pattern) ';' SP ;
pattern <-- alternative (SLASH SP alternative)* ;
alternative <-- expression+ ;
expression <-- [!]? SP primary ([*+?] SP)? ;
primary <-- '(' SP pattern ')' SP / '.' SP / literal / charclass / nonterminal ;
SLASH < '/' ;"
DRRACKET TERMINAL
(peg peg "nt-char <- [a-zA-Z0-9_\-] ;
nonterminal <-- nt-char+ !nt-char SP ;
SP < [ \t\n]* ;
literal <-- SQ (BS ['\\] / !['\\] .)* SQ SP ;
SQ < ['] ;
BS < [\\] ;
charclass <-- LB '^'? (cc-range / cc-escape / cc-single)+ RB SP ;
cc-range <-- cc-char DASH cc-char ;
cc-escape <-- BS . ;
cc-single <-- cc-char ;
cc-char <- !cc-escape-char . ;
cc-escape-char <- '[' / ']' / '-' / '^' / '\\' / 'n' / 't' ;
LB < '[' ;
RB < ']' ;
DASH < '-' ;
peg <-- SP grammar+ ;
grammar <-- (nonterminal ('<--' / '<-' / '<') SP pattern) ';' SP ;
pattern <-- alternative (SLASH SP alternative)* ;
alternative <-- expression+ ;
expression <-- [!]? SP primary ([*+?] SP)? ;
primary <-- '(' SP pattern ')' SP / '.' SP / literal / charclass / nonterminal ;
SLASH < '/' ;
")
OUTPUT
read: unknown escape sequence - in string
Hi,
I note that the library is released under GPLv3. Is it possible relicensing under LGPLv3+ so it can be used in other projects without forcing them to become GPL projects?
In case of affirmative answer, let me know, that I will create a pull request with correct headers on all source-files, and a clarification of the license in the README, following the GNU guidelines.
Otherwise if the GPL license was chosen deliberately, it is obviously 100% fair, i.e. it is your work! :-)
Many thanks in any case,
Massimo
cannot make info.rkt right for the racket pkg page.
We need an import feature like this:
import name1.rkt ;
import name2.rkt ;
import name3.rkt ;
rule1 <- .. ;
rule2 <- .. ;
To be able to split parsers up into multiple files, and also to import supporting functions for semantic actions.
https://www.youtube.com/watch?v=4QrZxfgZFDg
This is a very future function.
With this, will be possible to parse declaratively and easyly all of C, python and other syntax-ambiguous languages.
For porting define-for-syntax
consider:
(eval-when (expand load eval) (define (gen-id xxx) ...))
define those functions in a separate library and do (import (for (helper-library) expand run))
What's the easiest way to understand the peg syntax? I saw https://docs.racket-lang.org/peg/index.html#%28part._.P.E.G_.Syntax_.Reference%29 . Is there some additional reference material one should review? Thx
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.