Developer documentation

Tokenizer is the first tool used by Procasor. Tokenizer was developed for tokenization of English texts at the University of Sussex [3], its task is to pre-process the input sentence. This simple Perl scrip formats the input sentence into the form which can be processed by the following tools.

Tokenizer extracts tokens (substrings) from a given string (sentence). The tokens are separated by one delimiter (space character), other white spaces are ignored.

The sentences are tokenized according to the Penn Treebank conventions [1], e.g., "The stock didn't rise $5." is transformed to "The stock didn ' t rise $ 5" . The Tokenizer separates contractions into multiple tokens, splits the word "didn't" into three tokens "didn", "'" and "t". In general, every incoherent string is separated into stand-alone tokens.

When working with the Tokenizer we have to be careful about the sentences which are passed to its input. The empty sentences are problematic, in particular. The Tokenizer ignores empty sentences and continues with waiting for a non-empty input, which in consequence could cause the deadlock of the Parser. We prevent this deadlock by filtering the input.

POS tagging is a fundamental procedure that prepares the input sentence for the Collins Parser. Because the parser requires to receive sentences with POS-tags assigned, we use the MXPost Tagger [4].

The tool assigns an appropriate POS-tag to each word of the sentence. The tagger is based on a statistical model which is trained using a corpus annotated with POS-tags and assigns them to previously unseen text with state-of-the-art accuracy (96.6%).

The Collins parser [5] is used for constructing a parse tree from the input sentence. Before parsing that sentence, we pre-process it by the Tokenizer and the MXPost Tagger in order to gather the information, which the Collins parser requires for successful parsing.

Note: The parser requires a huge amount of memory, we recommend to have at least 200 MB of free memory to run the parser.

The Morp-a tool [6] is the morphological tool used for obtaining the lemma of a word. We use this tool to complete the information about words in the sentence processed by the Collins parser. The parse tree does not implicitly contain the lemma form of words in the parse tree and because these forms are required in linguistic analysis employed in Procasor, we complete this information for every word in the parse tree with the assistance of Morph-a tool.

The Morph-a tool differs from the other tools used in the Procasor in the nature of input data. The other three tools process whole sentences, the Morph-a tool processes single words of the sentence.

E.g., the output format of the Morp-a tool for word "submits" is "submit+s", where the token "submit" is the lemma of the input word.

When we try to match words of a phrase with the name of an entity or a conceptual object, we need to take the name's length into account. Consider a model with entities "Marketplace" and "Marketplace Information System" and a sentence "User contacts the marketplace information system.". Here, Marketplace Information System is the indirect object, but Marketplace would meet the matching requirements as well. To avoid the risk of misinterpretation, we need to start the matching from the longest names.

There are four types of action. First two are the most common, request sending and receiving. The third action is an internal action, which represents the system under design's internal change of state. The fourth action type is a special action which represents a change in the flow of control in the use case.

Each entity in the project has its acronym. This acronym should be unique and starts with a letter followed by several letters or digits. This acronym is only used when the type of action is sending or receiving a request. Otherwise, entity acronym is not used.

After entity acronym a dot follows to separate the entity acronym from the token. Each of these words should start with uppercase letter followed all letters lowercase. This rule should be applied on all words except the first one, which is whole lowercase. In fact, this rule exactly matches the convention of naming methods in many programming languages.

There are types of actions which are special and have the special token.

As said before, tokens are used for describing an action and are used as basic stones for building Pro-cases. If the use case describes communication of two entities, corresponding tokens should be found in use cases describing both entities.

For example, client as SuD calls getOrangesInStore() method on the store system. In this case, there should be another use case where the store system is the SuD, which describes the communication between the client and the store from the opposite view. And in this use case, the client should call getOrangesInStore() method on the SuD.

In the whole project should be some consistency of selected tokens. In fact, each token should be used more than one time, except the special and internal actions. This becomes a bit tricky if these tokens are built from sentences written by the user in use cases, since sentences are usually not identical even when they describe identical action.

The simple token is generated from words which were marked as representative object by the Tree analysis. They are put together by a rule, that first comes a verb and then follows other words in the order in which they are in the sentence. Words are put together in lemma, only if the type of action is condition, then the words are in original form. In most cases this is the best way of generating the token. If the sentence makes sense, then so does the simple token. This is the natural way of how human would use the words in the sentence to generate the token.

The learned token is useful for the case when the user was unsatisfied with the generated token and mixed his own token. In this case, the order and whether the words were used in the selected token may differ from the simple token. When the user writes the same or similar sentence to the mixed one in the project, then the user may expect to get the token made of words in the changed order.

The whole process of generating the learning token consist of four steps.

