-2
$\begingroup$

(r1) E → E+T

(r2) E → T

(r3) T → T F

(r4)T →F

(r5) F → F∗

(r6) F → a

(r7) F → b

I am just doing the exercise on the workshop. I just knew how to the build the SLR state machine for this CFG. After built the State machine. I have found the FOLLOW and FIRST set for this CFG. But I can not find the way that how to build an SLR table from the state machine,FOLLOW and FIRST set.

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ What did you try? Where did you get stuck? Isn't this a standard construction? $\endgroup$ – David Richerby Jun 3 '16 at 14:40
  • 1
    $\begingroup$ SLR parsing is well documented in textbooks (and other resources); just apply those methods. What did you try? Which resources did you read, and where did you get stuck in applying the techniques described there? There would be little point in repeating that material here a second time. We want you to exhaust all available resources before asking here, and show us in the question what approaches you considered and what research you did -- see cs.stackexchange.com/help/how-to-ask. $\endgroup$ – D.W.♦ Jun 3 '16 at 19:08
  • $\begingroup$ You dump a grammar, an automaton, and some sets on us. How do they relate? What do either of the latter have to do with an SLR table for the former? $\endgroup$ – Raphael♦ Jun 3 '16 at 22:54
  • $\begingroup$ I have read the textbooks. Still confuse how to draw a table. I just understand how to build the state machine graph and how to find FOLLOW set and FIRST set. Then, how to use that information to build table? $\endgroup$ – pocky0719 Jun 4 '16 at 11:07
  • $\begingroup$ Editing the question to delete all of your attempts at the problem probably isn't going to help -- it doesn't really address the feedback you got. You got some suggestions about how to improve the question, but none of those said "delete half of your question and remove all the partial progress you've made so far". If you'd like this to be considered for re-opening, I encourage you to go back and re-read the comments; spend some time studying the standard constructions in textbooks; and then follow the feedback in the previous comments. (cont.) $\endgroup$ – D.W.♦ Jun 7 '16 at 6:10
1
$\begingroup$

Given grammar

(r1) E → E + T

(r2) E → T

(r3) T → T F

(r4) T → F

(r5) F → F ∗

(r6) F → a

(r7) F → b

As you know how to develop the graph (wont be explained), the parse table construction will be based on the graph in the question.

The Augmented Grammar:

E' → E // New rule added, that's it

E → E + T

E → T

T → T F

T → F

F → F∗

F → a

F → b

Step 1

Draw a empty $n$ x $m$ table , and label it appropriately.  

$n$ = number of states in the graph

$m$ = number of all non‐terminals and all terminals in the grammar.

Terminal symbols are literal symbols which may appear in the outputs of the production rules of a formal grammar and which cannot be changed using the rules of the grammar. Here, a,b,+,*

Nonterminal symbols are those symbols which can be replaced. Here, E,T,F

$ - end of string

╔══════════════════╤═══╤═══════════════════╤══════════════╗
║                  │   │     Terminals     │ Non Termails ║
╠══════════════════╪═══╪═══╤═══╤═══╤═══╤═══╪════╤════╤════╣
║                  │   │ a │ b │ + │ * │ $ │ E  │ T  │ F  ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 0 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 1 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 2 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 3 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║ Number of states │ 4 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 5 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 6 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 7 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 8 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 9 │   │   │   │   │   │    │    │    ║
╚══════════════════╧═══╧═══╧═══╧═══╧═══╧═══╧════╧════╧════╝

Notation:

s1 = Shift in r1 (rule) in the given grammer

r1 = Reduce in r1 in the given grammer

and so on..

  1. Shift : A Shift step advances in the input stream by one symbol. That shifted symbol becomes a new single-node parse tree. (for easy understanding, when dot is not at the end of the rule, its shift)
  2. Reduce : A Reduce step applies a completed grammar rule to some of the recent parse trees, joining them together as one tree with a new root symbol. (for easy understanding, when dot is at the end of the rule, its reduce)

Step 2

Look into the graph, observer the transition from node 0.

enter image description here

You can find transitions:

(node 0,E) = node 1 // non terminal E involved

(node 0,T) = node 5 // non terminal T involved

(node 0,F) = node 6 // non terminal F involved

