COSC4307 Program-2 Due: Thursday, 9/24/2009
NEXT MATRIX GENERATION
Task: Write a program that computes and prints out the matrix NEXT (of size t-by-t)
where t is the number of terminal symbols of the grammar.
Note that NEXT[i][j] = 1 if and only if the i-th
terminal and the j-th terminal can possibly occur
next to each other in that order somewhere in a syntactically
correct program (or sentence) and else it is 0.
Requirements:
1. All non-terminals must be numbered (starting from one) first before
numbering all terminals in the same order as they appear in the given input grammar.
2. Outputs should include, in that order:
a. input grammar rules (as charater strings)
b. input grammar rules (as integers)
c. Leftmost-derivation matrix.
d. Rightmost-derivation matrix.
e. NEXT matrix.
INPUT GRAMMAR RULES
PASCAL := Program DECL ; BLOCK .
DECL := Var IDLIST : TYPE
DECL := Var IDLIST : TYPE ; DECL
IDLIST := Id
IDLIST := Id , IDLIST
TYPE := Integer
TYPE := Real
BLOCK := Begin BODY End
BODY := BODY ; S
BODY := S
S := Id = E
S := BLOCK
E := E + T
E := T
T := T * F
T := F
F := ( E )
F := Id
GRAMMAR SYMBOLS
1::: PASCAL
2::: DECL
3::: IDLIST
4::: TYPE
5::: BLOCK
6::: BODY
7::: S
8::: E
9::: T
10::: F
11::: Program
12::: ;
13::: .
14::: Var
15::: :
16::: Id
17::: ,
18::: Integer
19::: Real
20::: Begin
21::: End
22::: =
23::: +
24::: *
25::: (
26::: )
LEFTMOST-DERIVATION MATRIX
TERMS: 11 13 15 17 19 21 23 25
12 14 16 18 20 22 24 26
-----------------------------------------
PASCAL 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
DECL 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
IDLIST 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
TYPE 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
BLOCK 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
BODY 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
S 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
E 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
T 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
F 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
RIGHTMOST-DERIVATION MATRIX
TERMS: 11 13 15 17 19 21 23 25
12 14 16 18 20 22 24 26
-----------------------------------------
PASCAL 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
DECL 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
IDLIST 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
TYPE 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
BLOCK 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
BODY 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
S 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
E 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
T 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
F 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
THE NEXT MATRIX
TERMS: 11 13 15 17 19 21 23 25
12 14 16 18 20 22 24 26
----------------------------------------
Program 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
; 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0
. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Var 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
: 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
Id 0 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1
, 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
Integer 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Real 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Begin 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
End 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0
= 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
+ 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
* 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
( 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
) 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1