I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be nested.
For parsing those files I am required to use a handcrafted parser written in C++. More specifically, I need to extend the given parser and lexer base classes in order to specify the language. Unfortunately, I have some serious doubts about the theoretical fundamentals behind these classes, which I would like to discuss/clarify here. So, let me first give a little introduction to the architecture of all this (note that unfortunately I am not allowed to post any code here, but I don't think it's necessary anyway) - see also TL;DR below.
(Disclaimer: I would like to add upfront that after working with regular expression libraries (nowadays simply standard C++) and parser generators like ANTLR I am not at all a fan of this handcrafted solution and therefore my view might be a littled biased. I admit that I am neither a formal language specialist, nor have I dealt with any serious theoretical computer science topics beyond undergraduate level, and that itself has been a while. Still I am quite sure that the "parser" that I have to use is less than suboptimal and I doubt that it's even a parser in a "classical" sense)
Lexer:
As one would expect, the lexer tokenizes some input stream using an underlying (N)DFA, whose transitions are specified by the user in the derived class. This would be something like AddTransition(srcState, transition, dstState), where transition could be for example a string "keyword" -- a convenience function would then insert the respective transitions for each character 'k'->'e'->..., you get the point...
I find this solution rather cumbersome as it requires one to explicitely define the automaton for each token recognized by the lexer, sometimes urging me to draw automata on paper instead of simply writing it down as a regular expression that would work similarly (but would be way easier to express). Not to mention EOL, EOF issues that need to be taken care of in each case.
But so far, I think the lexer does what a lexer is supposed to do: It recognizes a regular language defined by the user and tokenizes it to be passed to the parser.
Parser:
The parser has a far more uncommon structure, at least from my point of view. As a layman, I would expect a parser to be implemented using some sort of $LL(k)$, $LR$, $LALR$, ... structure for reading in the tokens provided by the lexer and that generates a parse tree which can then be further processed. Most importantly, I would expect a typical parser to be able to recognize context-free languages by using some sort of pushdown automaton (PDA) implementation or the like (please correct me if I'm wrong).
Instead, the parser is based on the same structure as the lexer, that is, it uses a NDFA whose transitions are defined by the user. The complexity is even worse than with the lexer class, sometimes requiring the user to manually define hundreds of states and transitions, which easily lead to hard-to-spot bugs. For example, very simple differences in the parsed code like blah { vs. blah{ can lead to problems if transitions were not correctly defined. There are unit tests for these cases, but for some "technical" reasons for each grammatical rule with the similar underlying structure (e.g. to recognize foo {...} vs. bar {...}) the transitions need to be rewritten, therefore it's not enough to simply write and test if some construct <keyword> { <content> } works, but rather for each instance of <keyword> and <content> tests must be written. Of course, same applies to changes in the underlying grammar. Think of all the EOF, EOL etc. issues mentioned above - a nightmare!
But my main issue with this parser is the theoretical foundations it is built upon. It is supposed to read in languages which allow nested scopes surrounded by brackets (from my humble perspective, that's at least a context-free language). But the parser is built around a NDFA and as far as I know by the Pumping Lemma this is already an issue. In order to overcome the NDFA limitations, every automaton state may be assigned a callback function. For the states in question, these callbacks implement something like a bracket counter. For example, whenever a state for an opening bracket is reached, the counter is incremented and for a closing bracket, it is decremented accordingly.
This works fine so far, but wouldn't that already be a PDA rather than a DFA? I'm asking because the author insists on saying that the parser still has a pure NDFA structure and that it is a common misconception that NDFAs can't read nested structures, because that would only apply if one was going to have infinitely deep nesting. I admit I don't have too many arguments to argue that this is wrong, yet I find this statement very questionable, also because I've never seen any parsers in the wild which are implemented that way.
TL;DR
I have strong doubts that a parser which uses a simple (non-deterministic) Finite Automaton is suitable to parse languages with nested structures, assignments, variable definitions etc.. Since it doesn't apply any of the concepts commonly known from parsers (syntax trees, $LL$, $LR$ and their ilk) and simply uses callbacks to perform some action when reaching a state, I wonder if the term "parser" is correct at all. To me it seems more like a lexer on a higher level with lots of extensions to cope with corner cases.
But what puzzles me the most is that so far it seems to work fine, despite all the manual effort required to define states and transitions (leave aside the code duplication issues etc.). Therefore I wonder if there is maybe a strong misconception from my side?
Where does one draw the line between DFAs and PDAs (wrt. implementation)? To me, the NDFA combined with the bracket counter (which in theory can be seen as a stack) works more like a PDA.
Can the construct explained above be really called a "parser"? The term "parser" is used so naturally in combination with ASTs, CFGs and $LL$, $LR$ etc. that I wasn't able to find any discussions on that topic in the internet. Feel free to ask in case I need to clarify something (I admit it's hard to explain as a non-native speaker and also without being able to show code).