(node 0,a) = node 3 // terminal 'a' involved

(node 0,b) = node 4 // terminal 'b' involved

These transitions should be added to the table.

Row 0 of the table should be filled with transitions from node 0

When we take :

(node 0,a) = node 3

The intersection cell of row node 0 and column 'a' terminal can be filled by s3 as transition from node with E goes to node 3 is a shift.

╔══════════════════╤═══╤════════════════════╤══════════════╗
║                  │   │     Terminals      │ Non Termails ║
╠══════════════════╪═══╪════╤═══╤═══╤═══╤═══╪════╤════╤════╣
║                  │   │ a  │ b │ + │ * │ $ │ E  │ T  │ F  ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 0 │ s3 │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 1 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 2 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 3 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║ Number of states │ 4 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 5 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 6 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 7 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 8 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 9 │    │   │   │   │   │    │    │    ║
╚══════════════════╧═══╧════╧═══╧═══╧═══╧═══╧════╧════╧════╝

(node 0,b) = node 4

The intersection cell of row node 0 and column 'b' terminal can be filled by s4 as transition from node with E goes to node 4 is a shift.

╔══════════════════╤═══╤═════════════════════╤══════════════╗
║                  │   │      Terminals      │ Non Termails ║
╠══════════════════╪═══╪════╤════╤═══╤═══╤═══╪════╤════╤════╣
║                  │   │ a  │ b  │ + │ * │ $ │ E  │ T  │ F  ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 1 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 2 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 3 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║ Number of states │ 4 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 5 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 6 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 7 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 8 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 9 │    │    │   │   │   │    │    │    ║
╚══════════════════╧═══╧════╧════╧═══╧═══╧═══╧════╧════╧════╝

as we don't have any more terminal transition, we can move to non terminals.

(node 0,E) = node 1

The intersection cell of row node 0 and column 'E' non terminal can be filled by 1 as transition from node with E goes to node 1.

(node 0,T) = node 5

The intersection cell of row node 0 and column 'T' non terminal can be filled by 5 as transition from node with E goes to node 5.

(node 0,F) = node 6

The intersection cell of row node 0 and column 'F' non terminal can be filled by 6 as transition from node with E goes to node 6.

Note: No shift or reduce for non terminals

╔══════════════════╤═══╤═════════════════════╤══════════════╗
║                  │   │      Terminals      │ Non Termails ║
╠══════════════════╪═══╪════╤════╤═══╤═══╤═══╪════╤════╤════╣
║                  │   │ a  │ b  │ + │ * │ $ │ E  │ T  │ F  ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │   │   │   │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 1 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 2 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 3 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║ Number of states │ 4 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 5 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 6 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 7 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 8 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 9 │    │    │   │   │   │    │    │    ║
╚══════════════════╧═══╧════╧════╧═══╧═══╧═══╧════╧════╧════╝

and so on..

Note : The intersection cell of row node 1 and column '$' terminal can be filled by acc (accepted) as rule added to make your grammar an Augmented Grammar is reduced.

╔══════════════════╤═══╤════════════════════════╤══════════════╗
║                  │   │       Terminals        │ Non Termails ║
╠══════════════════╪═══╪════╤════╤════╤═══╤═════╪════╤════╤════╣
║                  │   │ a  │ b  │ +  │ * │  $  │ E  │ T  │ F  ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │    │   │     │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 1 │    │    │ s2 │   │ acc │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 2 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 3 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║ Number of states │ 4 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 5 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 6 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 7 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 8 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 9 │    │    │    │   │     │    │    │    ║
╚══════════════════╧═══╧════╧════╧════╧═══╧═════╧════╧════╧════╝

Step 3

node 3 has reduce to r6 and no further transition are allowed form node 3, thus all the intersecting cells with Follow(F) are marks as r6.

$Follow(F) = \{ a,b,+,*,\$ \} $

Note : Follow(F) is taken because reduction is to the rule (r6) F → a, Follow of rigth hand side should be taken.

