Assigned: Friday, 25 August 2023.

Due: Thursday, september 21, 2023 by 11：59 pm on Gradescope.

1    Introduction

I will start with a high-level description of the project in this section. In subsequent sections, I will go into a detailed description of the requirements and how to go about implementing a solution that satisies them.

The goal of this project is to implement a lexical analyzer automatically for any list of tokens that are speciied using regular expressions (if you do not know what a regular expression is, do not worry, it will be deined in this document). The input to your program will have two parts:

1.  The irst part of the input is a list of token deinitions separated by commas and terminated with the # (hash) symbol. Each token deinition in the list consists of a token name and a token description. The token description is a regular expression for the token. The list has the following form:

t1-name  t1-description  ,  t2-name  t2-description  ,  . . .  ,  tk-name  tk-description  #

2.  The second part of the input is an input stTing which is a sequence of letters and digits and space characters.

your program will read the list of token deinitions, represent the list internally in appropriate data structures, and then do lexical analysis on the input stTing to break it down into a sequence of tokens and lexeme pairs from the provided list of tokens. The output of the program will be this sequence of tokens and lexemes. If during the processing of the input string, your program cannot ind a token in the list that matches part of the remaining input (cannot ind a matching preix), it outputs ERROR and stops.  If the input to the program has a syntax error, then your program should not do any lexical analysis of the input string and instead it should output a syntax error message and exits. your program should also output error messages if the same name is used for multiple tokens or if one of the regular expressions generates the empty string.  More speciics about the input format and expected output are given in sections 2 and 3.

The remainder of this document is organized as follows.

1.  The second section describes the input format.

2.  The third section describes the expected output.

3.  The fourth section describes the requirements on your solution and the grading criteria.

4.  The ifth and largest section is a detailed explanation of how to go about implementing a solution. This section also includes a description of regular expressions.

5.  The last section includes general instructions that apply to all programming assignments in this class.

2.1 Examples

The following are four examples of input:

1.           t1 （a）l（b）  , t2 （a）.（（a）*）  , t3 （（（a）l（b））*）.（c） #

"a  aa  bb  aab"

This input speciies three tokens t1, t2, and t3 and an INPUT—TEXT “a aa bb aab".

2.         t1 （a）l（b）  ,  t2 （（c）*）.（b） #

"a  aa  bb  aad  aa"

This input speciies two tokens t1, t2, and an INPUT—TEXT “a aa bb aad aa".

3.            t1 （a）l（b）  ,  t2 （c）.（（a）*）  , t3 （（（a）l（b））*）.（（（c）l（d））*）# "aaabbcaaaa"

This input speciies three tokens t1, t2 and t3 and an INPUT—TEXT “aaabbcaaaa".

4.          tok （a）.（（b）l（_）） ,  toktok （a）l（_）,   tiktok （（a）.（a））.（a） # "aaabbcaaaa"

This input speciies three tokens whose names are tok, toktok, and tiktok and an IN-  PUT—TEXT “aaabbcaaaa". Recall that in the description of regular expressions, underscore  represents epsilon, so the regular expressions for the token tok is equivalent to（a）.（（b）I（E）） and the regular expressions for the token toktok is equivalent to（a）I（E）(if this is not clear,  it should become clear when you read the section on regular expressions).

Note 1 The code that we provided can be used to break down the input to your program into tokens like ID, LPAREN, RPAREN and so on. The code we provide has an object called lexer and a function GetToken（） that your program can use to read its input according to the ixed list of tokens given above (ID, LPAREN, ...).  your program will then have to break down the INPUT—TEXT string into a sequence of tokens according to the list of token deinitions in the input to the program. In order not to confuse the function that you are going to write to break down the INPUT—TEXT string from the function GetToken（） that we provided, you should call your function something else like my_GetToken（）, for example.

3 output Format

The output will be either a syntax error message, if the input has a syntax error, or a message indicating that one or more of the tokens have expressions that are not valid (see below) or a sequence of tokens and their corresponding lexemes according to the list of tokens provided if there are no errors. More speciically, the following are the output requirements (I start by describing the requirements, but below I give examples to clarify them).

