Question regarding complexity of grammar

Johann Neugebauer <mr.miller@gmx.at>
4 May 2007 13:22:44 -0400

          From comp.compilers

Related articles
Question regarding complexity of grammar mr.miller@gmx.at (Johann Neugebauer) (2007-05-04)
Re: Question regarding complexity of grammar cfc@shell01.TheWorld.com (Chris F Clark) (2007-05-06)
| List of all articles for this month |

From: Johann Neugebauer <mr.miller@gmx.at>
Newsgroups: comp.compilers
Date: 4 May 2007 13:22:44 -0400
Organization: Compilers Central
Keywords: parse, theory, question
Posted-Date: 04 May 2007 13:22:43 EDT

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.


Post a followup to this message

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