Compiler Principles Course Lab Report

Github repository: https://github.com/corvofeng/compiler

Main Course Objectives

Deepen the understanding of compiler principles and the process of constructing a compiler
Strengthen programming ability
Learn to write tool software

Course Requirements

SeuLex

Parsing of the Lex input file
Parsing of regular expressions
Implementing an algorithm to convert one regular expression to an NFA
Merging multiple NFAs
Implementing NFA determinization and minimization algorithms
Mapping between return states and returned content
Applying SeuLex

SeuYacc

Parsing of the Yacc input file
Constructing the pushdown automaton for the LR(1) grammar corresponding to a context-free grammar
Constructing the corresponding parsing table from the LR(1) pushdown automaton
Constructing the LR(1) driver program (the table-lookup program)
Mapping from LR(1) to LALR(1)
Building the symbol table and its management routines
Adding semantic action routines
Applying SeuYacc

Tools Used

This experiment used many open source tools as aids; below I list the most important ones. This section can be skipped entirely.

Linux

Operating system

In this project, to keep everyone’s environment uniform and to use existing mature development tools, our whole group used Linux as the development environment.

GCC

Compiler

Used as the compiler: the project also makes heavy use of new C++11 features, and a mature compiler greatly improved development efficiency.

GDB

Debugging tool

A sharp weapon for debugging memory leaks and Segmentation faults. Sometimes a thorough debugging session on a given breakpoint is more

efficient, and GDB’s command-line mode is sometimes clearer.

Git

Version control

Collaboration was easy with Git. Even though the group was small, we still worked collaboratively, and using Git greatly reduced

the difficulty of communication.

CMake (Makefile)

Build/install tool

The whole project is built with CMake, which has good cross-platform support and can feed many IDEs. Support for dynamic and static libraries greatly simplified project construction, letting developers focus on code as soon as possible.

Qt Creator

IDE

Like CMake, a powerful cross-platform development tool; all group members developed on Linux. Compared with Eclipse,

Qt Creator‘s excellent CMake support spared us the trouble of generating projects.

valgrind

Software analysis tool

Since the project is written in C++, memory control is a real headache; valgrind conveniently analyzes leaks. During

the project there was more than one memory leak, and with valgrind the leak locations were found quickly. Given our limited skill, we only used it for leak analysis.

lex & yacc

Programming tools

The project used lex and yacc as syntax and semantic analysis examples. Before the project started, we needed to understand Lex and Yacc first, and the existing tools helped us get started quickly.

Lex Design

Lex is the first core component of the whole project; this document introduces it in the sections below.

Lex Architecture Analysis

This diagram vividly introduces the use case of Lex and the goal we are going to implement: a Lex compiler — a tool that reads a Lex source program (lex.l) and generates lex.yy.c. Setting aside jargon like NFA and DFA, we already understand the input and output of the project; the remaining implementation details will be unfolded in the rest of this document.

Input File (the lex source program)

Due to implementation difficulty, the source program used in this project differs somewhat from a standard lex source program. The lex source program is stored in ./input/require.l (source fragment):

%{
#include "stdio.h"
#include "y.tab.h"
#define LT 1 extern int lineno;

int isDigit(char ch)
{
    if(ch <= '9' && ch >= '0')
        return 1;
    return 0;
}

int isLetter(char ch)
{
    if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
        return 1;
    return 0;
}
%}

%!
letter=isLetter
digit=isDig
%!

%%
({letter}|_)({letter}|_|{digit})* {
    int id = getKeyId(SYLEX_TEXT);
    if(id != 0)
        printf("<%s,->\n", SYLEX_TEXT);
    else {
        printf("<$ID,%s>\n", SYLEX_TEXT);
    }
}
%$
{digit}+(%.{digit}*)?((E|e)(%+|-)?{digit}+)? {
    printf("<$NUM,%s>\n", SYLEX_TEXT);
}
%%

A standard lex source file has no middle %! %! section. When writing programs yourself, [0-9], [a-zA-Z] are hard to express, so here we adopt a form of pre-defined functions, letting custom programs parse single characters.

