I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by the LL(1) parser generator.
In case somebody asks, yes, it's possible to parse plaintext HTTP using LL(1) parser, if the parser works together with the lexer, so that the parser automatically turns on and off tokens in the lexer. So, only those tokens that are valid in the context are matched in the deterministic finite automaton (DFA).
The particular grammar I'm using for my tests is this (yes, I know it's possible to fold the first header line incorrectly using the grammar, I'll fix this later):
headerField -> foldstart httpfield
headerField -> httptoken colon optspace httpfield
httpVersion -> httpname slash digit period digit
requestLine -> httptoken onespace uri onespace httpVersion crlf
requestHdrs -> (epsilon)
requestHdrs -> headerField crlf requestHdrs
requestWithHeaders -> requestLine requestHdrs crlf
The start nonterminal is requestWithHeaders
. The terminals are:
crlf, onespace, httpname, slash, digit, colon, optspace
httptoken, httpfield, period, uri, foldstart
...so every name that is lowercase only is terminal, and if there are uppercase characters in the middle, it's nonterminal.
Now, if I start using the stack [(endOfFile), requestWithHeaders]
, the maximum stack size is ever going to be 9 according to my tests. So, this grammar appears to have a maximum stack size.
The question is: how to prove the maximum stack size? I'm looking for an algorithm that terminates and gives me the answer 9
for this grammar. The algorithm need not terminate for a grammar that doesn't have a maximum stack size, so infinite recursion and infinite loops are permitted if the maximum stack size doesn't exist. (I can always limit the amount of CPU time given to the algorithm.)
I already have the code to calculate first-sets and follow-sets, and the code to generate the parser table, and the code to execute the parser using the parser table, so I'm not looking for advice for standard LL(1) parser implementation. I have already tested my parser with valid and invalid HTTP examples, and everything seems to work just fine.
The reason I'd like to determine this maximum stack size is that I want to avoid dynamic memory allocation in the parser. There is no need to allocate memory dynamically for cases where there is an upper bound for the stack size.