Re: How detect cycle in grammar ?

On 21 Lis, 19:20, Gene <gene.ress...@gmail.com> wrote:
> 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.


How works it algorithm, as I see:
- We have two marks, one for rules one for nonterminals
- Mark rule when all on the right is termianal or marked nontermianal
- Mark nonterminal only when all its rules is marked? (what when we
remove rule?)
A->A
A->B
B->b
We start from last rule. Mark B because all rhs ale terminal (b) and
mark rule "B->b"
as accessible.
A->B - right side all are marked, A not marked yet because has more
than one rule
A->B - rule not marked

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