第十回LL(1)文法の判断、再帰的降下分析プログラム

3640 ワード

1.文法G(S):
(1)S -> AB
(2)A ->Da|ε
(3)B -> cC
(4)C -> aADC |ε
(5)D -> b|ε
文法G(S)がLL(1)文法であることを検証しますか?
解:
  Select(A -> Da) = First(Da) = {b,a}
  Select(A -> ε) = (Follow(ε)-{ε})∪Follow(A) = {b,a,c,ε}
  Select(C -> aADC) = First(aADC) = {a}
  Select(C -> ε) = (Follow(ε)-{ε})∪Follow(C) = {ε}
  Select(D -> b) = First(b) = {b}
  Select(D -> ε) = (Follow(ε)-{ε})∪Follow(D) = {a,ε}
  ∵Select(A -> Da) ∩ Select(A -> ε) ≠ ∅
⑪文法G(s)はLL(1)文法ではありません.
 
2.(前回作業)左再帰を消した後の式文法はLL(1)文法ですか?
解:
左再帰を削除すると、次のようになります.
  E -> TE'
  E' -> +TE' | ε
  T -> FT'
  T' -> *FT' | ε
  F -> (E) | i
SELECT(E' -> +TE') = FIRST(+TE') = {+}
SELECT(E' -> ε) = (FIRST(ε) - { ε }) U FOLLOW(E') = FOLLOW(E') = { ) , ε }
SELECT(T' -> *FT') = FRIST(*FT')={ * }
SELECT(T' -> ε) = (FIRST(ε) - { ε }) U FOLLOW(T') = FOLLOW(T') = { ε,+,) }

SELECT(F -> (E) ) = FIRST((E)) = { ( }

SELECT(F -> i) = FIRST(i) = { i }

∵SELECT(E' -> +TE') ∩ SELECT(E' -> ε) = ø

   SELECT(T' -> *FT') ∩ SELECT(T' -> ε) = ø

   SELECT(F -> (E) ) ∩ SELECT(F -> i) = ø

∴ LL(1) 。

 

3. 2, LL(1) , 。

E()

    {T();

       E'();

     }

E'()

T()

T'()

F()

  :

void ParseE() {

  switch (lookahead) {

    case'(','i':

      ParseT();

      ParseE'();

      break;

    default:

      print("syntax error
");

      exit(0);

  }

}

void ParseE'(){

  switch(lookahead){

    case '+':

      MatchToken('+');

      ParseT();

      ParseE'();

      break;

    case ')','#':

      break;

    default:

      print("syntax error
");

      exit(0);

  }

}

void ParseT(){

  switch (lookahead) {

    case '(','i':

      ParseF();

      ParseT'();

      break;

    default:

      print("syntax error
");

      exit(0);

  }

}

void ParseT'(){

  switch(lookahead){

    case '*':

      MatchToken('*');

      ParseF();

      ParseT'();

      break;

    case '+',')','#':

      break;

    default:

      print("syntax error
");

      exit(0);

  }

}

void ParseF(){

  switch(lookahead){

    case '(':

      MatchToken('(');

      ParseE();

      MatchToken(')');

      break;

    case 'i':

      MatchToken('i');

      break;

    default:

      print("syntax error
");

      exit(0);

  }

}

 

 4. , , 。