strong LL(k) grammars

This is a discussion on strong LL(k) grammars within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Just a quickie: I know exactly what an LL(k) parser and grammar is, so that does not need any clarification. ...

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

    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
    Location
    Göteborg, Sweden
    Posts
    2,072
    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 Cprogramming.com
    Replies: 21
    Last Post: 03-01-2004, 07:31 PM
  2. 10,000 strong
    By Govtcheez in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 02-06-2002, 09:41 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21