1.  (syntax checking:  15 points, but no partial credit) If the input to your program is not in the correct format (not according to the grammar in section 2), there are two cases to consider

(a) If the irst syntax error that your program encounters occurs while parsing a regular expression, then your program should output the following and nothing else and stops

SYNTAX  ERROR  ⅠN  EXPRESSⅠON  OF token-name

where token-name is the name of the token that your program parses before parsing the regular expression (such a name must exist because if it is missing, your program must have encountered a syntax error before parsing the expression).

(b) If the irst syntax error that your program encounters in not in the regular expression of a token, then your program should output the following and nothing else

SNYTAX ERORR

You should make sure that your program doesn,t print anything before it completely parses the input. No partial credit on syntax checking means that you should pass all test cases on the submission site in order to get the 15 points. If your program fails any of the test cases for this category, you will get no credit for syntax checking. Only syntax checking has no partial credit.

2.  (semantic checking： 15 points) If the input to your program is syntactically correct (no syntax error), but some token name is declared more than once, then for every instance of the token name, except for the irst instance, your program should output

Line  line-number1: token-name  already declared  on  line  line-number2

where line-number1 is the line in which the duplicate token-name appears and line-number2 is the line in which the irst appearance of token-name occurs.

3.  (Epsilon error： 20 points) If there are no syntax errors and all tokens have distinct names, then, if any regular expressions of the tokens in the list of tokens can generate the empty string, then your program should output

EPSⅠLON  ⅠS  NOOOOOOOT  A TOKEN   !!!  token-name1 token-name2   . . . token-namek

where token-name1, token-name2, ..., token-namek is the list of names of the tokens whose regular expressions can generate the empty string.

4.  (Lexical Analysis ：60 points) If there is no syntax error and none of the expressions of the tokens can generate the empty string, your program should do lexical analysis on ⅠNPUT-TEXT and produce a sequence of tokens and lexemes in ⅠNPUT-TEXT according to the list of tokens speciied in the input to your program.  Each token and lexeme should be printed on a separate

line. The output on a given line will be of the form

t  ,    "lexeme"

where t is the name of a token and lexeme is the actual lexeme for the token t.  If during lexical analysis of ⅠNPUT-TEXT, a lexical error is encountered then ERROR is printed on a separate line and the program exits.

In doing lexical analysis for ⅠNPUT-TEXT, SPACE is treated as a separator and is otherwise ignored (we already discussed what that means in class).

The total of these points is 11o points. In addition, there are 1o points for programs that compile   correctly and are documented (it is very important that you read the“requirements and grading” below). so, the overall total is 12o points which will count as 12% of the course grade. Remember   that if you do not document your code, you will not get any credit for the submission (see below).

Note 2 The my-GetToken（） that you will write is a general function that takes a list of token representations and does lexical analysis according to those representations.  In later sections, I explain how you can implement this functionality, so do not worry about it yet, but keep in mind that you will be writing a general my-GetToken（） function.

Examples

Each of the following examples gives an input and the corresponding expected output. 1.         t1 （a）l（b）  ,  t2 （（a）*）.（a）

,

t3

（（（a）l（b））*）.（（（c）*）.（c）） #

"a  aac  bbc  aabc"

This input speciies three tokens t1, t2, and t3 and an INPUT—TEXT“a aac bbc aabc”. since the input is in the correct format and none of the regular expressions generates epsilon, the output of your program should be the list tokens in the INPUT—TEXT：

t1  ,  "a"

t3  ,  "aac"

t3  ,  "bbc"

t3  ,  "aabc"

Notice how t3 is deined across multiple lines. your program will not be aware of this because it will use the provided GetToken（） function which ignores space.

2.           t1 （a）l（b）  ,  t2 （（a）*）.（a）  , t3 （（（a）l（b））*）.（c） #

"a  aa  bbc  aad  aa"

