4 ms·
I hesitated on using BNF. It seemed overkill Presumably because there's no real nesting of terms in assembly code? Personally, I find BNF so simple that I'd pr
by kd0amg 10y ago
I hesitated on using BNF. It seemed overkill
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).
- greenshackle2 10y agoRight, 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.
- btilly 10y agoDon'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.
- kd0amg 10y agoYes, NFA! DFA only if it's LL(1).
- deleted 10y ago[deleted]
- ejanus 10y agoIs regular grammar same as context-free grammar?
- oldmanhorton 10y agoIt is not - see https://en.wikipedia.org/wiki/Chomsky_hierarchy 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.