Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #347

Re: How detect cycle in grammar ?

Show all headers | View raw

On Nov 20, 5:48 pm, Borneq <a.modera...@gmail.com> wrote:
> A->B
> B->B
> This grammar is not correct, B is looped.
>
> A->B
> B->C
> C->A
> This another grammar, cycle can be arbitrarily long.
> Is cycle when First(Nonterminal) not contain any terminal, even not
> epsilon?
>
> A->B
> B->   (=B->epsilon)
> in first A and B is epsilon

Cycles aren't the problem. You'll need cycles to represent lists and
nestings. Nonterminals that can never derive a terminal string are the
problem.

You should look up useless nonterminals in the Dragon Book or similar
reference.  This includes the algorithm for removing them from
grammars.

As I recall the algorithm starts with the lhs's of rules that expand
entirely to terminals (including epsilon) and recursively marks
nonterminals that have a rule where the entirely right hand side is
either marked or terminal.  When you're done marking in this manner,
the unmarked nonterminals are useless.  All rules involving them can
be deleted without changing the represented language.  If the start
symbol is unmarked, the language is empty.

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How detect cycle in grammar ? Borneq <a.moderacja@gmail.com> - 2011-11-20 08:48 -0800
  Re: How detect cycle in grammar ? Hans Aberg <haberg-news@telia.com> - 2011-11-21 18:14 +0100
  Re: How detect cycle in grammar ? Gene <gene.ressler@gmail.com> - 2011-11-21 10:20 -0800
    Re: How detect cycle in grammar ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-22 15:20 +0000
      Re: How detect cycle in grammar ? Quinn Tyler Jackson <quinn_jackson2004@yahoo.ca> - 2011-11-25 22:28 -0800
      Re: How detect cycle in grammar ? Gene <gene.ressler@gmail.com> - 2011-11-27 10:18 -0800
    Re: How detect cycle in grammar ? Borneq <a.moderacja@gmail.com> - 2011-11-23 12:56 -0800
    Re: How detect cycle in grammar ? Borneq <a.moderacja@gmail.com> - 2011-11-24 09:24 -0800
      Re: How detect cycle in grammar ? Gene <gene.ressler@gmail.com> - 2011-11-27 10:27 -0800
        Re: How detect cycle in grammar ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-28 16:46 +0000
          Re: How detect cycle in grammar ? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2011-11-29 07:31 +0000
            Re: How detect cycle in grammar ? Paul B Mann <paul@paulbmann.com> - 2011-12-01 02:46 -0800
              Re: How detect cycle in grammar ? Quinn Tyler Jackson <quinn_jackson2004@yahoo.ca> - 2011-12-02 09:20 -0800
          Re: How detect cycle in grammar ? Gene <gene.ressler@gmail.com> - 2011-12-07 06:29 -0800

csiph-web