Output File (the generated lexical analyzer)

This output file mainly consists of the scaner function.

// scanner function
void SYLEX_scanner(char *str)
{
    char ch = ' ';
    while(ch != '\0')
    {
        //printf("%c %d\n", ch, SYLEX_STATE);
        switch(SYLEX_STATE) {
        case 0: {
                    // not expanded here for space reasons
                    //...
                    break;
        }
        case 1: {
            ch = *str++;
            SYLEX_TEXT[SYLEX_TEXT_LEN++] = ch;
            if(isLetter(ch)){
                SYLEX_STATE = 30;
            }
            else if(isDigit(ch)){
                SYLEX_STATE = 31;
            }
            else if(ch == '_'){
                SYLEX_STATE = 32;
            }
               else {
SYLEX_TEXT[SYLEX_TEXT_LEN-1] = '\0';
SYLEX_TEXT_LEN = 0;
SYLEX_STATE = 0;
str --;
//---------------------
{    int id = getKeyId(SYLEX_TEXT);    if(id != 0)        printf("<%s,->\n", SYLEX_TEXT);    else {        printf("<$ID,%s>\n", SYLEX_TEXT);    }}
//---------------------
            }
                }
                    break;
        }
    }
}
int main(int argc, char **args)
{
    if(argc == 1)
    {
        printf("no input source file name");
        return 0;
    }
    else if(argc == 2)
    {
        strcpy(SYLEX_FILE_NAME, args[1]);
        sprintf(SYLEX_OUT_FILE_NAME, "%s.out", SYLEX_FILE_NAME);
    }
    else
    {
        strcpy(SYLEX_FILE_NAME, args[1]);
        strcpy(SYLEX_OUT_FILE_NAME, args[2]);
    }
    FILE* file = fopen(SYLEX_FILE_NAME, "r");
    while(NULL != fgets(SYLEX_BUFF, SYLEX_MAXSIZE_BUFF, file))
    {
        ++SYLEX_LINE;
        SYLEX_scanner(SYLEX_BUFF);
    }
    return 0;
}

This file is the output of the Lex program. You can see that case 1 contains the use of the parsing expressions: while Lex runs, it regex-parses the lex source file above and applies the operations of the matched regular expressions. In case 1 we get the operation output corresponding to the regular expression below:

({letter}|_)({letter}|_|{digit})* {
    int id = getKeyId(SYLEX_TEXT);
    if(id != 0)
        printf("<%s,->\n", SYLEX_TEXT);
    else {
        printf("<$ID,%s>\n", SYLEX_TEXT);
    }
}

Processing Flow

Now that we know the input and output of the Lex program, we introduce the flow. The document will walk through the whole process starting from regular expressions with a simple example.

Suppose we have the regular expression a*(b|(cd?))+ and the expression ef
Convert the regular expressions to NFAs

Conversion process

In the Re2NFA class, the functions re2post and post2nfa are defined, which respectively convert an infix regular expression to postfix and convert a postfix expression to an NFA. For the concrete implementation see ./lex/nfa.h in the project code.

Merge the NFA expressions

Merging process

Since merging also produces an NFA, we use the NFA2LIST class to merge; the user can keep calling the merge function. When merging, a new start node is created, then the character sets of the two NFAs are merged.

NFA to DFA

Conversion process

The subset construction method is used.

The initial state of the NFA is used as the initial state of the DFA, and a closure operation is performed: all states reachable only via edges labeled $\epsilon$. In the implementation I call this findSimple — expanding from a core point to all surrounding points. This function maps a core point to the points around it.

Taking the NFA above as an example, node 0 becomes the initial state of the DFA, and the findSimple function expands it, adding nodes 1, 3, 4, 7, 9 to the initial state of the DFA as well.

Here I want to explain that setting core points is very necessary: since every new DFA state must be compared with all previously existing DFA states, comparing all NFA states corresponding to each DFA state would be extremely costly. With core points set, the number of comparisons is greatly reduced.

