Re:Writing Your Own Programming Language
by btilly on Thursday November 10, 2016 @12:11PM
(#12922156)
Don't you mean an NFA?
If there is an ambiguity in the grammar that takes some time to resolve, a recursive descent parser can easily take exponential time. What tail call elimination does is keep you from having a giant call stack, but does not fix the potential (though rare) performance disaster.
Re:Writing Your Own Programming Language
by kd0amg on Thursday November 10, 2016 @01:40PM
(#12922977)
Yes, NFA! DFA only if it's LL(1).
Re:Writing Your Own Programming Language
by greenshackle2 on Thursday November 10, 2016 @11:38AM
(#12921892)
Right, with the syntax I chose there ends up being, IIRC, 6 different forms (<op>, <op> <arg1>, etc.), which can't be nested. Some of those forms share patterns which could be described as a nested grammar, but I just abstracted them in the parser code as functions (i.e. functions to parse patterns that show up in multiple forms).
I did use a lexer. I wrote an assembler before without using a lexer; using the lexer isn't that much simpler IMO, but it makes it more robust and makes it much easier to systematically catch syntax errors and produce meaningful errors.
Re:Writing Your Own Programming Language
by ejanus on Thursday November 10, 2016 @12:25PM
(#12922299)
Is regular grammar same as context-free grammar?
Re:Writing Your Own Programming Language
by oldmanhorton on Thursday November 10, 2016 @02:10PM
(#12923238)
It is not - see https://en.wikipedia.org/wiki/Chomsky_hierarchy for the where these terms come from. Context-free grammars are strict supersets of regular grammars and cover the vast majority of programming language constructs.
Presumably because there's no real nesting of terms in assembly code? Personally, I find BNF so simple that I'd probably still use it for describing the grammar, but lots of parser generator technology is heavier machinery than required (though a recursive descent parser built from a regular grammar is essentially a DFA if your language/compiler offers tail call elimination).