scanner specifications and parser specifications for the C_flat language

Follow the specifications: scanner specifications and parser specifications for the C_flat language. You are given the scanner code, but should make sure it is working before using it in your overall project. The scanner is given in the cfScannerDrJ.l file. The tokens file is also given file: cfTokensDrJ.y. Read the specifications and the Yacc-Flex book and tutorial for the purpose of the .y file.

You are also given a how-to-build-a-scanner document and a sample project: microscanner. **ATTACH A VIDEO SHOWING HOW TO DO THIS..LIKE CREATE FLEX AND YAAC ALSO ATTACH A VIDEO SHOWING WHILE RUNNING THE PROGRAM***

IM REQUESTING THIS…COZ ITS MY FIRST TIME AND I DONT KNOW HOW TO DO THIS..PLEase

How To Build a Flex/Yacc-Related Project in Visual Studio 2022
It has been shown that for each regular expression that denotes a regular language, L, there is
a corresponding finite state machine, M, that recognizes L, i.e., L = L(M). When one finds the
need to search for substrings within a given string, regular expressions can be used to specify
the set of sought-after strings and the corresponding machine can be used to recognize
substrings within a given string by indicating all occurrences. For example, a text-file might be
viewed as a given string and we may want to find all of occurrences of each substring within a
set of substrings. In compilers, scanners read text-files and identify lexemes or tokens and
return a corresponding code to the calling routine, such as a parser. Another example is that of
a user who is looking for all occurrences of a particular string.
Background
The operational semantics of deterministic finite automata (DFA) can be realized as a program
written on a computational model, such as a RAM-machine. To run the “engine” of a machine,
M, a string, α, is required as input. At the most simplest form, the DFA engine returns yes or no
when the input string is recognized or not, respectively. If looking for a substring α within a string
β, the latter string β must also be supplied. Sometimes more actions or information is needed,
such as the position of the substrings found, the length of substring found, the type of substring
found, etc.
EXAMPLE 1: Suppose that you have a regular expression: “a | bc”. This represents the
language { a, bc }. A machine generator such as flex/lex might generate a machine, M, such
that L = L(M), such as the one depicted below.
c
b
a
Suppose that we run the “engine” using M and using the string α = “bc”; the engine reports yes
(i.e. α ∈ L). If we run the “engine” using M and using the string α = “ac”, the engine reports no.
Besides providing the engine with one input string parameter that is tested for membership in
the language that the corresponding regular language denotes, one can also build engines that
accept a machine augmented with actions that are associated with at least one state (usually a
final state) and one input string, say β, is searched from left-to-right for any of the strings of the
language denoted by the regular expressions. When a match occurs, the action is executed.
Using the same machine above, one may augment the machine M with actions such as ones to
output a 1 when a substring “a” is found in a string β and output a 2 when a “bc” is found in a
string β. When a match occurs, the corresponding number is appended to an output string
which is initially empty. When reading the input string and no match occurs the machine can
output an error signal or simply ignore the string and read past it. After a substring is found and
the corresponding action is executed, such outputting a value, the machine is restarted and
Using Regular Expression Tool, flex, and Parser Tool, yacc, in Visual Studio 2022 IDE
Page 1 of 6
reading continues at the point in the overall string at the symbol immediately following the
recognized substring.
EXAMPLE 2: Consider the string β = aabcbcabcaa. The corresponding output would be: 1 1 2 2
1 2 1 1. Note that this models a stimulus-response behavior used in many cognitive models.
c
b
a
Code to Output 2 or
return a code 2 to calling function.
Code to Output 1 or
return a code 1 to calling function.
If a string β = aabccbca were given, depending on the machine actions, one could either ignore
the extra “c” or report an error. One could have the following respective outputs for β:


