LL (1) -Parsing-Tabelle der linksrekursiven Grammatik

  • Ich habe einen Compilerkurs von Stanford auf Coursera absolviert. Ich habe ein leichtes Missverständnis in der Parsing-Tabelle der folgenden Grammatik:

    S - & gt; Sa | b

    Laut der Professorentabelle sieht die Parsing-Tabelle folgendermaßen aus:

    • Wenn das äußerste linke Nichtterminal ist S und die Eingabe ist 'a', die Produktion ist nichts.

    • Wenn das äußerste linke Ende S ist und die Eingabe 'b' ist, ist die Produktion beides Sa und b.

    Wenn die Eingabe nur b ist, dann ist es richtig, es geht direkt zur Produktion b. Aber wie wird die Produktion Sa für die Eingabe b gehen?

    23 January 2014
    Raphael
2 answers
  • Es scheint, als hätten Sie Ihren Professor missverstanden. "Wenn das äußerste linke Ende S ist und die Eingabe 'b' ist, ist die Produktion sowohl Sa als auch b." bedeutet, dass sowohl Sa als auch b richtige Antworten sind, wenn das äußerste linke Ende S ist und die Eingabe 'b' ist. Das bedeutet, dass der Parser nicht weiß, an welche Produktion er gelangen soll, und steckt fest.

    Dies bedeutet, dass diese Grammatik mit dieser Parsertechnologie nicht analysiert werden kann. Sie müssen entweder die Grammatik ändern oder einen anderen Parser verwenden.

    07 October 2012
    Justin Standard
  • Diese Sprache ist Linksrekursion. Wenn Sie versuchen, die erste Produktion abzuleiten, erhalten Sie eine Art Endlosschleife $ S \ Rightarrow Sa \ Rightarrow Saa \ Rightarrow Saaa ... \ rightarrow Saaa ... aaa $ Es kann also nicht mit LL (1) analysiert werden. Wie @Alex ten Brink sagte, sollten Sie die Grammatik ändern.

    05 December 2013
    DucCuong