This input speciies three tokens t1, t2, and t3 and an INPUT—TEXT“a aa bbc aad aa”. since the input is in the correct format and none of the regular expressions generates epsilon, the output of your program should be the list tokens in the INPUT—TEXT the output of the  program should be

t1  ,  "a"

t2  ,  "aa"

t3  ,  "bbc"

t2  ,  "aa"

ERROR

Note that doing lexical analysis for INPUT—TEXT according to the list of tokens produces ERROR after the second t2 token because there is no token that starts with ,d,, so when my-GetToken（） is called for the ifth time, it will not be able to match any of the tokens in the list, so an ERROR output is produced and your program exits.

3.           t1a （a）l（b） , t2bc （a）.（（a）*）  , t34 （（（a）l（b））*）.（（c）l（d））# "aaabbcaaaa"

This input speciies three tokens whose names are t1a, t2bc, and t34 and an input text “aaabbcaaaa". since the input is in the correct format, the output of your program should be

the list tokens in the INPUT  TEXT:

t34  ,  "aaabbc"

t2bc  ,  "aaaa"

4.           t1 （a）l（b）  , t2 （（a）*）.（a）  , t3  （a）*,   t4  b   , t5 （（a）l（b））*   # "a  aac  bbc  aabc"

This input speciies ive tokens and an INPUT—TEXT “a aac bbc aabc". since the regular expressions of t3 and t5 can generate epsilon, the output is:

EPSⅠLON ⅠS  NOOOOOOOT A TOKEN   !!!    t3  t5

4    Requirements and Grading

You should write a program to produce the correct output for a given input as described above.  You  will be provided with a number of test cases but these test cases are not meant to be exhaustive. They are only meant to complement the speciication document (this document). In your solution, you are not allowed to use any built-in or library support for regular expressions in C/C++. This requirement will be enforced by checking your code.

The grade is broken down as follows for a total of 120 points

1.  submission compiles and code properly documented 10 points. To get the 10 points,

. the submission must compile and

. every function must have comments and

. every submitted ile must have your name.

2.  submission does not compile or some functions have no comments or submitted ile does not have your name: no credit for the submission.

3.  syntax checking: 15 points: There is no partial credit for this part.

4.  semantic checking: 15 points (grade is strictly proportional to the number of test cases that your program successfully passes)

5.  “EPsILON Is NOOOOOOOT A TOKEN !!!”  error cases: 20 points (grade is strictly proportional to the number of test cases that your program successfully passes)

6.  Lexical analysis of ⅠNPUT-TEXT: 60 points (grade is strictly proportional to the number of test cases that your program successfully passes)

Refer to sections 6 and 7 below for information about the compiler that we will use and the execution environment as well as for general instructions that are relevant for all programming assignments.

Note  3 If your  code  does  not  compile on the submission website, you will not receive any points, not even for documentation.  Do not wait until the last minute to submit because there can be unexpected issues when you submit especially if you are not developing your solution in an environment that is compatible with the environment of the submission website.

5    How to Implement a solution

The parser for this project is relatively simple, but this is the irst time you write a parser. So, it is important that you inish your parser completely before you attempt to do anything else. You should make sure that the parser is correctly parsing and producing syntax error messages when needed.

The main di伍culty in the project is in transforming a given list of token names and their regular ex- pression descriptions into a my-GetToken（） function for the given list of tokens.  This transformation will be done in three high-level steps:

1. Transform regular expressions into REGs.  The goal here is to parse a regular expression description and generate a graph that represents the regular expression1 . The generated graph will have a speciic format and I will describe below how to generate it. I will call it a TegulaT e从PTession gTaPh, or REG for short.

2. write a function match（r,s,p）, where r is a REG, s is a string and p is a position in the string s. The function match will a new position p, such that the substring of s between p and p, is the longest possible lexeme starting from position p in the string s that matches the regular expression of the graph r.

