LR(1) предметов и LALR(1) таблица разбора, как это сделать?

Question

LR(1) предметов и LALR(1) таблица разбора, как это сделать?

Из приведенной ниже грамматики создайте элементы LR(1) и объедините наборы элементов, которые дают набор элементов LALR(1). Я не уверен, как построить из этой грамматики

B -> id | id ( B) | Б. id | B [ B ] | Б. id ( B)

Ответьте пока: i0- B' -> .B, $ | .id, $ | .id ( B)

-1

bnf lr1

Источник

user7663682 06 мар '17 в 00:45

1 ответ

Другие вопросы по тегам bnf lr1

user1524750 20 мар '17 в 17:21 2017-03-20 17:21 · Answer 1 · 2017-03-20 17:21

Вот наборы элементов LALR(1), как указано в LRSTAR 8.0:

STATE MACHINE LISTING:

      +=>  Shift and goto next state.
      +<=  Shift and reduce.
       <=  Reduce.

///////////////////////////// STATE 0 /////////////////////////////
//
// *    0  G -> . B <eof> 

        2  <id>        +=>    2

        1  B           +=>    1

///////////////////////////// STATE 1 /////////////////////////////
//
// *    0  G -> B . <eof> 
// *    3  B -> B . '.' <id> 
// *    4  B -> B . '[' B ']' 
// *    5  B -> B . '.' <id> '(' B ')' 

        1  <eof>       +=>   11
        5  '.'         +=>    3
        6  '['         +=>    4

Came from: 0

///////////////////////////// STATE 2 /////////////////////////////
//
// *    1  B -> <id> . 
// *    2  B -> <id> . '(' B ')' 

        3  '('         +=>    5
           (default)    <=    1

Came from: 0 4 5 9

///////////////////////////// STATE 3 /////////////////////////////
//
// *    3  B -> B '.' . <id> 
// *    5  B -> B '.' . <id> '(' B ')' 

        2  <id>        +=>    6

Came from: 1 7 8 10

///////////////////////////// STATE 4 /////////////////////////////
//
// *    4  B -> B '[' . B ']' 

        2  <id>        +=>    2

        1  B           +=>    7

Came from: 1 7 8 10

///////////////////////////// STATE 5 /////////////////////////////
//
// *    2  B -> <id> '(' . B ')' 

        2  <id>        +=>    2

        1  B           +=>    8

Came from: 2

///////////////////////////// STATE 6 /////////////////////////////
//
// *    3  B -> B '.' <id> . 
// *    5  B -> B '.' <id> . '(' B ')' 

        3  '('         +=>    9
           (default)    <=    3

Came from: 3

///////////////////////////// STATE 7 /////////////////////////////
//
// *    3  B -> B . '.' <id> 
// *    4  B -> B . '[' B ']' 
// *    4  B -> B '[' B . ']' 
// *    5  B -> B . '.' <id> '(' B ')' 

        5  '.'         +=>    3
        6  '['         +=>    4
        7  ']'         +<=    4

Came from: 4

///////////////////////////// STATE 8 /////////////////////////////
//
// *    2  B -> <id> '(' B . ')' 
// *    3  B -> B . '.' <id> 
// *    4  B -> B . '[' B ']' 
// *    5  B -> B . '.' <id> '(' B ')' 

        4  ')'         +<=    2
        5  '.'         +=>    3
        6  '['         +=>    4

Came from: 5

///////////////////////////// STATE 9 /////////////////////////////
//
// *    5  B -> B '.' <id> '(' . B ')' 

        2  <id>        +=>    2

        1  B           +=>   10

Came from: 6

///////////////////////////// STATE 10 /////////////////////////////
//
// *    3  B -> B . '.' <id> 
// *    4  B -> B . '[' B ']' 
// *    5  B -> B . '.' <id> '(' B ')' 
// *    5  B -> B '.' <id> '(' B . ')' 

        5  '.'         +=>    3
        6  '['         +=>    4
        4  ')'         +<=    5

Came from: 9

///////////////////////////// STATE 11 /////////////////////////////
//
// *    0  G -> B <eof> . 

           (default)    <=    0

Came from: 1

//
////////////////////////////////////////////////////////////////////

Наборы предметов для минимального LR (1) одинаковы. Я не уверен насчет наборов канонических предметов LR (1). Таблицы синтаксического анализатора Canonical LR(1) непрактичны для использования, если грамматика не мала.