╔══════════════════╤═══╤═════════════════════════╤══════════════╗
║                  │   │        Terminals        │ Non Termails ║
╠══════════════════╪═══╪════╤════╤════╤════╤═════╪════╤════╤════╣
║                  │   │ a  │ b  │ +  │ *  │  $  │ E  │ T  │ F  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │    │    │     │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 1 │    │    │ s2 │    │ acc │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 2 │ s3 │ s4 │    │    │     │    │ 8  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 3 │ r6 │ r6 │ r6 │ r6 │ r6  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║ Number of states │ 4 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 5 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 6 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 7 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 8 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 9 │    │    │    │    │     │    │    │    ║
╚══════════════════╧═══╧════╧════╧════╧════╧═════╧════╧════╧════╝

node 5 has both reduce (to r2) and shift (with a,b) to r2.

The intersecting cells node 5 with Follow(E) are marks as r2.

$Follow(E) = \{ +,\$ \} $

(node 5,a) = node 3

The intersection cell of row node 5 and column 'a' terminal can be filled by s3 as transition from node with 'a' goes to node 3.

(node 5,b) = node 4

The intersection cell of row node 5 and column 'b' terminal can be filled by s4 as transition from node with 'b' goes to node 4.

╔══════════════════╤═══╤═════════════════════════╤══════════════╗
║                  │   │        Terminals        │ Non Termails ║
╠══════════════════╪═══╪════╤════╤════╤════╤═════╪════╤════╤════╣
║                  │   │ a  │ b  │ +  │ *  │  $  │ E  │ T  │ F  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │    │    │     │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 1 │    │    │ s2 │    │ acc │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 2 │ s3 │ s4 │    │    │     │    │ 8  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 3 │ r6 │ r6 │ r6 │ r6 │ r6  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║ Number of states │ 4 │ r7 │ r7 │ r7 │ r7 │ r7  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 5 │ s3 │ s4 │ r2 │    │ r2  │    │    │ 9  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 6 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 7 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 8 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 9 │    │    │    │    │     │    │    │    ║
╚══════════════════╧═══╧════╧════╧════╧════╧═════╧════╧════╧════╝

and so on..

Repeat the process until all transitions are exhausted.

Final result :

╔══════════════════╤═══╤═════════════════════════╤══════════════╗
║                  │   │        Terminals        │ Non Termails ║
╠══════════════════╪═══╪════╤════╤════╤════╤═════╪════╤════╤════╣
║                  │   │ a  │ b  │ +  │ *  │  $  │ E  │ T  │ F  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │    │    │     │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 1 │    │    │ s2 │    │ acc │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 2 │ s3 │ s4 │    │    │     │    │ 8  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 3 │ r6 │ r6 │ r6 │ r6 │ r6  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║ Number of states │ 4 │ r7 │ r7 │ r7 │ r7 │ r7  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 5 │ s3 │ s4 │ r2 │    │ r2  │    │    │ 9  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 6 │ r4 │ r4 │ r4 │ s7 │ r4  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 7 │ r5 │ r5 │ r5 │ r5 │ r5  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 8 │ s3 │ r4 │ r1 │    │ r1  │    │    │ 9  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 9 │ r3 │ r3 │ r3 │ s7 │ r3  │    │    │    ║
╚══════════════════╧═══╧════╧════╧════╧════╧═════╧════╧════╧════╝
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice Ascii Table, just wanted you to know that you can use LaTeX to embed table. Also do not worry, but on mobile the table looks like this. $\endgroup$ – Evil Jun 6 '16 at 4:17
  • $\begingroup$ Thank you so much! Really! But should " (node 0,E) = node 3 // terminal E involved " change to to (node 0,E) = node 1? $\endgroup$ – pocky0719 Jun 6 '16 at 11:50
  • $\begingroup$ Sorry for that and thanks @ChenhaoWei for pointing it out, its corrected now. I did typed it wrong initially but when I constructed the table I referred the graph directly so steps and final answer will be correct. $\endgroup$ – Alwyn Mathew Jun 6 '16 at 12:10
  • $\begingroup$ One more question. How to know the node number in the state machine? I can not understand why node 3 is F->a. $\endgroup$ – pocky0719 Jun 10 '16 at 4:14
  • $\begingroup$ BTW: " (node 0,T) = node 5 // terminal T involved" E and T is Non-terminal, a b is Terminal $\endgroup$ – pocky0719 Jun 10 '16 at 4:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.