3. write a class my-LexicalAnaly处er（list,s）, where list is a list of structures of the form ‘token-name, Teg—pointeT} and s is an input string. my-LexicalAnaly处er stores the list of structures and keeps track of the part of the input string that has been processed by updating a variable p which is the position of the next character in the input string that has not been processed. The class my-LexicalAnaly处er has a method my-GetToken（）. For every call of my-GetToken（）, match（r,s,p）is called for every REG T in the list starting from the current position p maintained in my-LexicalAnaly处er. my-GetToken（） returns the token with the longest matching preix together with its lexeme and updates the value of the current position p. If the longest matching preix matches more than one token, the matched token that is listed irst in the list of tokens is returned.

In what follows I describe how a regular expression description can be transformed into a REG and how to implement the function match（r,s,p）.  But irst, I will give an overview of regular expressions and the sets of strings they represent.

5.1    set of strings Represented by Regular Expressions

A regular expression is a compact representation of a set, possibly ininite, of strings.  For a given regular expression, we say that expression can geneTate a string s if the string s is in set that is represented by the regular expression. we start with a general description, then we give examples.

5.1.1 General description

we start with the simple expressions (the base cases)

.  (one-character strings) The regular expression a represents the set of strings ‘a}, that is the set consisting of only the string "a".

.  (Epsilon) The regular expression 一 represents the set of strings ‘e}, that is the set consisting of only the string e (which is the empty string).

For the inductive step (recursion of your parser), there are four cases:

.  (parentheses) If R is a regular expression, the regular expression（R）represents the same set of strings that R represents. The parentheses are used for grouping and to facilitate parsing and do not have a meaning otherwise.

.  (concatenation) If R1 and R2 are regular expressions that represents sets of strings  S1 and S2 respectively, then （R1）.（R2） represents the set of strings that can be obtained by concatenating one string from S1 with one string from S2 (order matters).

.  (union)  If  R1 and R2 are regular expressions that represents sets of strings  S1 and S2 respectively, then （R1）l（R2） represents the union of the two sets of strings S1 and S2.

.  (kleene star) The last case is the most interesting because it provides notation for an unlimited number of repetitions. If R is a regular expression that represents the set of strings S, then （R）* represents the set of strings that can be obtained by concatenating any number of strings from S, including zero strings (which gives us epsilon).

5.1.2 Examples

1.  The set of strings represented by a is

{a}

2.  The set of strings represented by b is

{b}

3.  The set of strings represented by （a）l（b） is

{a, b}

4.  The set of strings represented by （（a）l（b））.（c） is

{ac, bc}

5.  The set of strings represented by （（a）l（b））.（（c）l（d）） is

{ac, ad, bc, bd}

This requires some explanation.  the set of strings represented by （（a）l（b）） is ‘a, b}and the set of strings represented by （（c）l（d）） is ‘c, d} , so the set of strings represented by

（（a）l（b））.（（c）l（d））consists of strings that can be obtained by taking one string from the set ‘a）b} and one string from the set ‘c）d} and concatenating them together.  The possibilities

are

{ac）ad）bc）bd}

6.  The set of strings represented by （（c）l（d））.（（a）l（b）） is

{ca）cb）da）db}

Notice how this set is diferent from that of the previous example; order matters for concate- nation!

7.  The set of strings represented by （a）* is

{E）a）aa）aaa）aaaa） . . .}

8.  The set of strings represented by （b）* is

{E）b）bb）bbb）bbbb）. . .}

9.  The set of strings represented by （a）l（（b）*） is

{a）E）b）bb）bbb）bbbb）. . .}

1o.  The set of strings represented by （（a）*）l（（b）*） is

{E）a）b）aa）bb）aaa）bbb）aaaa）bbbb）. . .}

11.  The set of strings represented by （（a）l（b））* is

{E）a）b）aa）ab）ba）bb）aaa）aab）aba）abb）baa）bab）bba）bbb）. . .}

This also requires some explanation.  A string is in the set of strings represented by （（a）l（b））* if it is the concatenation of zero or more strings from the set of strings represented by (a)|(b) (the set ‘a）b}), so any string consisting of a sequence of zero or more a,s and b,s is in the set of strings represented by （（a）l（b））* .

5.2 constructing 大EGs

