PROJECT ON GRAMMARS
Course: IST 230/CMPSC 360
Deadline: see the calendar in Canvas for the deadline
Objective: To acquire a comprehensive understanding of the application of grammars and formal language theory to computing languages.
Given: Consider the following set of productions:
|
P01:
|
FN
|
→
|
FN-HEAD FN-BODY
|
|
P02:
|
FN-HEAD
|
→
|
TYPE id ( PARAM-LIST )
|
|
P03:
|
TYPE
|
→
|
char
|
|
P04:
|
TYPE
|
→
|
int
|
|
P05:
|
TYPE
|
→
|
real
|
|
P06:
|
PARAM-LIST
|
→
|
TYPE id
|
|
P07:
|
PARAM-LIST
|
→
|
PARAM-LIST , TYPE id
|
|
P08:
|
FN-BODY
|
→
|
{ VAR-DECL STMT return ( EXPRESN ) ; }
|
|
P09:
|
VAR-DECL
|
→
|
ë
|
|
P10:
|
VAR-DECL
|
→
|
TYPE ID-LIST ;
|
|
P11:
|
VAR-DECL
|
→
|
VAR-DECL TYPE ID-LIST ;
|
|
P12:
|
ID-LIST
|
→
|
id
|
|
P13:
|
ID-LIST
|
→
|
ID-LIST , id
|
|
P14:
|
STMT
|
→
|
ë
|
|
P15:
|
STMT
|
→
|
SIMPLE-STMT
|
|
P16:
|
STMT
|
→
|
SELECT-STMT
|
|
P17:
|
STMT
|
→
|
REPEAT-STMT
|
|
P18:
|
STMT
|
→
|
SEQUENCE-STMT
|
|
P19:
|
SIMPLE-STMT
|
→
|
ASSIGN-STMT
|
|
P20:
|
SIMPLE-STMT
|
→
|
FN-CALL-STMT
|
|
P21:
|
ASSIGN-STMT
|
→
|
var = EXPRESN ;
|
|
P22:
|
EXPRESN
|
→
|
ARITH-EXP
|
|
P23:
|
EXPRESN
|
→
|
BOOL-EXP
|
|
P24:
|
ARITH-EXP
|
→
|
TERM
|
|
P25:
|
ARITH-EXP
|
→
|
ARITH-EXP ADD-OP TERM
|
|
P26:
|
ADD-OP
|
→
|
+
|
|
P27:
|
ADD-OP
|
→
|
-
|
|
P28:
|
TERM
|
→
|
FAC
|
|
P29:
|
TERM
|
→
|
TERM MUL-OP FAC
|
|
P30:
|
MUL-OP
|
→
|
*
|
|
P31:
|
MUL-OP
|
→
|
/
|
|
P32:
|
FAC
|
→
|
( ARITH-EXP )
|
|
P33:
|
FAC
|
→
|
OPD
|
|
P34:
|
OPD
|
→
|
var
|
|
P35:
|
OPD
|
→
|
const
|
|
P36:
|
BOOL-EXP
|
→
|
RELN-EXP
|
|
P37:
|
BOOL-EXP
|
→
|
LOGIC-EXP
|
|
P38:
|
RELN-EXP
|
→
|
OPD RELN-OPR OPD
|
|
P39:
|
RELN-OPR
|
→
|
==
|
|
P40:
|
RELN-OPR
|
→
|
!=
|
|
P41:
|
RELN-OPR
|
→
|
<
|
|
P42:
|
RELN-OPR
|
→
|
<=
|
|
P43:
|
RELN-OPR
|
→
|
>
|
|
P44:
|
RELN-OPR
|
→
|
>=
|
|
P45:
|
LOGIC-EXP
|
→
|
OPD LOGIC-OPR OPD
|
|
P46:
|
LOGIC-EXP
|
→
|
LOGIC-OPR OPD
|
|
P47:
|
LOGIC-OPR
|
→
|
and
|
|
P48:
|
LOGIC-OPR
|
→
|
or
|
|
P49:
|
LOGIC-OPR
|
→
|
not
|
|
P50:
|
FN-CALL-STMT
|
→
|
id ( ARG-LIST ) ;
|
|
P51:
|
ARG-LIST
|
→
|
ë
|
|
P52:
|
ARG-LIST
|
→
|
id
|
|
P53:
|
ARG-LIST
|
→
|
ARG-LIST , id
|
|
P54:
|
SELECT-STMT
|
→
|
if CONDITION STMT else STMT
|
|
P55:
|
CONDITION
|
→
|
( BOOL-EXP )
|
|
P56:
|
REPEAT-STMT
|
→
|
DO-STMT
|
|
P57:
|
REPEAT-STMT
|
→
|
WHILE-STMT
|
|
P58:
|
DO-STMT
|
→
|
do { STMT } while CONDITION ;
|
|
P59:
|
WHILE-STMT
|
→
|
while CONDITION do { STMT } ;
|
|
P60:
|
SEQUENCE-STMT
|
→
|
STMT STMT
|
Instructions:
1. Rewrite the set of productions above in Extended Backus-Naur Form (EBNF).
2. Using a Push Down Automaton (PDA), determine if the following function is valid code according to the given set of productions.
int Max ( int x, int y )
{
int z ;
if ( x >y )
z = x ;
else
z = y ;
return ( z ) ;
}
3. Validate your answer in (2) by illustrating it with a derivation tree
Deliverable: Submit a paper Times New Roman font, 12 pt., double-space lines). The project must contain an introduction which includes the purpose of the project.
1)
BNF:
1. ::=
2. ::= ( )
3. ::= "char" | "int" | "real"
4. ::= , |
5. ::={ return ( ) ; }
6. ::= "" | | < ID-LIST>
7. ::= | |
8. ::= "" | | | | SEQUENCE - STMT
9. ::= |
10. ::= "var" =
11. ::= |
12. ::== | | |
13. ::= "+" | "-"
14. ::= |
15. ::= "*" | "/"
16. ::= ( ) |
17. ::= "var" | "const"
18. ::== |
19. ::=
20. ::= "==" | "!=" | "<" | "<=" | ">" | ">="
21. ::= | | | |
22. ::= "and" | "or" | "not"
23. ::= "id" ( ) ;
24. ::= "" | "id" | "id"
25. ::= if else
26. ::= <(BOOL-EXP)>
27. ::= |
28. ::= do { } while ;
29. ::= while do { }
30. ::=
EBNF:
1. ::=
2. ::= ( * )
3. ::= "char" | "int" | "real"
4. ::= , + | +
5. ::= { * return ( ) ; }
6. ::= "" | * | * < ID-LIST>*
7. ::= "id" | * , "id"
8. ::= "" | | | |
9. ::= |
10. ::= "var" = ;
11. ::= |
12. ::== * | * *
13. ::= "+" | "-"
14. ::= | *
15. ::= "*" | "/"
16. ::= ( * ) |
17. ::= "var" | "const"
18. ::== |
19. ::=
20. ::= "==" | "!=" | "<" | "<=" | ">" | ">="
21. ::= |
22. ::= "and" | "or" | "not"
23. ::= "id" ( * ) ;
24. ::= "" | "id" | * "id"
25. ::= if else
26. ::= <(BOOL-EXP)>
27. ::= |
28. ::= do { } while ;
29. ::= while do { }
30. ::=