Re: How detect cycle in grammar ?

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.

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