Grammer, indetifieres I. Give a grammar that defines the language of simple (non
ID: 3705640 • Letter: G
Question
Grammer, indetifieres
I. Give a grammar that defines the language of simple (non-method) function prototypes in C++. Examples of these would be "int f(int x),". "void g2(int jim, float x) "char abc (void) ;" In general, you must have a data type, an identifier, a parameter list which consists of zero or more type/name pairs separated by comma's., and a ting semicolon. For data types, you should allow char, int, and float. For identifiers function and parameter names), you should allow any combination of one or more character, where the first character must be a letter and all other characters may be a letter or a numeric digit. Only include spaces where they must occur (between types and identifiers).Explanation / Answer
For the grammar that follows here are the types of the various elements by type font or symbol:
•
Keywords are in this type font.
•
TOKEN CLASSES ARE IN THIS TYPE FONT.
•
Nonterminals are in this type font.
•
The symbol
means the empty string in a CS grammar sense.
1.1 Some Token Definitions
•
letter = a
|
. . .
|
z
|
A
|
. . .
|
Z
•
digit = 0
|
. . .
|
9
•
letdig = digit
|
letter
•
ID
= letter letdig
?
•
NUMCONST
= digit
+
•
CHARCONST
= is any representation for a single character by placing that character in
single quotes. A backslash is an escape character. Any character preceded by a backslash is
interpreted as that character. For example
x
is the letter x,
’
is a single quote,
\
is a single
backslash. There are
only two exceptions
to this rule:
n
is a newline character and
0
is
the null character.
•
White space
(a sequence of blanks and tabs) is ignored. Whitespace may be required to
separate some tokens in order to get the scanner not to collapse them into one token. For
example: “intx” is a single
ID
while “int x” is the type
int
followed by the
ID
x. The scanner,
by its nature, is a greedy matcher.
•
Comments
are ignored by the scanner. Comments begin with
//
and run to the end of the
line.
1
•
All
keywords
are in lowercase. You need not worry about being case independent since not
all lex/flex programs make that easy.
2 The Grammar
1.
program
?
declarationList
2.
declarationList
?
declarationList declaration
|
declaration
3.
declaration
?
varDeclaration
|
funDeclaration
|
recDeclaration
4.
recDeclaration
?
record
ID
{
localDeclarations
}
5.
varDeclaration
?
typeSpecifier varDeclList
;
6.
scopedVarDeclaration
?
scopedTypeSpecifier varDeclList
;
7.
varDeclList
?
varDeclList
,
varDeclInitialize
|
varDeclInitialize
8.
varDeclInitialize
?
varDeclId
|
varDeclId
:
simpleExpression
9.
varDeclId
?
ID
|
ID [ NUMCONST ]
10.
scopedTypeSpecifier
?
static
typeSpecifier
|
typeSpecifier
11.
typeSpecifier
?
returnTypeSpecifier
|
RECTYPE
12.
returnTypeSpecifier
?
int
|
bool
|
char
13.
funDeclaration
?
typeSpecifier
ID (
params
)
statement
|
ID (
params
)
statement
14.
params
?
paramList
|
15.
paramList
?
paramList
;
paramTypeList
|
paramTypeList
16.
paramTypeList
?
typeSpecifier paramIdList
17.
paramIdList
?
paramIdList
,
paramId
|
paramId
18.
paramId
?
ID
|
ID [ ]
2
19.
statement
?
expressionStmt
|
compoundStmt
|
selectionStmt
|
iterationStmt
|
returnStmt
|
breakStmt
20.
compoundStmt
?
{
localDeclarations statementList
}
21.
localDeclarations
?
localDeclarations scopedVarDeclaration
|
22.
statementList
?
statementList statement
|
23.
expressionStmt
?
expression
;
|
;
24.
selectionStmt
?
if
(
simpleExpression
)
statement
|
if
(
simpleExpression
)
statement
else
statement
25.
iterationStmt
?
while
(
simpleExpression
)
statement
26.
returnStmt
?
return
;
|
return
expression
;
27.
breakStmt
?
break
;
28.
expression
?
mutable
=
expression
|
mutable
+=
expression
|
mutable
?
=
expression
|
mutable
?
=
expression
|
mutable
/
=
expression
|
mutable
++
|
mutable
??
|
sim-
pleExpression
29.
simpleExpression
?
simpleExpression
or
andExpression
|
andExpression
30.
andExpression
?
andExpression
and
unaryRelExpression
|
unaryRelExpression
31.
unaryRelExpression
?
not
unaryRelExpression
|
relExpression
32.
relExpression
?
sumExpression relop sumExpression
|
sumExpression
33.
relop
?
<
=
|
<
|
>
|
>
=
|
==
|
! =
34.
sumExpression
?
sumExpression sumop term
|
term
35.
sumop
?
+
|
?
36.
term
?
term mulop unaryExpression
|
unaryExpression
37.
mulop
?
?
|
/
|
%
38.
unaryExpression
?
unaryop unaryExpression
|
factor
39.
unaryop
?
?
|
?
|
?
40.
factor
?
immutable
|
mutable
41.
mutable
?
ID
|
mutable
[
expression
]
|
mutable
.
ID
3
42.
immutable
?
(
expression
)
|
call
|
constant
43.
call
?
ID (
args
)
44.
args
?
argList
|
45.
argList
?
argList
,
expression
|
expression
46.
constant
?
NUMCONST
|
CHARCONST
|
true
|
false
3 Semantic Notes
•
The only numbers are
int
s.
•
There is no conversion or coercion between types such as between
int
s and
bool
s or
bool
s and
int
s.
•
There can only be one function with a given name. There is no function overloading.
•
The unary asterisk is the only unary operator that takes an array as an argument. It takes
an array and returns the size of the array.
•
The logical operators
and
and
or
are NOT short cutting. Although it is easy to do, we have
plenty of other stuff to implement.
•
In if statements the
else
is associated with the most recent
if
.
•
Expressions are evaluated in order consistent with operator associativity and precedence found
in mathematics. Also, no reordering of operands is allowed.
•
A char occupies the same space as an integer or bool.
•
Initialization of variables can only be with expressions that are constant, that is, they are
able to be evaluated to a constant at compile time. For this class, it is not necessary that you
actually evaluate the constant expression at compile time. But you will have to keep track of
whether the expression is const. Type of variable and expression must match (see exception
for char arrays below).
•
array and record assignment works. Array and record comparison don’t. We just don’t have
time. Passing of arrays and records are done by reference. Functions cannot return an array
or record.
•
Assignments in expressions happen at the time the assignment operator is encountered in the
order of evaluation. The value returned is value of the rhs of the assignment. Assignments
include the
++
and
??
operator. That is, the
++
and
??
operator do NOT behave as in
C or C++.
4
•
Function return type is specified in the function declaration, however if no type is given to
the function in the declaration then it is assumed the function does not return a value. To
aid discussion of this case, the type of the return value is said to be void, even though there
is no
void
keyword for the type specifier.
•
Code that exits a procedure without a
return
returns a 0 for an function returning
int
and
false
for a function returning
bool
and a blank for a function returning
char
.
•
All variables, functions, and record types must be declared before use.
•
Record types are stored like arrays except indexing is done with an
ID
.
•
Record types can contain items that are of record type but recursive record definition is not
allowed.
•
?
n
generates a uniform random integer in the range 0 to
|
n
|?
1 with the sign of
n
attached to
the result. ?5 is a random number in the range 0 to 4. ?
?
5 is a random number in the range
0 to
?
4. ?0 is undefined. ?
x
for array
x
gives a random element from the array
x
.
5
7
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.