Ist diese Grammatik mehrdeutig?

  • Ich habe die Grammatik:

    $ \ qquad \ begin {align} S & amp; \ bis S = P \ mid S \ neq P \ mid P \\ P & amp; \ bis NUM \ end {align} $

    Diese Grammatik leidet an linker Rekursion. Um die linke Rekursion zu beseitigen, habe ich:

    $ \ qquad \ begin {align} S & amp; \ zu PS '\\ S' & amp; \ zu \, = PS '\ mid \, \ neq PS' \ mid \ varepsilon \\ P & amp; \ bis NUM \ end {align} $

    Beim Erstellen der LL (1) -Parsing-Tabelle stellt sich jedoch heraus, dass die Grammatik mehrdeutig ist. Gibt es eine Möglichkeit, die Grammatik zu unterscheiden, ohne die generierte Sprache zu ändern, oder habe ich irgendwo einen Fehler gemacht?

    Dies ist meine bisherige Arbeit:

     Non-terminal Nullable First            Follow
    S            False    NUM              $
        S'           True     !=, ==, epsilon  $
    P            False    NUM              $, ==, !=
    
    Parse Table
         !=       ==    NUM      $
    S                   ->PS'
    S'  ->!=PS'  ->==PS'        ->epsilon
    P                   ->NUM
     
    18 July 2012
    Raphael
1 answer
  • Wir können $ NUM $ und damit $ P $ ein Terminalsymbol betrachten. Außerdem kommt $ S $ in jeder Ableitung nur einmal vor. Wenn also Unklarheiten bestehen, muss dies von

    $ \ qquad \ displaystyle S '\ nach \, = PS' \ mid \, \ neq PS '\ mid herrühren \ varepsilon $

    Nun ist dieses Fragment ein rechts-regulär Grammatik mit nur einem Nichtterminal, dessen rechte Seite keine Präfixe hat. Jeder Begriff hat also nur eine Ableitung, die sich aus Länge und Permutation von $ = $ und $ \ neq $ ergibt.

    Ihre Grammatik ist insgesamt eindeutig. Die obigen Beobachtungen legen auch nahe, dass die Grammatik in einem Durchgang von links nach rechts mit einem Token-Lookahead analysiert werden kann (unterscheiden Sie $ = $ und $ \ neq $). Tatsächlich ist die Grammatik im Grunde eine deterministische (keine gemeinsamen Präfixe) und eine rechts-reguläre (alle $ P $ durch $ NUM $ ersetzen) Grammatik, daher ist es sicherlich eine LL (1) -Grammatik.

    Ich schlage daher vor, die Konstruktion der Parsing-Tabelle erneut zu betrachten (Ihr bevorzugtes Lehrbuch oder Wikipedia ) - Sie müssen einen Fehler gemacht haben.

    18 July 2012
    Raphael