Below I describe it in pseudocode:

while (there exists an unvisited DFA state) {
  take that state;
  for (each input symbol a) {

      if (the state can reach a node via a) {
          make that node the core node of a new state
      }

      if (the new state has 0 core nodes) {
          no new state is produced
          continue
      }

      if (that state already exists) {
          only add the state to the `DFA` paths
      } else {
          create the new state
          mark it as unvisited
          add the new state to the `DFA` paths
      }
  }
}

Taking DFA state 0 above as an example, we traverse the symbols a, b, c, d, e, f. At the same time, we will find that DFA states with these core nodes can be constructed (core nodes in parentheses): - 0 -> e -> 1 (16) - 0 -> a -> 2 (7) - 0 -> c -> 4 (15) - 0 -> b -> 3 (12)

With the core nodes in hand, findSimple can be used to expand them.

Important Data Structure Definitions

Basic Data Structures

/*
 * NFA node
 *
 * Represents an NFA state plus zero or one or two arrows exiting.
 * if c == Match, no arrows out; matching state.
 * If c == Split, unlabeled arrows to out and out1 (if != NULL).
 * If c < 256, labeled arrow with character c to out.
 *
 * Explanation: the enum represents the state of a node; it may have no outgoing edges (e.g. the tail node), one,
 * or two. Of course, we can guarantee that no node has more than two outgoing edges, and when there are two,
 * one of them must be a sigma edge — that is, directly reachable.
 *
 * if c == Match: no outgoing edges, meaning the state is a matching state
 * if c == Split: this state represents one or two sigma edges
 * if c < 256   : this state has one real edge; the real edge is out, the non-real one is out1
 */
class State {
    int c;
    State *out;
    State *out1;
    std::string endFunc;        // function corresponding to the end state; only valid when this node is Match
};

/*
 * NFA fragment — hence the name "fragment"
 */
class Frag
{
    State *start;   // start node
    State *end;     // tail node
};

/**
 * DFA node state
 */
class DState {
    std::map<DState*, int> out;  // records the states this DFA node can reach and the paths
    std::set<State*> coreState;  // the core NFA states represented by the current state, used later for state comparison
    std::set<State*> allState;   // records all possible states; filled after getAllState is called
    bool hasTravel = false;      // during DFA construction, whether this state has been visited
    bool isEnd = false;          // whether it is an accepting node
    std::string endFunc;         // function to execute in the end state; only manipulable when this node is an end state
};

NFA and DFA

/*
 * Each regex statement corresponds to one NFA
 *
 */
class Re2NFA {
    string func;            // handler function of this NFA's terminal state — the outcome of this NFA
    State * nfa_s = NULL;   // stores the parsed data
    State * nfa_e = NULL;   // the final matching state
    std::set<int> char_set; // input symbol set
};

/*
 *   This class is mainly used to merge NFAs; the merged result is still an NFA, only the final handler functions of the
 *   different NFA chains differ. Note that this class also does `new` operations. We follow the principle "whoever creates, releases":
 *   objects created by this class are reclaimed by it uniformly in the end.
 *
 */
class NFA2LIST {
    State *nfa_s = NULL;
    std::set<int> char_set;
    std::set<State*> st_create; // tracks newly created resources, for final release
};

// NFA converted to DFA
class N2DFA {
    DState *dstart;
    NFA *nfa;
};

Lex

class Lex {
    std::ostream *out = NULL;       // analyzer output
    std::istream *in = NULL;        // Lex source file input

    std::vector<Re2NFA*> re2NFAList;// stores the many NFAs
    NFA2LIST nfa2List;              // stores the combined NFA

    N2DFA* pN2DFA = NULL;           // stores the parsed DFA
};

Using the Generated Lexical Analyzer

We have obtained the generated lexical analyzer (e.g. out.c); next we parse a file:

☁  input  gcc out.c -o out # out is our lexical analyzer

