Compiler Design with Flex and Bison
Reg. No. ……………… Name: …………………………………………….
Reg. No. ……………… Name:………………………………………………
Course: Compiler Design
Duration: 3 Hours
Tools: Flex, Bison, GCC (Linux/WSL/Ubuntu)
Lab Overview
Learning Objectives:
Write Flex specifications using regular expressions to tokenize source input
Write Bison grammars in BNF to parse context-free languages
Combine both tools to build a fully functional expression evaluator
Handle operator precedence, associativity, and basic error reporting
Construct a working arithmetic expression compiler.
Environment Setup
Installation
Run the following on Ubuntu terminal to confirm the presence of Flex, Bison and C/C++
compiler in your system.
flex --version
bison --version
gcc --version
If they are not installed, then run the following commands.
sudo apt update
sudo apt install flex bison gcc build-essential -y
Part 1 — Flex: The Lexical Analyzer
Concept
Flex reads a .l file containing regular expression rules and generates a C function yylex() that
scans input and returns tokens — the smallest meaningful units of a language (keywords,
numbers, operators, etc.).
A Flex file has three sections separated by %%:
[Definitions]
%%
[Rules: regex { action }]
%%
[User code]
Exercise 1.1 — Scanning
All the files and folders created in this Lab should be inside a directory named lab2. Within it,
create a new directory, name it ex1. Inside it, create the file ex1.l:
Terminal commands:
In your terminal, go into the course directory and run these commands successively
# Create the lab2 folder
mkdir lab2
# Go into lab2 folder/directory
cd lab2
ls
# Create the ex1 folder/directory
mkdir ex1
# Go into the ex1 directory
cd ex1
ls
# Create the ex1.l file
touch ex1.l
ls
# Go back to the parentdirectory (lab2)
cd ..
# Launch VS code
code .
VS Code will launch withing the lab2 directory.
Type the following code into ex1.l
%{
#include <stdio.h>
%}
%%
[0-9]+ { printf("INTEGER: %s\n", yytext); }
[a-zA-Z][a-zA-Z0-9]* { printf("IDENTIFIER: %s\n", yytext); }
"+" { printf("PLUS\n"); }
"-" { printf("MINUS\n"); }
"*" { printf("MULTIPLY\n"); }
"/" { printf("DIVIDE\n"); }
"=" { printf("ASSIGN\n"); }
[ \t\n] ; /* skip whitespace */
. { printf("UNKNOWN: %s\n", yytext); }
%%
int main() {
yylex();
return 0;
}
int yywrap() {
return 1;
}
Compile and run:
From the terminal, while in ex1 directory, run the following commands.
ls
flex ex1.l
ls
gcc [Link].c -o ex1 -lfl
echo "x = 10 + y * 3" | ./ex1
Expected output:
IDENTIFIER: x
ASSIGN
INTEGER: 10
PLUS
IDENTIFIER: y
MULTIPLY
INTEGER: 3
Explanations for the code and commands
int main() {
yylex();
return 0;
}
int main()
Every C program requires a main() function to execute. In a standalone Flex program, this is the
entry point. When you run ./ex1, the operating system calls main().
yylex()
This is the core function generated by Flex. When you run flex ex1.l, Flex translates all your
regular expressions into a giant C function called yylex() inside [Link]+1
When main() calls yylex(), the following happens:
1. yylex() starts reading from the standard input stream (by default, stdin, though it can
be changed by pointing the yyin file pointer to a different file).
2. It reads characters one by one and buffers them.
3. It compares the buffered characters against the regular expressions you wrote in the Rules
section.
4. When it finds a match, it executes the corresponding C action (e.g., printing the token).
5. It continues looping, scanning, and matching until it hits the End-of-File (EOF) character.
int yywrap() {
return 1;
}
yywrap()
yywrap() is a callback function that yylex() automatically calls when it reaches the end of the
input file (EOF).
Its purpose is to tell the scanner what to do next:
return 1: Tells yylex() that there is no more input. Scanning is completely finished,
and yylex() should return back to main(), allowing the program to exit.
return 0: Tells yylex() that the programmer has opened a new file and pointed the
yyin variable to it. yylex() will then seamlessly continue scanning the new file without
interrupting the program. This is useful for compilers that need to scan multiple files at
once (like #include files).
If you do not define yywrap(), the C compiler (GCC) will throw a "linker error" because
yylex() expects the function to exist. Alternatively, you can omit writing this function by either
compiling with the -lfl flag (which links a default Flex library containing yywrap()) or by
putting %option noyywrap at the top of your .l file.
Commands:
flex ex1.l
This command runs the Flex (Fast Lexical Analyzer) generator on the specification file ex1.l.
flex: Invokes the Flex compiler.
ex1.l: This is the input file containing your regular expressions and C actions (the rules for
tokenizing the input).
Flex reads the .l file and automatically generates a C source file named [Link].c in the same
directory.
What is inside [Link].c? It contains a massive C function called yylex(), which is a
deterministic finite automaton (DFA) constructed from the regular expressions you wrote. This
function is capable of reading a character stream, matching patterns, and executing your C code
blocks when a match is [Link].
gcc [Link].c -o ex1 -lfl
This compiles the C code generated by Flex into a runnable executable file.
gcc: The GNU C Compiler, used to compile C code into machine code.
[Link].c: The C source file that was just generated by Flex in the previous step.
-o ex1: The output flag. It tells GCC to name the resulting executable program ex1 instead of
the default [Link].
-lfl: The linker flag that links the Flex Library (libfl) to your program.
Why -lfl? By default, Flex programs require a function called yywrap() to know what to do
when they reach the end of an input file. The Flex library provides a default implementation of
yywrap() (which just returns 1, meaning "stop reading"). It also provides a default main()
function if you didn't write one. Without -lfl, the GCC linker would throw an "undefined
reference" [Link]+1
echo "x = 10 + y * 3" | ./ex1
This executes the compiled program (ex1) and feeds it a mathematical expression as input.
echo "x = 10 + y * 3": The echo command prints the string "x = 10 + y * 3" to
standard output.
| (The Pipe): In Unix/Linux, the pipe operator takes the standard output (stdout) of the
command on the left and connects it directly to the standard input (stdin) of the command on the
right.
./ex1: Runs your compiled lexical analyzer. The ./ tells the system to look for the executable
in the current directory.
Because of the pipe, your scanner doesn't wait for you to type input on the keyboard. It
immediately reads x = 10 + y * 3 as if it were a file. The yylex() function inside
./ex1 scans this string character by character, matches it against the regex rules defined in
ex1.l, prints out the tokens (e.g., IDENTIFIER: x, ASSIGN, INTEGER: 10), and then
terminates when it hits the end of the string.
Exercise 1.1 Screenshots 📸
Take a screenshot of your terminal showing the execution of the commands above and the
outputs. Paste the screenshot below.
Exercise 1.2 — Keyword Recognition
Real languages have reserved keywords like if, while, int.
Keywords must be matched before identifiers. Create a directory named ex2 (in lab2), within it
create the file ex2.l:
mkdir ex2 # while in lab2
cd ex2
tourch ex2.l
Type in the following code into ex2.l
%{
#include <stdio.h>
%}
%%
"if" { printf("KEYWORD: if\n"); }
"while" { printf("KEYWORD: while\n"); }
"int" { printf("KEYWORD: int\n"); }
"float" { printf("KEYWORD: float\n"); }
[a-zA-Z][a-zA-Z0-9]* { printf("IDENTIFIER: %s\n", yytext); }
[0-9]+\.[0-9]+ { printf("FLOAT: %s\n", yytext); }
[0-9]+ { printf("INTEGER: %s\n", yytext); }
[ \t\n] ;
. { printf("SYMBOL: %s\n", yytext); }
%%
int main() {
yylex();
return 0;
}
int yywrap() {
return 1;
}
Save the file and run the following commands (while in ex2):
ls
flex ex2.l
ls
gcc [Link].c -o ex2 -lfl
ls
echo "int x = 5; if x while float y" | ./ex2
echo "int x = 5; if x while float y" | ./ex2
This command tests the lexical analyzer (scanner) program ex2 by feeding it a deliberately
nonsensical string of C-like code to see how it categorizes the tokens.
1. echo "int x = 5; if x while float y"
The echo command simply prints the exact string "int x = 5; if x while float y" to the
standard output. Notice that this is not valid C syntax—it is just a random sequence of keywords,
identifiers, numbers, and symbols. The scanner doesn't care about grammar or logic; its only job
is to recognize individual words.
2. | (The Pipe)
The pipe takes the string printed by echo and sends it directly into the standard input of the next
command, rather than displaying it on your screen.
3. ./ex2
This executes your compiled Flex program ex2
How ex2 Processes the Input:
When ./ex2 runs, the yylex() function scans the piped string from left to right, matching the
longest possible chunks of text against your regular expressions.
Here is exactly how it will tokenize the input string:
1. "int" $\rightarrow$ Matches the exact keyword rule. Outputs: KEYWORD: int
2. " " $\rightarrow$ Matches the whitespace rule [ \t\n]. Action: do nothing (skip).
3. "x" $\rightarrow$ Matches the identifier rule [a-zA-Z][a-zA-Z0-9]*. Outputs:
IDENTIFIER: x
4. " " $\rightarrow$ Skipped.
5. "=" $\rightarrow$ Doesn't match any specific word rule, falls to the catch-all . rule.
Outputs: SYMBOL: =
6. " " $\rightarrow$ Skipped.
7. "5" $\rightarrow$ Matches the integer rule [0-9]+. Outputs: INTEGER: 5
8. ";" $\rightarrow$ Falls to the catch-all . rule. Outputs: SYMBOL: ;
9. " " $\rightarrow$ Skipped.
10. "if" $\rightarrow$ Matches keyword rule. Outputs: KEYWORD: if
11. " " $\rightarrow$ Skipped.
12. "x" $\rightarrow$ Matches identifier rule. Outputs: IDENTIFIER: x
13. " " $\rightarrow$ Skipped.
14. "while" $\rightarrow$ Matches keyword rule. Outputs: KEYWORD: while
15. " " $\rightarrow$ Skipped.
16. "float" $\rightarrow$ Matches keyword rule. Outputs: KEYWORD: float
17. " " $\rightarrow$ Skipped.
18. "y" $\rightarrow$ Matches identifier rule. Outputs: IDENTIFIER: y
This specific test string highlights a crucial concept in compiler design: Lexical analysis vs.
Syntax analysis.
Your scanner (./ex2) will perfectly categorize every token in this string without throwing any
errors, even though if x while float y is complete gibberish in C. This shows that the
Lexical Analyzer (Flex) only cares about vocabulary (spelling). It is up to the Syntax Analyzer
(Bison) in the next phase of the compiler to care about grammar (sentence structure) and catch
the syntax error.
Exercise 1.2 Screenshots 📸
Take a screenshot of your terminal showing the execution of the commands above and the
outputs. Paste the screenshot below.
Exercise 1.3 — Line and Column Counting
Token position tracking is critical for error messages. Within lab2 directory create a ex3 folder
and put a file ex3.l inside it. Type the following code in ex3.l.
%{
#include <stdio.h>
int line_num = 1;
int col_num = 1;
%}
%%
\n { line_num++; col_num = 1; }
[ \t]+ { col_num += yyleng; }
[0-9]+ {
printf("INTEGER '%s' at line %d, col %d\n",
yytext, line_num, col_num);
col_num += yyleng;
}
[a-zA-Z][a-zA-Z0-9]* {
printf("IDENT '%s' at line %d, col %d\n",
yytext, line_num, col_num);
col_num += yyleng;
}
. { col_num++; }
%%
int main() {
yylex();
return 0;
}
int yywrap() {
return 1;
}
flex ex3.l
ls
gcc [Link].c -o ex3 -lfl
printf "x = 10\ny = 20 + x" | ./ex3
yyleng is a built-in Flex variable that holds the length of the current match — useful for
advancing column counters.
Part 2 — Bison: The Parser
Concept
Bison reads a .y file with a BNF context-free grammar and generates an LALR(1) parser
function yyparse(). When a grammar rule is fully matched (reduced), Bison executes its
associated C semantic action.
A Bison file also has three sections:
[Declarations: tokens, types, precedence]
%%
[Grammar rules with semantic actions]
%%
[User code]
The $$ symbol refers to the left-hand side value; $1, $2, $3 refer to the right-hand side
components in order.
Exercise 2.1 — A Simple Expression Parser
Create new directory ex4 in lab2. Create a file ex4.y within ex4.
ex4.y is a parser for basic addition expressions:
Put the following code in ex4.y
%{
#include <stdio.h>
void yyerror(const char *s);
int yylex();
%}
%token NUMBER
%%
input:
expr '\n' { printf("Result: %d\n", $1); }
;
expr:
expr '+' NUMBER { $$ = $1 + $3; }
| NUMBER { $$ = $1; }
;
%%
#include <ctype.h>
int yylex() {
int c;
while ((c = getchar()) == ' '); /* skip spaces */
if (isdigit(c)) {
yylval = c - '0';
return NUMBER;
}
return c; /* return operator as-is */
}
void yyerror(const char *s) {
fprintf(stderr, "Error: %s\n", s);
}
int main() {
yyparse();
return 0;
}
Ls
bison -d ex4.y
ls
gcc [Link].c -o ex4
ls
echo "3 + 5 + 2" | ./ex4
Expected output: Result: 10
The -d flag tells Bison to generate [Link].h — the header with token definitions that Flex will
later include.
Exercise 2.1 Screenshots 📸
Take a screenshot of your terminal showing the execution of the Bison and echo commands
above and their outputs. Paste the screenshot below.
Exercise 2.2 — Operator Precedence and Associativity
A critical concept in parsing arithmetic is that * binds more tightly than +, and operators
associate left-to-right. Bison handles this with precedence declarations so you don't have to
restructure your grammar.
Create ex5 directory. Within it create ex5.y:
%{
#include <stdio.h>
void yyerror(const char *s);
int yylex();
%}
%token NUMBER
/* Precedence: lowest to highest */
%left '+' '-'
%left '*' '/'
%right UMINUS /* unary minus — highest */
%%
input:
expr '\n' { printf("= %d\n", $1); }
;
expr:
expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr {
if ($3 == 0) { yyerror("Division by zero"); $$ = 0; }
else $$ = $1 / $3;
}
| '-' expr %prec UMINUS { $$ = -$2; }
| '(' expr ')' { $$ = $2; }
| NUMBER { $$ = $1; }
;
%%
#include <ctype.h>
int yylex() {
int c;
while ((c = getchar()) == ' ');
if (isdigit(c)) {
yylval = c - '0';
return NUMBER;
}
return c;
}
void yyerror(const char *s) {
fprintf(stderr, "Parse error: %s\n", s);
}
int main() {
yyparse();
return 0;
}
Run these commands in the terminal
ls
bison -d ex5.y
ls
gcc [Link].c -o ex5
ls
echo "2 + 3 * 4" | ./ex5 # Should give 14, not 20
echo "(2 + 3) * 4" | ./ex5 # Should give 20
Exercise 2.2 Screenshots 📸
Take a screenshot of your terminal showing the execution of the Bison and echo commands
above and the outputs. Paste the screenshot below.
Exercise 2.3 — Error Recovery
Good compilers report all errors — not just the first one. Bison has a built-in error token for
recovery. Modify ex5.y grammar rules:
input:
expr '\n' { printf("= %d\n", $1); }
| error '\n' {
fprintf(stderr, "Skipping bad expression\n");
yyerrok; /* reset error state */
}
;
The yyerrok macro resets the parser after error recovery so it can continue parsing subsequent
lines. Rebuild and test:
Run this command
ls
bison -d ex5.y
ls
gcc [Link].c -o ex5
ls
printf "2 + 3\nbad %%% input\n" | ./ex5
You should observe that the parser reports the error on some lines (line 2) but still successfully
evaluates other lines.
This output demonstrates Bison's built-in error recovery mechanism.
What happens when we piped the two-line string into ./ex5.
printf "2 + 3\nbad %%% input\n" | ./ex5
The Input String
The printf command sends twoseparate lines of text, separated by newline (\n) characters:
1. 2 + 3
2. bad %%% input
Line 1: 2 + 3
The lexer reads the numbers and the plus sign. The parser recognizes this as a valid expr,
calculates the result, and prints:
= 5
Line 2: bad %%% input
The lexer reads the characters b, a, d, %, %, etc., and sends them to the parser.
The parser looks at its grammar rules and realizes that bad (which the lexer likely sent as
individual unrecognized character tokens) does not match any valid mathematical expression
rule.
When Bison encounters a token it doesn't expect, it immediately:
1. Triggers a syntax error.
2. Automatically calls the yyerror() function you wrote in the C code section.
This is why you see:
Parse error: syntax error (This is printed by your fprintf(stderr, "Parse error: %s\
n", s); inside yyerror).
The Error Recovery Phase:
Normally, a parser would crash and exit immediately upon hitting a syntax error. However, in
ex5.y, we added this specific rule to the input non-terminal:
input:
expr '\n' { printf("= %d\n", $1); }
| error '\n' {
fprintf(stderr, "Skipping bad expression\n");
yyerrok;
}
;
Bison has a special built-in token called error. When the parser realizes the input is invalid, it
discards tokens from the stack until it reaches a state where the error token is valid.
In our rule, the parser essentially says: "I will throw away all this garbage input until I see a
newline (\n)."
Once it hits the \n at the end of bad %%% input, it executes the semantic action attached to the
error rule, which prints:
Skipping bad expression
Then, it runs the yyerrok macro. This tells Bison to clear its error state and resume parsing
normally.
This exercise shows that compilers shouldn't just crash on the first typo. By using the error
token, a compiler can report an error on line 10, skip the rest of that broken statement, and
continue parsing line 11 so it can report all errors in the file at once.
Exercise 2.3 Screenshots 📸
Take a screenshot of your terminal showing the execution of the commands executed in this
exercise and the outputs. Paste the screenshot below.
Part 3 — Full Integration: A Working Calculator
Now we combine Flex and Bison into a multi-line calculator that supports variables, all four
arithmetic operators, and parentheses.
File Structure
Within the lab2 folder, create another directory named calculator. Within this new directory
create two files, calc.l and calc.y
calculator/
├── calc.l (Flex scanner)
├── calc.y (Bison parser)
└── Makefile
We will use the Makefile to automate the build process. When building a compiler, you have multiple steps: running
Bison, running Flex, and finally compiling the generated C files into an executable. Doing this manually every time
you change a file gets tedious.
A Makefile is a script that the make utility reads to figure out how to compile and link a program.
Step 3.1 — The Bison Grammar: calc.y
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void yyerror(const char *s);
int yylex();
/* Simple variable store: a-z */
double vars[26];
%}
%union {
double dval;
int vindex; /* variable index 0-25 */
}
%token <dval> NUMBER
%token <vindex> VAR
%token NEWLINE
%type <dval> expr
%left '+' '-'
%left '*' '/'
%right UMINUS
%%
program:
/* empty */
| program statement
;
statement:
NEWLINE
| expr NEWLINE { printf("\t= %.6g\n", $1); }
| VAR '=' expr NEWLINE {
vars[$1] = $3;
printf("\t%c = %.6g\n", $1 + 'a', $3);
}
| error NEWLINE { yyerrok; }
;
expr:
expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr {
if ($3 == 0.0)
yyerror("Division by zero");
else
$$ = $1 / $3;
}
| '-' expr %prec UMINUS { $$ = -$2; }
| '(' expr ')' { $$ = $2; }
| NUMBER { $$ = $1; }
| VAR { $$ = vars[$1]; }
;
%%
void yyerror(const char *s) {
fprintf(stderr, " Error: %s\n", s);
}
int main() {
printf("Calculator — type expressions, e.g. x = 5 + 3\n");
printf("Variables a-z supported. Ctrl+D to exit.\n\n");
return yyparse();
}
Step 3.2 — The Flex Scanner: calc.l
%{
#include "[Link].h" /* Bison-generated token definitions */
#include <stdlib.h>
void yyerror(const char *s);
%}
%%
[0-9]+(\.[0-9]*)? { [Link] = atof(yytext); return NUMBER; }
[a-z] { [Link] = yytext[0] - 'a'; return VAR; }
"+" { return '+'; }
"-" { return '-'; }
"*" { return '*'; }
"/" { return '/'; }
"(" { return '('; }
")" { return ')'; }
"=" { return '='; }
\n { return NEWLINE; }
[ \t] ; /* skip spaces and tabs */
. {
yyerror("Unknown character");
}
%%
int yywrap() {
return 1;
}
Step 3.3 — The Makefile
makefile
all: calc
calc: calc.l calc.y
bison -d calc.y
flex calc.l
gcc [Link].c [Link].c -o calc -lm
clean:
rm -f [Link].c [Link].c [Link].h calc
Build and run:
make
ls
./calc
Test session:
Calculator — type expressions, e.g. x = 5 + 3
Variables a-z supported. Ctrl+D to exit.
x = 10 + 5
x = 15
y=x*2-3
y = 27
(x + y) / 3
= 14
z = -x + y * 2
z = 44
10 / 0
Error: Division by zero
Part 3 Screenshots 📸
Take a screenshot of your terminal showing the execution of the commands executed in this
exercise (Part 3) and the outputs. Paste the screenshot below.
Step 3.4 — Understanding the %union Directive
The %union block is how Bison handles tokens that carry different value types (integers vs.
strings vs. floats).
%union {
double dval; /* for NUMBER tokens */
int vindex; /* for VAR tokens (index into vars[]) */
}
%token <dval> NUMBER — means NUMBER carries a double
%token <vindex> VAR — means VAR carries an int
%type <dval> expr — means the expr non-terminal produces a double
In Flex, you set these values via [Link] and [Link] before returning the token.
In Bison actions, $1, $2 etc. automatically use the correct union member.
Lab Assessment Exercises
Complete these before submitting:
1. Add a % (modulo) operator to the calculator for integer division remainder.
rebuild and run y = 56 % 5
make
ls
./calc
y = 56 % 5
Provide the screenshot.
2. Add a ^ (power) operator using the C pow() function from <math.h>. Think carefully —
should it be %left or %right?
rebuild and run i = 2 + 5^5
make
ls
./calc
i = 2 + 5^5
Provide the screenshot.