Comments (3)
Your expression grammar is what is referred to as left-recursive because of this bit:
let expression = recursive(|expression| {
let logic = expression
.clone()
.then(choice((
just("==").to(LogicOperator::Equal),
just("!=").to(LogicOperator::NotEqual),
just(">").to(LogicOperator::Greater),
just("<").to(LogicOperator::Less),
just(">=").to(LogicOperator::GreaterOrEqual),
just("<=").to(LogicOperator::LessOrEqual),
just("&&").to(LogicOperator::And),
just("||").to(LogicOperator::Or),
)))
.padded()
.then(expression)
.map(|((left, operator), right)| {
Expression::Logic(Box::new(Logic {
left,
operator,
right,
}))
});
let value = value.map(|value| Expression::Value(value));
choice((logic, value))
});
You have defined an expression as this:
expression := expression op expression
| value
In order to parse an expression, we have to parse an expression… and to do this we have to parse an expression… and to do this we have to parse an expression.
A weakness of parser combinators (or recursive descent parsers in general) is that they aren’t suited to handle left recursion. When they encounter it, they blow the stack because they don’t know when to stop trying to parse the left hand side.
There are many ways to solve this problem, such as either precedence climbing or pratt parsing (described here). Chumsky has built-in support for pratt parsing using the pratt
feature!
To see how to use it, check out the documentation, which has an example for you.
from chumsky.
We did previously attempt to add a panic for this case, but it ended up producing false positives when used in combination with memoisation. I'd like to resurrect attempts at solving that at some point.
from chumsky.
Thank you for the quick response. I was able to get the pratt parser working.
let value_expression = value.map(|value| Expression::Value(value));
let logic_expression = value_expression.pratt((
infix(left(1), operator("=="), |left, right| {
Expression::Logic(Box::new(Logic::Equal(left, right)))
}),
infix(left(1), operator("!="), |left, right| {
Expression::Logic(Box::new(Logic::NotEqual(left, right)))
}),
infix(left(1), operator(">"), |left, right| {
Expression::Logic(Box::new(Logic::Greater(left, right)))
}),
infix(left(1), operator("<"), |left, right| {
Expression::Logic(Box::new(Logic::Less(left, right)))
}),
infix(left(1), operator(">="), |left, right| {
Expression::Logic(Box::new(Logic::GreaterOrEqual(left, right)))
}),
infix(left(1), operator("<="), |left, right| {
Expression::Logic(Box::new(Logic::LessOrEqual(left, right)))
}),
infix(left(1), operator("&&"), |left, right| {
Expression::Logic(Box::new(Logic::And(left, right)))
}),
infix(left(1), operator("||"), |left, right| {
Expression::Logic(Box::new(Logic::Or(left, right)))
}),
));
It would be cool if there were some warning about this when using recursive
since it's so easy to make an infinite loop. I'm not sure if that's possible but it would be nice.
from chumsky.
Related Issues (20)
- `/examples/foo.rs` is different from the tutorial HOT 1
- Ability to create warnings HOT 2
- `vars` gets not correctly truncated in example code HOT 1
- error: "unknown feature stdsimd" cause by the dependency of ahash when update rustc to 1.78.0-nightly HOT 2
- Cannot ignore whitespace without changing the width of the span HOT 3
- Cannot use custom span type with Stream HOT 3
- `skip_until` is consuming the `until` HOT 6
- Strange padding issue? HOT 1
- WebAssembly build error HOT 6
- MapExtra cannot infer state type HOT 1
- How to debug and see the parsing process trace of chumsky combinators. HOT 2
- Combine `then` and `or_not` preventing extraneous backtracking HOT 1
- Labels don't show unless the EOI is in it's place HOT 2
- no method named `to_slice` found for opaque type `impl Parser<_, <_ as Character>::Collection, Error = _> + Copy + Clone` in the current scope HOT 3
- In big sequences of just's separated by or's, is it preferred to map the ouput every time or match at the end? HOT 2
- I'm upgrading to 1.0.0-alpha.7 I can't get the parser function signature right HOT 1
- docs.rs links to GH files appear broken HOT 1
- Stack overflow caused by defining an unused parser HOT 2
- Add a `spanned` method for automatically wrapping the parser result in a `Span`
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 chumsky.