Paper on Grammars

gina123

project_on_grammars.docx

Home >Computer Science homework help >Paper on Grammars

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. (30 points) Rewrite the set of productions above in Extended Backus-Naur Form (EBNF).

2. (35 points) 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. (35 points) 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.

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>*