Purpose The purpose of this assignment is to give you more practice with recursi
ID: 3599459 • Letter: P
Question
Purpose
The purpose of this assignment is to give you more practice with recursion. You must utilize recursion to implement the grammar given below. You are building what is known as a 'recursive descent parser', which is used by compilers and by the tools you use to build a compiler!
Below is a grammar that represents a restricted form of an infix expression. The restriction is that unless you use parenthesis for clarification, you can only have one '+' or '-' per expression. In addition, '*' and/or '/' may not appear consecutively (A/B*C) -- note that A/B+C/D is valid.
<expression> = <term> | <term>+<term> | <term>-<term>
<term> = <factor> | <factor>*<factor> | <factor>/<factor>
<factor> = <letter> | (<expression>)
<letter> = A | B | C | D | ... | Z
Thus A+B-C is not valid. Similarly, A/B*C is not valid. Note that A+(B-C) is fine, as is (A/B)*C.
Here is some pseudocode to aid you in construction of your algorithm:
FIND AN EXPRESSION
Find a term
if (next symbol is a + or a -)
Find a term
FIND A TERM
Find a factor
if (next symbol is a * or a /)
Find a factor
FIND A FACTOR
if (the first symbol is a letter)
Done
else if (the first symbol is a '(' )
Find an expression starting at character after '('
Check for ')'
else
No factor exists
Given an input file that contains infix expressions, you must process each of those expressions and state whether an infix expression is valid based on the above grammar, or not valid. Your program should print each expression processed and report whether or not it is valid. As an example, if your input file contained:
A+B-C
A+B*C
A/B+C
(A+B)-C
(A)
(A-B-C)
Your program output should be as follows:
A+B-C is NOT Valid
A+B*C is Valid
A/B+C is Valid
(A+B)-C is Valid
(A) is Valid
(A-B-C) is NOT Valid
Your input file will be named infix.txt -- you may hard code this into your program. This file will contain one infix expression per line. The valid characters used for an infix expression will be upper case letters, parens, and the arithmetic operators for addition, subtraction, multiplication, and division. Any other characters are not valid (your recursive descent parser will report expressions that contain such characters as not valid).Name the class that contains your code for the recursive descent parser, Parser. Name the class to test your Parser, TestParser. The TestParser class should be used to open the input file, read an infix expression from the file, then pass that expression to the Parser for validation. The TestParser class should report whether or not an expression was valid based on the results returned from the Parser.
Explanation / Answer
typedef enum {ident, number, lparen, rparen, times, slash, plus,
minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
varsym, procsym, period, oddsym} Symbol;
Symbol sym;
void getsym(void);
void error(const char msg[]);
void expression(void);
int accept(Symbol s) {
if (sym == s) {
getsym();
return 1;
}
return 0;
}
int expect(Symbol s) {
if (accept(s))
return 1;
error("expect: unexpected symbol");
return 0;
}
void factor(void) {
if (accept(ident)) {
;
} else if (accept(number)) {
;
} else if (accept(lparen)) {
expression();
expect(rparen);
} else {
error("factor: syntax error");
getsym();
}
}
void term(void) {
factor();
while (sym == times || sym == slash) {
getsym();
factor();
}
}
void expression(void) {
if (sym == plus || sym == minus)
getsym();
term();
while (sym == plus || sym == minus) {
getsym();
term();
}
}
void condition(void) {
if (accept(oddsym)) {
expression();
} else {
expression();
if (sym == eql || sym == neq || sym == lss ||
sym == leq || sym == gtr || sym == geq) {
getsym();
expression();
} else {
error("condition:valid operator");
error("condition: invalid operator");
getsym();
}
}
}
void statement(void) {
if (accept(ident)) {
expect(becomes);
expression();
} else if (accept(callsym)) {
expect(ident);
} else if (accept(beginsym)) {
do {
statement();
} while (accept(semicolon));
expect(endsym);
} else if (accept(ifsym)) {
condition();
expect(thensym);
statement();
} else if (accept(whilesym)) {
condition();
expect(dosym);
statement();
}
}
void block(void) {
if (accept(constsym)) {
do {
expect(ident);
expect(eql);
expect(number);
} while (accept(comma));
expect(semicolon);
}
if (accept(varsym)) {
do {
expect(ident);
} while (accept(comma));
expect(semicolon);
}
while (accept(procsym)) {
expect(ident);
expect(semicolon);
block();
expect(semicolon);
}
statement();
}
void program(void) {
getsym();
block();
expect(period);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.