Comp 303 Syntax and Semantics Attribute Grammar
Attribute Grammar Practice
Question (1) Consider the following BNF Grammar
<Program>::=program <declaration-seq>begin<statement-seq>end
<declaration-seq>::= <declaration>| <declaration-seq>; <declaration>
<declaration>::= var <id> : <type>
<type>::= int | bool
<statement-seq>::= <statement>| <statement-seq>; <statement>
<statement>::= if <expr> then <statement>| <id> := <expr>
<expr>::= num| <id>| true |false
Construct an attribute grammar that satisfies the following informal conditions:
1) No identifier may be declared than once in the declaration part.
2) All identifiers that appear in statements must be declared in the declaration part.
3) The type of identifier on the left side of the assignment statement and expression
on the right side are the same.
4) The type of expression in if-statement is boolean.
Dr. Ashraf M. Bhery 1
Comp 303 Syntax and Semantics Attribute Grammar
Question (2) Consider the following BNF Grammar
<program>::=program <declaration-seq>begin<statement-seq>end
<declaration-seq>::= <declaration>| <declaration-seq> <declaration>
<declaration>::= <var-decls >| proc <id>(<var-decls>)=<statement>
<var-decls>::=<type> <id>| <var-decls>; <type> <id>
<type>::= int | bool | char
<statement-seq>::= <statement>| <statement-seq>; <statement>
<statement>::= if <expr> then <statement>| call <id> (<arg-list>);
<arg-list > ::= <expr> | < arg-list >, <expr>
<expr>::= num| <id>| true |false
Construct an attribute grammar that satisfies the following informal conditions:
1) No identifier may be declared than once in the declaration part.
2) All identifiers that appear in statements must be declared in the declaration
part.
3) The identifier on call statement must be declared as procedure (proc) and types
of arg-list in call statement must be matched with the corresponding types of
procedure formal parameters (var-decls).
4) The type of expression in if-statement is boolean.
Dr. Ashraf M. Bhery 2
Comp 303 Syntax and Semantics Attribute Grammar
Question (3) Consider the following BNF Grammar
<program>::=declare <declaration-seq>begin<statement-seq>end
<declaration-seq>::= <declaration>| <declaration-seq> ;<declaration>
<declaration>::= <var-decls >| proc <id> =<statement> |
proc <id>(<var-decls>)=<statement>
<var-decls>::=<type> <id>| <var-decls>; <type> <id>
<type>::= int | bool
<statement-seq>::= <statement>| <statement-seq>; <statement>
<statement>::= input <id>| call <id> (<arg-list>) | call <id>
<arg-list > ::= <expr> | < arg-list >, <expr>
<expr>::= num| <id>| true |false
Construct an attribute grammar that satisfies the following informal conditions:
1) No identifier may be declared than once in the declaration part.
2) All identifiers that appear in statements must be declared in the declaration
part.
3) The identifier on call statement must be declared as procedure (proc). If the
procedure so named has parameters (<var-decls>), an equal number of
arguments (<arg-list>) must be present in the call and the type of each
argument (<expr>) must match the type of the corresponding parameter.
4) The type of identifier on the input statement must be integer.
Dr. Ashraf M. Bhery 3
Comp 303 Syntax and Semantics Attribute Grammar
Question (4) Consider the following BNF Grammar
<program>::=program <id> is <block>
<block> ::=<decs>begin<stats>end
<decs>::= ℇ | <decs> <dec>
<dec>::= const <id> =<exp>; | var <id>: <type>; |
type <id> = array [num] ;
<type>::= int | bool | <id>
<stats>::= <stat>| <stats>; <stat>
<stat>::= <id> := <exp>| if <exp> then <stats> end-if |
if <exp> then <stats> else <states>end-if
<expr>::= num| true |false
Construct an attribute grammar that satisfies the following informal conditions:
1) The program name identifier may not be declared elsewhere in the
program.
2) No identifier may be declared than once in the declaration part.
3) All identifiers that appear in statements must be declared in the
declaration part.
4) The type of <exp> on the if statement must be bool.
5) The identifier on the left side of an assignment statement must be
declared as a variable, and the expression on the right must be of the
same type.
Dr. Ashraf M. Bhery 4
Comp 303 Syntax and Semantics Attribute Grammar
Question (6) Consider the following BNF Grammar
<program>::=declare <declaration-seq>begin<statement-seq>end
<declaration-seq>::= <declaration>| <declaration-seq> ;<declaration>
<declaration>::= var id : <type> | const id = <expr>|
proc <id> =<statement> |
proc <id>(<declaration-seq >)=<statement>
<type>::= int | bool
<statement-seq>::= <statement>| <statement-seq>; <statement>
<statement>::= input id | call id (<arg-list>) | call id
<arg-list > ::= <expr> | < arg-list >, <expr>
<expr>::= num| true |false
Construct an attribute grammar that satisfies the following informal conditions:
1) No identifier may be declared than once in the declaration part.
2) All identifiers that appear in statements must be declared in the
declaration part.
3) If the procedure declaration has parameters (<declaration-seq>), then
each parameter must be declared as a variable.
4) The identifier on call statement must be declared as procedure (proc). If
the procedure so named has parameters (<declaration-seq>), an equal
number of arguments (<arg-list>) must be present in the call and the type
of each argument (<expr>) must match the type of the corresponding
parameter.
5) The id on the input statement must be declared as a variable and its type
must be integer.
Dr. Ashraf M. Bhery 5
Comp 303 Syntax and Semantics Attribute Grammar
Question (7) Consider the following BNF Grammar
<program>::=program <id> is <block>
<block> ::=<decs>begin<stats>end
<decs>::= var id : <type>; | <decs> var <id>: <type>;
<type>::= int | bool
<stats>::= <stat>| <stats>; <stat>
<stat>::=
if <expr> then <stats> elsif <expr> then <stats> else <stats> end-if
| to <expr> do <stats> end-to | id := <expr>
<expr>::= num| true |false
Construct an attribute grammar that satisfies the following informal conditions:
1) The program name identifier may not be declared elsewhere in the
program.
2) No identifier may be declared than once in the declaration part.
3) All identifiers that appear in statements must be declared in the
declaration part.
4) The type of <exp> on the if-statement must be boolean.
5) The type of <exp> on the to-statement must be integer.
6) The identifier on the left side of an assignment statement and the
expression on the right must be of the same type.
Dr. Ashraf M. Bhery 6
Comp 303 Syntax and Semantics Attribute Grammar
Question (8) Consider the following BNF Grammar
<program>::= <decl-seq><stat-seq>
<dec-seq>::= <dec>| <dec-seq> <dec>
<dec>::= <var-decls >| <type> id (<var-decls>){ <body>}
<var-decls>::=<type> <id> | <var-decls> ;<type> <id>
<body> ::= <expr>
<type>::= int | bool
<stat-seq>::= id := <expr> | <stat-seq>; id := <expr>
<expr>::= num| true |false| <call>| <expr> + <expr>
<call>::= id (<expr-list>)
<expr-list > ::= <expr> | < expr-list>, <expr>
Construct an attribute grammar that satisfies the following informal conditions:
1) No identifier may be declared than once in the declaration part.
2) All identifiers that appear in statements must be declared in the
declaration part.
3) All identifiers that appear in the function body must be declared either in
the function formal parameters (represented by the rule <var-decls>) or in
the declaration part of the program. If it is declared in the function formal
parameter, then its type must be used.
4) The identifier on the left side of an assignment statement must be
declared as a variable, and the expression on the right side must be of the
same type.
5) The identifier that appears in call expression must be declared as function
and the actual parameters (represented by <expr- list>) must match the
type of the formal parameter in the function declaration.
Dr. Ashraf M. Bhery 7
Comp 303 Syntax and Semantics Attribute Grammar
Question (9) Consider the following BNF Grammar
<program>::= <block>
<block>::= <decs>begin<stats>end
<decs>::= ℇ | var id: <type>; <decs>
<type>::= int | bool
<stats>::= <stat><stats-tail>
<stats-tail>::= ℇ | <stat> <stats-tail>
<stat>::= read id |write <expr>| if <exp> then <stats> end-if | <block>
<expr>::= num| true |false
Construct an attribute grammar that satisfies the following informal conditions:
1) No identifier may be declared than once in the same block.
2) (scope and visibility rule) If a statement (say s) contains an identifier (say
x), then this identifier x must be either declared in the same block
containing x or within outer enclosed block. If x is declared in more than
one scope, then the innermost scope must be applied.
3) The type of <exp> on the if-statement must be bool.
4) The identifier on the read statement must be declared as integer.
Dr. Ashraf M. Bhery 8
Comp 303 Syntax and Semantics Attribute Grammar
Question (10) Consider the following BNF Grammar
<program> ::= program <id> is <block>
<block> ::= <declaration-seq> begin <command-seq> end
<declaration-seq>::= <declaration>| <declaration-seq> <declaration>
<declaration>::= <type> <id>| <declartion>; <type> <id>
<type>::= int | bool | char
<statement-seq>::= <statement>| <statement-seq>; <statement>
<statement>::= if <expr> then <statement>| <id> := <expr>
<expr>::= num| <id>| true |false
Construct an attribute grammar that satisfies the following informal conditions:
1) The program name identifier may not be declared elsewhere in the
program
2) No identifier may be declared than once in the declaration part.
3) All identifiers that appear in statements must be declared in the
declaration part.
4) The type of expression in if-statement is boolean.
5) The identifier on the left side of an assignment command must be
declared as a variable, and the expression on the right must be of the
same type.
Dr. Ashraf M. Bhery 9
Comp 303 Syntax and Semantics Attribute Grammar
Question (11) A protocol for communication between computers is being
designed. To increase the security of the communication, it was decided that the
structure of the sequences that are transmitted should be made up from a sequence
of blocks, each block having the same length. The blocks are separated using an
asterisk ‘*’. There is no separator either at the beginning or end of the complete
sequence. Write down an attribute grammar that generates valid sequence of
blocks
Question (12) Consider the following grammar for integer binary trees
<btree> ::= nil | (<number> <btree> <btree>)
<number> ::= <D>| <number> <D>
D>::= 0|1|…|9
Write an attribute grammar to check that a binary tree is ordered, i.e.,
that the tree is a binary search tree.
Dr. Ashraf M. Bhery 10
Comp 303 Syntax and Semantics Attribute Grammar
Question (13)
Write down a semantic analyzer phase that satisfies the following semantic
conditions:
1. Table names are unique,
2. Within a table, attribute names are unique,
3. In assignment statement,
a) The LHS table cannot have been defined or assigned previously,
b) Operands in the RHS of assignment shall have been either defined as
tables or assigned previously,
4. In union operation , the two tables share an identical names and types of
attributes,
5. In projection statement( project),
a) The id should be previously either defined as a table or assigned
previously,
b) Names of projection attributes (<id-list>) shall be unique,
c) The projection attributes (<id-list>) should be belongs to the table id.
Dr. Ashraf M. Bhery 11
