Re: Extended context-free grammar

Dirk Thierbach wrote:
- If there are productions "S ::= x' T A", "T ::= x U B" and
"U ::= u C", then add a production "S ::= "u C B A".

This is a very interesting approach, one I hadn't considered.
But, it doesn't look like it is guaranteed to terminate. For
example, if the original grammar is
S ::= x' T A
T ::= x U B
U ::= x' T
then it looks like we get into an infinite loop, if I understand
your transformation rules correctly. First we add the production
S ::= x' T B A
then we add the production
S ::= x' T B B A
and then
S ::= x' T B B B A
and so on ad infinitum. It may be that this kind of case can be
detected and avoided; I don't know yet. Thanks for pointing out
the potential relevance of Greibach normal form -- that seems
promising and worthy of further examination.
.

Relevant Pages

  • Re: Terminating A LispWorks Evaluation
    ... Gary Brown wrote: ... > How do you terminate an interactive LispWorks evaluation? ... > and then I cause an infinite loop but can't stop it without exiting. ...
    (comp.lang.lisp)
  • Re: Terminating A LispWorks Evaluation
    ... Gary Brown wrote: ... > How do you terminate an interactive LispWorks evaluation? ... > and then I cause an infinite loop but can't stop it without exiting. ...
    (comp.lang.lisp)
  • Re: Terminating A LispWorks Evaluation
    ... >> How do you terminate an interactive LispWorks evaluation? ... >> and then I cause an infinite loop but can't stop it without exiting. ...
    (comp.lang.lisp)
  • Stuck in an infinite loop
    ... I constantly come across cases when I have to terminate a running ... script file, because it enters an infinite loop. ... Prev by Date: ...
    (comp.soft-sys.matlab)
  • Re: Computing Follow set
    ... From the production B -> bA, ... This ends up being an infinite loop when I code it. ... repeatedly recalculate them, until they stop growing. ...
    (comp.compilers)