11221
1 1 2 err 2 1
The output that is used depends on the application. For example, the first output string that
ignores an unrecognized substring could be used while searching for occurrences of substrings
in a find operation in a text editor or a search for a file name in an operating system file system.
The second output string could be used by a scanner in a compiler. In this case, the string β is
the source file. The scanner does the work of matching lexemes and tokens and the parser
would use the output codes.
Visual Studio Project Settings and Steps to Create an “.exe” for the “Engine” of a DFA
The following steps show how to build an executable file that represents a finite state
automaton, M, such that L(M) = L, from a set of regular expressions that denote a regular
language L, and an “engine” that runs the machine given an input string. One starts with a textfile containing regular expressions written in a meta-language that flex/lex parses. The program
flex/lex translates the set of regular expressions into a DFA, M. This machine M along with the
DFA engine is implemented in C. This C code has to be translated to an object file, which is
then linked with appropriate libraries by linker. The linker generates the executable file. At this
point the executable file can be run. The program accepts strings as input and the program
indicates whether the string is a match or not a match.
When using flex we must provide a text-file whose name ends with extension (suffix) “.l” whose
contents consists of a set of regular expressions along with their corresponding actions, where
the actions are expressed as legal C code fragments. These regular expressions comprise the
middle section of three sections. (The sections are delimited with “%%” strings.) The first section
may contain definitions (names) of regular expressions and supporting functions written in C.
The last section may only contain supporting C code.
Using Regular Expression Tool, flex, and Parser Tool, yacc, in Visual Studio 2022 IDE
Page 2 of 6
Overall, we have the following dataflow:
Examples: tokens.y or
holds %token
definitions
yacc.exe -d
y.tab.c
for full parser, this
holds production rules
VS C/C++ compiler
y.tab.h is
#include’d in lex.yy.c
and y.tab.c
y.tab.h
y.tab.obj
regexpr.l
flex.exe
regular expressions
denoting language
L
lex.yy.c
VS C/C++ compiler
Visual Studio
default runtime
and other libraries
libfl.a
lex.yy.obj
Visual Studio
Linker
α∈L
projectname.exe
α∉L
DFA M such that L
= L(M)
α = a1a2…an
Using Regular Expression Tool, flex, and Parser Tool, yacc, in Visual Studio 2022 IDE
Page 3 of 6
1. To begin, create a Visual Studio Solution for a homework assignment or project. For
example, suppose the solution name is CS435Project.
2. If it is a homework assignment with several problems, it is best to create a solution and
then a separate project for each homework problem. Note that this structure is not a
requirement; instead, you may choose to have a separate solution for each problem in a
given assignment.
3. To create a new flex (.l) file or yacc (.y) file you can use Visual Studio editor or your
favorite text editor, such as notepad, textpad, etc. If using VS, create a new item and
choose a utility file->text file, name it and remove the .txt and put in extension of .l for a
flex file or .y for yacc file. Make sure the file has the proper extension name. For this
example, assume the full filename of regexpr.l. Make sure it is saved or copied into the
project folder that contains or will contain your C source code files.
4. Add regexpr.l file (and, if need, the .y file) to the project under the source folder (really a
filter rather than a folder) even though it is a “utility” file.
5. Choose Project Properties.
6. Expand Build Events and select Pre-Build Event. In the command line type box type flex
regexpr.l. You may need to modify the path to the flex.exe file. For example, the flex.exe
file could be in the parent folder of the current project folder. (Remember that “..” in a
path name means the parent folder.)
Using Regular Expression Tool, flex, and Parser Tool, yacc, in Visual Studio 2022 IDE
Page 4 of 6
Optional: If you are generating the token names from yacc input file your command line would
look like this: yacc -d tokens.y & flex regexpr.l. The ampersand means: do the first command,
and then, start the second command. The yacc command with option –d means to generate a
header file, y.tab.h, that contains several #defines that allow for mnemonic (symbolic names)
for token numbers. If you are only sending back a return value that need not be “named” from
the scanner to the caller (e.g., main(), then you don’t need the yacc command. When writing a
full parser using yacc one does need that command above.
7. Go to the project properties -> Linker -> Input and then add libfl.a to the Additional
Dependencies property slot. See below. If you have several projects in a solution, you
might want to put one libfl.a up one level; if so, then you may have to put “..\libfl.a”.
Again, remember that “..” in a path name means the parent folder.
Using Regular Expression Tool, flex, and Parser Tool, yacc, in Visual Studio 2022 IDE
Page 5 of 6
8. Because we are using some “old” C code that is generated by an “old” tool, make sure
that the following the safe exception handler code option is set to No.
9. Also, because of old “C” code, make sure that you have the following #pragma
statement in the “verbatim .l code”, which appears in the start of the code in the regexpr.l
file:
%{
#pragma warning(disable : 4996)
#include
#include
#include
#include “y.tab.h”
…
%}
10. The first time to create the lex.yy.c file you need to simply build the project without any .h
or .c files. The prebuild step will run and create the .c files and, if applicable the y.tab.h
file. You may get some warnings and usually they should be addressed. However, this
code is generated by flex and we have no control over what flex generates. We can go
into the lex.yy.c file and fix the code “by hand.” However, editing that code is tedious and
time-consuming and the code will work well enough for what is needed here.
11. Once the lex.yy.c is created add it to the source file folder in the project.
12. If yacc is used, add y.tab.h to the header file folder and y.tab.c to the source file folder.
13. Clean/Build/Re-Build the project again and now the preprocessor and C compiler will
include the y.tab.h file in corresponding .c files and will run once each for y.tab.c and
lex.yy.c. The linker will then link the object files and reference the appropriate libraries
and produce a .exe file.
Using Regular Expression Tool, flex, and Parser Tool, yacc, in Visual Studio 2022 IDE
Page 6 of 6
Project 4: Translator Project (Part B) Using Flex and Yacc
for the C♭ (C flat) Language
Parser Specifications
1
Overview of Project 4: C flat Parser
This document is a continuation of the specifications for a translator project that scans and parses a subset
of C, called C-flat, notated as C♭ . The translator is to be constructed with the compiler tools: flex and
yacc. Use the structure of Part A (scanner) for the flex and yacc input files as a guide. They will need to
be modified for this project.
You must replace the driver used to test your scanner; it is no longer needed. A sample driver for the
parser is shown in the body of this document. You should make minor changes, where appropriate to the
rest of your .l file. If you have a working scanner (regular expressions and actions work), then that second
section of the .l will need no changes or, perhaps, a few modifications.
Most of your work will be adding production rules to the second of three sections in your .y file. There
will be some additional code and yacc directives added to the first section of your .y file. Depending on how
you structure your verbatim C code, there may also be additional code needed in the third section of your
.y file.
2
What, When and Where to turn in
ˆ What to turn in: You must zip all files for your parser project. You must also include your files:
.l, .y, lex.yy.c, y.tab.h, y.tab.c, all *.obj files, and, of course, cfParserLastName.exe. Also,
include your test source files containing C♭ source code, their respective listings, and respective .txt
files containing redirected standard output of tokens. Name your .zip file: cfParserLastName.zip.
ˆ When and Where to turn in: Before the due date and time shown on the assessment link under the
Project Folder on Blackboard.
3
File and Command-Line Specifications
This section specifies the usage of the translator and the files needed by the user of translator, but does not
indicate the files needed for constructing the translator. First, the required user files and their descriptions
are provided. Finally, the command-line syntax and semantics are presented.
3.1
Files Used and Descriptions
Below are descriptions of all the files that will ultimately be used by the fully-completed version of the
translator. Since the translator will be developed incrementally the code listing file will not be used by the
scanner and parser. However, the files containing the source and source listing must be handled by both the
scanner and parser. The handling of the code listing file is to be added during the development of the code
generator.
The source listing file is always produced. After opening the source and listing files, the parser should be
invoked. (The parser calls yylex(); do not call yylex() directly.) The source listing file name that should
1
be the source filename with .cf replaced with .txt. To generalize, no matter what the suffix extension of
the source file, that extension should be replaced with .txt and, if there is no extension, .txt should be
appended.
1. Input Files:
(a) Source File: A text file containing a program written in C♭ source code. A user of C♭ supplies
the name of this file on a command-line. The file should have an extension of .cf. The C♭
translator has the responsibility of opening, scanning, parsing, and closing this file.
2. Output Files:
(a) Source Listing: This file is always produced and overwritten if it already exists. The contents
are a copy of the source file except with line numbers in starting in column 1. If there are any
scanner errors, you must indicate where the error occurs. At the end of the source listing you
must print on a separate lines the following:
Compilation Complete. ### errors reported.
Source Program = ### lines.
The ### is replaced with the actual number, right-justified. For syntax or lexical errors, print the
error message on a new line right below the source line where the error occurs. Note: for this part
of the project you are not expected to implement error recovery and should stop parsing as soon
as an error is discovered. Hence, this number representing errors reported will be either 0 or 1.
In the case of an error print the listing file, before the above summary, the following:
Parsing failed. Error on line: ### at lexeme.
For emphasis: stop after the first error found.
(b) Standard Output: Besides creating the source code file as described above, it is convenient to
print the same last two lines Compilation Complete. … or the error message for syntax or
lexical errors to standard output so that you do not have to open up the listing file to see the
results, especially during testing.
3.2
Command-Line Syntax
The command line syntax is as follows:
cfParserLastName.exe sourceFileName.cf
Of course, sourceFileName.cf is just a sample name; use the legal naming convention of Windows and
use .cf at the end. You can use Visual Studio to edit your test source code files. If you use notepad, save as ”all
files” with a .cf suffix. For each run, the listing file must be created and given the name sourceFileName.txt.
When you open this file connect yyin to the file descriptor. (See sample driver below.)
If no sourceFileName.cf argument is given, use standard input as the input file. You will set yyin to
stdin. In this case use yyin.txt as the listing file name. You can type your code directly from the keyboard
in this case. On Windows, you end the source input with a control-Z.
A sample parser driver (main) program is shown in the next section. This main program is only a
framework. Your main program must handle all arguments on the command line and open all appropriate
files as specified above and in Part A (cf scanner) project specifications.
2
4
Parser Driver
This code can be placed in the ”.l” file; it replaces the driver used for testing your scanner. You can
eliminate the mnemonic names of internal TOKEN names. Keep the other %token directives and %union
directives. You will add to them for the purpose of indicating associativity and precedence of operators. Look
at the your Lex/Yacc book for how to use %left, %right, and how to order your operators for indicating
precedence. Note that the #pragma warning(disable : 4996) is for the allowing legacy functions, which
are generated by flex.
Here is the code for the parser driver along with additional declarations and definitions of utility functions,
variables, and constants. You may need to change some of the file and string functions to names appropriate
for the dialect of the c compiler and libraries.
//For processing string literals
#pragma warning(disable : 4996)
#define MAX_STR_LIT_LEN 200
char buf[MAX_STR_LIT_LEN];
char *s;
//Utility for creating filenames based upon the source code name.
char *changeFileNameExtension(const char *src, const char* extName)
{
unsigned targetBodyNameLen = 0;
unsigned extNameLen = strlen(extName);
char *targetName = “”;
char * pch = strchr(src,’.’); //find last occurrence of . for extension name
if( pch != NULL){
targetBodyNameLen = pch-src;
}
else {
targetBodyNameLen = strlen(src)+1;
}
targetName = (char *)malloc(targetBodyNameLen+extNameLen+4);
targetName[targetBodyNameLen] = ’\0’;
strncpy(targetName, src, targetBodyNameLen);
targetName = strcat(targetName,”.”);
targetName = strcat(targetName, extName);
return targetName;
}
FILE *listingFile;
int lines;
main(int argc, char **argv)
{
int token;
char *infile;
char *listing;
errno_t fileErrorCode;
extern FILE *yyin;
extern FILE *listingFile;
extern int lines;
numerrors = 1;
if (argc>1) {
infile = _strdup(argv[1]);
3
printf(“Infile is %s\n”, infile);
if( (fileErrorCode = fopen_s(&yyin, infile, “r”)) != 0 ) {
fprintf(stderr,”Source file, %s, was not opened. Error code = %d\n”,
infile, fileErrorCode);
exit( fileErrorCode );
}
// if ((yyin = fopen(argv[1], “r”))==0) {
// fprintf(stderr, “Error opening source file: %s”, argv[1]);
// exit(1);
// }
}
else { infile = _strdup(“yyin”);
yyin = stdin;
}
listing = changeFileNameExtension(infile, “txt”);
if( (fileErrorCode = fopen_s(&listingFile, listing, “w”)) != 0 ) {
fprintf(stderr,”Listing file, %s, was not opened. Error code = %d\n”,
listing, fileErrorCode);
exit( 1 );
}
// if ((listingFile = fopen(listing, “w”))==0) {
// fprintf(stderr,”Listing file, %s, was not opened.\n”, listing);
// exit(1);
// }
lines = 1;
fprintf(listingFile, “%3d
“, lines);
if( !yyparse() )
{
printf(“\nCompilation Complete. 0 errors reported.\n”);
printf(“Source Program = %4d lines.\n”, lines);
fprintf(listingFile, “\nCompilation Complete. 0 errors reported.\n”);
fprintf(listingFile, “Source Program = %4d lines.\n”, lines);
fclose(yyin);
fclose(listingFile);
return 0;
}
else
{
printf(“\nParsing failed. Error on line: %i at %s\n”, lines, yytext);
fprintf(listingFile, “\nParsing failed. Error on line: %i at %s\n”, lines, yytext);
fclose(listingFile);
return 2; //arbitrary non-zero error number
}
}
4
5
C flat Token Specification
With the exception of scanf and printf as reserved words, the tokens for C♭ are the same as C89. In Part
A of this project (Project 3), a full scanner for C89 was required to be written. Even though only a subset
of tokens of C89 are utilized in C♭ , use the full C♭ (C89) scanner from Part A. This allows you to make
the least version your scanner. I strongly suggest that you use the token names from your scanner in the
production rules supplied to Yacc. If you use single character tokens in the Yacc syntax for the production
rules, you will have to make some minor changes to your scanner from Part A. For example, consider the
if statement. You can represent tokens with single character lexemes in the right-hand side of a production
rule as one of the two ways. For example:
or as
if LPAREN expression RPAREN statement
if ’(’ expression ’)’ statement
In the second approach, yacc scans the single character and there is no need for your scanner to return
a token LPAREN for left-parenthesis or RPAREN for a right-parenthesis. I think it’s best that you use the first
approach.
In whatever approach you take, remember to use the -d option for yacc so that y.tab.h is generated.
6
A Context-Free Grammar for C flat
The EBNF meta-syntax that is used below for the presentation of C♭ grammar uses the following conventions.
The nonterminals are all in italics. The ::= or -> operators that are typically used in BNF or EBNF are
replaced with the colon character, :. The right-hand-sides are indented and all right-hand-side alternatives
are written on separate lines. The non-italicized words are terminals. Moreover, the terminals are shown in
a typewriter-like font, such as INT_LITERAL. The subscript of opt indicates that the preceding non-terminal
is optional. Iteration of a non-terminal or terminal construct is expressed through recursive rules, usually
left-recursive, which are better than right-recursive for LALR(1) parser generators like Yacc.
Production rule syntax shown below needs to be modified for yacc and flex to properly build an LALR(1)
table-driven parser and table-driven DFA scanner for C♭ , respectively. This grammar must be modified so
that yacc will not give shift-reduce or reduce-reduce conflict errors. See your flex/yacc textbook and the
tutorial on Blackboard for approaches to resolve these conflicts and how to change the grammar. This is the
core task of this project. See the Hints section below for more about this topic.
Again, remember that C♭ is not a subset of C89 since scanf and printf statements are not reserved
words in C syntax. Many other semantic issues also show that C♭ is not a subset of C89, for example,
parameter passing semantics differ.
Some of the sentences generated by this grammar will be shown to be illegal semantically. For example,
the substring shown below is syntactically correct, but will have illegal semantics.
…
int x;
x = “abc”;
…
In C♭ , we will not be able to assign string literals to variables since there is not a string data type. Several
other examples can be cited. Once this parser is written and this project is completed, then compile-time
semantic errors will be considered in future projects.
HINTS: These productions are written to help you eliminate some reduce-reduce and shift-reduction
errors. Again, as mentioned above, this grammar must be modified so that yacc will not give shift-reduce
or reduce-reduce conflict errors.
Remember to convert productions with the optionalopt into two productions appropriately.
Remember that left-recursion is good and right-recursion is bad for bottom-up parsers, such as LALR(1)
parsers as generated by yacc.
5
Remember to give precedence and associativity to operators. You may leave all the tokens in your
scanner; their presence will not cause problems for the parser. Do not add any terminals other than what is
given.
Remember to convert all the dashes (-) into underscores (_) for the nonterminals for all productions
inside your .y file.
You will probably have shift-reduce errors or reduce-reduce errors as indicated by yacc. To see more
information about which productions are giving you problems add the -v option (which book calls flag) to
the yacc command line. This option has yacc produced a file called: y.output. (You still need -v option, so
the full option list for yacc should be: -dv option.) If you get these errors, you must revise the productions
to fix the shift-reduce and reduce-reduce errors, but do not revise the C♭ language from the one generated
by these productions given below.
6
C♭ Grammar:
C♭ -translation-unit:
external-decl-defn
C♭ -translation-unit external-decl-defn
external-decl-defn:
function-decl-defn
declaration
function-decl-defn:
declarator compound-statement
declaration-specifiers declarator compound-statement
declaration-list:
declaration
declaration-list declaration
declaration:
declaration-specifiers init-declarator-listopt ;
declaration-specifiers:
storage-class-specifier declaration-specifiersopt
type-specifier declaration-specifiersopt
type-qualifier declaration-specifiersopt
storage-class-specifier:
auto
static
extern
type-specifier:
int
unsigned
long
float
double
type-qualifier:
const
init-declarator-list:
init-declarator
init-declarator-list , init-declarator
init-declarator:
declarator
declarator initializer
initializer:
= expression
declarator:
IDENTIFIER
declarator ( )
7
declarator ( parameter-type-list )
declarator ( formal-parm-list )
declarator [ const-expression ]
declarator [ ]
formal-parm-list:
formal-parameter
formal-parm-list , formal-parameter
formal-parameter:
type-specifier-list IDENTIFIER
parameter-type-list:
type-specifier-list
parameter-type-list , type-specifier-list
type-specifier-list:
type-specifier
type-specifier-list type-specifier
identifier-list:
IDENTIFIER
identifier-list , IDENTIFIER
statement-list:
statement
statement-list statement
compound-statement:
{ declaration-listopt statement-listopt }
statement:
compound-statement
if ( expression ) statement
if ( expression ) statement else statement
while ( expression ) statement
return ;
return expression ;
expression ;
;
expression-list:
expression
expression-list , expression
const-expression:
conditional-expr
expression:
conditional-expr
unary-expr assignment-op expression
assignment-op:
=
+=
-=
8
*=
\=
conditional-expr:
logical-or-expr
logical-or-expr:
logical-and-expr
logical-or-expr || logical-and-expr
logical-and-expr:
equality-expr
logical-and-expr && equality-expr
equality-expr:
relational-expr
equality-expr == relational-expr
equality-expr != relational-expr
relational-expr:
add-expr
relational-expr < add-expr relational-expr > add-expr
relational-expr = add-expr
add-expr:
mult-expr
add-expr + mult-expr
add-expr – mult-expr
mult-expr:
unary-expr
mult-expr * unary-expr
mult-expr / unary-expr
mult-expr % unary-expr
unary-expr:
postfix-expr
++ unary-expr
— unary-expr
– unary-expr
+ unary-expr
! unary-expr
postfix-expr:
primary-expr
primary-expr [ expression ]
scanf ( identifier-list )
printf ( expression-list )
primary-expr ( expression-listopt )
postfix-expr ++
postfix-expr —
9
primary-expr:
IDENTIFIER
REAL_LITERAL
INT_LITERAL
STR_LITERAL
( expression )
7
Some Examples
Test03.cf:
unsigned int f(int);
float add(int x, double y) {
return x + y;
}
int main()
{
int x;
int y;
printf(x + y, add(x, y));
return 0;
}
Test03.txt:
1
unsigned int f(int);
2
float add(int x, double y) {
3
return x + y;
4
}
5
6
int main()
7
{
8
int x;
9
int y;
10
printf(x + y, add(x, y));
11
return 0;
12
}
Compilation Complete. 0 errors reported.
Source Program =
12 lines.
Test03err.cf:
unsigned int f(int);
float add(int x, double y) {
return x + y;
}
int main()
{
int x;
10
int y;
printf(x + y, add(x, y);
return 0;
}
Test03err.txt:
1
unsigned int f(int);
2
float add(int x, double y) {
3
return x + y;
4
}
5
6
int main()
7
{
8
int x;
9
int y;
10
printf(x + y, add(x, y);
Parsing failed. Error on line: 10 at ;
Test08.cf:
unsigned int f(int);
float add(int x, double y) {
return x + y;
}
int main()
{
int max = 200;
int a[200];
int x;
int y;
unsigned i = 0;
scanf( x, y);
while( i < MAX ) { a[i++] = 0; } i = 0; while( i < MAX ) { a[i] = x + y; scanf( x, y); i++; }; if( i > 0 ) {
printf( a[i]/ i );
}
else {
printf(“i