利用VC设计简易逻辑表达式词法分析器

简易逻辑表达式词法分析器

待分析的逻辑表达式如下：

                EXISTS(x)(Missile(x) AND Owns(Father(Nono),Part_of(x))) => Sells(West,x,Nono)

为了处理逻辑表达式，必须首先提取出逻辑表达式的各个部分：关键字(AND, OR, NOT, FORALL, EXISTS, =>)、谓词和参数，同时必须对于表达式中多余的空格必须删除。这项工作由一个词法分析器完成。

该词法分析器最基础的部分是一个自定义节点Node，定义如下：

class Node
...{
public:
    // VARIABLEs
    enum NodeType ...{KEYWORD, PREDICATE, PARAM};    // Types of the node.
    static wstring KeyWord[];
    NodeType type;
    wstring content;    // content of the node.
    int level;    // Record the level of the node,for example: 
                // Owns(Nono,Sub(x))---"Owns" in level 0,"Nono""Sub" in level 1 and x in level 2.

    // FUNCTIONs
    Node();
    Node(wstring con,NodeType type_=KEYWORD,int lev=0);
    ~Node();
    virtual Node& operator=(Node&); // Overrides of operator=

protected:

};

Node主要有三个部分：该节点内容、节点类型、节点的等级（用以对提取出的表达式进行进一步的分析）。

同时定义了一个链表：

typedef list<Node> NodeList; // Define List.

该链表用于存储整个逻辑表达式。

同时定义了一个类Parser，封装了NodeList，用于对逻辑表达式进行操作。

class Parser
...{
public:
    // VARIABLEs
    NodeList list;
    Node* node;
    
    // FUNCTIONs
    Parser()...{ node=NULL;};
    ~Parser();
    Node* Parse(wstring str,int cur_pos=0); // function to parse a string.

private:

};

词法分析器的核心函数就是Node* Parser::Parse(wstring str,int cur_pos)，该函数主要针对逻辑表达式中的'('、' '、','以及')'进行分析，流程图如下：

运行结果如下：

 
分析结果以树的形式表示：同一级节点表示具有相同的等级，参数比它的谓词的等级要高，比如Missile(x)中Missile等级为0级，x为1级。分
析之后各个节点存储在Parser.list中，可以根据该链表的节点的level属性将各节点插入树种的相应位置。
     分析以上逻辑表达式可知，各个节点的等级如下：
      Missile  x  AND  Owns  Nono  Sub  x  =>  Sells  West  x  Nono
         0         1   0         0           1         1    2  0      0          1      1      1
    
可见，利用堆栈来辅助将节点插入树中是最理想的方法。思路如下：将树的TVI_ROOT压栈；若当前节点的等级大于其前一个节点，将前一个节点压栈；若当
前节点等级小于前一个节点，出栈前一节点等级 和 
当前节点等级之差次；若当前节点等级等于前一节点等级，既不压栈也不出栈。每个当前节点的父节点为栈顶元素。

源代码如下：

/**///////////////////////////////////////////////////
//    
//    Function Name: Parse
//    Input:    a wstring(must), 
//            the start position of being parsed(choiced).
//    Output: a parsed list's head.
//
/**///////////////////////////////////////////////////
Node* Parser::Parse(wstring str,int cur_pos)
...{
//    int start=cur_pos;
    Node* tmpNode=NULL;
    wchar_t pstr[40]=L"";    // temp var to record words.
    int k=0; // used together with pstr.
    int level=0;
    int space_pos=0;
    
    // Deal with the first keywords of a propositional fuction.
    // Such as NOT, EXISTS(x), FORALL(y) and so on.
    // EXAMPLE: EXISTS(x)(Missile(x) AND Owns(Nono,x)) => Sells(West,x,Nono)
    // EXAMPLE: NOT(Missile(x)) AND Owns(Nono,Sub(x)) => Sells(West,x,Nono)
    // EXAMPLE: Missile(x) AND Owns(Nono,Sub(x)) => Sells(West,x,Nono)
    while(cur_pos!=str.length())
    ...{
        if(str[cur_pos]==L'(')    // Words before '(' only can be KEYWORD or PREDICATE.
        ...{
            bool isKeyWord=false;
            for(int i=0;i<sizeof(Node::KEYWORD);++i)
            ...{
                if(!wcscmp(pstr,Node::KeyWord[i].c_str())) //pstr==Node::KeyWord[i]
                ...{
                    isKeyWord=true;
                    tmpNode=new Node(pstr,Node::KEYWORD,level);
                    list.push_back(*tmpNode);    // Insert keyword.
                    break;
                }
            }
            if(!isKeyWord && wcscmp(pstr,L"")) //pstr is not keyword or NULL
            ...{
                tmpNode=new Node(pstr,Node::PREDICATE,level);
                list.push_back(*tmpNode);    // Insert PREDICATE.
            }
            ++level;
            ++cur_pos;
            k=0;
        }
        else if(str[cur_pos]==L' ')
        ...{
            if(str[cur_pos-1]!=L')') // if a ' ' follows ')',then compare the following to or three with keyword.
            ...{
                if(wcscmp(pstr,L"")) // pstr is not empty 
                ...{
                    wstring strAND(str,cur_pos-3,3);
                    wstring strOR(str,cur_pos-2,2);
                    if(!strAND.compare(L"AND") || !strOR.compare(L"OR") || !strOR.compare(L"=>"))
                    ...{
                        tmpNode=new Node(pstr,Node::KEYWORD,level);
                        list.push_back(*tmpNode);    // Insert keyword.
                        ++cur_pos;
                        k=0;

                        memset(pstr,L'',sizeof(pstr));
                        continue;
                    }
                    else 
                        exit(0);    // Error!
                }
            }
                
            ++cur_pos;    // Ignore whitespace.
            continue;
        }
        else if(str[cur_pos]==L',') // pstr must be a param
        ...{
            if(!wcscmp(pstr,L"") && str[cur_pos-1]==L')') // In a case like: Owns(Father(Nono),Sub(x))
            ...{
                ++cur_pos;
            }
            else if(wcscmp(pstr,L"")) // pstr is not empty 
            ...{
                if(str[cur_pos-1]==L')') // Something between a ')' and a ',', Error!
                    exit(1);
                else
                ...{
                    tmpNode=new Node(pstr,Node::PARAM,level);
                    list.push_back(*tmpNode);    // Insert PARAM.
                    ++cur_pos;
                }    
            }        

            k=0;
        }
        else if(str[cur_pos]==L')')    
        ...{
            if(!wcscmp(pstr,L"") && str[cur_pos-1]==L')') // In a case like: Owns(Father(Nono),Sub(x))
            ...{
                ++cur_pos;
            }
            else if(wcscmp(pstr,L"")) //if pstr is not empty
            ...{
                if(str[cur_pos-1]==L')')    // Error!
                    exit(1);
                else
                ...{
                    tmpNode=new Node(pstr,Node::PARAM,level);
                    list.push_back(*tmpNode);    // Insert PARAM.
                    ++cur_pos;
                }
            }

            --level;
            k=0;
        }
        else
        ...{
            pstr[k++]=str[cur_pos++];
            continue;
        }

        memset(pstr,L'',sizeof(pstr));
    }
    return &list.front();
}