# Why can we (apparently) implement CFG parsers only using (N)DFAs?

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).

## migrated from cstheory.stackexchange.comApr 25 at 15:34

This question came from our site for theoretical computer scientists and researchers in related fields.

• A NFA with counter(s) is no longer an NFA, but a (multi-)counter automaton. Depending on the set of instructions allowed on the counter(s), they might recognise any recursive language, c.f. en.wikipedia.org/wiki/Register_machine. – Sylvain Apr 17 at 18:46
• Thanks @Sylvain. But my question is: What are the limitations of this particular parsing "technique"? Apparently, I can parse everything which I could parse with some CFG parser using a counter automation/(N)DFAs+counter (actually even more). What's the difference to a "parser" in the common sense? – andreee Apr 23 at 9:04
• Putting it differently: Looking at this list of parsers, there is no single parser algorithm that uses counter automatons/NFA with counters. Why is that, if it apparently seems to work? – andreee Apr 23 at 9:15
• @andreee, I've edited my answer to include a perspective on that latter question. – D.W. Apr 25 at 18:33
• Could you trim this down a bit? (Actually, a lot.) You've written two-and-a-half pages of text (at my browser settings) but, really, only the last two sections of the "parser" section are relevant. We don't need to know about your views about this library, or its lexer or that you're working in C++ or any of the other stuff. – David Richerby Apr 25 at 19:21

## 2 Answers

We can't answer questions about your specific codebase. In general: A NDFA, by definition, has no memory other than the state of the automaton. It sounds like your program has additional memory/variables/state (e.g., the counters updated by the callbacks), which means your program is not implementing a NDFA; it is doing something more. A DFA with multiple counters is Turing-complete if you can do some minimal operations on them; see, e.g., https://en.wikipedia.org/wiki/Counter_machine.

So why do we usually use parsers based on pushdown automata rather than counter automata? Because it is usually a nicer way to think about the problem. It's a very helpful abstraction to be able to write down the grammar of the language as a context-free grammar; that's natural and expressive and is easy to think about. Pragmatically, this decomposition of concerns (write down a declarative specification of the language as a context-free grammar; leave it up to someone else to construct a tool that turns this into a parsing implementation) has proven useful and powerful. In contrast, counter automata don't have those benefit. For instance, with an implementation based on counter automata, there is no separation of concerns between the spec and the implementation; the implementation is the spec.

• Thanks for your answer. I see that there is a lot of (maybe unnecessary) extra information in my question, however the problem stated here is not about the code base, but rather about the fundamentals of how parsers are built/defined. I wonder why there seems to be only the definition of a parser (transforming tokens into an AST wrt. a given CFG) and why the structure that I use works nonetheless (despite being rather inefficient). Where are the limitations (if any)? – andreee Apr 23 at 8:59

Deterministic finite automata (and nondeterministic) can only recognize regular languages. If the parser can recognize context-free grammars then it is not a DFA or NFA.

To recognize context-free grammars the model must be at least as "powerful" as pushdown automata.

It seems the codebase is complicated so this may have been inadvertently implemented (especially if there are counters and other state). If the parser truly is a finite automaton then there will be a way to break it. A pure finite automata will store nothing other than its current state.