Comments (2)
Actually, I think most of these cases have already been fixed.
There are basically two types of duplication:
- The same meta-variable used for more than one terminal or nonterminal.
- The same variable name used for more than one field in a production.
Your pull request #22 fixed the missing loop in the check-meta!
(thanks!) that ensures the metavariables are unique, and I believe the names used in productions have been checked for uniqueness correctly for a while.
In both cases you are correct that these are O(n^2) operations, though generally, these will be very short lists, and the overhead of the hash table is likely to overwhelm the benefit of its use.
That said, I've been thinking about using a prefix-trie implementation for the metavariables, where the prefix-trie would be stored as part of the language definition to use for lookup. The benefit to this is that we could allow for a wider variety of acceptable metavariable names and allow for some flexibility on the suffixes allowed, with the added benefit that lookup would be O(log(n)), instead of the current O(n), and we would effectively get uniqueness checking as part of the construction process for O(n log n). (As you note, not as cheap as a hash table, but I think the other benefits make it worth the cost in this case, though you may disagree.)
The other source of non-uniqueness in the language definitions currently is the productions themselves. There is actually a more serious bug hiding here than just duplication. Things with similar "shape" will also alias each other. For instance in the definition:
(define (operator? x) (memq x '(+ - *)))
(define-language L
(terminals
(symbol (x))
(fixnum (n))
(operator (op)))
(Program (prog)
(begin e* ... e))
(Expr (e)
(set! x0 x1)
(set! x0 n1)
(set! x0 (op x1 x2))
(set! x0 (op x1 n2))))
All of the set!
forms have the same "shape" being a list of three elements that starts with the set!
keyword. This is not checked, and nanopass framework will treat these as though they are all unique cases, but will generate code where both the parser and meta-parser will only ever match which ever of these comes first.
I think in these cases, it should, as you say, be using the types to help distinguish these. I've thought about trying to approach this using tree automata or something similar, but I've not spent the time to figure out exactly how to apply this, and I believe it will require rewriting the parser and meta-parser, but should put the code in a little bit better algorithmic class as well.
These are definitely on my todo list!
from nanopass-framework-scheme.
I have been thinking about combining this with something like Racket's PEG package and allowing passes to be defined on rules within that, which would avoid the shape related problem, but I'm not entirely sure of the feasibility of that idea.
from nanopass-framework-scheme.
Related Issues (20)
- Framework cannot handle languages with simple list of terminals HOT 2
- Terminal names not checked for uniqueness HOT 1
- Nonterminals can have multiple instances of the same production
- Add auto-generation of transformers when the output is the non-language (*)
- Add foldable transformers
- trace does not seem to work properly with multiple return values
- Using nanopass with non-Lispy source language. HOT 2
- not an issue
- Exception: meta not found HOT 3
- Allow wider variety of suffixes for meta-variables.
- trace-define-pass problem on cross compile HOT 3
- trace-define-pass should use current-error-port HOT 2
- Test Fails on Windows 10. HOT 1
- let example didn't work. HOT 2
- Could nanopass-framework-scheme be published on AKKU? HOT 1
- define-pass should work with a language with no nonterminals.
- Need a way to define passes that do not auto-generate transformers.
- Why no top-level cata if the full "in -> out" cata syntax is used? HOT 1
- Other documentation ideas: cheatsheet/table + gentle tutorial HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from nanopass-framework-scheme.