The first step is picking up the most similar token from all tokens used in the project. This is done by the same algorithm as in [the section called “Merging the Tokens”]. If the picked token is similar enough, than the process continues with the next step, otherwise no learned token is generated. The rate of the similarity can be set by the user in preferences (percents of similarity to perform the token learning process). This token and its sentence will be called the chosen sentence and the chosen token further in this section. The sentence and token on which the token learning process is applied will be called the given sentence or the given token.

The second step is learning the structure of the chosen token and applying this structure to the given sentence. First of all, the words which are equal are selected. There should be some equal words, because the tokens are similar. The words will be used in the given token on same position in the chosen token.

In the third step we select the words from the given sentence which have the same POS-tag as a not assigned word in the chosen sentence which were used in the chosen token. If there are more words with the same POS-tag in the given sentence which were not used in the given token, we pick the one, that has the most similar length.

The fourth step is applied on the rest of the words in the chosen sentence which still have no pair in the given sentence and were used in the chosen token. Each two pairs determinate a boarder in which the another word in the chosen sentence should have a pair word. If there are more words, we pick such word, which has the most similar length.

The next and final step is checking, whether the learned token generating process was successful or not. We compute the number of the words from the chosen sentence which have a pair in the given sentence. Then we compute the number of the words in the chosen sentence which were used in the chosen token. If the quotient of these numbers converted to percents is equal to or greater than the user variable (percents of similarity to perform token learning), then the given token generated by this process is used.

In the case when selected token is not already used in the project and the action, which represents the sentence has already its token in the project. Then the user can use the action's token instead of the selected token. The user can choose the token to merge with in three ways.

The user can choose the token from the list of most similar tokens or from the list of tokens from opposite use cases. You can find more about the opposite use cases in [the section called “Opposite Use Cases”]. And there is the last way of choosing the token to merge with and it is to pick the token from the list of all tokens in the project. More information about these lists and the graphical interface you will find in User documentation in the section Graphical User Interface.

The algorithm of finding the most similar token is used with merging and with token learning. The algorithm counts the length of the common subsequence of two words. The subsequence must be successive. These lengths are multiplied together and product is resulted. This algorithm does not impeach the order. Therefore, if the token consists of the same words in different order, then this algorithm results in finding these words as very similar.

This way of changing the selected token is useful when the user is not satisfied with the order of the words used in the selected token or if the user is not satisfied which words were used and which were not. The user can pick the words which were in sentence and were not marked as subject or indirect object.

The last way of changing the selected token is that the user can write the token by hand. Then the sentence to which the token refers is marked as written by hand.

For the finite state machine (FSM) storage, creation and transformation, we use the following data structures.

A Machine stores finite state machine's states and transitions. Machines can be nested one in another, to support this, the machine stores information about its parent machine, its abort handler, and may contain another machines. In addition to internal states, a machine has the initial state and the final state.

A State is a state in the finite state machine. Every state has a unique name, that is used when the state machine is exported to UML.

The Connectable interface is implemented by classes, that can be connected with transitions. A connectable object must remember the information about incoming and outgoing transitions. This interface is implemented by the state class and the machine class, which allows us to perform nesting one machine into another with grace.

A Transition is an oriented connection between two connectable objects. It contains the information about its start and end state and an expression. This expression represents the event performed when using the transition to move from its start state to its end state.

An Expression interface stores a general expressions. Various classes representing Pro-case operations (atomic, sequence, alternative and so on) implement this interface. During the Pro-case derivation process, simple expressions are combined into complex ones.

Creation of the finite state machine is performed by the MachineBuilder class.

States and transitions for the main success scenario are added first (described in detail in [the section called “Adding States and Transitions for a Step”]). Second, branch steps are processed, this processing takes several rounds. A branch is only processed, when its parent (the step which the branch is connected to) has already been processed. When steps are added for the branch, it will not be processed in following rounds. We remember in which round the branch was processed, this information is useful later, when computing layout for the UML State Machine.

Processing a branch step includes determining the branch's parent step(s). The conditions first step will be connected to its parent step(s) with a transition containing an atomic transition with the condition token. For variations, branches are connected to the parent step's post-state, for extensions, parent's pre-state is used. After that, states and transitions for each step of the branch are added. Finally, we create a void (or lambda) transition from the branch's final step, to the step following the extended step. If a branch has more parent steps, multiple copies of states and conditions are created, each connected to one of the parent steps.

For the step, two states are created. The first one is called a pre-state, representing the moment before event is performed. The other one is called a post-state and represents the moment after the event is performed. If the action type is including a use case, a new machine is created and included in the main machine, instead of creating the post- and pre- states.

A transition is created to connect the newly created pre-state to the post-state of the previous step. Usually, a void expression is used. For the first step of a branch, we use an atomic expression that contains the token of the condition, that triggers the branch.

Other operations are driven by the action type of the added step.

For internal actions and request sending and receiving actions, we create a transition from the pre-state to the post-state, containing an atomic expression with the steps token.