☁  input  cat main.c        # view the file we are going to parse
#include <stdio.h>
#include <string.h>
#include"aaa.h"

int main()
{
    int a = 5;
    int b = a + 3.5E3 - 5;
    char s[] = "I love the world\n";
    for(int i=0; i<5; i++)
        printf("%s\n",s);
}

☁  input  ./out main.c      # parse the file
#include <stdio.h>  // should be preprocessed; ignore for now
#include <string.h>  // should be preprocessed; ignore for now
#include"aaa.h"  // should be preprocessed; ignore for now
<int,->
<$ID,main>
<(,->
<),->
<{,->
<int,->
<$ID,a>
<=,->
<$NUM,5>
<;,->
<int,->
<$ID,b>
<=,->
<$ID,a>
<+,->
...

Yacc Design

Yacc Architecture Design

Similar to Lex, Yacc is a tool for generating y.tab.c, and y.tab.c is the syntax analyzer. As you can see, the input is the Yacc source program and the output is y.tab.c. In this program’s processing, the Yacc handler is integrated into Yacc itself; the syntax analyzer is not made standalone, and only a predictive parsing table was used for simple testing.

Yacc Input File


%{

#include <stdio>


%}

%!
%token NUM
%head  expr

%left + -
%left * +
%right UNINUS

%!
%%

expr    : expr '+' expr {$$ = $1 + $3; }
        | expr '-' expr {$$ = $1 - $3; }
        | expr '*' expr {$$ = $1 * $3; }
        | expr '/' expr {$$ = $1 / $3; }
        | '('expr')'      {$$ = $2;}
        | NUM
        |
        ;
%%

For parsing convenience, this grammar differs slightly from the standard Yacc grammar, but this does not affect grammar parsing.

What is enclosed in %{, %} is still the predefined output of the grammar; since we do not produce y.tab.c, it serves only as a place holder here. %!, $! contain token, head, and left/right, all meaningful here: token records the terminals, head records the starting non-terminal (expr above), and left, right record precedence and associativity.

Yacc Output

In this project Yacc has no output; we added a parse function to the Yacc class, which reads the lexical analyzer’s generated file and produces the parsing output.

Lexical analyzer output file

<$NUM,23>
<+,->
<$NUM,16>
<*,->
<$NUM,3>

Output of the parse function

                  0                                                     s3
a                 0  3                    23                            A->a
A                 0  2                    23                            s8
A +               0  2  8                 23   0                        s3
A + a             0  2  8  3              23   0  16                    A->a
A + A             0  2  8 18              23   0  16                    s7
A + A *           0  2  8 18  7           23   0  16   0                s3
A + A * a         0  2  8 18  7  3        23   0  16   0   3            A->a
A + A * A         0  2  8 18  7 17        23   0  16   0   3            A->A*A
A + A             0  2  8 18              23   0  48                    A->A+A
A                 0  2                    71                            Accept
Accept

Processing Flow

Now that we know the input and output of the Yacc program, the flow description trims away irrelevant input/output and picks the main logic for introduction; for very specific details please read the code. Here we use the following grammar as an example for flow analysis:

"S->S;A",
"S->A",
"A -> E",
"A->i=E",
"E->E+i",
"E->i"

Storing the grammar and solving the First sets

When the grammar is saved, it is first transformed: productions with the same non-terminal are merged, so the grammar above is stored like this:

1
2
3

A -> E|i=E
E -> E+i|i
S -> A|S;A

To solve the First sets, just call the makeFirst function.

/**
 * Get the First sets of the grammar, computed via the dfs function
 * @brief makeFirst
 */
void makeFirst() {
    // Although this loops recursively, at runtime many cases return directly, so the complexity is not high
    for (auto it : pExprVec) {
        Expression *pExpr = it;
        dfs(pExpr);
    }
}

/**
 * This code was not written by me; it mainly refers to the following code:
 *     http://www.kancloud.cn/digest/compile-principle/143016
 *
 * Only a brief analysis can be given.
 * There are mainly 4 rules for solving FIRST sets:
 *  1. if X is a terminal, then FIRST(X) = {X} — a terminal's FIRST set is itself
 *  2. if X is a non-terminal and there is a production X→a…, a∈VT, then a∈FIRST(X);
 *     X→~, then ~∈FIRST(X)
 *  3. if X -> Y1 Y2 Y3 .. YK and Y1 Y2 .. YK-1 can derive ~,
 *    then FIRST(YK)∈FIRST(X)
 *
 * The program adopts a somewhat different approach:
 *
 * if this item (X) has already been parsed, return
 * else mark it as being parsed
 *
 * traverse all productions of this item (e.g. F->(E)|i traverses F->(E) and F->i in turn):
 *
 *     traverse each unit x in the production:
 *         if x is a terminal, add it directly and end the inner loop
 *
 *         if x is a non-terminal:
 *               get the productions corresponding to that non-terminal
 *               dfs(production) — recursive call
 *               merge that item's FIRST set into FIRST(X)
 *               if the production contains ~
 *                   rule three is satisfied; continue with the next non-terminal
 *               else
 *                  end the inner loop
 *
 * @brief dfs
 * @param pExpr
 */
void dfs(Expression* pExpr);

The pasted code above may not make the function’s usage easy to grasp; I will analyze it step by step below.

Let’s go through it in order. For A -> E|i=E, parsing A -> E gives First(E)∈First(A); the depth-first traversal will solve First(E): First(E) = i, then First(A) = First(E) ∩ {i}.

Then for S->A|S;A, we know First(S)=First(A).

So First(A) = First(S) = First(E) = {i}.

Constructing the LR(1) item set family

/**
 *   This function builds the LR1 state transition graph. It first inserts (push_back) the initial state, so lrStateVec[0] is the
 *   initial state, and then starts calling getAllNextState(start). If states were added, the loop continues
 *   until every state has obtained its next-state family.
 *
 * @brief iterms
 */
void iterms();

Next I will explain the whole construction of the item set family starting from the initial state.

Building the LR(1) initial state

In the items function, the expression #->.S, $ is first inserted as the start of the closure computation.

Closure computation of the core productions

Taking the closure expansion of the initial state’s core production as an example, # -> .S term char: $ — expanding this expression uses the LRState::findAllExpr function, which mainly does this: keep traversing the standard states; the function mainly uses LRState::findAllExpr:

/**
 * The function is mainly called in findAllExpr to increase the number of expressions in the current state, e.g.
 *
 * S-> .A, $ (input is A$)
 * directly add A -> .<production>, $ to the vector group
 *
 * S-> .ABC, $ (input is ABC$)
 * add A -> .<production>, FIRST{B} to the vector group
 *
 * S-> .Abc, $ (input is Abc$)
 * add A -> .<production>, b to the vector group
 *
 * @brief increaseState
 * @param s
 * @param term
 */
void increaseState(string &s);

LR(1) item set family state transitions

When we reach some state and have performed the closure computation from the core productions, we next need to reach the next state; at this point the items function calls LR1::getAllNextState to expand:

/**
 *   Get all successor states of this state. If the state already exists among the previous states, the original state is added to this
 *   state's successor family, and no state is added to the state vector group.
 *
 *   If the obtained state is new, it is added to the state vector group and numbered; the numbering information
 *   is kept in the state2id map.
 *
 * @brief getAllNextState
 * @param start
 * @return
 */
bool getAllNextState(LRState *start);

Building the ACTION and GOTO tables

After the LR(1) item set family is built, the LR1::makeACTIONGOTO function can be called to build the predictive parsing table. During construction, ambiguous grammars may cause conflicts; here conflicts mainly appear in building the Action table. The specific influence of precedence and associativity on table construction will not be expanded here — I believe interested readers will explore the code.

/**
 * Build the Action table. Facts show this is a terrible function — even recursion cannot save it.
 *
 *   The LR1 tables we normally build must consider ambiguous grammars; once an ambiguous grammar appears, we need to state it explicitly.
 *  If a grammar is ambiguous and no precedence or associativity is defined in it, then at the LR1 stage it is considered an erroneous
 *  choice.
 *  Likewise, if a grammar defines precedence and associativity, we need to react at conflicting positions: for
 *  ambiguous positions a decision must be made to ensure our predictive parsing table is unique.
 *
 * @brief actionHelp
 * @param start
 * @param res_action
 * @param term
 */
void actionHelp(LRState *start, vector<vector<string>> &res_action,
    map<string, int>& term);

/**
 * @brief gotoHelp
 * @param start
 * @param res_goto
 * @param nonTerm
 */
void gotoHelp(LRState *start, vector<vector<int>> &res_goto,
  map<string, int>& nonTerm);

Performing syntax analysis

Once we have the ACTION and GOTO tables, we need to apply them. Here we directly use the final output as the example. This does not mean our LR1 only applies to the current input — it is only for convenience of explanation, and the computation process in this example has been verified over a long time. The whole grammar is:


0: A -> .(A)    term char: ? ---- {$$=$2;}
1: A -> .A*A    term char: ? ---- {$$=$1*$3;}
2: A -> .A+A    term char: ? ---- {$$=$1+$3;}
3: A -> .A-A    term char: ? ---- {$$=$1-$3;}
4: A -> .A/A    term char: ? ---- {$$=$1/$3;}
5: A -> .a    term char: ? ----

The header is ( ) * + - / NUM $

The header is A

Text to parse:

<$NUM,23>
<+,->
<$NUM,16>
<*,->
<$NUM,3>

When we read NUM we are in state 0; the corresponding action is s3 — a shift, and we are now in state 3. Then we read +, and the action is r5 — reduce with production 5. Continuing this way, the stack diagram is below:

symbol stack      state stack             actual computation stack       current action
                  0                                                     s3
a                 0  3                    23                            A->a
A                 0  2                    23                            s8
A +               0  2  8                 23   0                        s3
A + a             0  2  8  3              23   0  16                    A->a
A + A             0  2  8 18              23   0  16                    s7
A + A *           0  2  8 18  7           23   0  16   0                s3
A + A * a         0  2  8 18  7  3        23   0  16   0   3            A->a
A + A * A         0  2  8 18  7 17        23   0  16   0   3            A->A*A
A + A             0  2  8 18              23   0  48                    A->A+A
A                 0  2                    71                            Accept

Important Data Structure Definitions

/**
 * Saves a single expression, e.g.
 * S -> a | b
 *
 *  This expression form is mainly used for grammar definition and is convenient for solving FIRST sets
 * @brief The Expression class
 */
class Expression {
    string left;
    set<string> right;
};

/**
 *   Representation of a single expression. In the LR1 state transition graph, a single expression needs various information recorded, including:
 * the position the current expression has parsed to, and the current expression's terminator. This expression is mainly used for recording states in the transition graph.
 *
 * For example:
 *   S -> aB.c,  $
 * where . means parsing has reached just before the letter c, and this expression's terminator is $
 *
 * @brief The SingleExpress class
 */
class SingleExpress {
    string left;
    string right;
    string func;
    int pos = 0;
    char term;
};

/**
 * This class saves the grammar, e.g.
 * S -> aSb
 * S -> ~
 * @brief The Grammar class
 */
class Grammar {
    map<string, Expression*> left2Expr;
    map<string, set<char>> first;
    string nonTermHead;        // gets the head node of the non-terminals
    set<string> term;            // saves the set of terminals: a, b, +, i ...
    set<string> nonTerm;         // saves the set of non-terminals (always uppercase letters): S, A, B ..

};


/**
 *   This class records every state in the LR1 state transition graph. For the various state information, we need standard states to compare
 *   against.
 *   This class has the static variable lrStateStandard. When using this class, first call getStandardState to record the standard
 *   states; after use, please call deleteStandardState yourself.
 *
 * @brief The LRState class
 */
class LRState {
    std::map<char, LRState*> out;
    /**
     *
     * acc = -2; means the state is an intermediate state and can only shift
     * acc = -1; means the state is accepting, i.e. complete
     * acc >= 0; means production number acc can be used to reduce
     *
     */
    int acc = -2;

    /**
     *  For ordinary states, this variable represents the core expr
     *
     *  For the static variable lrStateStandard, coreExpr then represents all the standard productions, and each
     *  production's position is also a fixed value
     * @brief coreExpr
     */
    vector<SingleExpress*> coreExpr;

};

/**
 * The whole LR1 parsing class:
 *   carries grammar parsing, state construction, state deduplication, state transitions, and construction of the Action and Goto tables
 * @brief The LR1 class
 */
class LR1 {
    Grammar *grammar = NULL;            // the grammar for this LR1 parse

    /*
     * Storage for the ACTION and GOTO tables
     */
    vector<vector<string>> res_action;
    vector<vector<int>> res_goto;
    map<string, int> actionTerm;
    map<string, int> gotoNonTerm;

        // saves precedence, e.g. * > + is stored as <*, +>
    map<string, string> prior;

    // saves associativity: if * is left-associative it is stored as <*, 1>; right-associative as <*, 2>, to distinguish them
    map<string, int> assoc;
};

Using the Syntax Analyzer

The concrete parsing process was listed above; next I mainly explain how to use the syntax analyzer:

# use the lexical analysis tool to generate the file to parse
./out input/yacc_test.c > lex.out

./bin/yacc_rel ./input/require.y lex.out

Problems Encountered in the Project

A fairly large project runs into many problems. Here I pick some of the perplexing problems encountered during the whole process, also as a reminder to myself to keep improving my programming skills to solve the problems met in future study and life.

Problems in Lex

Converting infix regular expressions to postfix

Building the reverse Polish expression was our first step. Infix-to-postfix conversion had actually been done long before, but as the input of the whole program, its correctness had to be guaranteed first. Moreover, the postfix form of a regular expression differs slightly from that of an ordinary arithmetic expression, because an ordinary expression is joined by +-*/, while a regular expression is joined by an invisible concatenation operator.

Therefore, before writing code I first searched for similar problems, confirmed that others had written code already, and completed it only after referring to theirs. I believe this is unavoidable in project construction: sometimes, due to project requirements, we need to look at other people’s programs for reference beforehand.

Defining the NFA

The NFA is the basis for converting to a DFA, and the representation of the NFA persisted all the way to the final construction of the lexical analyzer. Converting the postfix form of a regular expression to an NFA has, to some extent, a determinate form. Here we first proved that each NFA node needs at most two outgoing edges to represent all cases, including a+, a*, a|b ... Actually this step is where the problem affecting the whole Lex construction lay: due to a small mistake of mine, the construction of NFAs of the a|b form went wrong throughout the whole NFA construction, affecting even the final composition of the lexical analyzer. I have to say such an annoying little error caused the failure of the entire system.

Implementing the actions for regular expressions

Current program state: The previous program had actually already completed the conversion from NFA to DFA. But multiple NFAs have multiple end and initial states; converting NFAs to DFAs separately still cannot solve the analysis problem. Therefore, here we need to merge the NFAs first, and convert to a DFA after merging.

Problem: Ideas are always nice, but the problems that follow are not simple. Multiple NFAs have multiple end states, and the operation function corresponding to each end state differs. So although we merged the NFAs, the end-state information carried by each NFA could not be merged. This is the truly awkward moment: without solving this problem, the program cannot continue.

Solution: At this point I added an endFunc variable to the State and DState classes. Overall, adding the variable causes extra space usage and makes the program less elegant. But by then the main framework was already defined; the NFA and DFA creation classes could not be modified much more. When there are many states, the program’s memory footprint rises.

Since I pursued separating the DFA from the NFA as much as possible, and defined the State and DState classes separately, the resulting problem could only be solved by using extra space. This approach has pros and cons, but it is not a stopgap — it is a way of solving the problem.

Representing regular expression states

Function input:

({letter}|_)({letter}|_|{digit})* {
     int id = getKeyId(SYLEX_TEXT);
     if(id != 0)
        printf("<%s,->\n", SYLEX_TEXT);
     else {
         printf("<$ID,%s>\n", SYLEX_TEXT);
     }
}

Here is a regular expression matching variable names (strings of letters, digits and underscores that may only start with a letter or underscore), together with the operation corresponding to the expression.

First, getReAndFunc is called to separate the regular expression from the processing logic; we get re and func corresponding to the two parts: re = ({letter}|)({letter}||{digit})* func = {…} The regular expression is then processed: because the expression contains long names like {letter} and {digit}, we use state2ch to perform the {letter} -> char substitution. The generated regular expression becomes: re_s = (a|)(a||b)* — here a and b are only filler characters; in the real substituted regex, a and b are invisible characters.

In addition: For a regular expression like (%=?), because the expression contains ‘‘, direct matching would produce errors, so we use % for escaping; the escape in a regular expression is *, which we also modify here, and it becomes: (*=?)

After this basic processing of the regular expression, we store the expression and its corresponding handler function into the NFA class: Re2NFA *pre2Nfa = new Re2NFA(re_s, func);

Problems in Yacc

Representing productions

Everything is hard at the beginning. From the very start of building Yacc, the problem of saving expressions could not be avoided, because constructing the LR1 state family requires building the First sets, so the initial choice of data structure matters. Choosing Expression can save expressions like S -> a | b, making it convenient to find the productions corresponding to the same non-terminal — but it is exactly such productions that caused trouble for the later LR1 construction. Since the expressions saved in the Expression class are mixed together, checking them at every state transition would be an enormous amount of work. Unable to bear this trouble, a new custom class SingleExpression was used when constructing the item set family; state transitions use S -> aB.c, $.

The closure operation (expanding from the core productions)

In the whole expansion process, at first I only wanted the form from core productions to all productions, but in the end I discovered that during expansion we would encounter the end of a production (okay, I hadn’t considered that), and the subsequent parameter-tuning process was quite laborious.

if (pos >= right.size()) { // if the current position is already at the end, do not process
    i++;

    if (right.size() == 1 &&  right.at(0) == nonTermHead.at(0)) { // current state is accepting
            //cout << right.at(pos - 1) << endl;
        this->acc = -1;
    } else {        // non-accepting state, but the end has been reached
        // this->termAll += term;
        // cout << "************" << endl;
        // cout << this->termAll<< endl;
        // cout << "************" << endl;

        this->acc = this->findExprByLeftRight(sExpr->left, right); // find this expression's position among the standard expressions
    }
    continue;
}

Problems Using CMake

Building libraries with CMake

The project involves a large number of .cpp, .h files; without a suitable management tool it is impossible to keep everyone’s progress in sync. Taking Lex as an example:

set(SOURCE_LIB ./lex.cpp ./lex.h
                ./nfa.cpp ./nfa.h
                ./dfa.cpp ./dfa.h
                ./state.h ./state.cpp)
add_library(lex ${SOURCE_LIB})

Adding input files

The build process needs some input files. Since CMake builds out-of-source, the Lex and Yacc files must both be fed in; the following copies the files into the build directory.

file(COPY
    ./main.c ./require.l
    ./run.sh ./MyMake
    ./yacc_test.c ./require.y
    DESTINATION ${PROJECT_BINARY_DIR}/input)

Group Division of Labor

This course design project consisted of three people: 09014310 Feng Panhe, 09014312 Feng Yuhao,
09014315 Zhang Chunqiu

Lex

Infix to postfix for regular expressions, postfix to NFA, NFA to DFA, construction of the Lex analysis program (reading the lex source file, generating the analyzer), writing the lex source file, defining the lex source file specification

Yacc

Storing expressions and generating First sets, constructing the LR1 item set family, constructing the predictive parsing table, reading and parsing the Yacc source file, applying the parsing results (syntax analysis using the predictive parsing table)