Homework 3: Tiny Calculator parsing with YACC/Bison)
Overview
This assignment builds on Homework 2 and focuses on extending your knowledge of compiler design. Specifically, you will
complete the syntax analysis phase by combining the deliverables from Homework 2 (lexical analysis using flex) with this
assignment's deliverable (syntax analysis using yacc or its GNU version, bison).
Feel free to seek ChatGPT help under the following guidelines:
Use it for suggestions, but ensure the work you submit is your own.
Share your experience in details in your README or submission comments if ChatGPT played a significant role in
solving the problem.
Objectives
Similar to Homework 2 (Lexical Analysis), the objectives of this assignment are:
1. Understanding the syntax analysis process as the application of the grammar of any programming language.
2. Many other business applications outside of the programming language domain need lexical and syntax analysis to handle
the user inputs in a more rigorous and user-friendly way.
3. Learning aged but extremely useful and popular tools, (f)lex and yacc (or bison). In homework 3, you are asked to use both
(f)lex and bison (yacc).
Before you start: Preparation
Read "Section 4.1 Introduction" in the textbook to get the basic ideas and background knowledge.
The front end of the compiler design is syntax analysis, which consists of two parts: lexical analysis, and syntactic
analysis. In the previous homework, you used the Unix (f)lex tool to understand how lexical analysis works. In this
homework, you are asked to combine the deliverable of the previous homework with the deliverable of this homework to
complete the full syntax analysis. You will be using yet another Unix tool, yacc (Yet Another Compiler Compiler) or bison
(yacc's GNU version) for syntax analysis (parsing).
Review class notes on the yacc/bison tool.
Refer to the diagram illustrating interactions between lex and yacc , noting that every time the parser ( yacc/bison ) needs
a token, it calls Lex::yylex() .
Below is the diagram describing lex and yacc interactions. Note that every time the parser (yacc/bison) needs a token,
Yacc/bison::yyparese() calls Lex::yylex().
Homework 3: Tiny Calculator parsing with YACC/Bison)
%23view_name%3Dmon 1/7
Additional references: yacc/bison tool references:
precedence as well as associativity
Read both the Operator Precedence and Context-Dependent Precedence sections for handling general
operator precedence rules and unary minus operator
To Do
1. Write BNF grammar rules
Write BNF grammar rules to implement the tiny calculator with the following features. The grammar rules with detailed
descriptions must be listed in a comment section at the beginning of your code file or in a separate Markdown file.
statement_list: list of binary expression statements
statement (assignment): var = expression
expression:
(expression) : An expression in parenthesis to allow users to set precedence
5 binary arithmetic operations: +, -, *, /, ^.
- The behavior of each binary operation is the same as in Homework 2.
Variables: Support C-like identifiers to store numbers
Numbers: Support C-like signed integer or signed float numbers. (stored as double type internally)
NOTE: The calculator should support signs (+, -) e.g., 2 - -3 + 2 - 7 - -2 (output: 2)
2. Implement the Tiny Calculator
Use Unix yacc/bison tool to implement a rudimentary tiny calculator that:
computes the following basic arithmetic operation expressions.
I. addition: +
II. subtract: -
III. multiplication: *
IV. division: /
Homework 3: Tiny Calculator parsing with YACC/Bison)
%23view_name%3Dmon 2/7
V. exponents: ^
Accepts user-entered binary arithmetic expressions, one per line.
Processes multiple expressions interactively until the user exits.
To commit operations, the user enters the RETURN key at the end of the statement.
Note that the user should be able to enter any number of expressions. See the Expected Output [8][9][10] cases.
For each calculation, the user may enter either an expression or assignment, as shown in the expected output file.
The input number for each operand can be an integer or double-precision floating point number.
Follows operator precedence and associativity rules.
Error Handling
Your program must recognize and handle the following errors:
Incorrect number format
Invalid grammar or missing operators
invalid infix binary arithmetic operation
rejecting any letters in the expression (invalid operands and/or operator type)
unmatching (nested) parentheses
Divide by zero error
Referring to undefined variables
You should test all the test cases in the Expected Outputs section below. Your results must be consistent with
the expected outputs.
3. Compare flex vs. yacc/bison
In your README, explain what tasks could not be performed using only the flex tool in Homework 2 but can now be
achieved using the yacc/bison tool. Provide clear reasoning for your observations.
Hints and guidelines:
1. Full implementation of the MIT bison Example: readme.md - Postfix Notation Calculator - Replit
(https://replit.com/@sungheenam/Postfix-Notation-Calculator#readme.md)
This REPL fully implements the example in the MIT example (Bison - Examples (mit.edu)
(http://web.mit.edu/gnu/doc/html/bison_5.html) ) above.
You may fork from the repl and read the readme.md file and sample output first before playing around with it. The
repl also has a makefile example; it is not the best one, but it would help you simplify the build process.
2. More examples in addition to the MIT example above
Example program for the lex and yacc programs - IBM Documentation (https://www.ibm.com/docs/en/aix/7.1?
topic=information-example-program-lex-yacc-programs) (A good starting point. It's somewhat similar to this
assignment)
3. flex programming
Update the flex program from HW2 to work with the bison code in HW3. Note that most of the programming logic
would be moved to the bison file. Basically, using the flex tool truly as the lexical analyzer purpose only.
Include "<your program>.tab.h" in the flex program. The *.tab.h file will be automatically generated when the bison
script gets processed. Read the postfix readme.md file linked above.
For this homework, you don't need to define any subroutines except yywrap() in flex because those subroutines in
flex including main() will be migrated to the bison program.
In the regular expression rules section of your flex code, you need to return the token and its lexeme when a token
defined in the bison file is recognized. For example, for var token in "stmt: var = expr",
In the definition section of the flex code:
var [_[:alpha:]][_[:alnum:]]*?
Homework 3: Tiny Calculator parsing with YACC/Bison)
%23view_name%3Dmon 3/7
In the rules section, write a C++ code to pass the var token:
{var} {yylval.var = new std::string(yytext); return VAR;}??
4. yacc/bison programming.
Feel free to use C++ instead of C for Bison programming. Refer to the makefile example below to compile with
"g++" instead of "GCC".
Note that in your C++ code, you can't use the "using namespace std" macro, rather, you must use fully qualified
identifiers such as std::string, std::map, std::cout, std::endl, ...
Define the following in the declaration section:
In the C code definition section:
A. external functions?
extern int yylex();
extern int yyparse();
extern void yyerror(const char* s);
B. Storing values for the variables: You can use any data structure for the purpose, but I recommend using a C++
map (dictionary) data structure.
std::map<std::string, double> vars; // a dictionary storing variable names and their values
In the bison definition section:
A. Associating yylval with tokens' Values:
yylval is used to pass semantic values from the lexer (Flex) to the parser (Bison). It acts as a communication
channel between the scanner (lexer) and the parser.
Steps to Associate yylval with Tokens' Values
1. Define a union for Token Values ( %union )
2. Associate Each Token with a Data Type ( %token <type> )
3. Assign Values in the Lexer ( yylex() ) - see above in "flex programming"
4. Use yylval in the Grammar Rules
Data structure to store the values of some tokens (see below for hints of its usage)
%union {
? double dval; /* to store numbers token value */
? std::string *var; /* to store variable ID */
}
A. token (from flex) for terminals. Tokens are what's returned by the flex tool:
%token e.g., % token <dval> NUMBER /* NUMBER token returns a double number */
B. type for non-terminals defined in the grammar if they return values:
%type e.g., % type <dval> expr /* expr return a double number */
C. Association rules for operators:
%right or
%left
D. Precedence rules for operators - Order matters!
The precedence of operators is determined by the order in which they appear, with the lowest precedence at
the top and the highest at the bottom
Define rules (grammar)
An assignment rule (stmt: var = expr) may associate a variable in the dictionary (vars) with the value of expr
e.g. vars[*$1] = $3;
Homework 3: Tiny Calculator parsing with YACC/Bison)
%23view_name%3Dmon 4/7
A good example of defining rules that is similar to this assignment: Bison - Examples (mit.edu):
(http://web.mit.edu/gnu/doc/html/bison_5.html) Infix Notation Calculator: calc
(http://web.mit.edu/gnu/doc/html/bison_toc.html#SEC27)
Build Instructions example
A make file example: (https://ucdenver.instructure.com/courses/558317/files/25220969?wrap=1)
(https://ucdenver.instructure.com/courses/558317/files/25220969/download?download_frd=1)
Disclaimer: This makefile includes a basic set of commands and is intended as a beginner's guide to understanding
makefile formats. It should be treated as a starting point.
For effective use, always execute 'make clean' before running 'make' from the "Shell" tab rather than clicking the green
"Run" button. Additionally, note that this makefile contains additional commands designed to rename generated *.c files
to *.cpp files, as the 'g++' compiler is employed instead of 'gcc'.
Entering command sequence for C++ manually:
//lex program : calc.l, yacc program : calc.y
$flex calc.l
$bison -dtv calc.y # use bison instead of yacc
$mv -f lex.yy.c lex.yy.cpp
$mv -f calc.tab.c calc.tab.cpp
g++ -c -std=c++11 lex.yy.cpp -lm
g++ -c -std=c++11 calc.tab.cpp -lm
g++ -o calc *.o -lstdc++ -lm
Expected Outputs
Expected Output example file (https://ucdenver.instructure.com/courses/558317/files/25872913?wrap=1)
(https://ucdenver.instructure.com/courses/558317/files/25872913/download?download_frd=1)
Your output should include, at least, all the test cases in the file
REPL Setup:
First, create a new REPL with "Bash", not a "C++" or "C".
Installing Flex: When you execute the 'flex' command for the first time from the REPL console, it will prompt you to
install flex. From the two available options, select the "flex" option.
Installing Bison/Yacc: Upon running the 'bison' or 'yacc' command from the REPL console, you will be prompted to
install a bison/yacc application. Select the "yacc" option, not 'bison_3_5'. The current REPL version encounters
installation issues with the 'bison_3_5' application for reasons unknown to us.
In Case that Bison_3_5 has been installed:
If you have installed bison_3_5 already, perform the following steps to fix the issue:
1. Click on the three dots (the "more" icon) located in the File Navigation window s leftmost column.
2. Choose "Show hidden ..." (the last option in the list). This will show all hidden files.
3. In the File Navigation window s lower section, locate the "replit.nix" file.
Homework 3: Tiny Calculator parsing with YACC/Bison)
%23view_name%3Dmon 5/7
4. This file holds your REPL configuration information. Within the 'deps = [ .... ]' section, if an entry for the
"pkgs.bison_3_5" instance is present, manually remove the line.
5. Run the "bison -dtv <your yacc code>.y" command from the command line window, ensuring you choose the
"yacc" option this time.
Note: For our assignment s intent, "yacc" is equally good as "bison".
Deliverable
Read the rubric first before you submit it. Submit the following items:
(f)lex and yacc/bison source codes. Please submit two sets of identical files - one with the original source code files and the
other with *.txt extensions for my review.
An output file demonstrating the test results, which cover the operations in the Expected Output section above.
A readme.md containing:
the answers to the comparison task from Step 3 in the "ToDo" list
BNF grammar rules and program documentation
Or
REPL "join" link containing
flex and bison source codes
The output file with your test results covers at least the operations in the Expected Output section above.
readme.md file for answering the tasks and the BNF documentation of your program
Extra Credit (Your own project): up to 10 points
Can you think of any project you have worked on or would work on in the future where yacc/lex can help to simplify a front-end
interface? Submit:
A one-page proposal with a synopsis of the project that describes how the lex/yacc tool would help your project.
(f)lex and yacc/bison source code and output demonstrating implementation of the project.
View Rubric
HW3 Bison - Tiny Calculator
Criteria Points
Description of
criterion
/5 pts
why_bison
Using this assignment as example, describe the tasks that could not be done or were
extremely difficult to implement if flex alone were used.
5 pts
Homework 3: Tiny Calculator parsing with YACC/Bison)
%23view_name%3Dmon 6/7
Choose a submission type
Bison
Implementation
/40 pts
Rules
/5 pts
Extra credit
/0 pts
Bison Implementation
- General arithmetic operations completeness: 10
* -2 if not displaying calculation number
- Precedence and association of operators: 5
* -2 if unary sign precedence (+/-) is not properly handled
- Handling variables correctly: 10 points
* -3 if no variable update message is displayed
* -3 if the variable output is not properly displayed
- Interworking with flex: 5 points
- Error handling: 10 points
* -2 if not check if a referenced variable is defined or not
* -3 if no DBZ check
* -2 if displaying output when there is an error
40 pts
Rules
- Correctly listing all the rules (productions)
5 pts
Extra Credit
- Proposal: 2
- Completeness of implementation: 8
0 pts
Text Web URL Upload More
Submit Assignment
Homework 3: Tiny Calculator parsing with YACC/Bison)
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
