Reference no: EM131309093

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. <FN> ::= <FN-HEAD> <FN-BODY>
2. <FN-HEAD> ::= <TYPE> ( <PARAM-LIST)> )
3. <TYPE> ::= "char" | "int" | "real"
4. <PARAM-LIST> ::= <PARAM-LIST> , <TYPE> | <TYPE>
5. <FN-BODY> ::={ <VAR-DECL> <STMT> return ( <EXPRESN> ) ; }
6. <VAR-DECL> ::= "" | <TYPE> <ID-LIST> | <VAR-DECL> <TYPE> < ID-LIST>
7. <ID-LIST> ::= <id> | <ID-LIST> | <id>
8. <STMT> ::= "" | <SIMPLE-STMT> | <SELECT-STMT> | <REPEAT-STMT> | SEQUENCE - STMT
9. <SIMPLE-STMT> ::= <ASSIGN-STMT> | <FN-CALL-STMT>
10. <ASSIGN-STMT> ::= "var" = <EXPRESN ;>
11. <EXPRESN> ::= <ARITH-EXP> | <BOOL-EXP>
12. <ARITH-EXP> ::== <TERM> | <ARITH-EXP> | <ADD OP> | <TERM>
13. <ADD-OP> ::= "+" | "-"
14. <TERM> ::= <FAC> | <TERM> <MUL-OP> <FAC>
15. <MUL-OP> ::= "*" | "/"
16. <FAC> ::= ( <ARITH-EXP> ) | <OPD>
17. <OPD> ::= "var" | "const"
18. <BOOL-EXP> ::== <RELN-EXP> | <LOGIC-EXP>
19. <RELN-EXP> ::= <OPD> <RELN-OPR> <OPD>
20. <RELN-OPR> ::= "==" | "!=" | "<" | "<=" | ">" | ">="
21. <LOGIC-EXP> ::= <OPD> | <LOGIC-OPR> | <OPD> | <LOGIC-OPR> | <OPD>
22. <LOGIC-OPR> ::= "and" | "or" | "not"
23. <FN-CALL-STMT> ::= "id" ( <ARG-LIST> ) ;
24. <ARG-LIST> ::= "" | "id" | <ARG-LIST> "id"
25. <SELECTION-STMT> ::= if <CONDITION> <STMT> else <STMT>
26. <CONDITION> ::= <(BOOL-EXP)>
27. <REPEAT-STMT> ::= <DO-STMT> | <WHILE-STMT>
28. <DO-STMT> ::= do { <STMT> } while <CONDITION>;
29. <WHILE-STMT> ::= while <CONDITION> do { <STMT> }
30. <SEQUENCE-STMT> ::= <STMT> <STMT>

 

EBNF:

 

1. <FN> ::= <FN-HEAD> <FN-BODY>
2. <FN-HEAD> ::= <TYPE> ( <PARAM-LIST)>* )
3. <TYPE> ::= "char" | "int" | "real"
4. <PARAM-LIST> ::= <PARAM-LIST> , <TYPE>+ | <TYPE>+
5. <FN-BODY> ::= { <VAR-DECL>* <STMT> return ( <EXPRESN> ) ; }
6. <VAR-DECL> ::= "" | <TYPE> <ID-LIST>* | <VAR-DECL>* <TYPE> < ID-LIST>*
7. <ID-LIST> ::= "id" | <ID-LIST>* , "id"
8. <STMT> ::= "" | <SIMPLE-STMT> | <SELECT-STMT> | <REPEAT-STMT> | <SEQUENCE - STMT>
9. <SIMPLE-STMT> ::= <ASSIGN-STMT> | <FN-CALL-STMT>
10. <ASSIGN-STMT> ::= "var" = <EXPRESN> ;
11. <EXPRESN> ::= <ARITH-EXP*> | <BOOL-EXP>
12. <ARITH-EXP> ::== <TERM>* | <ARITH-EXP>* <ADD OP> <TERM>*
13. <ADD-OP> ::= "+" | "-"
14. <TERM> ::= <FAC> | <TERM>* <MUL-OP> <FAC>
15. <MUL-OP> ::= "*" | "/"
16. <FAC> ::= ( <ARITH-EXP>* ) | <OPD>
17. <OPD> ::= "var" | "const"
18. <BOOL-EXP> ::== <RELN-EXP> | <LOGIC-EXP>
19. <RELN-EXP> ::= <OPD> <RELN-OPR> <OPD>
20. <RELN-OPR> ::= "==" | "!=" | "<" | "<=" | ">" | ">="
21. <LOGIC-EXP> ::= <OPD> <LOGIC-OPR> <OPD> | <LOGIC-OPR> <OPD>
22. <LOGIC-OPR> ::= "and" | "or" | "not"
23. <FN-CALL-STMT> ::= "id" ( <ARG-LIST>* ) ;
24. <ARG-LIST> ::= "" | "id" | <ARG-LIST>* "id"
25. <SELECTION-STMT> ::= if <CONDITION> <STMT> else <STMT>
26. <CONDITION> ::= <(BOOL-EXP)>
27. <REPEAT-STMT> ::= <DO-STMT> | <WHILE-STMT>
28. <DO-STMT> ::= do { <STMT> } while <CONDITION>;
29. <WHILE-STMT> ::= while <CONDITION> do { <STMT> }
30. <SEQUENCE-STMT> ::= <STMT> <STMT>