Recall that we want to construct graphs that represent the regular expressions.  Those graphs are called REGs (regular expression graphs). The construction of REGs is done recursively. The construction we use is called Thompson,s construction. Each REG has a exactly one start node and exactly one accept node.  For the base cases of epsilon and a, where a is a character of the alphabet, the REGs are shown in Figure 1. For the recursive cases, the constructions are shown in Figures 2, 3, and 4.  An example REG for the regular expression （（a）*）.（（b）*） is shown in Figure 5.

5.2.1 Data structures and code for REGs

In the construction of REGs, every node has at most two outgoing arrows. This will allow us to use a simple representation of a REG node.

Figure 1: Regular expressions graphs for the base cases

Figure 2: Regular expression graph for the an expression obtained using the dot operator

struct REG-node  {

struct REG-node  * first-neighbor;

char first-label;

struct REG-node  *  second-neighbor;

char  second-label;

}

In  the  representation,   first-neighbor  is  the  irst  node  pointed  to  by  a  REG  node  and second-neighbor is the second node pointed to by a REG node.  first-label and second-label are the labels of the arrows from the node to its neighbors. If a node has only one neighbor, then second-neighbor will be NULL. If a node has no neighbors, then both first-neighbor and second-neighbor will be NULL.

An alternative representation uses a vector of neighbors instead two speciic neighbors.  That would make it easier to iterate over all neighbors of a REG node and avoid checking if the node has zero, one or two neighbors.

Figure 3: Regular expression graph for the an expression obtained using the or operator

Figure 4: Regular expression graph for the an expression obtained using the star operator

The REG graph itself is represented as a structure with two pointers to two REG nodes:

struct REG  {

struct REG-node  *  start;

struct REG-node  *  accept;

}

The irst pointer points to the (unique) start node and the second pointer points to the (unique) accept node. Later, when we discuss the match（） function, we will explain what these nodes are used for.

In your parser, you should write a function parse-expr（） that parses a regular expression and returns the REG of the regular expression that is parsed.  The construction of REGs is done recursively. An outline of the process is shown on the next page.

Figure 5: Regular expression graph for the an expression obtained using concatenation and star operators

网truct REG  *  par网e-expr()

号

//  if  expre网网ion  i网  UNDERSCORE  or  a  CHAR, 网ay   ' a '   for  example //  create  a REG  for the  expre网网ion  and return  a pointer to  it // （网ee  Figure  1,  for  how  the  REG  look网  like）

//  if  expre网网ion  i网 （R1）.（R2）

//

//           the program will  call par网e-expr（） twice,  once

//            to  par网e  R1  and  once to  par网e R2

//

//           Each  of the two  call网 will return  a REG,  网ay they  are

//           r1  and r2

//

//            con网truct  a  new  REG r for （R1）.（R2） u网ing the

//            two  REG网 r1  and r2

//           （网ee  Figure  2 for  how the two REG网  are  combined）

//

//           return r

//

//  the  ca网e网  for （R1）l（R2）  and （R）*   are  网imilar  and

//  are  omitted from the de网cription

Figure 6: Data structure representation for the REG of （（a）*）.（（b*））

}

5.2.2 Detailed Examples for REG Construction

I consider the regular expression（（a）*）.（（b）*）and explain step by step how its REG is constructed (Figure 5).

when parsing （（a）*）.（（b）*）, the irst expression to be fully parsed and its REG is constructed is a (Figure 1). In Figure 5, the nodes for the REG of the regular expression a have numbers 1 and 2 to indicate that they are the irst two nodes to be created.

The second expression to be fully parsed and its REG constructed when parsing （（a）*）.（（b）*） is （a）* . The REG for （a）* is obtained from the REG for the regular expression a by adding two more nodes (3 and 4) and adding the appropriate arrows as described in the general case in Figure 4. The starting node for the REG of （a）* is the newly created node 3 and the accept node is the newly created node 4.

The third regular expression to be fully parsed while parsing（（a）*）.（（b）*）is the regular expression b. The REG for regular expression b is constructed as shown in Figure 1. The nodes for this REG are numbered 5 and 6.