For termination actions and goto, we create a lambda transition from this states pre-state to the according state. This is the machine's final state for use case terminating action; the following step's pre-state for the branch terminating actions, or the pre-state of the goto action target.

For a use case including action, we create a new machine and include it in the main machine (as mentioned above). In addition, we search extensions of this step for an extension marked as "Handles included use case failure". If such extension is located, the pre-state of its first step is marked as the abort handler for the newly created machine. After this, we add the new machines states and transitions using this very algorithm.

For an abort action, we create a lambda transition to the final state of the current finite state machine. If this machine is included in some other machine, further tasks are performed. If the FSM has an abort handler set, we created a transition from the machine to the abort handler state. In the expression of this transition, we repeat the token of the condition, that triggered the branch, that ended with the abort action. If the abort handler is not set, we create a transition (with the condition token) from the machine, to the final state of the parent machine. We repeat this, until we encounter an abort handler, or until we reach the topmost FSM.

Before we proceed to the FSM creation, we check whether semantic information is present and valid for every step of the use case. This check is implemented in the FitnessChecker class.

When performing [the section called “Adding States and Transitions for a Step”], some of the states we would like to connect may not exists. For this reason, we don't create the transitions immediately, but we collect them in a task list. Having added all states, we add all transitions stored in this task list. The same applies to the included machines, where the abort handler state does not exist by the time we process the use case including step.

For access to the states of a machine by step mark, we maintain an index during the FSM creation process.

As mentioned in the User documentation, linguistic tools run in background to provide the opportunity to use Procasor without the need to wait until linguistic operations are completed. This is implemented by running the Parser in an independent thread. When initializing the PipeLine, the Parser creates other threads for ParserTools. This approach allows to allocate a new thread for every important part of the PipeLine, which guarantees that each linguistic process can run independently of others.

The synchronization of threads in which ParserTools run is guaranteed by pipes connecting individual objects of the PipeLine.

In the case an error occurs - the ParserTool detects an unexpected output of a linguistic tools, the PipeLine is broken and the message describing such event is sent through InfoQueue to the Parser. The parser evaluates the received message, and starts closing of the Broken PipeLine. The ParserTool is closed immediately after it sends the message about its error state, other ParserTools are closed when the error message is received by the Parser.

The BrokenPipeLine is closed and we can start initialization of the new PipeLine, after that, the user can continue with sentence analysis.

The Parser generates a log file, where information describing processes and actions inside the PipeLine is gathered. Each line of the log file represents one message received either by the ParserTool - it is the output of the linguistic tool, or by the Parser - the message was generated by one of the ParserTools after the interpretation of the linguistic tool output.

An example of the log file content:

STARTING: USER location=Parser/runProcess
message: Initialization of the PipeLine...
...
STARTING: ADMIN location=MXPostTagger/runProcess
message: MXPostTagger:
Executing .mxpost tagger.project 
...
RUNNING: ADMIN location=MXPostTagger/checkRunningError 
message: MXPostTagger : Output >12 Seller NNP adjusts VBZ / DT
enters VBZ price NN and CC enters VBZ contact 
NN and CC billing NN information NN . . 
...
RUNNING: USER location=Parser/checkQueueRun
message: MXPostTagger: The sentence processed properly.

The first token defines the state of the PipeLine: starting, running, error or closing, then, type of the message follows: user or admin. The third token determines the place inside the program where the message was generated and the last token is the content of the message.

The type of the message determines whether the content of the message will be displayed on the Parser console (USER type messages will be displayed, ADMIN messages are hidden ).

The messages are passed to the log file by the ParserMessageSender class located in cz.cuni.mff.procasor.gui. The log file is being recorded into the file: "logs/pipeLine.log"

Regular expressions are an important part of error checking implemented in the Parser. Regular expression ensure, that output data of linguistic tool are processed properly, it means that the following linguistic tool will obtain the input, that has the required form.

In the case, that the output format of linguistic tool does not respond to the regular expression, the error message is sent through the InfoQueue to the Parser, linguistic process is stopped and the Parser is restarted as described in the section called “Restarting the Parser”.

The situation, that has lead to the unexpected output of the linguistic tools, is described in log file in detail, see the section called “Log File Format”. Analysis of the log file allows us to consider modification of regular expression - in the case that this modification will not affect following linguistic tools.

The modification of the Collins parser was specific. The main difference was in the standard input of the parser. The tool did not processed data from its standard input, the sentences were read from the file specified in the input parameter of the Parser instead. From the standard input, the Collins parser read the statistical model which was used for the sentence processing.

Before employing the Collins parser into Procasor we have modified it, the tool now reads the statistical model from the file specified in its input parameters, this modification gives us the opportunity to read the input sentences from the standard input of the process. As for the other tools, buffering of the output has to be turned off.

For storing the data in configuration file we use XML. Each data segment has its own tag, which encloses the data value:

The configuration data can be found in "config/config.xml" file, which is included under the Procasor root directory.