41–50 of 87 posts
Thanks for building this, I completed the "make a lisp" project, but the parsing stage was greatly simplified so it is nice to have a resource to learn more about the parsing/lexing stage.
Does anyone know if there are any good resources on "tolerant parsing," if that is the correct terminology? For example, when I write C# in Visual Studio, the IDE remains amazingly helpful even when the code is incomplete and would be rejected by a traditional parser. I'd guess that Microsoft simply has the budget to have the VS/C# dev teams grind out hundreds or thousands of special cases that are specific to C#...…
Does anyone know if there are any good resources on "tolerant parsing," if that is the correct terminology? For example, when I write C# in Visual Studio, the IDE remains amazingly helpful even when the code is incomplete and would be rejected by a traditional parser. I'd guess that Microsoft simply has the budget to have the VS/C# dev teams grind out hundreds or thousands of special cases that are specific to C#...…
For example, a language with a C-like syntax, you'll often be parsing a sequence of statements separated by semi-colons (a block). If a statement fails to parse, you can just consume tokens until you hit the next semi-colon and then try to continue to parse statements from there.
Fairly crude approaches like this are easy to implement (at least with recursive-descent) but can be surprisingly effective. It's easy to construct counter examples where an approach like this will get it wrong but in practice it's hugely more useful to the poor user than just abandoning the parse completely.
Earlier quoted context omitted.
Parsing with derivatives is not all that slow: https://www.microsoft.com/en-us/research/uploads/prod/2019/0... The paper shows that it can compete with re2 (by google).
This is not what I'm talking about. "Parsing with Derivatives" is the title of a 2011 paper by Matt Might, David Darais, and Daniel Spiewak that generalizes the Brzozowski derivative from regular expressions to context-free grammars. In the present discussion, I assumed the context to be about CFGs instead of REs because that is most often what people are referring to when we talk about parsers in programming languag…
[1] https://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf
For example, consider addition and subtraction in most grammars. They can be expressed as "summation ::= factor ((PLUS | MINUS) factor) * " and factor can be similarly defined as "factor ::= multiplicand ((MUL | DIV) multiplicand) * ".
Authors of PTAPG note that these regularities can be exploited for speed. And I think "parsing with derivatives" techniques can be used for speedy parsing too.
Does anyone know if there are any good resources on "tolerant parsing," if that is the correct terminology? For example, when I write C# in Visual Studio, the IDE remains amazingly helpful even when the code is incomplete and would be rejected by a traditional parser. I'd guess that Microsoft simply has the budget to have the VS/C# dev teams grind out hundreds or thousands of special cases that are specific to C#...…
I'd like to see something like this for practitioners. I kind of have a feel for what's out there, but I don't know of anything that is: 1. pleasant to use 2. simple 3. scannerless 4. supports left recursion that produces a left-associative parse
Earlier quoted context omitted.
This is not what I'm talking about. "Parsing with Derivatives" is the title of a 2011 paper by Matt Might, David Darais, and Daniel Spiewak that generalizes the Brzozowski derivative from regular expressions to context-free grammars. In the present discussion, I assumed the context to be about CFGs instead of REs because that is most often what people are referring to when we talk about parsers in programming languag…
According to "Parsing Techniques: A Practical Guide" [1], it is quite common for computer languages to have most of the grammar in the regular grammars class and some parts to be, actually, context-free. [1] https://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf For example, consider addition and subtraction in most grammars. They can be expressed as "summation ::= factor ((PLUS | MINUS) factor) * " and factor ca…
If you talk to parsing people about "parsing with derivatives", they will undoubtedly assume that you specifically mean the Might et al work and not some other, more general notion, regardless of whether one could technically call such notion a "parsing with derivatives" technique. I have never heard of anybody calling anything else "parsing with derivatives" and, indeed, the paper you linked never uses this phrase (the closest they come is "matching with derivatives", which is a bit different in semantics).
I appreciate the points you've raised, and I do think the RE-parsing paper you linked previously looks very interesting (I hadn't seen it before), but the crux of the issue is that you misinterpreted what I said and haven't yet acknowledged that misinterpretation. Instead, it feels like you're trying to fight me on other points to win back some ground or something, though I hope I'm just misreading this because I find that kind of a frustrating conversational method.
This is great! I'm working on designing a language right now and I'm just getting to the point where I have to parse the AST. Looking forward to taking this course, I just purchased it on Udemy.
Enjoy