利用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();
}