Question regarding complexity of grammar

Hi everybody,
I have defined a simple grammar that I have built a parser for. It
allows the definition of nested sections:


[section]
{
  [subsection]
  {
    [subsubsection]
    {
      ...
    }
    [subsubsection]
    {
      ...
    }
  }
}


Any section may have an arbitrary amount of subsections, subsubsections
etc. First, I wonder if this simple grammar can be categorized in some
way, I have read that there are various types of grammars around that
can be parsed with different runtime complexity. This is exactly my
second question, I have already created a parser using Lex and Yacc. I
have defined tokens for all elements that are allowed within the
grammar. This is a recursive parser as I have only defined what a
section is and that a section may contain an arbitrary amount of
subsections. The parser works pretty fine but as I do not understand the
code that is produced by Lex/Yacc I wonder what runtime complexity this
parser has? Personally, I believe that it is O(n) but I am not quite
sure about that.

Return to the comp.compilers page.
Search the comp.compilers archives again.