A program implements the algorithm to transform right linear grammar to the nondeterministic finite automaton (NFA). The program reads the grammar from the given input file or from the standard output. According to specified options then the program performs needed operations:
-i: writes out the loaded grammar from the internal representation of the program-1: writes out the grammar, which is the result after the application of Sentence 3.2 (page 25)-2: writes out the NFA accepting the same language, which is generated by the loaded grammar; application of the Sentence 3.6 (page 28)
The individual options can be entered commonly, then the program performs
all required operations and writes out their results in the following
order: -i, -1, -2. Please note that the individual outputs
immediately follow each other. When any option will not be entered then
the output of the program will be empty. When two input files were
specified, the program will process the first and ignore others.
cat test/valid_tests/test_01.in | ./plg-2-nka -1 -2- reading from standard output./plg-2-nka -i -1 test/valid_tests/test_01.in- reading from the file
The program tries to be as helpful as possible to the user in the case when some error in the input has occurred. The error is localized as accurately as possible, meaning that the user receives information about which part of the grammar has format errors. The user also receives information about which specification conditions have been violated. We list some examples of the error outputs, shorted by generic messages, which are generated by inputs in the testing suite:
- invalid format of variable:
Variables must be character in the range [A-Z]: ["a"] - not right linear grammar:
Invalid format of productions no.: ["4. line: A->aAa (no right linear grammar)"] - invalid arrow in production:
Missing or badly located arrows in productions no.: ["4. line: 0. column"] - missing terminal in production:
Invalid format of productions no.: ["4. line: A->bA (missing terminal(s): b)"]
The remaining error messages are available in the ErrorController source file or eventually in the control test file. We showed only a minor part of the possible error outputs based on the accurately detected errors.
The format of the input grammar is given by the specification, but the program try to be as tolerant as possible:
- The user can insert the empty lines between the individual productions and such, for instance, separate the cluster of the rules with a free line for better clarity. The example of this option we can see in the one of the test input.
- Another similar option, it is accessibility to insert the different whitespaces (spaces, tabs, etc.) to the individual lines between the symbols on them. This allows the user to make the input grammar somewhat clearer, but also vice versa, as show one of the test input.
- This program also accepts the multiple representations of some symbol in
its relevant set. Thus, when the same variables, terminals or productions
would be represented multiply times, then they will be accepted only in
one occurrence. In such a case, the program writes out the following
warning message to inform the user:
Variables should no be entered twice in the input list: ["A: 2"]. The program will try to recover from the potential inattention of the user and will continue to operate. - With respect to the Definition 2.2 (page 8), the program allows
to user insert the epsilon symbol
#anywhere on the string or eventually concatenate the more epsilons in epsilon rulesS->#. With apply rule 2 from the mentioned definition, we can remove the epsilon symbols in the non-epsilon rules and reduce epsilons to one in epsilon rules. This flexibility we can see in one of the test input and the applied reduction subsequently in the program output with option-i.
Although, that the specification skips the simple productions in the input grammar, this program supports their presence in the productions set of the input grammar. This means, that the transformation according to Sentence 3.2 (page 25) also applies the last step to transform simple productions. The implementation of this step you can find in the TransformGrammar source module and the examples of the input grammars with the simple productions in empty language test or epsilon language test.
The next extended feature of this program is the detection whether
the language of the given grammar is empty. Inside the
GrammarControl module is implemented the Algorithm 4.1
(page 65) to verify this property of the grammar. When the language
of the processing grammar is empty, then the program writes out the
warning for the user in the following form: WARNING: The given grammar generates empty language!. One of the possible reasons for
the empty language can be, that the start symbol is not present in
any production left side. The program also verifies this feature and
when it is satisfied, then writes out the following warning for
the user: The start symbol should be included at least in one production on the left side.
The test directory contains the python script that serves
to automatic testing the correctness of this program. This script is
composed of two parts, whereas the first tests invalid inputs, the
second one tests valid inputs with all possible options. The invalid
inputs (15) are available in the subdirectory and they are tested to the
right error outputs, which are located in the error outputs file, and
to the non-zero exit code of the program. The valid inputs (20) are available
also in the subdirectory of the main test directory and with except
the input, it also contains the expected outputs for the individual
possible option. Thus, one test suite includes the 4 files: input file
(test_name.in) and output files (test_name-i.out, test_name-1.out,
test_name-2.out). Both cases of the test suites focus on a variety of
situations that can be experienced in the input grammars. To run the
python script you can use the following command:
make && python3 test/test.py 2> /dev/null
The output will be contained the resulting summaries from both testing suites. When the test was successful the line will be highlighted by green colour and otherwise will be highlighted by the red colour. We recommend redirecting the standard error output for the clearest test summary since otherwise, it will contain the warning messages from the run of the program.