How to determine maximum stack size of LL(1) parser?

Question

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.

Answer 1

OK. So you have a pushdown automaton, and out of all reachable stack configurations, you want to know the stack depth (length) of the longest such configuration.

I have two answers: a simple, practical answer that might suffice for your specific situation but doesn't scale, and a general answer that will apply more broadly.

Simple answer

Enumerate all possible stack configurations. This should be easy. Just think of this as a giant graph, with one vertex per reachable stack configuration, and an edge from each such stack configuration to every other configuration that is reachable in a single step. Now use any graph exploration algorithm, such as DFS, to explore the graph. Out of all the configurations you visit, keep track of which one had the largest stack depth.

You have 5 nonterminals. If the maximum stack depth is $9$, there will be at most $5^9$ reachable stack configurations, i.e., about 2 million of them. It's easy to explore all such configurations and store them all in a simple data structure.

Of course this would not scale to larger cases, as the complexity is exponential.

General solution

The set of reachable stack configurations of a pushdown automaton is regular. Therefore, you can build a DFA that concisely represents all such reachable stack configurations. This DFA is not too large (linear in the size of the PDA, I think) and can be built efficiently (in quadratic or cubic time, I think). Then, you can check whether the DFA has any cycles and the length of the longest path in the DFA, and that will tell you the stack depth of the deepest reachable stack configuration.

This will give you an efficient, polynomial-time algorithm that scales even to large, non-trivial grammars. The cost is that it takes more work to understand the algorithms and implement them correctly, so I'd try the simple solution above first, and only fall back to this if necessary.

Answer 2

Not sure if this is the correct answer, but I quickly crafted the following algorithm in Python:

crlf, onespace, httpname, slash, digit, colon, optspace = range(0,7)
httptoken, httpfield, period, uri, foldstart = range(7,12)

terminals = [crlf, onespace, httpname, slash, digit, colon, optspace,
             httptoken, httpfield, period, uri, foldstart]

headerField, version, requestLine, requestHdrs, requestWithHdrs = range(20,25)

rules = [(headerField, [foldstart, httpfield]), 
         (headerField, [httptoken, colon, optspace, httpfield]),
         (version, [httpname, slash, digit, period, digit]),
         (requestLine, [httptoken, onespace, uri, onespace, version, crlf]),
         (requestHdrs, []),
         (requestHdrs, [headerField, crlf, requestHdrs]),
         (requestWithHdrs, [requestLine, requestHdrs, crlf])]

max_stacks = {}
changed = True
for a in terminals:
  max_stacks[a] = 1
while changed:
  changed = False
  for rule in rules:
    lhs, rhs = rule
    cursz = 0 
    if len(rhs) > 0: 
      cursz = len(rhs) - 1 + max_stacks[rhs[0]]
    if lhs not in max_stacks or max_stacks[lhs] < cursz:
      changed = True
      max_stacks[lhs] = cursz
print 1 + max_stacks[requestWithHdrs]

Note the 1 + which takes into account the special endOfFile indicator.

It prints 9, although I'm not 100% confident that I got the algorithm correctly.

Edit: the algorithm might be incorrect, now I assume the following would be the correct algorithm, it also prints 9:

max_stacks = {}
changed = True
for a in terminals:
  max_stacks[a] = 1
while changed:
  changed = False
  for rule in rules:
    lhs = rule[0]
    rhs = list(rule[1])
    cursz = len(rhs)
    while len(rhs) > 0:
      tmpsz = len(rhs) - 1 + max_stacks.setdefault(rhs[0], 0)
      del rhs[0]
      if tmpsz > cursz:
        cursz = tmpsz
    if lhs not in max_stacks or max_stacks[lhs] < cursz:
      changed = True
      max_stacks[lhs] = cursz

Edit again, I implemented D.W.'s algorithm:

def get_max_sz_dfs(Tt, rules, terminals, S, eof=object()):
  visiteds = set()
  maxvisited = 0
  # in case somebody uses without EOF symbol:
  initial = (eof is None) and (S,) or (eof, S)
  visitqueue = []
  visitqueue.append(initial)
  while visitqueue:
    current = visitqueue.pop()
    visiteds.add(current)
    if len(current) > maxvisited:
      maxvisited = len(current)
    last = current[-1]
    if last in terminals:
      if current[:-1] not in visiteds:
        visitqueue.append(current[:-1])
      continue
    if last == eof:
      continue
    A = last
    for a in terminals:
      if Tt[A][a] != None:
        rule = rules[Tt[A][a]]
        rhs = rule[1]
        newtuple = current[:-1] + tuple(reversed(rhs))
        if newtuple not in visiteds:
          visitqueue.append(newtuple)
  return maxvisited

S is the start token, Tt[A][a] tells which rule to use for state A and terminal a, i.e. it's the parser state transition table. terminals is the list of terminals, and rules is the list of rules in the format above.

If you're reading this, please ignore my two first attempts and use the algorithm suggested by D.W.