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.


I found http://programming4.us/desktop/408.aspx section "4 Reduction
of Grammar"
I interpret this: we mark nonterminal as usable if any its production
contains only terminals or marked previously nonterminals.
But what if nonterminal has one using production and one useless? For
example
A->A
A->B
B->b
How eliminate A->A ?

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