Create a context free grammar that will generate and parse elements of a simple
ID: 3742557 • Letter: C
Question
Create a context free grammar that will generate and parse elements of a simple programming
language that includes the following elements. Comments are in []’s. This project contains no
programming on your part
• Single lines will be terminated with a semi-colon.
• Statement blocks will be bounded by curly brackets.
• Comma separated lists
• Data types [note all lowercase]:
boolean [literals true and false]
char [literals contained within single quotes]
double [positive decimals only]
int [positive integers only]
string [literals contained within double quotes]
• Identifiers / Variables:
Alphabetic [variables can begin with and include any number of upper or lowercase
alphabetic characters, A through Z and a through z]
Numberic [variables cannot begin with numbers, but can contain any number of digits
0 through 9 after the initial character in the variable]
Underscore [variables can begin with and include any number of underscores, but
cannot be only underscore(s), _ , the variable must also contain at least
one alphanumeric character and follow the other rules defined for them]
• Operators given here:
= [assignment]
+ [addition, mathematical and string]
– [subtraction]
* [multiplication]
/ [division]
% [modulo]
== [equivalence]
() [precedence using parens]
• Printing function: variables and literal strings
print [function name]
() [data to print contained within parens]
• Single conditional statement:
if [start of statement]
() [parens contain boolean condition / value]
{} [contain statements]
Explanation / Answer
A CFG for Arithmetic Expressions
An example grammar that generates strings representing arithmetic expressions with the four operators +, -, *, /, and numbers as operands is:
The only nonterminal symbol in this grammar is <expression>, which is also the start symbol. The terminal symbols are {+,-,*,/,(,),number}. (We will interpret "number" to represent any valid number.)
The first rule (or production) states that an <expression> can be rewritten as (or replaced by) a number. In other words, a number is a valid expression.
The second rule says that an <expression> enclosed in parentheses is also an <expression>. Note that this rule defines an expression in terms of expressions, an example of the use of recursion in the definition of context-free grammars.
The remaining rules say that the sum, difference, product, or division of two <expression>s is also an expression.
A CFG for C++ compound statements:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.