Thread: strong LL(k) grammars

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Plano, Texas, United States

    strong LL(k) grammars

    Just a quickie:

    I know exactly what an LL(k) parser and grammar is, so that does not need any clarification.

    However, I cannot understand the difference between an LL(k) grammar and a strong LL(k) grammar.

    Can anyone explain that difference?

    The textbook explains it like this:

    Let G = ( V, sigma, P, S ) be a context-free grammar with endmarker #^k. G is strong LL(k) if whenever there are two leftmost derivations:

    S ->* u1 A v1 -> u1 x v1 ->* u1 z w1

    s ->* u2 A v2 -> u2 y v2 ->* u2 z w2

    where ui, wi, z are elements of sigma* and length(z) = k, then x = y.
    What I understand from that (tell me if I am right or wrong): A strong LL(k) grammar is an LL(k) grammar that can derive a specific input string in 2 different ways and come out with the same result.

    If that is true, why would that be, and why would it be called so? It almost seems to me that it would be more weak than strong.
    My Website

    "Circular logic is good because it is."

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Göteborg, Sweden
    Based on the textbook, isn't "strong" exactly the opposite of what you said?
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Strong Paranoia
    By ZakkWylde969 in forum A Brief History of
    Replies: 21
    Last Post: 03-01-2004, 07:31 PM
  2. 10,000 strong
    By Govtcheez in forum A Brief History of
    Replies: 3
    Last Post: 02-06-2002, 09:41 PM